Sorted collections

In sorted.diesel:

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.

extend module Stdlib;

module SortedCollection;
abstract class sorted_collection[T] isa ordered_collection[T],
                                               - type param is covariant:
                                               sorted_collection[`S >= T];
abstract class sorted_collection_exactly[T]
                                        isa ordered_collection_exactly[T],
                                            sorted_collection[T];
abstract class m_sorted_collection[T]
        isa sorted_collection_exactly[T], extensible_ordered_collection[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.

abstract class simple_binary_tree[T <= ordered[T]]
                                        isa sorted_collection_exactly[T];
object empty_tree[T <= ordered[T]] isa simple_binary_tree[T];
class tree_node[T <= ordered[T]] isa simple_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.

class m_binary_tree[T <= ordered[T]] isa m_sorted_collection[T];
  fun new_sorted_collection[T <= ordered[T]]():m_binary_tree[T];

end module SortedCollection;

In skiplist.diesel:

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. Skip lists suppress duplicates, like sets.

extend module Stdlib;

module SkipList;
class skip_list[T <= comparable[T]] isa m_sorted_collection[T],
                                               removable_collection[T];
  fun new_skip_list[T <= partially_ordered[T]]():skip_list[T];
  fun new_predicate_skip_list[T <= comparable[T]](cmp:&(T,T):bool
                                                         ):skip_list[T];
module SkipListImpl;
abstract class skip_list_node[T];
  fun value(:skip_list_node[`T]):T;
  fun is_nil(:skip_list_node[`T]):bool;
class skip_list_cons[T] isa skip_list_node[T];
  field forward(:skip_list_cons[`T]):array[skip_list_node[T]];
  fun new_skip_list_node[`T](level:int, new_value:T):skip_list_cons[T];
object skip_list_nil[T] isa skip_list_node[T];
object skip_list_nil_value isa ordered[`T];
object rand_sl_level_stream;
  field rs(:rand_sl_level_stream):random_stream;
  fun next(r:rand_sl_level_stream, current_level:int):int;

end module SkipListImpl;

end module SkipList;