Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

10 Ordered Set Datastructures
 10.1 Usage
 10.2 API
 10.3 Default methods

10 Ordered Set Datastructures

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:

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

10.1 Usage

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

10.2 API

Every implementation of an ordered set datastructure must follow the API set out below

10.2-1 IsOrderedSetDS
‣ IsOrderedSetDS( arg )( filter )

Returns: true or false

Category of ordered set.

10.2-2 IsStandardOrderedSetDS
‣ IsStandardOrderedSetDS( arg )( filter )

Returns: true or false

Subcategory of ordered sets where the ordering is GAP's default <

10.2-3 OrderedSetDS
‣ 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.

10.2-4 OrderedSetDS
‣ OrderedSetDS( arg1, arg2, arg3 )( constructor )

10.2-5 OrderedSetDS
‣ OrderedSetDS( arg1, arg2, arg3 )( constructor )

10.2-6 OrderedSetDS
‣ OrderedSetDS( arg1, arg2, arg3 )( constructor )

10.2-7 OrderedSetDS
‣ OrderedSetDS( arg1, arg2 )( constructor )

10.2-8 OrderedSetDS
‣ OrderedSetDS( arg1, arg2 )( constructor )

10.2-9 OrderedSetDS
‣ OrderedSetDS( arg )( constructor )

10.2-10 AddSet
‣ 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.

10.2-11 RemoveSet
‣ 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.

10.2-13 LessFunction
‣ LessFunction( set )( attribute )

The binary function to perform the comparison for elements of the set.

10.2-14 Size
‣ Size( set )( attribute )

The number of objects in the set

10.2-15 IteratorSorted
‣ 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).

10.3 Default methods

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.

10.3-1 Iterator
‣ Iterator( arg )( operation )

10.3-2 AsSSortedList
‣ AsSSortedList( arg )( attribute )

10.3-3 AsSortedList
‣ AsSortedList( arg )( attribute )

10.3-4 AsList
‣ AsList( arg )( attribute )

10.3-5 EnumeratorSorted
‣ EnumeratorSorted( arg )( attribute )

10.3-6 Enumerator
‣ Enumerator( arg )( attribute )

10.3-7 IsEmpty
‣ IsEmpty( arg )( property )

Returns: true or false

10.3-8 Length
‣ Length( arg )( attribute )

10.3-9 Position
‣ Position( arg1, arg2, arg3 )( operation )

10.3-10 PositionSortedOp
‣ PositionSortedOp( arg1, arg2 )( operation )

10.3-11 PositionSortedOp
‣ PositionSortedOp( arg1, arg2, arg3 )( operation )
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 Bib Ind

generated by GAPDoc2HTML