MODULE BST;

(* A module for creating and searching binary search trees. *)

IMPORT List;

PRIVATE CONST NoChildren = (NIL, NIL);

PRIVATE PROC tree := FromList2(l, len) IS 
  IF 
    len = 0 -> tree := NIL 
  | len = 1 -> tree := (CAR(l), NoChildren) 
  | VAR mid, suffix, left, right IN 
      mid := len DIV 2; 
      suffix := List.SuffixFrom(l, mid); 
      left := FromList2(List.Prefix(l, mid), mid); 
      right := FromList2(CDR(suffix), len - mid - 1); 
      tree := (CAR(suffix), (left, right)) 
    END 
  FI 
END;

PROC tree := FromList(l) IS 
  tree := FromList2(l, List.Length(l)) 
END;

(* Return a balanced binary search tree containing the 
   elements of the list "l". "l" should be a list of "(key, 
   value)" pairs such that the successive "key" values are 
   non-decreasing according to some total order. *)

PROC elt := Find(k, tree, order) IS 
  VAR root, cmp IN 
    elt := NIL; 
    DO 
      tree # NIL -> 
        root := CAR(tree); 
        cmp := APPLY(order, k, CAR(root)); 
        IF 
          cmp < 0 -> tree := CAR(CDR(tree)) 
        | cmp > 0 -> tree := CDR(CDR(tree)) 
        | elt := root; tree := NIL 
        FI 
    OD 
  END 
END;

(* If there is a pair "(key, value)" in "tree" such that 
   "APPLY(order, k, key) = 0", return it. Otherwise, return 
   "NIL". 

   The closure "order" should define a total order "<" on "K 
   x Key", where "K" is the domain of key values passed as 
   the first argument to the "Find" procedure, and "Key" is 
   the domain of the keys in the "tree". The call 
   "APPLY(order, k, key)" should return a value less than, 
   equal to, or greater than 0 as "k" is less than, equal to, 
   or greater than "key" according to "<". *)

PRIVATE PROC res := NumOrder(k, key) IS res := k - key END;

PROC elt := FindNum(k, tree) IS 
  elt := Find(k, tree, NumOrder) 
END;

(* Call "Find" above for the order in which both "k" and the 
   keys in the "tree" are numbers. *)

PRIVATE PROC res := IntervalOrder(k, int) IS 
  IF 
    k < CAR(int) -> res := -1 | k > CAR(CDR(int)) -> res := 1 
  | res := 0 
  FI 
END;

PROC elt := FindInterval(k, tree) IS 
  elt := Find(k, tree, IntervalOrder) 
END;

(* Call "Find" above for the order in which "k" is a number 
   and the keys in the "tree" are intervals of the form 
   "[start, end, ...]", where "start" and "end" are numbers, 
   and the ellipses denote an arbitrary number of additional 
   elements (possibly zero). *)