blob: e3de5031a93d50d1177a4e1daae97e4ece22f76f (
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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id: SingleLinkedList.scala 16893 2009-01-13 13:09:22Z cunei $
package scala.collection.generic
/** 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.
* !!! todo: integrate with LinearSequence, need to drop null then.
* @author Matthias Zenger
* @author Martin Odersky
* @version 2.8
*/
trait LinkedListTemplate[A, This >: Null <: Sequence[A] with LinkedListTemplate[A, This]] extends SequenceTemplate[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 =
if (next eq null) next = that else next.append(that)
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 = thisCollection
while (i < n && (these ne null)) {
these = these.next.asInstanceOf[This] // !!! concrete overrides abstract problem
i += 1
}
these
}
override def apply(n: Int): A = {
val loc = drop(n)
if (loc ne null) loc.elem
else throw new IndexOutOfBoundsException(n.toString)
}
def update(n: Int, x: A) {
val loc = drop(n)
if (loc ne null) loc.elem = x
else throw new IndexOutOfBoundsException(n.toString)
}
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): Unit = {
var these = this
while (these ne null) {
f(these.elem);
these = these.next
}
}
}
|
