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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
import generic._
import Seq.fill
import TraversableView.NoBuilder
/** A template trait for a non-strict view of a sequence.
* @author Sean McDirmid
* @author Martin Odersky
* @version 2.8
*/
trait SeqViewLike[+A,
+Coll,
+This <: SeqView[A, Coll] with SeqViewLike[A, Coll, This]]
extends Seq[A]
with SeqLike[A, This]
with IterableView[A, Coll]
with IterableViewLike[A, Coll, This]
with views.SeqTransformations[A, Coll, This]
{ self =>
trait Transformed[+B] extends views.SeqLike[B, Coll] with super.Transformed[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)).toSeq(idx - index(row))
}
}
trait Appended[B >: A] extends Transformed[B] with super.Appended[B] {
protected[this] lazy val restSeq = rest.toSeq
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 Zipped[B] extends Transformed[(A, B)] with super.Zipped[B] {
protected[this] lazy val thatSeq = other.toSeq
override def length: Int = self.length min thatSeq.length
override def apply(idx: Int) = (self.apply(idx), thatSeq.apply(idx))
}
trait ZippedAll[A1 >: A, B] extends Transformed[(A1, B)] with super.ZippedAll[A1, B] {
protected[this] lazy val thatSeq = other.toSeq
override def length: Int = self.length max thatSeq.length
override def apply(idx: Int) =
(if (idx < self.length) self.apply(idx) else thisElem,
if (idx < thatSeq.length) thatSeq.apply(idx) else thatElem)
}
trait Reversed extends Transformed[A] {
override def iterator: Iterator[A] = createReversedIterator
override def length: Int = self.length
override def apply(idx: Int): A = self.apply(length - 1 - idx)
override def stringPrefix = self.stringPrefix+"R"
private def createReversedIterator = {
var lst = List[A]()
for (elem <- self) lst ::= elem
lst.iterator
}
}
trait Patched[B >: A] extends Transformed[B] {
protected[this] val from: Int
protected[this] val patch: Seq[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 = self.stringPrefix+"P"
}
override def reverse: This = newReversed.asInstanceOf[This]
override def patch[B >: A, That](from: Int, patch: Seq[B], replaced: Int)(implicit bf: CanBuildFrom[This, B, That]): That = {
newPatched(from, patch, replaced).asInstanceOf[That]
// was: val b = bf(repr)
// if (b.isInstanceOf[NoBuilder[_]]) newPatched(from, patch, replaced).asInstanceOf[That]
// else super.patch[B, That](from, patch, replaced)(bf)
}
//TR TODO: updated, +: ed :+ ed
override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: CanBuildFrom[This, B, That]): That =
patch(length, fill(len - length)(elem), 0)
override def reverseMap[B, That](f: A => B)(implicit bf: CanBuildFrom[This, B, That]): That =
reverse.map(f)
override def stringPrefix = "SeqView"
}
|
