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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.generic
import Sequence.fill
import TraversableView.NoBuilder
/** A non-strict projection of an iterable.
* @author Sean McDirmid
* @author Martin Odersky
* @version 2.8
*/
trait SequenceViewTemplate[+A,
+Coll <: Sequence[_],
+This <: SequenceView[A, Coll] with SequenceViewTemplate[A, Coll, This]]
extends Sequence[A] with SequenceTemplate[A, This] with IterableView[A, Coll] with IterableViewTemplate[A, Coll, This]
{ self =>
trait Transformed[+B] extends SequenceView[B, Coll] with super.Transformed[B] {
override def length: Int
override def apply(idx: Int): B
}
trait Sliced extends Transformed[A] with super.Sliced {
override def length = ((until min self.length) - from) max 0
override def apply(idx: Int): A =
if (idx + from < until) self.apply(idx + from)
else throw new IndexOutOfBoundsException(idx.toString)
}
trait Mapped[B] extends Transformed[B] with super.Mapped[B] {
override def length = self.length
override def apply(idx: Int): B = mapping(self apply idx)
}
trait FlatMapped[B] extends Transformed[B] with super.FlatMapped[B] {
protected[this] lazy val index = {
val index = new Array[Int](self.length + 1)
index(0) = 0
for (i <- 0 until self.length)
index(i + 1) = index(i) + mapping(self(i)).size
index
}
protected[this] def findRow(idx: Int, lo: Int, hi: Int): Int = {
val mid = (lo + hi) / 2
if (idx < index(mid)) findRow(idx, lo, mid - 1)
else if (idx >= index(mid + 1)) findRow(idx, mid + 1, hi)
else mid
}
override def length = index(self.length)
override def apply(idx: Int) = {
val row = findRow(idx, 0, self.length - 1)
mapping(self(row)).toSequence(idx - index(row))
}
}
trait Appended[B >: A] extends Transformed[B] with super.Appended[B] {
lazy val restSeq = rest.toSequence
override def length = self.length + restSeq.length
override def apply(idx: Int) =
if (idx < self.length) self(idx) else restSeq(idx - self.length)
}
trait Filtered extends Transformed[A] with super.Filtered {
protected[this] lazy val index = {
var len = 0
val arr = new Array[Int](self.length)
for (i <- 0 until self.length)
if (pred(self(i))) {
arr(len) = i
len += 1
}
arr take len
}
override def length = index.length
override def apply(idx: Int) = self(index(idx))
}
trait TakenWhile extends Transformed[A] with super.TakenWhile {
protected[this] lazy val len = self prefixLength pred
override def length = len
override def apply(idx: Int) =
if (idx < len) self(idx)
else throw new IndexOutOfBoundsException(idx.toString)
}
trait DroppedWhile extends Transformed[A] with super.DroppedWhile {
protected[this] lazy val start = self prefixLength pred
override def length = self.length - start
override def apply(idx: Int) =
if (idx >= 0) self(idx + start)
else throw new IndexOutOfBoundsException(idx.toString)
}
trait Reversed extends Transformed[A] {
override def iterator: Iterator[A] = self.reverseIterator
override def length: Int = self.length
override def apply(idx: Int): A = self.apply(length - 1 - idx)
override def stringPrefix = super.stringPrefix+"R"
}
trait Patched[B >: A] extends Transformed[B] {
protected[this] val from: Int
protected[this] val patch: Sequence[B]
protected[this] val replaced: Int
private lazy val plen = patch.length
override def iterator: Iterator[B] = self.iterator patch (from, patch.iterator, replaced)
override def length: Int = self.length + plen - replaced
override def apply(idx: Int): B =
if (idx < from) self.apply(idx)
else if (idx < from + plen) patch.apply(idx - from)
else self.apply(idx - plen + replaced)
override def stringPrefix = super.stringPrefix+"P"
}
trait Zipped[B] extends Transformed[(A, B)] {
protected[this] val other: Sequence[B]
override def iterator: Iterator[(A, B)] = self.iterator zip other.iterator
override def length = self.length min other.length
override def apply(idx: Int): (A, B) = (self.apply(idx), other.apply(idx))
override def stringPrefix = super.stringPrefix+"Z"
}
/** Boilerplate method, to override in each subclass
* This method could be eliminated if Scala had virtual classes
*/
protected override def newAppended[B >: A](that: Traversable[B]): Transformed[B] = new Appended[B] { val rest = that }
protected override def newMapped[B](f: A => B): Transformed[B] = new Mapped[B] { val mapping = f }
protected override def newFlatMapped[B](f: A => Traversable[B]): Transformed[B] = new FlatMapped[B] { val mapping = f }
protected override def newFiltered(p: A => Boolean): Transformed[A] = new Filtered { val pred = p }
protected override def newSliced(_from: Int, _until: Int): Transformed[A] = new Sliced { val from = _from; val until = _until }
protected override def newDroppedWhile(p: A => Boolean): Transformed[A] = new DroppedWhile { val pred = p }
protected override def newTakenWhile(p: A => Boolean): Transformed[A] = new TakenWhile { val pred = p }
protected def newReversed: Transformed[A] = new Reversed { }
protected def newPatched[B >: A](_from: Int, _patch: Sequence[B], _replaced: Int): Transformed[B] = new Patched[B] {
val from = _from; val patch = _patch; val replaced = _replaced
}
protected def newZipped[B](that: Sequence[B]): Transformed[(A, B)] = new Zipped[B] {
val other = that
}
override def reverse: This = newReversed.asInstanceOf[This]
override def patch[B >: A, That](from: Int, patch: Sequence[B], replaced: Int)(implicit bf: BuilderFactory[B, That, This]): That = {
newPatched(from, patch, replaced).asInstanceOf[That]
// was: val b = bf(thisCollection)
// if (b.isInstanceOf[NoBuilder[_]]) newPatched(from, patch, replaced).asInstanceOf[That]
// else super.patch[B, That](from, patch, replaced)(bf)
}
override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: BuilderFactory[B, That, This]): That =
patch(length, fill(len - length)(elem), 0)
override def zip[A1 >: A, B, That](that: Sequence[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = {
newZipped(that).asInstanceOf[That]
// was: val b = bf(thisCollection)
// if (b.isInstanceOf[NoBuilder[_]]) newZipped(that).asInstanceOf[That]
// else super.zip[A1, B, That](that)(bf)
}
override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That =
zip[A1, Int, That](Sequence.range(0, length))(bf)
override def zipAll[B, A1 >: A, That](that: Sequence[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That =
self.padTo(that.length, thisElem).zip(that.padTo(this.length, thatElem))(bf.asInstanceOf[BuilderFactory[(A1, B), That, Any]])
}
|