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
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2013, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
package scala
package collection
package mutable
import scala.annotation.tailrec
/** This extensible class may be used as a basis for implementing linked
* list. Type variable `A` refers to the element type of the
* list, type variable `This` is used to model self types of
* linked lists.
*
* $singleLinkedListExample
*
* @author Matthias Zenger
* @author Martin Odersky
* @version 1.0, 08/07/2003
* @since 2.8
*
* @tparam A type of the elements contained in the linked list
* @tparam This the type of the actual linked list holding the elements
*
* @define Coll `LinkedList`
* @define coll linked list
*
* @define singleLinkedListExample
* If the list is empty `next` must be set to `this`. The last node in every
* mutable linked list is empty.
*
* Examples (`_` represents no value):
*
* {{{
*
* Empty:
*
* [ _ ] --,
* [ ] <-`
*
* Single element:
*
* [ x ] --> [ _ ] --,
* [ ] <-`
*
* More elements:
*
* [ x ] --> [ y ] --> [ z ] --> [ _ ] --,
* [ ] <-`
*
* }}}
*/
@deprecated("low-level linked lists are deprecated due to idiosyncrasies in interface and incomplete features", "2.11.0")
trait LinkedListLike[A, This <: Seq[A] with LinkedListLike[A, This]] extends SeqLike[A, This] { self =>
var elem: A = _
var next: This = _
override def isEmpty = next eq this
/** Determines the length of this $coll by traversing and counting every
* node.
*/
override def length: Int = length0(repr, 0)
@tailrec private def length0(elem: This, acc: Int): Int =
if (elem.isEmpty) acc else length0(elem.next, acc + 1)
override def head: A =
if (isEmpty) throw new NoSuchElementException
else elem
override def tail: This = {
require(nonEmpty, "tail of empty list")
next
}
/** If `this` is empty then it does nothing and returns `that`. Otherwise, appends `that` to `this`. The append
* requires a full traversal of `this`.
*
* Examples:
*
* {{{
* scala> val a = LinkedList(1, 2)
* a: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2)
*
* scala> val b = LinkedList(1, 2)
* b: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2)
*
* scala> a.append(b)
* res0: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 1, 2)
*
* scala> println(a)
* LinkedList(1, 2, 1, 2)
* }}}
*
* {{{
* scala> val a = new LinkedList[Int]()
* a: scala.collection.mutable.LinkedList[Int] = LinkedList()
*
* scala> val b = LinkedList(1, 2)
* b: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2)
*
* scala> val c = a.append(b)
* c: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2)
*
* scala> println(a)
* LinkedList()
* }}}
*
* @return the list after append (this is the list itself if nonempty,
* or list `that` if list this is empty. )
*/
def append(that: This): This = {
@tailrec
def loop(x: This) {
if (x.next.isEmpty) x.next = that
else loop(x.next)
}
if (isEmpty) that
else { loop(repr); repr }
}
/** Insert linked list `that` at current position of this linked list
* @note this linked list must not be empty
*/
def insert(that: This): Unit = {
require(nonEmpty, "insert into empty list")
if (that.nonEmpty) {
that append next
next = that
}
}
override def drop(n: Int): This = {
var i = 0
var these: This = repr
while (i < n && !these.isEmpty) {
these = these.next
i += 1
}
these
}
private def atLocation[T](n: Int)(f: This => T) = {
val loc = drop(n)
if (loc.nonEmpty) 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.nonEmpty) Some(loc.elem)
else None
}
override def iterator: Iterator[A] = new AbstractIterator[A] {
var elems = self
def hasNext = elems.nonEmpty
def next = {
val res = elems.elem
elems = elems.next
res
}
}
override def foreach[U](f: A => U) {
var these = this
while (these.nonEmpty) {
f(these.elem)
these = these.next
}
}
/** Return a clone of this list.
*
* @return a `LinkedList` with the same elements.
*/
override def clone(): This = {
val bf = newBuilder
bf ++= this
bf.result()
}
}
|
