path: root/sources/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 <: Ord[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 <: Ord[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 <: Ord[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 Ord[Date] {
    def year = y;
    def month = m;
    def day = d;

    def <(that: Date): Boolean = {
      (year < that.year) ||
      (year == that.year && month < that.month) ||
      (month == that.month && day < that.day)
    }

    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]();
    ()
  }

}