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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
import generic._
import immutable.{List, Stream}
import annotation.unchecked.uncheckedVariance
/** A template trait for iterable collections of type `Iterable[A]`.
* $iterableInfo
* @define iterableInfo
* This is a base trait for all $mutability Scala collections that define an `iterator`
* method to step through one-by-one the collection's elements.
* Implementations of this trait need to provide a concrete method with
* signature:
* {{{
* def iterator: Iterator[A]
* }}}
* They also need to provide a method `newBuilder`
* which creates a builder for collections of the same kind.
*
* This trait implements `Iterable`'s `foreach`
* method by stepping through all elements using `iterator`.
* Subclasses should re-implement `foreach` with something more efficient,
* if possible.
* This trait adds methods `iterator`, `sameElements`,
* `takeRight`, `dropRight` to the methods inherited
* from trait <a href="../Traversable.html" target="ContentFrame">
* `Traversable`</a>.
* Note: This trait replaces every method that uses `break` in
* `TraversableLike` by an iterator version.
*
* @author Martin Odersky
* @version 2.8
* @since 2.8
* @tparam A the element type of the collection
* @tparam Repr the type of the actual collection containing the elements.
*
* @define Coll Iterable
* @define coll iterable collection
* @define zipthatinfo the class of the returned collection. Where possible, `That` is
* the same class as the current collection class `Repr`, but this
* depends on the element type `(A1, B)` being admissible for that class,
* which means that an implicit instance of type `CanBuildFrom[Repr, (A1, B), That]`.
* is found.
* @define zipbfinfo an implicit value of class `CanBuildFrom` which determines the
* result class `That` from the current representation type `Repr`
* and the new element type `(A1, B)`.
*/
trait IterableLike[+A, +Repr] extends Equals with TraversableLike[A, Repr] {
self =>
override protected[this] def thisCollection: Iterable[A] = this.asInstanceOf[Iterable[A]]
override protected[this] def toCollection(repr: Repr): Iterable[A] = repr.asInstanceOf[Iterable[A]]
/** Creates a new iterator over all elements contained in this
* iterable object.
*
* @return the new iterator
*/
def iterator: Iterator[A]
/** Applies a function `f` to all elements of this $coll.
*
* Note: this method underlies the implementation of most other bulk operations.
* Subclasses should re-implement this method if a more efficient implementation exists.
*
* @usecase def foreach(f: A => Unit): Unit
*/
def foreach[U](f: A => U): Unit =
iterator.foreach(f)
override /*TraversableLike*/ def forall(p: A => Boolean): Boolean =
iterator.forall(p)
override /*TraversableLike*/ def exists(p: A => Boolean): Boolean =
iterator.exists(p)
override /*TraversableLike*/ def find(p: A => Boolean): Option[A] =
iterator.find(p)
/*
override /*TraversableLike*/ def mapFind[B](f: A => Option[B]): Option[B] =
iterator.mapFind(f)
*/
override /*TraversableLike*/ def isEmpty: Boolean =
!iterator.hasNext
override /*TraversableLike*/ def foldRight[B](z: B)(op: (A, B) => B): B =
iterator.foldRight(z)(op)
override /*TraversableLike*/ def reduceRight[B >: A](op: (A, B) => B): B =
iterator.reduceRight(op)
override /*TraversableLike*/ def toIterable: Iterable[A] =
thisCollection
override /*TraversableLike*/ def head: A =
if (isEmpty) throw new NoSuchElementException
else iterator.next
override /*TraversableLike*/ def take(n: Int): Repr = {
val b = newBuilder
b.sizeHintBounded(n, this)
var i = 0
val it = iterator
while (i < n && it.hasNext) {
b += it.next
i += 1
}
b.result
}
override /*TraversableLike*/ def slice(from: Int, until: Int): Repr = {
val b = newBuilder
b.sizeHintBounded(until - from, this)
var i = from
val it = iterator drop from
while (i < until && it.hasNext) {
b += it.next
i += 1
}
b.result
}
override /*TraversableLike*/ def takeWhile(p: A => Boolean): Repr = {
val b = newBuilder
val it = iterator
while (it.hasNext) {
val x = it.next
if (!p(x)) return b.result
b += x
}
b.result
}
/** Partitions elements in fixed size ${coll}s.
* @see Iterator#grouped
*
* @param size the number of elements per group
* @return An iterator producing ${coll}s of size `size`, except the
* last will be truncated if the elements don't divide evenly.
*/
def grouped(size: Int): Iterator[Repr] =
for (xs <- iterator grouped size) yield {
val b = newBuilder
b ++= xs
b.result
}
/** Groups elements in fixed size blocks by passing a "sliding window"
* over them (as opposed to partitioning them, as is done in grouped.)
* @see Iterator#sliding
*
* @param size the number of elements per group
* @param step the distance between the first elements of successive
* groups (defaults to 1)
* @return An iterator producing ${coll}s of size `size`, except the
* last will be truncated if the elements don't divide evenly.
*/
def sliding[B >: A](size: Int): Iterator[Repr] = sliding(size, 1)
def sliding[B >: A](size: Int, step: Int): Iterator[Repr] =
for (xs <- iterator.sliding(size, step)) yield {
val b = newBuilder
b ++= xs
b.result
}
/** Selects last ''n'' elements.
* $orderDependent
*
* @param n the number of elements to take
* @return a $coll consisting only of the last `n` elements of this $coll, or else the
* whole $coll, if it has less than `n` elements.
*/
def takeRight(n: Int): Repr = {
val b = newBuilder
b.sizeHintBounded(n, this)
val lead = this.iterator drop n
var go = false
for (x <- this) {
if (lead.hasNext) lead.next
else go = true
if (go) b += x
}
b.result
}
/** Selects all elements except last ''n'' ones.
* $orderDependent
*
* @param n The number of elements to take
* @return a $coll consisting of all elements of this $coll except the first `n` ones, or else the
* empty $coll, if this $coll has less than `n` elements.
*/
def dropRight(n: Int): Repr = {
val b = newBuilder
if (n >= 0) b.sizeHint(this, -n)
val lead = iterator drop n
val it = iterator
while (lead.hasNext) {
b += it.next
lead.next
}
b.result
}
override /*TraversableLike*/ def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
var i = start
val end = (start + len) min xs.length
val it = iterator
while (i < end && it.hasNext) {
xs(i) = it.next
i += 1
}
}
/** Returns a $coll formed from this $coll and another iterable collection
* by combining corresponding elements in pairs.
* If one of the two collections is longer than the other, its remaining elements are ignored.
*
* $orderDependent
*
* @param that The iterable providing the second half of each result pair
* @tparam A1 the type of the first half of the returned pairs (this is always a supertype
* of the collection's element type `A`).
* @tparam B the type of the second half of the returned pairs
* @tparam That $zipthatinfo
* @param bf $zipbfinfo
* @return a new collection of type `That` containing pairs consisting of
* corresponding elements of this $coll and `that`. The length
* of the returned collection is the minimum of the lengths of this $coll and `that`.
*
* @usecase def zip[B](that: Iterable[B]): $Coll[(A, B)]
*
* @param that The iterable providing the second half of each result pair
* @tparam B the type of the second half of the returned pairs
* @return a new $coll containing pairs consisting of
* corresponding elements of this $coll and `that`. The length
* of the returned collection is the minimum of the lengths of this $coll and `that`.
*/
def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: CanBuildFrom[Repr, (A1, B), That]): That = {
val b = bf(repr)
val these = this.iterator
val those = that.iterator
while (these.hasNext && those.hasNext)
b += ((these.next, those.next))
b.result
}
/** Returns a $coll formed from this $coll and another iterable collection
* by combining corresponding elements in pairs.
* If one of the two collections is shorter than the other,
* placeholder elements are used to extend the shorter collection to the length of the longer.
*
* $orderDependent
*
* @param that the iterable providing the second half of each result pair
* @param thisElem the element to be used to fill up the result if this $coll is shorter than `that`.
* @param thatElem the element to be used to fill up the result if `that` is shorter than this $coll.
* @return a new collection of type `That` containing pairs consisting of
* corresponding elements of this $coll and `that`. The length
* of the returned collection is the maximum of the lengths of this $coll and `that`.
* If this $coll is shorter than `that`, `thisElem` values are used to pad the result.
* If `that` is shorter than this $coll, `thatElem` values are used to pad the result.
*
* @usecase def zipAll[B](that: Iterable[B], thisElem: A, thatElem: B): $Coll[(A, B)]
*
* @param that The iterable providing the second half of each result pair
* @param thisElem the element to be used to fill up the result if this $coll is shorter than `that`.
* @param thatElem the element to be used to fill up the result if `that` is shorter than this $coll.
* @tparam B the type of the second half of the returned pairs
* @return a new $coll containing pairs consisting of
* corresponding elements of this $coll and `that`. The length
* of the returned collection is the maximum of the lengths of this $coll and `that`.
* If this $coll is shorter than `that`, `thisElem` values are used to pad the result.
* If `that` is shorter than this $coll, `thatElem` values are used to pad the result.
*/
def zipAll[B, A1 >: A, That](that: Iterable[B], thisElem: A1, thatElem: B)(implicit bf: CanBuildFrom[Repr, (A1, B), That]): That = {
val b = bf(repr)
val these = this.iterator
val those = that.iterator
while (these.hasNext && those.hasNext)
b += ((these.next, those.next))
while (these.hasNext)
b += ((these.next, thatElem))
while (those.hasNext)
b += ((thisElem, those.next))
b.result
}
/** Zips this $coll with its indices.
*
* $orderDependent
*
* @tparam A1 the type of the first half of the returned pairs (this is always a supertype
* of the collection's element type `A`).
* @tparam That the class of the returned collection. Where possible, `That` is
* the same class as the current collection class `Repr`, but this
* depends on the element type `(A1, Int)` being admissible for that class,
* which means that an implicit instance of type `CanBuildFrom[Repr, (A1, Int), That]`.
* is found.
* @tparam bf an implicit value of class `CanBuildFrom` which determines the
* result class `That` from the current representation type `Repr`
* and the new element type `(A1, Int)`.
* @return A new collection of type `That` containing pairs consisting of all elements of this
* $coll paired with their index. Indices start at `0`.
*
* @usecase def zipWithIndex: $Coll[(A, Int)]
*
* @return A new $coll containing pairs consisting of all elements of this
* $coll paired with their index. Indices start at `0`.
* @example
* `List("a", "b", "c").zipWithIndex = List(("a", 0), ("b", 1), ("c", 2))`
*
*/
def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
val b = bf(repr)
var i = 0
for (x <- this) {
b += ((x, i))
i +=1
}
b.result
}
/** Checks if the other iterable collection contains the same elements in the same order as this $coll.
*
* $orderDependent
* $willNotTerminateInf
*
* @param that the collection to compare with.
* @tparam B the type of the elements of collection `that`.
* @return `true`, if both collections contain the same elements in the same order, `false` otherwise.
*
* @usecase def sameElements(that: Iterable[A]): Boolean
*
* @param that the collection to compare with.
* @return `true`, if both collections contain the same elements in the same order, `false` otherwise.
*/
def sameElements[B >: A](that: Iterable[B]): Boolean = {
val these = this.iterator
val those = that.iterator
while (these.hasNext && those.hasNext)
if (these.next != those.next)
return false
!these.hasNext && !those.hasNext
}
override /*TraversableLike*/ def toStream: Stream[A] = iterator.toStream
/** Method called from equality methods, so that user-defined subclasses can
* refuse to be equal to other collections of the same kind.
* @param that The object with which this $coll should be compared
* @return `true`, if this $coll can possibly equal `that`, `false` otherwise. The test
* takes into consideration only the run-time types of objects but ignores their elements.
*/
override /*TraversableLike*/ def canEqual(that: Any) = true
override /*TraversableLike*/ def view = new IterableView[A, Repr] {
protected lazy val underlying = self.repr
override def iterator = self.iterator
}
override /*TraversableLike*/ def view(from: Int, until: Int) = view.slice(from, until)
@deprecated("use `iterator' instead")
def elements = iterator
@deprecated("use `head' instead") def first: A = head
/** `None` if iterable is empty.
*/
@deprecated("use `headOption' instead") def firstOption: Option[A] = headOption
/**
* returns a projection that can be used to call non-strict `filter`,
* `map`, and `flatMap` methods that build projections
* of the collection.
*/
@deprecated("use `view' instead")
def projection = view
}
|