8000 Merge pull request #110 from scala/iterable-builders · szeiger/scala@c52e348 · GitHub
[go: up one dir, main page]
Skip to content

Commit c52e348

Browse files
julienrfjulienrf
authored
Merge pull request scala#110 from scala/iterable-builders
Pull up the newBuilder method from Buildable to IterableOps.
2 parents d9e35fd + 4bf69ec commit c52e348

37 files changed

+298
-135
lines changed

‎src/main/scala/strawman/collection/ArrayOps.scala

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,19 @@
11
package strawman
22
package collection
33

4-
import scala.{Array, Char, Int, AnyVal}
4+
import scala.{AnyVal, Array, Char, Int}
55
import scala.Predef.???
6-
import mutable.ArrayBuffer
6+
import mutable.{ArrayBuffer, GrowableBuilder}
77

88
import scala.reflect.ClassTag
9+
910
class ArrayOps[A](val xs: Array[A])
1011
extends AnyVal
11-
with SeqOps[A, immutable.Seq, Array[A]] // should be IndexedSeq once we have an instance type
12-
with Buildable[A, Array[A]]
13-
with ArrayLike[A] {
12+
with SeqOps[A, immutable.IndexedSeq, Array[A]]
13+
with StrictOptimizedIterableOps[A, Array[A]]
14+
with ArrayLike[A] {
1415

15-
protected def coll = new ArrayView(xs)
16+
protected[this] def coll = new ArrayView(xs)
1617

1718
def length = xs.length
1819
def apply(i: Int) = xs.apply(i)
@@ -21,12 +22,12 @@ class ArrayOps[A](val xs: Array[A])
2122

2223
def elemTag: ClassTag[A] = ClassTag(xs.getClass.getComponentType)
2324

24-
def iterableFactory = immutable.Seq
25+
def iterableFactory = immutable.IndexedSeq
2526

2627
protected[this] def fromTaggedIterable[B: ClassTag](coll: Iterable[B]): Array[B] = coll.toArray[B]
2728
protected[this] def fromSpecificIterable(coll: Iterable[A]): Array[A] = coll.toArray[A](elemTag)
2829

29-
protected[this] def newBuilder = new ArrayBuffer[A].mapResult(_.toArray(elemTag))
30+
protected[this] def newSpecificBuilder() = new GrowableBuilder(ArrayBuffer.empty[A]).mapResult(_.toArray(elemTag))
3031

3132
override def knownSize = xs.length
3233

‎src/main/scala/strawman/collection/BitSet.scala

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ trait BitSetOps[+C <: BitSet with BitSetOps[C]]
1212
extends SortedSetOps[Int, SortedSet, C] {
1313
import BitSetOps._
1414

15-
protected def coll: C
15+
protected[this] def coll: C
1616

1717
final def ordering: Ordering[Int] = Ordering.Int
1818

‎src/main/scala/strawman/collection/Factories.scala

Lines changed: 59 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -28,10 +28,6 @@ trait IterableFactory[+CC[_]] {
2828

2929
}
3030

31-
trait IterableFactoryWithBuilder[+CC[_]] extends IterableFactory[CC] {
32-
def newBuilder[A](): Builder[A, CC[A]]
33-
}
34-
3531
object IterableFactory {
3632
import scala.language.implicitConversions
3733

@@ -47,6 +43,18 @@ object IterableFactory {
4743

4844
}
4945

46+
trait IterableFactoryWithBuilder[+CC[_]] extends IterableFactory[CC] {
47+
def newBuilder[A](): Builder[A, CC[A]]
48+
}
49+
50+
object IterableFactoryWithBuilder {
51+
class Delegate[CC[_]](delegate: IterableFactoryWithBuilder[CC])
52+
extends IterableFactory.Delegate[CC](delegate)
53+
with IterableFactoryWithBuilder[CC] {
54+
def newBuilder[A](): Builder[A, CC[A]] = delegate.newBuilder()
55+
}
56+
}
57+
5058
trait SpecificIterableFactory[-A, +C] extends FromSpecificIterable[A, C] {
5159
def empty: C
5260

@@ -55,8 +63,12 @@ trait SpecificIterableFactory[-A, +C] extends FromSpecificIterable[A, C] {
5563
def fill(n: Int)(elem: => A): C = fromSpecificIterable(View.Fill(n)(elem))
5664
}
5765

66+
trait SpecificIterableFactoryWithBuilder[-A, +C] extends SpecificIterableFactory[A, C] {
67+
def newBuilder(): Builder[A, C]
68+
}
69+
5870
/** Factory methods for collections of kind `* −> * -> *` */
59-
trait MapFactory[+CC[X, Y]] {
71+
trait MapFactory[+CC[_, _]] {
6072

6173
def empty[K, V]: CC[K, V]
6274
def fromIterable[K, V](it: Iterable[(K, V)]): CC[K, V]
@@ -67,14 +79,28 @@ trait MapFactory[+CC[X, Y]] {
6779
object MapFactory {
6880
import scala.language.implicitConversions
6981

70-
implicit def toSpecific[K, V, CC[X, Y]](factory: MapFactory[CC]): FromSpecificIterable[(K, V), CC[K, V]] =
82+
implicit def toSpecific[K, V, CC[_, _]](factory: MapFactory[CC]): FromSpecificIterable[(K, V), CC[K, V]] =
7183
new FromSpecificIterable[(K, V), CC[K, V]] {
7284
def fromSpecificIterable(it: Iterable[(K, V)]): CC[K, V] = factory.fromIterable[K, V](it)
7385
}
7486

75-
class Delegate[C[X, Y]](delegate: MapFactory[C]) extends MapFactory[C] {
76-
def fromIterable[K, V](it: Iterable[(K, V)]): C[K, V] = delegate.fromIterable(it)
77-
def empty[K, V]: C[K, V] = delegate.empty
87+
class Delegate[CC[_, _]](delegate: MapFactory[CC]) extends MapFactory[CC] {
88+
def fromIterable[K, V](it: Iterable[(K, V)]): CC[K, V] = delegate.fromIterable(it)
89+
def empty[K, V]: CC[K, V] = delegate.empty
90+
}
91+
92+
}
93+
94+
trait MapFactoryWithBuilder[+CC[_, _]] extends MapFactory[CC] {
95+
def newBuilder[K, V](): Builder[(K, V), CC[K, V]]
96+
}
97+
98+
object MapFactoryWithBuilder {
99+
100+
class Delegate[CC[_, _]](delegate: MapFactoryWithBuilder[CC])
101+
extends MapFactory.Delegate[CC](delegate)
102+
with MapFactoryWithBuilder[CC] {
103+
def newBuilder[K, V](): Builder[(K, V), CC[K, V]] = delegate.newBuilder()
78104
}
79105

80106
}
@@ -106,6 +132,18 @@ object SortedIterableFactory {
106132

107133
}
108134

135+
trait SortedIterableFactoryWithBuilder[+CC[_]] extends SortedIterableFactory[CC] {
136+
def newBuilder[A : Ordering](): Builder[A, CC[A]]
137+
}
138+
139+
object SortedIterableFactoryWithBuilder {
140+
class Delegate[CC[_]](delegate: SortedIterableFactoryWithBuilder[CC])
141+
extends SortedIterableFactory.Delegate[CC](delegate)
142+
with SortedIterableFactoryWithBuilder[CC] {
143+
def newBuilder[A: Ordering](): Builder[A, CC[A]] = delegate.newBuilder()
144+
}
145+
}
146+
109147
/** Factory methods for collections of kind `* −> * -> *` which require an implicit evidence value for the key type */
110148
trait SortedMapFactory[+CC[X, Y]] {
111149

@@ -131,3 +169,15 @@ object SortedMapFactory {
131169
}
132170

133171
}
172+
173+
trait SortedMapFactoryWithBuilder[+CC[_, _]] extends SortedMapFactory[CC] {
174+
def newBuilder[K : Ordering, V](): Builder[(K, V), CC[K, V]]
175+
}
176+
177+
object SortedMapFactoryWithBuilder {
178+
class Delegate[CC[_, _]](delegate: SortedMapFactoryWithBuilder[CC])
179+
extends SortedMapFactory.Delegate[CC](delegate)
180+
with SortedMapFactoryWithBuilder[CC] {
181+
def newBuilder[K: Ordering, V](): Builder[(K, V), CC[K, V]] = delegate.newBuilder()
182+
}
183+
}

‎src/main/scala/strawman/collection/Iterable.scala

Lines changed: 15 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,8 @@ import java.lang.String
1313
trait Iterable[+A] extends IterableOnce[A] with IterableOps[A, Iterable, Iterable[A]] {
1414

1515
/** The collection itself */
16-
protected def coll: this.type = this
16+
protected[this] def coll: this.type = this
17+
1718
}
1819

1920
/** Base trait for Iterable operations
@@ -28,13 +29,23 @@ trait Iterable[+A] extends IterableOnce[A] with IterableOps[A, Iterable, Iterabl
2829
*/
2930
trait IterableOps[+A, +CC[X], +C] extends Any {
3031

31-
protected def coll: Iterable[A]
32+
protected[this] def coll: Iterable[A]
3233

3334
protected[this] def fromSpecificIterable(coll: Iterable[A]): C
3435

36+
protected[this] def fromIterable[E](it: Iterable[E]): CC[E] = iterableFactory.fromIterable(it)
37+
3538
def iterableFactory: IterableFactory[CC]
3639

37-
protected[this] def fromIterable[E](it: Iterable[E]): CC[E] = iterableFactory.fromIterable(it)
40+
/**
41+
* @return a strict builder for the same collection type.
42+
*
43+
* Note that in the case of lazy collections (e.g. [[View]] or [[immutable.LazyList]]),
44+
* it is possible to implement this method but the resulting `Builder` will break laziness.
45+
* As a consequence, operations should preferably be implemented on top of views rather
46+
* than builders.
47+
*/
48+
protected[this] def newSpecificBuilder(): Builder[A, C]
3849

3950
/** Apply `f` to each element for its side effects
4051
* Note: [U] parameter needed to help scalac's type inference.
@@ -93,7 +104,7 @@ trait IterableOps[+A, +CC[X], +C] extends Any {
93104
* xs.to(ArrayBuffer)
94105
* xs.to(BitSet) // for xs: Iterable[Int]
95106
*/
96-
def to[C](f: FromSpecificIterable[A, C]): C = f.fromSpecificIterable(coll)
107+
def to[C1](f: FromSpecificIterable[A, C1]): C1 = f.fromSpecificIterable(coll)
97108

98109
/** Convert collection to array. */
99110
def toArray[B >: A: ClassTag]: Array[B] =
@@ -265,25 +276,3 @@ trait IterableOps[+A, +CC[X], +C] extends Any {
265276
def zip[B](xs: IterableOnce[B]): CC[(A @uncheckedVariance, B)] = fromIterable(View.Zip(coll, xs))
266277
// sound bcs of VarianceNote
267278
}
268-
269-
/** Base trait for strict collections that can be built using a builder.
270-
* @tparam A the element type of the collection
271-
* @tparam C the type of the underlying collection
272-
*/
273-
trait Buildable[+A, +C] extends Any with IterableOps[A, AnyConstr, C] {
274-
275-
/** Creates a new builder. */
276-
protected[this] def newBuilder: Builder[A, C]
277-
278-
/** Optimized, push-based version of `partition`. */
279-
override def partition(p: A => Boolean): (C, C) = {
280-
val l, r = newBuilder
281-
coll.iterator().foreach(x => (if (p(x)) l else r) += x)
282-
(l.result(), r.result())
283-
}
284-
285-
// one might also override other transforms here to avoid generating
286-
// iterators if it helps efficiency.
287-
}
288-
289-

‎src/main/scala/strawman/collection/Map.scala

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ trait MapOps[K, +V, +CC[X, Y] <: Map[X, Y], +C <: Map[K, V]]
1414
extends IterableOps[(K, V), Iterable, C]
1515
with PartialFunction[K, V] {
1616

17-
protected def coll: Map[K, V]
17+
protected[this] def coll: Map[K, V]
1818

1919
/** Similar to fromIterable, but returns a Map collection type */
2020
protected[this] def mapFromIterable[K2, V2](it: Iterable[(K2, V2)]): CC[K2, V2]
@@ -85,4 +85,4 @@ trait MapOps[K, +V, +CC[X, Y] <: Map[X, Y], +C <: Map[K, V]]
8585

8686
}
8787

88-
object Map extends MapFactory.Delegate[Map](immutable.Map)
88+
object Map extends MapFactoryWithBuilder.Delegate[Map](immutable.Map)

‎src/main/scala/strawman/collection/Seq.scala

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,7 @@ trait IndexedSeqOps[+A, +CC[X] <: IndexedSeq[X], +C] extends Any with SeqOps[A,
8686
/** Base trait for linear Seq operations */
8787
trait LinearSeqOps[+A, +CC[X] <: LinearSeq[X], +C <: LinearSeq[A]] extends Any with SeqOps[A, CC, C] {
8888

89-
protected def coll: Seq[A]
89+
protected[this] def coll: Seq[A]
9090

9191
/** To be overridden in implementations: */
9292
def isEmpty: Boolean

‎src/main/scala/strawman/collection/Set.scala

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ trait SetOps[A, +CC[X], +C <: Set[A]]
1414
with (A => Boolean)
1515
with Equals {
1616

17-
protected def coll: C
17+
protected[this] def coll: C
1818

1919
def contains(elem: A): Boolean
2020

‎src/main/scala/strawman/collection/SortedMap.scala

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,4 +48,4 @@ trait SortedMapOps[K, +V, +CC[X, Y] <: SortedMap[X, Y] with SortedMapOps[X, Y, C
4848

4949
}
5050

51-
object SortedMap extends SortedMapFactory.Delegate[SortedMap](TreeMap)
51+
object SortedMap extends SortedMapFactoryWithBuilder.Delegate[SortedMap](TreeMap)

‎src/main/scala/strawman/collection/SortedSet.scala

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,4 +32,4 @@ trait SortedSetOps[A, +CC[X], +C <: SortedSet[A]]
3232
)
3333
}
3434

35-
object SortedSet extends SortedIterableFactory.Delegate[SortedSet](immutable.SortedSet)
35+
object SortedSet extends SortedIterableFactoryWithBuilder.Delegate[SortedSet](immutable.SortedSet)

‎src/main/scala/strawman/collection/StrictOptimizedIterableOps.scala

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package strawman
2+
package collection
3+
4+
import scala.{Any, Boolean}
5+
6+
/**
7+
* Trait that overrides operations to take advantage of strict builders.
8+
*
9+
* @tparam A Elements type
10+
* @tparam C Collection type
11+
*/
12+
trait StrictOptimizedIterableOps[+A, +C]
13+
extends Any
14+
with IterableOps[A, AnyConstr, C] {
15+
16+
/** Optimized, push-based version of `partition`. */
17+
override def partition(p: A => Boolean): (C, C) = {
18+
val l, r = newSpecificBuilder()
19+
coll.iterator().foreach(x => (if (p(x)) l else r) += x)
20+
(l.result(), r.result())
21+
}
22+
23+
// one might also override other transforms here to avoid generating
24+
// iterators if it helps efficiency.
25+
26+
}

0 commit comments

Comments
 (0)
0