Skip to content
Newer
Older
100644 148 lines (137 sloc) 5.97 KB
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
1 /* __ *\
2 ** ________ ___ / / ___ Scala API **
3 ** / __/ __// _ | / / / _ | (c) 2005-2007, LAMP/EPFL **
4 ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
5 ** /____/\___/_/ |_/____/_/ | | **
6 ** |/ **
7 \* */
8
e30503f updated svn:keywords and scaladoc comments
michelou authored Feb 27, 2007
9 // $Id$
a961d3d @odersky 1.
odersky authored Jan 3, 2007
10 package scala.collection.immutable
11
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
12 @serializable
a961d3d @odersky 1.
odersky authored Jan 3, 2007
13 abstract class RedBlack[A] {
14
540c308 removed primitive type aliases from the standar...
michelou authored Jun 8, 2007
15 def isSmaller(x: A, y: A): Boolean
a961d3d @odersky 1.
odersky authored Jan 3, 2007
16
17 private def blacken[B](t: Tree[B]): Tree[B] = t match {
18 case RedTree(k, v, l, r) => BlackTree(k, v, l, r)
19 case t => t
20 }
540c308 removed primitive type aliases from the standar...
michelou authored Jun 8, 2007
21 private def mkTree[B](isBlack: Boolean, k: A, v: B, l: Tree[B], r: Tree[B]) =
a961d3d @odersky 1.
odersky authored Jan 3, 2007
22 if (isBlack) BlackTree(k, v, l, r) else RedTree(k, v, l, r)
23
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
24 @serializable
a961d3d @odersky 1.
odersky authored Jan 3, 2007
25 abstract class Tree[+B] {
540c308 removed primitive type aliases from the standar...
michelou authored Jun 8, 2007
26 def isEmpty: Boolean
27 def isBlack: Boolean
a961d3d @odersky 1.
odersky authored Jan 3, 2007
28 def lookup(x: A): Tree[B]
29 def update[B1 >: B](k: A, v: B1): Tree[B1] = blacken(upd(k, v))
30 def delete(k: A): Tree[B] = del(k)
853b942
Sean McDirmid authored Feb 26, 2007
31
32 def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T];
0168115
Sean McDirmid authored Feb 27, 2007
33 def elements : ImmutableIterator[Pair[A,B]];
853b942
Sean McDirmid authored Feb 26, 2007
34 def elementsSlow: Iterator[Pair[A, B]];
a961d3d @odersky 1.
odersky authored Jan 3, 2007
35 def upd[B1 >: B](k: A, v: B1): Tree[B1]
36 def del(k: A): Tree[B]
37 def smallest: NonEmpty[B]
853b942
Sean McDirmid authored Feb 26, 2007
38 def range(from : Option[A], until : Option[A]) : Tree[B]
39 def first : A
40 def last : A
41 def count : Int
a961d3d @odersky 1.
odersky authored Jan 3, 2007
42 }
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
43 @serializable
a961d3d @odersky 1.
odersky authored Jan 3, 2007
44 abstract class NonEmpty[+B] extends Tree[B] {
45 def isEmpty = false
46 def key: A
47 def value: B
48 def left: Tree[B]
49 def right: Tree[B]
50 def lookup(k: A): Tree[B] =
51 if (isSmaller(k, key)) left.lookup(k)
52 else if (isSmaller(key, k)) right.lookup(k)
53 else this
54 def upd[B1 >: B](k: A, v: B1): Tree[B1] = {
540c308 removed primitive type aliases from the standar...
michelou authored Jun 8, 2007
55 def balanceLeft(isBlack: Boolean, z: A, zv: B, l: Tree[B1], d: Tree[B1]) = l match {
d932455 @dragos Reverted Lex's changes until we fix the type ch...
dragos authored Jan 19, 2007
56 case RedTree(y, yv, RedTree(x, xv, a, b), c) =>
57 RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
58 case RedTree(x, xv, a, RedTree(y, yv, b, c)) =>
59 RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
60 case _ =>
61 mkTree(isBlack, z, zv, l, d)
62 }
540c308 removed primitive type aliases from the standar...
michelou authored Jun 8, 2007
63 def balanceRight(isBlack: Boolean, x: A, xv: B, a: Tree[B1], r: Tree[B1]) = r match {
d932455 @dragos Reverted Lex's changes until we fix the type ch...
dragos authored Jan 19, 2007
64 case RedTree(z, zv, RedTree(y, yv, b, c), d) =>
65 RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
66 case RedTree(y, yv, b, RedTree(z, zv, c, d)) =>
67 RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
68 case _ =>
69 mkTree(isBlack, x, xv, a, r)
70 }
a961d3d @odersky 1.
odersky authored Jan 3, 2007
71 if (isSmaller(k, key)) balanceLeft(isBlack, key, value, left.upd(k, v), right)
72 else if (isSmaller(key, k)) balanceRight(isBlack, key, value, left, right.upd(k, v))
73 else mkTree(isBlack, k, v, left, right)
74 }
75 def del(k: A): Tree[B] = {
76 if (isSmaller(k, key)) mkTree(isBlack, key, value, left.del(k), right)
77 else if (isSmaller(key, k)) mkTree(isBlack, key, value, left, right.del(k))
78 else if (left.isEmpty) right
79 else if (right.isEmpty) left
80 else {
81 val s = right.smallest
82 mkTree(isBlack, s.key, s.value, left, right.del(s.key))
83 }
84 }
85 def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
0168115
Sean McDirmid authored Feb 27, 2007
86 def elements : ImmutableIterator[Pair[A,B]] =
853b942
Sean McDirmid authored Feb 26, 2007
87 left.elements.append(Pair(key,value), () => right.elements)
88
89 def elementsSlow: Iterator[Pair[A, B]] =
90 left.elementsSlow append Iterator.single(Pair(key, value)) append right.elementsSlow
91
92 def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T] = {
93 val left = this.left.visit(input)(f)
94 if (!left._1) return left
95 val middle = f(left._2, key, value)
96 if (!middle._1) return middle
97 return this.right.visit(middle._2)(f)
98 }
99 override def range(from : Option[A], until : Option[A]) : Tree[B] = {
100 if (from == None && until == None) return this
101 if (from != None && isSmaller(key, from.get)) return right.range(from, until);
102 if (until != None && (isSmaller(until.get,key) || !isSmaller(key,until.get)))
103 return left.range(from, until);
104 val newLeft = left.range(from, None)
105 val newRight = right.range(None, until)
106 if ((newLeft eq left) && (newRight eq right)) this
107 else if (newLeft eq Empty) newRight.upd(key, value);
108 else if (newRight eq Empty) newLeft.upd(key, value);
109 else mkTree(isBlack, key, value, newLeft, newRight)
110 }
111 def first = if (left .isEmpty) key else left.first
112 def last = if (right.isEmpty) key else right.last
113 def count = 1 + left.count + right.count
a961d3d @odersky 1.
odersky authored Jan 3, 2007
114 }
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
115 @serializable
a961d3d @odersky 1.
odersky authored Jan 3, 2007
116 case object Empty extends Tree[Nothing] {
117 def isEmpty = true
118 def isBlack = true
119 def lookup(k: A): Tree[Nothing] = this
120 def upd[B](k: A, v: B): Tree[B] = RedTree(k, v, Empty, Empty)
121 def del(k: A): Tree[Nothing] = this
122 def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
853b942
Sean McDirmid authored Feb 26, 2007
123 def elementsSlow: Iterator[Pair[A, Nothing]] = Iterator.empty
0168115
Sean McDirmid authored Feb 27, 2007
124 def elements : ImmutableIterator[Pair[A,Nothing]] = ImmutableIterator.empty
853b942
Sean McDirmid authored Feb 26, 2007
125 def visit[T](input : T)(f : (T,A,Nothing) => Tuple2[Boolean,T]) = Tuple2(true,input)
126
127 def range(from : Option[A], until : Option[A]) = this
128 def first = throw new NoSuchElementException("empty map")
129 def last = throw new NoSuchElementException("empty map")
130 def count = 0
a961d3d @odersky 1.
odersky authored Jan 3, 2007
131 }
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
132 @serializable
a961d3d @odersky 1.
odersky authored Jan 3, 2007
133 case class RedTree[+B](override val key: A,
134 override val value: B,
135 override val left: Tree[B],
136 override val right: Tree[B]) extends NonEmpty[B] {
137 def isBlack = false
138 }
4362112 updated annotations in Scala library
michelou authored Feb 20, 2007
139 @serializable
a961d3d @odersky 1.
odersky authored Jan 3, 2007
140 case class BlackTree[+B](override val key: A,
141 override val value: B,
142 override val left: Tree[B],
143 override val right: Tree[B]) extends NonEmpty[B] {
144 def isBlack = true
145 }
146 }
147
Something went wrong with that request. Please try again.