src/Pure/General/linear_set.scala

tuned;

/*  Title:      Pure/General/linear_set.scala
    Author:     Makarius
    Author:     Fabian Immler, TU Munich

Sets with canonical linear order, or immutable linked-lists.
*/

package isabelle

import scala.collection.SetLike
import scala.collection.generic.{ImmutableSetFactory, CanBuildFrom,
  GenericSetTemplate, GenericCompanion}


object Linear_Set extends ImmutableSetFactory[Linear_Set]
{
  private case class Rep[A](
    val start: Option[A], val end: Option[A], val nexts: Map[A, A], prevs: Map[A, A])

  private def empty_rep[A] = Rep[A](None, None, Map(), Map())

  private def make[A](start: Option[A], end: Option[A], nexts: Map[A, A], prevs: Map[A, A])
    : Linear_Set[A] = new Linear_Set[A] { override val rep = Rep(start, end, nexts, prevs) }

  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Linear_Set[A]] = setCanBuildFrom[A]
  override def empty[A] = new Linear_Set[A]

  class Duplicate[A](x: A) extends Exception
  class Undefined[A](x: A) extends Exception
  class Next_Undefined[A](x: Option[A]) extends Exception
}


class Linear_Set[A]
  extends scala.collection.immutable.Set[A]
  with GenericSetTemplate[A, Linear_Set]
  with SetLike[A, Linear_Set[A]]
{
  override def companion: GenericCompanion[Linear_Set] = Linear_Set


  /* representation */

  protected val rep = Linear_Set.empty_rep[A]


  /* relative addressing */

  // FIXME check definedness??
  def next(elem: A): Option[A] = rep.nexts.get(elem)
  def prev(elem: A): Option[A] = rep.prevs.get(elem)

  def get_after(hook: Option[A]): Option[A] =
    hook match {
      case None => rep.start
      case Some(elem) =>
        if (!contains(elem)) throw new Linear_Set.Undefined(elem)
        next(elem)
    }

  def insert_after(hook: Option[A], elem: A): Linear_Set[A] =
    if (contains(elem)) throw new Linear_Set.Duplicate(elem)
    else
      hook match {
        case None =>
          rep.start match {
            case None => Linear_Set.make(Some(elem), Some(elem), Map(), Map())
            case Some(elem1) =>
              Linear_Set.make(Some(elem), rep.end,
                rep.nexts + (elem -> elem1), rep.prevs + (elem1 -> elem))
          }
        case Some(elem1) =>
          if (!contains(elem1)) throw new Linear_Set.Undefined(elem1)
          else
            rep.nexts.get(elem1) match {
              case None =>
                Linear_Set.make(rep.start, Some(elem),
                  rep.nexts + (elem1 -> elem), rep.prevs + (elem -> elem1))
              case Some(elem2) =>
                Linear_Set.make(rep.start, rep.end,
                  rep.nexts + (elem1 -> elem) + (elem -> elem2),
                  rep.prevs + (elem2 -> elem) + (elem -> elem1))
            }
      }

  def delete_after(hook: Option[A]): Linear_Set[A] =
    hook match {
      case None =>
        rep.start match {
          case None => throw new Linear_Set.Next_Undefined[A](None)
          case Some(elem1) =>
            rep.nexts.get(elem1) match {
              case None => empty
              case Some(elem2) =>
                Linear_Set.make(Some(elem2), rep.end, rep.nexts - elem1, rep.prevs - elem2)
            }
        }
      case Some(elem1) =>
        if (!contains(elem1)) throw new Linear_Set.Undefined(elem1)
        else
          rep.nexts.get(elem1) match {
            case None => throw new Linear_Set.Next_Undefined(Some(elem1))
            case Some(elem2) =>
              rep.nexts.get(elem2) match {
                case None =>
                  Linear_Set.make(rep.start, Some(elem1), rep.nexts - elem1, rep.prevs - elem2)
                case Some(elem3) =>
                  Linear_Set.make(rep.start, rep.end,
                    rep.nexts - elem2 + (elem1 -> elem3),
                    rep.prevs - elem2 + (elem3 -> elem1))
              }
          }
    }

  def append_after(hook: Option[A], elems: Seq[A]): Linear_Set[A] =
    ((hook, this) /: elems) {
      case ((last_elem, set), elem) => (Some(elem), set.insert_after(last_elem, elem))
    }._2

  def delete_between(from: Option[A], to: Option[A]): Linear_Set[A] =
  {
    if (isEmpty) this
    else {
      val next =
        if (from == rep.end) None
        else if (from == None) rep.start
        else from.map(rep.nexts(_))
      if (next == to) this
      else delete_after(from).delete_between(from, to)
    }
  }


  /* Set methods */

  override def stringPrefix = "Linear_Set"

  override def isEmpty: Boolean = !rep.start.isDefined
  override def size: Int = if (isEmpty) 0 else rep.nexts.size + 1

  def contains(elem: A): Boolean =
    !isEmpty && (rep.end.get == elem || rep.nexts.isDefinedAt(elem))

  private def make_iterator(start: Option[A], which: Map[A, A]): Iterator[A] = new Iterator[A] {
    private var next_elem = start
    def hasNext(): Boolean = next_elem.isDefined
    def next(): A =
      next_elem match {
        case Some(elem) =>
          next_elem = which.get(elem)
          elem
        case None => Iterator.empty.next()
      }
  }

  override def iterator: Iterator[A] = make_iterator(rep.start, rep.nexts)

  def iterator(elem: A): Iterator[A] =
    if (contains(elem)) make_iterator(Some(elem), rep.nexts)
    else throw new Linear_Set.Undefined(elem)

  def reverse_iterator(elem: A): Iterator[A] =
    if (contains(elem)) make_iterator(Some(elem), rep.prevs)
    else throw new Linear_Set.Undefined(elem)

  def + (elem: A): Linear_Set[A] = insert_after(rep.end, elem)

  def - (elem: A): Linear_Set[A] =
    if (!contains(elem)) throw new Linear_Set.Undefined(elem)
    else delete_after(prev(elem))
}