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
|
package examples.tcpoly.collection
trait HOSeq {
// an internal interface that encapsulates the accumulation of elements (of type elT) to produce
// a structure of type coll[elT] -- different kinds of collections should provide different implicit
// values implementing this interface, in order to provide more performant ways of building that structure
trait Accumulator[+coll[x], elT] {
def += (el: elT): Unit
def result: coll[elT]
}
// Iterable abstracts over the type of its structure as well as its elements (see PolyP's Bifunctor)
// m[x] is intentionally unbounded: fold can then be defined nicely
// variance: if we write m[+x] instead of +m[+x], x is an invariant position because its enclosing type
// is an invariant position -- should probably rule that out?
trait Iterable[+t] {
type m[+x]
//def unit[a](orig: a): m[a]
def iterator: Iterator[t]
// construct an empty accumulator that will produce the same structure as this iterable, with elements of type t
def accumulator[t]: Accumulator[m, t]
def filter(p: t => Boolean): m[t] = {
val buf = accumulator[t]
val elems = iterator
while (elems.hasNext) { val x = elems.next; if (p(x)) buf += x }
buf.result
}
def map[s](f: t => s): m[s] = {
val buf = accumulator[s]
val elems = iterator
while (elems.hasNext) buf += f(elems.next)
buf.result
}
// flatMap is a more specialized map, it only works if the mapped function produces Iterable values,
// which are then added to the result one by one
// the compiler should be able to find the right accumulator (implicit buf) to build the result
// to get concat, resColl = SingletonIterable, f = unit for SingletonIterable
def flatMap[resColl[+x] <: Iterable[x], s](f: t => resColl[s])(implicit buf: Accumulator[resColl, s]): resColl[s] = {
// TODO: would a viewbound for resColl[x] be better?
// -- 2nd-order type params are not yet in scope in view bound
val elems = iterator
while (elems.hasNext) {
val elemss: Iterator[s] = f(elems.next).iterator
while (elemss.hasNext) buf += elemss.next
}
buf.result
}
}
final class ListBuffer[A] {
private var start: List[A] = Nil
private var last: ::[A] = _
private var exported: Boolean = false
/** Appends a single element to this buffer.
*
* @param x the element to append.
*/
def += (x: A): Unit = {
if (exported) copy
if (start.isEmpty) {
last = new HOSeq.this.:: (x, Nil)
start = last
} else {
val last1 = last
last = new HOSeq.this.:: (x, null) // hack: ::'s tail will actually be last
//last1.tl = last
}
}
/** Converts this buffer to a list
*/
def toList: List[A] = {
exported = !start.isEmpty
start
}
/** Clears the buffer contents.
*/
def clear: Unit = {
start = Nil
exported = false
}
/** Copy contents of this buffer */
private def copy: Unit = {
var cursor = start
val limit = last.tail
clear
while (cursor ne limit) {
this += cursor.head
cursor = cursor.tail
}
}
}
implicit def listAccumulator[elT]: Accumulator[List, elT] = new Accumulator[List, elT] {
private[this] val buff = new ListBuffer[elT]
def += (el: elT): Unit = buff += el
def result: List[elT] = buff.toList
}
trait List[+t] extends Iterable[t] {
type m[+x] = List[x]
def head: t
def tail: List[t]
def isEmpty: Boolean
def iterator: Iterator[t] = new Iterator[t] {
var these = List.this
def hasNext: Boolean = !these.isEmpty
def next: t =
if (!hasNext)
throw new NoSuchElementException("next on empty Iterator")
else {
val result = these.head; these = these.tail; result
}
}
// construct an empty accumulator that will produce the same structure as this iterable, with elements of type t
def accumulator[t]: Accumulator[List, t] = listAccumulator[t]
}
// TODO: the var tl approach does not seem to work because subtyping isn't fully working yet
final case class ::[+b](hd: b, private val tl: List[b]) extends List[b] {
def head = hd
def tail = if (tl==null) this else tl // hack
override def isEmpty: Boolean = false
}
case object Nil extends List[Nothing] {
def isEmpty = true
def head: Nothing =
throw new NoSuchElementException("head of empty list")
def tail: List[Nothing] =
throw new NoSuchElementException("tail of empty list")
}
}
|
