blob: 5e706b5e62ccf8dd28bcf4f12cf9dbffe80a0b6a (
plain) (
blame)
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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection
package mutable
import generic._
import annotation.tailrec
/** This extensible class may be used as a basis for implementing linked
* list. Type variable <code>A</code> refers to the element type of the
* list, type variable <code>This</code> is used to model self types of
* linked lists.
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.8
*/
trait LinkedListLike[A, This >: Null <: Sequence[A] with LinkedListLike[A, This]] extends SequenceLike[A, This] { self =>
var elem: A = _
var next: This = _
override def isEmpty = false
override def length: Int = 1 + (if (next eq null) 0 else next.length)
override def head: A = elem
override def tail: This = next
def append(that: This): Unit = {
@tailrec
def loop(x: This): Unit = {
if (x.next eq null) x.next = that
else loop(x.next)
}
loop(repr)
}
def insert(that: This): Unit = if (that ne null) {
that.append(next)
next = that
}
override def drop(n: Int): This = {
var i = 0
var these: This = repr
while (i < n && (these ne null)) {
these = these.next.asInstanceOf[This] // !!! concrete overrides abstract problem
i += 1
}
these
}
private def atLocation[T](n: Int)(f: This => T) = {
val loc = drop(n)
if (loc ne null) f(loc)
else throw new IndexOutOfBoundsException(n.toString)
}
override def apply(n: Int): A = atLocation(n)(_.elem)
def update(n: Int, x: A): Unit = atLocation(n)(_.elem = x)
def get(n: Int): Option[A] = {
val loc = drop(n)
if (loc ne null) Some(loc.elem)
else None
}
override def iterator: Iterator[A] = new Iterator[A] {
var elems = self
def hasNext = (elems ne null)
def next = {
val res = elems.elem
elems = elems.next
res;
}
}
override def foreach[B](f: A => B) {
var these = this
while (these ne null) {
f(these.elem);
these = these.next
}
}
}
|
