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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection.mutable
import scala.collection.AbstractIterator
import scala.collection.Iterator
import scala.collection.generic._
import scala.annotation.tailrec
import scala.reflect.ClassTag
/** A buffer that stores elements in an unrolled linked list.
*
* Unrolled linked lists store elements in linked fixed size
* arrays.
*
* Unrolled buffers retain locality and low memory overhead
* properties of array buffers, but offer much more efficient
* element addition, since they never reallocate and copy the
* internal array.
*
* However, they provide `O(n/m)` complexity random access,
* where `n` is the number of elements, and `m` the size of
* internal array chunks.
*
* Ideal to use when:
* - elements are added to the buffer and then all of the
* elements are traversed sequentially
* - two unrolled buffers need to be concatenated (see `concat`)
*
* Better than singly linked lists for random access, but
* should still be avoided for such a purpose.
*
* @define coll unrolled buffer
* @define Coll `UnrolledBuffer`
* @author Aleksandar Prokopec
*
*/
@SerialVersionUID(1L)
sealed class UnrolledBuffer[T](implicit val tag: ClassTag[T])
extends scala.collection.mutable.AbstractBuffer[T]
with scala.collection.mutable.Buffer[T]
with scala.collection.mutable.BufferLike[T, UnrolledBuffer[T]]
with GenericClassTagTraversableTemplate[T, UnrolledBuffer]
with scala.collection.mutable.Builder[T, UnrolledBuffer[T]]
with Serializable
{
import UnrolledBuffer.Unrolled
@transient private var headptr = newUnrolled
@transient private var lastptr = headptr
@transient private var sz = 0
private[collection] def headPtr = headptr
private[collection] def headPtr_=(head: Unrolled[T]) = headptr = head
private[collection] def lastPtr = lastptr
private[collection] def lastPtr_=(last: Unrolled[T]) = lastptr = last
private[collection] def size_=(s: Int) = sz = s
protected[this] override def newBuilder = new UnrolledBuffer[T]
protected def newUnrolled = new Unrolled[T](this)
// The below would allow more flexible behavior without requiring inheritance
// that is risky because all the important internals are private.
// private var myLengthPolicy: Int => Int = x => x
//
// /** Specifies how the array lengths should vary.
// *
// * By default, `UnrolledBuffer` uses arrays of a fixed size. A length
// * policy can be given that changes this scheme to, for instance, an
// * exponential growth.
// *
// * @param nextLength computes the length of the next array from the length of the latest one
// */
// def setLengthPolicy(nextLength: Int => Int): Unit = { myLengthPolicy = nextLength }
private[collection] def calcNextLength(sz: Int) = sz // myLengthPolicy(sz)
def classTagCompanion = UnrolledBuffer
/** Concatenates the target unrolled buffer to this unrolled buffer.
*
* The specified buffer `that` is cleared after this operation. This is
* an O(1) operation.
*
* @param that the unrolled buffer whose elements are added to this buffer
*/
def concat(that: UnrolledBuffer[T]) = {
// bind the two together
if (!lastptr.bind(that.headptr)) lastptr = that.lastPtr
// update size
sz += that.sz
// `that` is no longer usable, so clear it
// here we rely on the fact that `clear` allocates
// new nodes instead of modifying the previous ones
that.clear()
// return a reference to this
this
}
def +=(elem: T) = {
lastptr = lastptr.append(elem)
sz += 1
this
}
def clear() {
headptr = newUnrolled
lastptr = headptr
sz = 0
}
def iterator: Iterator[T] = new AbstractIterator[T] {
var pos: Int = -1
var node: Unrolled[T] = headptr
scan()
private def scan() {
pos += 1
while (pos >= node.size) {
pos = 0
node = node.next
if (node eq null) return
}
}
def hasNext = node ne null
def next = if (hasNext) {
val r = node.array(pos)
scan()
r
} else Iterator.empty.next()
}
// this should be faster than the iterator
override def foreach[U](f: T => U) = headptr.foreach(f)
def result = this
def length = sz
def apply(idx: Int) =
if (idx >= 0 && idx < sz) headptr(idx)
else throw new IndexOutOfBoundsException(idx.toString)
def update(idx: Int, newelem: T) =
if (idx >= 0 && idx < sz) headptr(idx) = newelem
else throw new IndexOutOfBoundsException(idx.toString)
def remove(idx: Int) =
if (idx >= 0 && idx < sz) {
sz -= 1
headptr.remove(idx, this)
} else throw new IndexOutOfBoundsException(idx.toString)
def +=:(elem: T) = {
headptr = headptr prepend elem
sz += 1
this
}
def insertAll(idx: Int, elems: scala.collection.Traversable[T]) =
if (idx >= 0 && idx <= sz) {
headptr.insertAll(idx, elems, this)
sz += elems.size
} else throw new IndexOutOfBoundsException(idx.toString)
private def writeObject(out: java.io.ObjectOutputStream) {
out.defaultWriteObject
out writeInt sz
for (elem <- this) out writeObject elem
}
private def readObject(in: java.io.ObjectInputStream) {
in.defaultReadObject
val num = in.readInt
headPtr = newUnrolled
lastPtr = headPtr
sz = 0
var i = 0
while (i < num) {
this += in.readObject.asInstanceOf[T]
i += 1
}
}
override def clone(): UnrolledBuffer[T] = new UnrolledBuffer[T] ++= this
override def stringPrefix = "UnrolledBuffer"
}
object UnrolledBuffer extends ClassTagTraversableFactory[UnrolledBuffer] {
/** $genericCanBuildFromInfo */
implicit def canBuildFrom[T](implicit t: ClassTag[T]): CanBuildFrom[Coll, T, UnrolledBuffer[T]] =
new GenericCanBuildFrom[T]
def newBuilder[T](implicit t: ClassTag[T]): Builder[T, UnrolledBuffer[T]] = new UnrolledBuffer[T]
val waterline = 50
val waterlineDelim = 100 // TODO -- fix this name! It's a denominator, not a delimiter. (But it's part of the API so we can't just change it.)
private[collection] val unrolledlength = 32
/** Unrolled buffer node.
*/
class Unrolled[T: ClassTag] private[collection] (var size: Int, var array: Array[T], var next: Unrolled[T], val buff: UnrolledBuffer[T] = null) {
private[collection] def this() = this(0, new Array[T](unrolledlength), null, null)
private[collection] def this(b: UnrolledBuffer[T]) = this(0, new Array[T](unrolledlength), null, b)
private def nextlength = if (buff eq null) unrolledlength else buff.calcNextLength(array.length)
// adds and returns itself or the new unrolled if full
@tailrec final def append(elem: T): Unrolled[T] = if (size < array.length) {
array(size) = elem
size += 1
this
} else {
next = new Unrolled[T](0, new Array[T](nextlength), null, buff)
next append elem
}
def foreach[U](f: T => U) {
var unrolled = this
var i = 0
while (unrolled ne null) {
val chunkarr = unrolled.array
val chunksz = unrolled.size
while (i < chunksz) {
val elem = chunkarr(i)
f(elem)
i += 1
}
i = 0
unrolled = unrolled.next
}
}
@tailrec final def apply(idx: Int): T =
if (idx < size) array(idx) else next.apply(idx - size)
@tailrec final def update(idx: Int, newelem: T): Unit =
if (idx < size) array(idx) = newelem else next.update(idx - size, newelem)
@tailrec final def locate(idx: Int): Unrolled[T] =
if (idx < size) this else next.locate(idx - size)
def prepend(elem: T) = if (size < array.length) {
// shift the elements of the array right
// then insert the element
shiftright()
array(0) = elem
size += 1
this
} else {
// allocate a new node and store element
// then make it point to this
val newhead = new Unrolled[T](buff)
newhead append elem
newhead.next = this
newhead
}
// shifts right assuming enough space
private def shiftright() {
var i = size - 1
while (i >= 0) {
array(i + 1) = array(i)
i -= 1
}
}
// returns pointer to new last if changed
@tailrec final def remove(idx: Int, buffer: UnrolledBuffer[T]): T =
if (idx < size) {
// remove the element
// then try to merge with the next bucket
val r = array(idx)
shiftleft(idx)
size -= 1
if (tryMergeWithNext()) buffer.lastPtr = this
r
} else next.remove(idx - size, buffer)
// shifts left elements after `leftb` (overwrites `leftb`)
private def shiftleft(leftb: Int) {
var i = leftb
while (i < (size - 1)) {
array(i) = array(i + 1)
i += 1
}
nullout(i, i + 1)
}
protected def tryMergeWithNext() = if (next != null && (size + next.size) < (array.length * waterline / waterlineDelim)) {
// copy the next array, then discard the next node
Array.copy(next.array, 0, array, size, next.size)
size = size + next.size
next = next.next
if (next eq null) true else false // checks if last node was thrown out
} else false
@tailrec final def insertAll(idx: Int, t: scala.collection.Traversable[T], buffer: UnrolledBuffer[T]): Unit = {
if (idx < size) {
// divide this node at the appropriate position and insert all into head
// update new next
val newnextnode = new Unrolled[T](0, new Array(array.length), null, buff)
Array.copy(array, idx, newnextnode.array, 0, size - idx)
newnextnode.size = size - idx
newnextnode.next = next
// update this
nullout(idx, size)
size = idx
next = null
// insert everything from iterable to this
var curr = this
for (elem <- t) curr = curr append elem
curr.next = newnextnode
// try to merge the last node of this with the newnextnode and fix tail pointer if needed
if (curr.tryMergeWithNext()) buffer.lastPtr = curr
else if (newnextnode.next eq null) buffer.lastPtr = newnextnode
}
else if (idx == size || (next eq null)) {
var curr = this
for (elem <- t) curr = curr append elem
}
else next.insertAll(idx - size, t, buffer)
}
private def nullout(from: Int, until: Int) {
var idx = from
while (idx < until) {
array(idx) = null.asInstanceOf[T] // TODO find a way to assign a default here!!
idx += 1
}
}
// assumes this is the last node
// `thathead` and `thatlast` are head and last node
// of the other unrolled list, respectively
def bind(thathead: Unrolled[T]) = {
assert(next eq null)
next = thathead
tryMergeWithNext()
}
override def toString = array.take(size).mkString("Unrolled@%08x".format(System.identityHashCode(this)) + "[" + size + "/" + array.length + "](", ", ", ")") + " -> " + (if (next ne null) next.toString else "")
}
}
// This is used by scala.collection.parallel.mutable.UnrolledParArrayCombiner:
// Todo -- revisit whether inheritance is the best way to achieve this functionality
private[collection] class DoublingUnrolledBuffer[T](implicit t: ClassTag[T]) extends UnrolledBuffer[T]()(t) {
override def calcNextLength(sz: Int) = if (sz < 10000) sz * 2 else sz
protected override def newUnrolled = new UnrolledBuffer.Unrolled[T](0, new Array[T](4), null, this)
}
|