In this chapter we deal with datastructures designed to represent sets of objects which have an intrinsic ordering. Such datastructures should support fast (possibly amortised) \(O(\log n)\) addition, deletion and membership test operations and allow efficient iteration through all the objects in the datastructure in the order determined by the given comparison function. Since they represent a set, adding an object equal to one already present has no effect.
We refer to these as ordered set datastructure because the differ from the GAP notion of a set in a number of ways:
They all lie in a common family OrderedSetDSFamily and pay no attention to the families of the objects stored in them.
Equality of these structures is by identity, not equality of the represented set
The ordering of the objects in the set does not have to be default GAP ordering "less than", but is determined by the attribute LessFunction (10.2-13)
Three implementations of ordered set data structures are currently included: skiplists, binary search trees and (as a specialisation of binary search trees) AVL trees. AVL trees seem to be the fastest in general, and memory usage is similar. More details to come
gap> s := OrderedSetDS(IsSkipListRep, {x,y} -> String(x) < String(y)); <skiplist 0 entries> gap> Addset(s, 1); gap> AddSet(s, 2); gap> AddSet(s, 10); gap> AddSet(s, (1,2,3)); gap> RemoveSet(s, (1,2,3)); 1 gap> AsListSorted(s); [ 1, 10, 2 ] gap> b := OrderedSetDS(IsBinarySearchTreeRep, Primes); <bst size 168> gap> 91 in b; false gap> 97 in b; true
Every implementation of an ordered set datastructure must follow the API set out below
‣ IsOrderedSetDS( arg ) | ( filter ) |
Returns: true or false
Category of ordered set.
‣ IsStandardOrderedSetDS( arg ) | ( filter ) |
Returns: true or false
Subcategory of ordered sets where the ordering is GAP's default <
‣ OrderedSetDS( filter[, lessThan[, initialEntries[, randomSource]]] ) | ( constructor ) |
Returns: an ordered set datastructure
The family that contains all ordered set datastructures. Constructors for ordered sets
The argument filter is a filter that the resulting ordered set object will have.
The optional argument lessThan must be a binary function that returns true if its first argument is less than its second argument, and false otherwise. The default lessThan is GAP's built in <.
The optional argument initialEntries gives a collection of elements that the ordered set is initialised with, and defaults to the empty set.
The optional argument randomSource is useful in a number of possible implementations that use randomised methods to achieve good amortised complexity with high probability and simple data structures. It defaults to the global Mersenne twister.
‣ OrderedSetDS( arg1, arg2, arg3 ) | ( constructor ) |
‣ OrderedSetDS( arg1, arg2, arg3 ) | ( constructor ) |
‣ OrderedSetDS( arg1, arg2, arg3 ) | ( constructor ) |
‣ OrderedSetDS( arg1, arg2 ) | ( constructor ) |
‣ OrderedSetDS( arg1, arg2 ) | ( constructor ) |
‣ OrderedSetDS( arg ) | ( constructor ) |
‣ AddSet( set, object ) | ( operation ) |
Other constructors cover making an ordered set from another ordered set, from an iterator, from a function and an iterator, or from a function, an iterator and a random source.
Adds object to set. Does nothing if objectinsetset.
‣ RemoveSet( set, object ) | ( operation ) |
Returns: 0 or 1
Removes object from set if present, and returns the number of copies of object that were in set, that is 0 or 1. This for consistency with multisets.
10.2-12 \in‣ \in( object, set ) | ( operation ) |
All objects in IsOrderedSetDS must implement \in, which returns true if object is present in set and false otherwise.
‣ LessFunction( set ) | ( attribute ) |
The binary function to perform the comparison for elements of the set.
‣ Size( set ) | ( attribute ) |
The number of objects in the set
‣ IteratorSorted( set ) | ( operation ) |
Returns: iterator
Returns an iterator of set that can be used to iterate through the elements of set in the order imposed by LessFunction (10.2-13).
Default methods based on IteratorSorted (Reference: IteratorSorted) are installed for the following operations and attributes, but can be overridden for data structures that support better algorithms.
‣ Iterator( arg ) | ( operation ) |
‣ AsSSortedList( arg ) | ( attribute ) |
‣ AsSortedList( arg ) | ( attribute ) |
‣ AsList( arg ) | ( attribute ) |
‣ EnumeratorSorted( arg ) | ( attribute ) |
‣ Enumerator( arg ) | ( attribute ) |
‣ IsEmpty( arg ) | ( property ) |
Returns: true or false
‣ Length( arg ) | ( attribute ) |
‣ Position( arg1, arg2, arg3 ) | ( operation ) |
‣ PositionSortedOp( arg1, arg2 ) | ( operation ) |
‣ PositionSortedOp( arg1, arg2, arg3 ) | ( operation ) |
generated by GAPDoc2HTML