34528
|
1 |
/* Title: LinearSet.scala
|
34527
|
2 |
Author: Makarius
|
|
3 |
|
|
4 |
Sets with canonical linear order, or immutable linked-lists.
|
|
5 |
*/
|
|
6 |
|
|
7 |
object LinearSet
|
|
8 |
{
|
|
9 |
def empty[A]: LinearSet[A] = new LinearSet[A]
|
|
10 |
def apply[A](elems: A*): LinearSet[A] =
|
|
11 |
(empty[A] /: elems) ((s, elem) => s + elem)
|
|
12 |
|
|
13 |
class Duplicate(s: String) extends Exception(s)
|
|
14 |
class Undefined(s: String) extends Exception(s)
|
|
15 |
|
|
16 |
private def make[A](first: Option[A], last: Option[A], b: Map[A, A]): LinearSet[A] =
|
|
17 |
new LinearSet[A] {
|
|
18 |
override val first_elem = first
|
|
19 |
override val last_elem = last
|
|
20 |
override val body = b
|
|
21 |
}
|
|
22 |
}
|
|
23 |
|
|
24 |
class LinearSet[A] extends scala.collection.immutable.Set[A]
|
|
25 |
{
|
|
26 |
/* representation */
|
|
27 |
|
|
28 |
val first_elem: Option[A] = None
|
|
29 |
val last_elem: Option[A] = None
|
|
30 |
val body: Map[A, A] = Map.empty
|
|
31 |
|
|
32 |
|
|
33 |
/* basic methods */
|
|
34 |
|
|
35 |
override def isEmpty: Boolean = !last_elem.isDefined
|
|
36 |
def size: Int = if (isEmpty) 0 else body.size + 1
|
|
37 |
|
|
38 |
def empty[B] = LinearSet.empty[B]
|
|
39 |
|
|
40 |
def contains(elem: A): Boolean =
|
|
41 |
!isEmpty && (last_elem.get == elem || body.isDefinedAt(elem))
|
|
42 |
|
34529
|
43 |
def insert_after(hook: Option[A], elem: A): LinearSet[A] =
|
34527
|
44 |
if (contains(elem)) throw new LinearSet.Duplicate(elem.toString)
|
34529
|
45 |
else hook match {
|
|
46 |
case Some(hook) =>
|
|
47 |
if (!contains(hook)) throw new LinearSet.Undefined(hook.toString)
|
|
48 |
else if (body.isDefinedAt(hook))
|
|
49 |
LinearSet.make(first_elem, last_elem, body - hook + (hook -> elem) + (elem -> body(hook)))
|
|
50 |
else LinearSet.make(first_elem, Some(elem), body + (hook -> elem))
|
|
51 |
case None =>
|
|
52 |
if (isEmpty) LinearSet.make(Some(elem), Some(elem), Map.empty)
|
|
53 |
else LinearSet.make(Some(elem), last_elem, body + (elem -> first_elem.get))
|
|
54 |
}
|
|
55 |
|
|
56 |
def +(elem: A): LinearSet[A] = insert_after(last_elem, elem)
|
34527
|
57 |
|
34530
|
58 |
def delete_after(elem: Option[A]): LinearSet[A] =
|
|
59 |
elem match {
|
|
60 |
case Some(elem) =>
|
|
61 |
if (!contains(elem)) throw new LinearSet.Undefined(elem.toString)
|
|
62 |
else if (!body.isDefinedAt(elem)) throw new LinearSet.Undefined(null)
|
|
63 |
else if (body(elem) == last_elem.get) LinearSet.make(first_elem, Some(elem), body - elem)
|
|
64 |
else LinearSet.make(first_elem, last_elem, body - elem - body(elem) + (elem -> body(body(elem))))
|
|
65 |
case None =>
|
|
66 |
if (isEmpty) throw new LinearSet.Undefined(null)
|
|
67 |
else if (size == 1) empty
|
|
68 |
else LinearSet.make(Some(body(first_elem.get)), last_elem, body - first_elem.get)
|
|
69 |
}
|
|
70 |
|
34527
|
71 |
def -(elem: A): LinearSet[A] =
|
|
72 |
if (!contains(elem)) throw new LinearSet.Undefined(elem.toString)
|
34530
|
73 |
else delete_after(body find (p => p._2 == elem) map (p => p._1))
|
34527
|
74 |
|
|
75 |
def elements = new Iterator[A] {
|
|
76 |
private var next_elem = first_elem
|
|
77 |
def hasNext = next_elem.isDefined
|
|
78 |
def next = {
|
|
79 |
val elem = next_elem.get
|
|
80 |
next_elem = if (body.isDefinedAt(elem)) Some(body(elem)) else None
|
|
81 |
elem
|
|
82 |
}
|
|
83 |
}
|
|
84 |
} |