next up previous index
Next: stack, queue Up: Collections Previous: Lists   Index

Sorted collections

In sorted.cecil:

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];
abstract object m_sorted_collection[T] isa sorted_collection[T],
                                           extensible_ordered[T];
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 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 m_sorted_collections. Like m_lists, therefore, m_binary_trees are defined as convenient wrappers around simple_binary_trees.

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];
m_binary_tree is a mutable sorted collection implemented as a wrapper around simple_binary_tree. Warning: the current implementation of binary trees does not support any of the remove protocol expected of an m_sorted_collection. This should be implemented sometime. Also, these binary trees are not self-balancing, so in the worst case an add operation can take O(length) time. In skiplist.cecil:

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];
  method copy_empty(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;
Skip lists are an alternative implementation of mutable sorted collections that perform probabilistically better than balanced trees. Skip lists can be sorted using either the element type's natural ordering or using a user-supplied ordering function.


next up previous index
Next: stack, queue Up: Collections Previous: Lists   Index

Cecil/Vortex Project