src/Tools/jEdit/src/utils/LinearSet.scala
author immler@in.tum.de
Wed, 04 Mar 2009 17:07:47 +0100
changeset 34527 79ad42a9497f
child 34528 3c3a23c1eb8c
permissions -rw-r--r--
added Makarius' LinearSet
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
34527
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     1
/*  Title:      linear_set.scala
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     2
    Author:     Makarius
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     3
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     4
Sets with canonical linear order, or immutable linked-lists.
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     5
*/
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     6
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     7
object LinearSet
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     8
{
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
     9
  def empty[A]: LinearSet[A] = new LinearSet[A]
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    10
  def apply[A](elems: A*): LinearSet[A] =
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    11
    (empty[A] /: elems) ((s, elem) => s + elem)
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    12
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    13
  class Duplicate(s: String) extends Exception(s)
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    14
  class Undefined(s: String) extends Exception(s)
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    15
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    16
  private def make[A](first: Option[A], last: Option[A], b: Map[A, A]): LinearSet[A] =
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    17
    new LinearSet[A] {
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    18
      override val first_elem = first
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    19
      override val last_elem = last
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    20
      override val body = b
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    21
    }
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    22
}
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    23
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    24
class LinearSet[A] extends scala.collection.immutable.Set[A]
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    25
{
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    26
  /* representation */
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    27
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    28
  val first_elem: Option[A] = None
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    29
  val last_elem: Option[A] = None
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    30
  val body: Map[A, A] = Map.empty
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    31
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    32
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    33
  /* basic methods */
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    34
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    35
  override def isEmpty: Boolean = !last_elem.isDefined
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    36
  def size: Int = if (isEmpty) 0 else body.size + 1
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    37
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    38
  def empty[B] = LinearSet.empty[B]
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    39
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    40
  def contains(elem: A): Boolean =
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    41
    !isEmpty && (last_elem.get == elem || body.isDefinedAt(elem))
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    42
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    43
  def +(elem: A): LinearSet[A] =
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    44
    if (contains(elem)) throw new LinearSet.Duplicate(elem.toString)
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    45
    else if (isEmpty) LinearSet.make(Some(elem), Some(elem), Map.empty)
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    46
    else LinearSet.make(first_elem, Some(elem), body + (last_elem.get -> elem))
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    47
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    48
  def -(elem: A): LinearSet[A] =
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    49
    if (!contains(elem)) throw new LinearSet.Undefined(elem.toString)
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    50
    else error("FIXME")
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    51
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    52
  def elements = new Iterator[A] {
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    53
    private var next_elem = first_elem
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    54
    def hasNext = next_elem.isDefined
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    55
    def next = {
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    56
      val elem = next_elem.get
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    57
      next_elem = if (body.isDefinedAt(elem)) Some(body(elem)) else None
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    58
      elem
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    59
    }
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    60
  }
79ad42a9497f added Makarius' LinearSet
immler@in.tum.de
parents:
diff changeset
    61
}