path: root/docs/examples/maps.scala

package examples;

object maps {

  import scala.collection.immutable._;

  trait MapStruct[kt, vt] {
    trait Map with Function1[kt, vt] {
      def extend(key: kt, value: vt): Map;
      def remove(key: kt): Map;
      def domain: Stream[kt];
      def range: Stream[vt];
    }
    type map <: Map;
    val empty: map;
  }

  class AlgBinTree[kt <: Ordered[kt], vt <: AnyRef]() extends MapStruct[kt, vt] {
    type map = AlgMap;

    val empty: AlgMap = Empty();

    private case class
      Empty(),
      Node(key: kt, value: vt, l: map, r: map) extends AlgMap {}

    trait AlgMap extends Map {
      def apply(key: kt): vt = this match {
        case Empty() => null
        case Node(k, v, l, r) =>
          if (key < k) l.apply(key)
          else if (key > k) r.apply(key)
          else v
      }

      def extend(key: kt, value: vt): map = this match {
        case Empty()=> Node(key, value, empty, empty)
        case Node(k, v, l, r) =>
          if (key < k) Node(k, v, l.extend(key, value), r)
          else if (key > k) Node(k, v, l, r.extend(key, value))
          else Node(k, value, l, r)
      }

      def remove(key: kt): map = this match {
        case Empty()=> empty
        case Node(k, v, l, r) =>
          if (key < k) Node(k, v, l.remove(key), r)
          else if (key > k) Node(k, v, l, r.remove(key))
          else if (l == empty) r
          else if (r == empty) l
          else {
          val midKey = r.domain.head;
          Node(midKey, r.apply(midKey), l, r.remove(midKey))
        }
      }

      def domain: Stream[kt] = this match {
        case Empty()=> Stream.empty
        case Node(k, v, l, r) => l.domain append Stream.cons(k, r.domain)
      }

      def range: Stream[vt] = this match {
        case Empty()=> Stream.empty
        case Node(k, v, l, r) => l.range append Stream.cons(v, r.range)
      }
    }
  }

  class OOBinTree[kt <: Ordered[kt], vt <: AnyRef]() extends MapStruct[kt, vt] {
    type map = OOMap;

    trait OOMap extends Map {
      def apply(key: kt): vt;
      def extend(key: kt, value: vt): map;
      def remove(key: kt): map;
      def domain: Stream[kt];
      def range: Stream[vt];
    }
    val empty: OOMap = new OOMap {
      def apply(key: kt): vt = null;
      def extend(key: kt, value: vt) = new Node(key, value, empty, empty);
      def remove(key: kt) = empty;
      def domain: Stream[kt] = Stream.empty;
      def range: Stream[vt] = Stream.empty;
    }
    private class Node(k: kt, v: vt, l: map, r: map) extends OOMap {
      def apply(key: kt): vt =
	if (key < k) l.apply(key)
	else if (key > k) r.apply(key)
	else v;
      def extend(key: kt, value: vt): map =
	if (key < k) new Node(k, v, l.extend(key, value), r)
	else if (key > k) new Node(k, v, l, r.extend(key, value))
	else new Node(k, value, l, r);
      def remove(key: kt): map =
	if (key < k) new Node(k, v, l.remove(key), r)
	else if (key > k) new Node(k, v, l, r.remove(key))
	else if (l == empty) r
	else if (r == empty) l
	else {
	  val midKey = r.domain.head;
	  new Node(midKey, r(midKey), l, r.remove(midKey))
	}
      def domain: Stream[kt] = l.domain append Stream.cons(k, r.domain);
      def range: Stream[vt] = l.range append Stream.cons(v, r.range);
    }
  }

  class MutBinTree[kt <: Ordered[kt], vt <: AnyRef]() extends MapStruct[kt, vt] {
    type map = MutMap;
    class MutMap(key: kt, value: vt) extends Map {
      val k = key;
      var v = value;
      var l, r = empty;

      def apply(key: kt): vt =
        if (this == empty) null
        else if (key < k) l.apply(key)
        else if (key > k) r.apply(key)
        else v;

      def extend(key: kt, value: vt): map =
        if (this == empty) new MutMap(key, value)
        else {
          if (key < k) l = l.extend(key, value)
          else if (key > k) r = r.extend(key, value)
          else v = value;
          this
        }

      def remove(key: kt): map =
        if (this == empty) this
        else if (key < k) { l = l.remove(key) ; this }
        else if (key > k) { r = r.remove(key) ; this }
        else if (l == empty) r
        else if (r == empty) l
        else {
          var mid = r;
          while (!(mid.l == empty)) { mid = mid.l }
          mid.r = r.remove(mid.k);
          mid.l = l;
          mid
        }

      def domain: Stream[kt] =
        if (this == empty) Stream.empty;
        else l.domain append Stream.cons(k, r.domain);

      def range: Stream[vt] =
        if (this == empty) Stream.empty;
        else l.range append Stream.cons(v, r.range);
    }
    val empty = new MutMap(null, null);
  }

  class Date(y: Int, m: Int, d: Int) with Ordered[Date] {
    def year = y;
    def month = m;
    def day = d;

    def compareTo[b >: Date <% Ordered[b]](that: b): int = that match {
      case other: Date =>
        if ((year == other.year) &&
            (month == other.month) &&
            (day == other.day))
           0
        else if ((year < other.year) ||
                 (year == other.year && month < other.month) ||
                 (month == other.month && day < other.day))
          -1
        else
          1
      case _ =>
        -(that compareTo this)
    }

    override def equals(that: Any): Boolean =
      that.isInstanceOf[Date] && {
         val o = that.asInstanceOf[Date];
         day == o.day && month == o.month && year == o.year
      }
  }

  def main(args: Array[String]) = {
    val t = new OOBinTree[Date, String]();
    ()
  }

}