-- Copyright 1993-1998, by the Cecil Project
-- Department of Computer Science and Engineering, University of Washington
-- See the LICENSE file for license information.

(--DOC
  A sorted collection is an ordered collection of totally-ordered values but
  not a sequence; the order of the elements is determined internally by the
  elements themselves (and their `<' method), not externally by the client.

  Sorted collections inherit `length', `is_empty', `do', `pick_any',
  `includes', `find', `copy', `reverse_do', `flatten', etc.,
  from ordered collections.

  In addition, mutable sorted collections support the behavior of extensible
  ordered collections, such as `add', `remove_first', and
  `remove_last' (but not `add_{first,last}').

  Two concrete implementations of sorted collections exist, one based on
  binary trees and another based on skip-lists.
--)


abstract object sorted_collection[T] isa ordered_collection[T];
extend type sorted_collection[`T] subtypes sorted_collection[`S >= T];

method view_stream(c@:sorted_collection[`T]):stream[T] {
    let a:array[T] := new_array[T]();
    c.do(&(x:T){ a.add(x); });
    view_stream(a) }


-- mutable sorted collections

abstract object m_sorted_collection[T] isa sorted_collection[T],
	                                   extensible_ordered[T];


--DOC Simple binary trees are an implementation of sorted collections
--DOC based on binary trees. They are akin to simple lists in that they
--DOC support an add operation, but not in place, and so they do not
--DOC support the full protocol of `m_sorted_collections'. Like `m_lists',
--DOC therefore, `m_binary_trees' are defined as convenient wrappers around
--DOC `simple_binary_trees'.

abstract object simple_binary_tree[T <= ordered[T]] isa sorted_collection[T];
signature add(simple_binary_tree[`T], x:T):simple_binary_tree[T];
method collection_name(@:simple_binary_tree[`T]):string { "simple_bin_tree" }
signature copy(simple_binary_tree[`T]):simple_binary_tree[T];

concrete representation empty_tree[T <= ordered[T]] isa simple_binary_tree[T];
method length(t@:empty_tree[`T]):int { 0 }
method do(t@:empty_tree[`T], c:&(T):void):void {}
method reverse_do(t@:empty_tree[`T], c:&(T):void):void {}
method add(t@:empty_tree[`T], x:T):simple_binary_tree[T] {
    concrete object isa tree_node[T] { data := x } }
method copy(t@:empty_tree[`T]):simple_binary_tree[T] { t }

template representation tree_node[T <= ordered[T]] isa simple_binary_tree[T];
private var field left(t@:tree_node[`T]):simple_binary_tree[T] := empty_tree[T];
private var field right(t@:tree_node[`T]):simple_binary_tree[T] := empty_tree[T];
private field data(t@:tree_node[`T]):T;
method length(t@:tree_node[`T]):int { t.left.length + t.right.length + 1 }
method is_empty(t@:tree_node[`T]):bool { false }
method do(t@:tree_node[`T], c:&(T):void):void {
	do(t.left, c);
	eval(c, t.data);
	do(t.right, c);
}
method reverse_do(t@:tree_node[`T], c:&(T):void):void {
	reverse_do(t.right, c);
	eval(c, t.data);
	reverse_do(t.left, c);
}
method add(t@:tree_node[`T], x:T):simple_binary_tree[T] {
    if( x < t.data,
	{ t.left  := add(t.left,  x); },
	{ t.right := add(t.right, x); } );
    t }
method copy(t@:tree_node[`T]):simple_binary_tree[T] {
    concrete object isa tree_node[T] {
	data := t.data, left := t.left.copy, right := t.right.copy } }


--DOC `m_binary_tree' is a mutable sorted collection implemented as a
--DOC wrapper around `simple_binary_tree'.
--DOC Warning: the current implementation of binary trees does not
--DOC support any of the remove protocol expected of an
--DOC `m_sorted_collection'. This should be implemented sometime. Also,
--DOC these binary trees are not self-balancing, so in the worst case an
--DOC add operation can take O(length) time.

template object m_binary_tree[T <= ordered[T]] isa m_sorted_collection[T];

private var field tree(@:m_binary_tree[`T]):simple_binary_tree[T] :=
    empty_tree[T];

method length(t@:m_binary_tree[`T]):int { t.tree.length }
method is_empty(t@:m_binary_tree[`T]):bool { t.tree.is_empty }
method do(t@:m_binary_tree[`T], c:&(T):void):void { do(t.tree, c); }
method reverse_do(t@:m_binary_tree[`T], c:&(T):void):void {
    reverse_do(t.tree, c); }
method add(t@:m_binary_tree[`T], x:T):void { t.tree := add(t.tree, x); }
method collection_name(@:m_binary_tree[`T]):string { "bin_tree" }

method new_sorted_collection[T <= ordered[T]]():m_binary_tree[T] {
    concrete object isa m_binary_tree[T] }

method copy(t@:m_binary_tree[`T]):m_binary_tree[T] {
    concrete object isa m_binary_tree[T] { tree := t.tree.copy } }