blob: 4f1a878e022f459d8547fe1ec2adcb15249548ce (
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2010, 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 `A` refers to the element type of the
* list, type variable `This` is used to model self types of
* linked lists.
*
* @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
*/
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
override def length: Int = if (isEmpty) 0 else next.length + 1
override def head: A = elem
override def tail: This = {
require(nonEmpty, "tail of empty list")
next
}
/** Append linked list `that` at current position of this linked list
* @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.asInstanceOf[This] // !!! concrete overrides abstract problem
i += 1
}
these
}
private def atLocation[T](n: Int)(f: This => T) = {
val loc = drop(n)
if (!loc.isEmpty) 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 Iterator[A] {
var elems = self
def hasNext = elems.nonEmpty
def next = {
val res = elems.elem
elems = elems.next
res
}
}
override def foreach[B](f: A => B) {
var these = this
while (these.nonEmpty) {
f(these.elem)
these = these.next
}
}
}
|
