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 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;
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;
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];
method copy(t@:empty_tree[`T]):simple_binary_tree[T];
template representation tree_node[T <= ordered[T]] isa simple_binary_tree[T];
method length(t@:tree_node[`T]):int;
method is_empty(t@:tree_node[`T]):bool;
method do(t@:tree_node[`T], c:&(T):void):void;
method reverse_do(t@:tree_node[`T], c:&(T):void):void;
method add(t@:tree_node[`T], x:T):simple_binary_tree[T];
method copy(t@:tree_node[`T]):simple_binary_tree[T];
Simple binary trees are an implementation of sorted collections
based on binary trees. They are akin to simple lists in that they
support an add operation, but not in place, and so they do not
support the full protocol of
template object m_binary_tree[T <= ordered[T]] isa m_sorted_collection[T];
method length(t@:m_binary_tree[`T]):int;
method is_empty(t@:m_binary_tree[`T]):bool;
method do(t@:m_binary_tree[`T], c:&(T):void):void;
method reverse_do(t@:m_binary_tree[`T], c:&(T):void):void;
method add(t@:m_binary_tree[`T], x:T):void;
method collection_name(@:m_binary_tree[`T]):string;
method new_sorted_collection[T <= ordered[T]]():m_binary_tree[T];
method copy(t@:m_binary_tree[`T]):m_binary_tree[T];
template object skip_list[T <= comparable[T]] isa m_sorted_collection[T],
removable_collection[T];
method less_than(t@:skip_list[`T], e1:T, e2:T):bool;
method less_than(t@:skip_list[`T],
e1:T, e2@:skip_list_nil_value):bool;
method less_than(t@:skip_list[`T],
e1@:skip_list_nil_value, e2:T):bool;
method less_than(t@:skip_list[`T],
e1@:skip_list_nil_value,e2@:skip_list_nil_value):bool;
method new_skip_list[T <= partially_ordered[T]]():skip_list[T];
method new_predicate_skip_list[T <= comparable[T]](cmp:&(T,T):bool
):skip_list[T];
method add(l@:skip_list[`T], new_value:T):void;
method includes(l@:skip_list[`T], elem:T):bool;
method do(l@:skip_list[`T], c:&(T):void):void;
method remove(l@:skip_list[`T], value:T, if_absent:&():void):void;
method length(l@:skip_list[`T]):int;
method is_empty(l@:skip_list[`T]):bool;
method first(l@:skip_list[`T]):T;
method last(l@:skip_list[`T]):T;
method remove_first(l@:skip_list[`T], if_empty:&():`S):T|S;
method remove_last(l@:skip_list[`T], if_empty:&():`S):T|S;
method collection_name(@:skip_list[`T]):string;
method copy(l@:skip_list[`T]):skip_list[T];
template object skip_list_node[T];
field value(@:skip_list_node[`T]):T;
field forward(@:skip_list_node[`T]):array[skip_list_node[T]];
method new_skip_list_node[`T](level:int, new_value:T):skip_list_node[T];
method is_nil(sln@:skip_list_node[`T]):bool;
method print_string(sln@:skip_list_node[`T]):string;
method copy(sln@:skip_list_node[`T]):skip_list_node[T];
concrete representation skip_list_nil[T] subtypes skip_list_node[T];
method value(@:skip_list_nil[`T]):T;
method is_nil(@:skip_list_nil[`T]):bool;
method print_string(@:skip_list_nil[`T]):string;
method copy(l@:skip_list_nil[`T]):skip_list_nil[T];
concrete representation skip_list_nil_value isa ordered[`T];
method = (x1@:skip_list_nil_value, x2@:skip_list_nil_value):bool;
method = (x1@:skip_list_nil_value, x2@:comparable[`T]):bool;
method = (x1@:comparable[`T], x2@:skip_list_nil_value):bool;
method < (x1@:skip_list_nil_value, x2@:skip_list_nil_value):bool;
method < (x1@:skip_list_nil_value, x2@:ordered[`T]):bool;
method < (x1@:ordered[`T], x2@:skip_list_nil_value):bool;
concrete representation rand_sl_level_stream;
field rs(@:rand_sl_level_stream):random_stream;
method next(r@:rand_sl_level_stream, current_level:int):int;