This repository has been archived by the owner on Dec 22, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 72
/
View.scala
181 lines (153 loc) · 6.12 KB
/
View.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
package strawman.collection
import scala.{Any, Boolean, Equals, Int, Nothing, annotation}
import scala.Predef.intWrapper
/** Concrete collection type: View */
trait View[+A] extends Iterable[A] with IterableOps[A, View, View[A]] {
override def view = this
/** Avoid copying if source collection is already a view. */
override def fromIterable[B](c: Iterable[B]): View[B] = c match {
case c: View[B] => c
case _ => View.fromIterator(c.iterator())
}
override protected[this] def fromSpecificIterable(coll: Iterable[A]): View[A] =
fromIterable(coll)
override def className = "View"
}
/** This object reifies operations on views as case classes */
object View {
def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] {
def iterator() = it
}
/** The empty view */
case object Empty extends View[Nothing] {
def iterator() = Iterator.empty
override def knownSize = 0
}
/** A view with given elements */
case class Elems[A](xs: A*) extends View[A] {
def iterator() = Iterator(xs: _*)
override def knownSize = xs.length // should be: xs.knownSize, but A*'s are not sequences in this strawman.
}
/** A view filled with `n` identical elements */
case class Fill[A](n: Int)(elem: => A) extends View[A] {
def iterator() =
new Iterator[A] {
private var i = 0
def hasNext: Boolean = i < n
def next(): A = {
i = i + 1
if (i <= n) elem else Iterator.empty.next()
}
}
override def knownSize: Int = n
}
/** A view that filters an underlying collection. */
case class Filter[A](underlying: Iterable[A], p: A => Boolean) extends View[A] {
def iterator() = underlying.iterator().filter(p)
}
/** A view that partitions an underlying collection into two views */
case class Partition[A](underlying: Iterable[A], p: A => Boolean) {
/** The view consisting of all elements of the underlying collection
* that satisfy `p`.
*/
val left = Partitioned(this, true)
/** The view consisting of all elements of the underlying collection
* that do not satisfy `p`.
*/
val right = Partitioned(this, false)
}
/** A view representing one half of a partition. */
case class Partitioned[A](partition: Partition[A], cond: Boolean) extends View[A] {
def iterator() = partition.underlying.iterator().filter(x => partition.p(x) == cond)
}
/** A view that drops leading elements of the underlying collection. */
case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] {
def iterator() = underlying.iterator().drop(n)
protected val normN = n max 0
override def knownSize =
if (underlying.knownSize >= 0) (underlying.knownSize - normN) max 0 else -1
}
/** A view that takes leading elements of the underlying collection. */
case class Take[A](underlying: Iterable[A], n: Int) extends View[A] {
def iterator() = underlying.iterator().take(n)
protected val normN = n max 0
override def knownSize =
if (underlying.knownSize >= 0) underlying.knownSize min normN else -1
}
/** A view that maps elements of the underlying collection. */
case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] {
def iterator() = underlying.iterator().map(f)
override def knownSize = underlying.knownSize
}
/** A view that flatmaps elements of the underlying collection. */
case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] {
def iterator() = underlying.iterator().flatMap(f)
}
/** A view that concatenates elements of the underlying collection with the elements
* of another collection or iterator.
*/
case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] {
def iterator() = underlying.iterator() ++ other
override def knownSize = other match {
case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 =>
underlying.knownSize + other.knownSize
case _ =>
-1
}
}
/** A view that zips elements of the underlying collection with the elements
* of another collection or iterator.
*/
case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] {
def iterator() = underlying.iterator().zip(other)
override def knownSize = other match {
case other: Iterable[_] => underlying.knownSize min other.knownSize
case _ => -1
}
}
}
/** A trait representing indexable collections with finite length */
trait ArrayLike[+A] extends Any {
def length: Int
def apply(i: Int): A
}
/** View defined in terms of indexing a range */
trait IndexedView[+A] extends View[A] with ArrayLike[A] { self =>
def iterator(): Iterator[A] = new Iterator[A] {
private var current = 0
def hasNext = current < self.length
def next(): A = {
val r = apply(current)
current += 1
r
}
}
override def take(n: Int): IndexedView[A] = new IndexedView.Take(this, n)
override def drop(n: Int): IndexedView[A] = new IndexedView.Drop(this, n)
override def map[B](f: A => B): IndexedView[B] = new IndexedView.Map(this, f)
def reverse: IndexedView[A] = new IndexedView.Reverse(this)
}
object IndexedView {
class Take[A](underlying: IndexedView[A], n: Int)
extends View.Take(underlying, n) with IndexedView[A] {
override def iterator() = super.iterator() // needed to avoid "conflicting overrides" error
def length = underlying.length min normN
def apply(i: Int) = underlying.apply(i)
}
class Drop[A](underlying: IndexedView[A], n: Int)
extends View.Take(underlying, n) with IndexedView[A] {
override def iterator() = super.iterator()
def length = (underlying.length - normN) max 0
def apply(i: Int) = underlying.apply(i + normN)
}
class Map[A, B](underlying: IndexedView[A], f: A => B)
extends View.Map(underlying, f) with IndexedView[B] {
override def iterator() = super.iterator()
def length = underlying.length
def apply(n: Int) = f(underlying.apply(n))
}
case class Reverse[A](underlying: IndexedView[A]) extends IndexedView[A] {
def length = underlying.length
def apply(i: Int) = underlying.apply(length - 1 - i)
}
}