Skip List Containers

This chapter discusses the following skip list containers:

WCPtrSkipListDict<Key,Value>
WCPtrSkipListSet<Type>
WCPtrSkipList<Type>
WCValSkipListDict<Key,Value>
WCValSkipListSet<Type>
WCValSkipList<Type>

WCPtrSkipListDict<Key,Value> Class

Declared:

wcskip.h

The WCPtrSkipListDict<Key,Value> class is a templated class used to store objects in a dictionary. Dictionaries store values with an associated key, which may be of any type. One example of a dictionary used in everyday life is the phone book. The phone numbers are the data values, and the customer's name is the key. The equality operator of the key's type is used to locate the key-value pairs.

In the description of each member function, the text Key is used to indicate the template parameter defining the type of the indices pointed to by the pointers stored in the dictionary. The text Value is used to indicate the template parameter defining the type of the data pointed to by the pointers stored in the dictionary.

Pointers to the key values are stored in the dictionary. Destructors aren't called on the keys pointed to. The key values pointed to in the dictionary shouldn't be changed such that the equivalence to the old value is modified.

The iterator classes for skip lists have the same function and operator interface as the hash iterator classes. See the chapter on Hash Iterators for more information.

The WCExcept class is a base class of the WCPtrSkipListDict<Key,Value> class and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCPtrSkipListDict<Key,Value> object. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCPtrSkipListDict<Key,Value> class requires Key to have:

A well defined equivalence operator with constant parameters
```
    int operator ==( const Key & ) const
    
```
A well defined less-than operator with constant parameters
```
    int operator <( const Key & ) const
    
```

Public Member Functions

The following member functions are declared in the public interface:

WCPtrSkipListDict( unsigned = WCSkipListDict_PROB_QUARTER, 
                   unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCPtrSkipListDict( unsigned = WCSkipListDict_PROB_QUARTER, 
                   unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
                   void * (*user_alloc)( size_t size ),
                   void (*user_dealloc)( void *old, 
                                         size_t size ) );
WCPtrSkipListDict( const WCPtrSkipListDict & );
virtual ~WCPtrSkipListDict();
void clear();
void clearAndDestroy();
int contains( const Key * ) const;
unsigned entries() const;
Value * find( const Key * ) const;
Value * findKeyAndValue( const Key *, Key * & ) const;
void forAll( void (*user_fn)( Key *, Value *, void * ), 
             void * );
int insert( Key *, Value * );
int isEmpty() const;
Value * remove( const Key * );

Public Member Operators

The following member operators are declared in the public interface:

Value * & operator [ ]( const Key * );
Value * const & operator [ ]( const Key * ) const;
WCPtrSkipListDict & operator =( const WCPtrSkipListDict & );
int operator ==( const WCPtrSkipListDict & ) const;

WCPtrSkipListDict<Key,Value>::WCPtrSkipListDict()

create a WCPtrSkipListDict<Key,Value> object

Synopsis:

#include <wcskip.h>
public:
WCPtrSkipListDict( 
    unsigned = WCSKIPLIST_PROB_QUARTER,
    unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCPtrSkipListDict( 
    unsigned = WCSKIPLIST_PROB_QUARTER,
    unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
    void * (*user_alloc)( size_t ),
    void (*user_dealloc)( void *, size_t ) );
WCPtrSkipListDict( const WCPtrSkipListDict & );

Semantics:

There are three forms of the public WCPtrSkipListDict<Key,Value> constructor:

The first creates an WCPtrSkipListDict<Key,Value> object with no entries. The first optional parameter, which defaults to the constant WCSKIPLIST_PROB_QUARTER determines the probability of having a certain number of pointers in each skip list node. The second optional parameter, which defaults to the constant WCDEFAULT_SKIPLIST_MAX_PTRS, determines the maximum number of pointers that are allowed in any skip list node. WCDEFAULT_SKIPLIST_MAX_PTRS is the maximum effective value of the second parameter.
If an allocation failure occurs while creating the skip list, the out_of_memory exception is thrown if it's enabled.
The second form of this constructor also creates an WCPtrSkipListDict<Key,Value> object with no entries. Allocator and deallocator functions are specified for use when entries are inserted and removed from the list dictionary. The semantics of this constructor are the same as the constructor without the memory management functions.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a list dictionary. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
```
    WCPtrSkipListDictItemSize( Key, Value,
                               num_of_pointers )
    
```
The third form of this constructor is the copy constructor for the WCPtrSkipListDict<Key,Value> class. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.
If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The public WCPtrSkipListDict<Key,Value> constructor creates an initialized WCPtrSkipListDict<Key,Value> object.

WCPtrSkipListDict<Key,Value>::~WCPtrSkipListDict()

destroy a WCPtrSkipListDict<Key,Value> object

Synopsis:

#include <wcskip.h>
public:
virtual ~WCPtrSkipListDict();

Semantics:

The public WCPtrSkipListDict<Key,Value> destructor is the destructor for the WCPtrSkipListDict<Key,Value> class.

If the number of dictionary elements isn't zero, and the not_empty exception is enabled, the exception is thrown. Otherwise, the dictionary elements are cleared using the clear() member function.

The objects to which the dictionary elements point aren't deleted unless the clearAndDestroy() member function is explicitly called before the destructor is called.

The call to this destructor is inserted implicitly by the compiler at the point where the WCPtrSkipListDict<Key,Value> object goes out of scope.

Results:

The public WCPtrSkipListDict<Key,Value> destructor destroys an WCPtrSkipListDict<Key,Value> object.

WCPtrSkipListDict<Key,Value>::clear()

clear the dictionary

Synopsis:

#include <wcskip.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the dictionary so that it has no entries. Objects pointed to by the dictionary elements aren't deleted. The dictionary object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

The clear() public member function clears the dictionary to have no elements.

WCPtrSkipListDict<Key,Value>::clearAndDestroy()

clear the dictionary, destroying any elements in it

Synopsis:

#include <wcskip.h>
public:
void clearAndDestroy();

Semantics:

The clearAndDestroy() public member function is used to clear the dictionary and delete the objects pointed to by the dictionary elements. The dictionary object isn't destroyed and re-created by this function, so the dictionary object destructor isn't invoked.

Results:

The clearAndDestroy() public member function clears the dictionary by deleting the objects pointed to by the dictionary elements.

WCPtrSkipListDict<Key,Value>::contains()

determine whether or not a given element is in the dictionary

Synopsis:

#include <wcskip.h>
public:
int contains( const Key & ) const;

Semantics:

The contains() public member function returns non-zero if an element with the specified key is stored in the dictionary, or zero if there is no equivalent element. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The contains() public member function returns a non-zero value if the Key is found in the dictionary.

WCPtrSkipListDict<Key,Value>::entries()

count the elements in the dictionary

Synopsis:

#include <wcskip.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the dictionary.

Results:

This function returns the number of elements in the dictionary.

WCPtrSkipListDict<Key,Value>::find()

find an element in the dictionary

Synopsis:

#include <wcskip.h>
public:
Value * find( const Key * ) const;

Semantics:

The find() public member function is used to find an element with an equivalent key in the dictionary. If an equivalent element is found, a pointer to the element Value is returned. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCPtrSkipListDict<Key,Value>::findKeyAndValue()

find an element in the dictionary

Synopsis:

#include <wcskip.h>
public:
Value * findKeyAndValue( const Key *, 
                         Key * & ) const;

Semantics:

The findKeyAndValue() public member function is used to find an element in the dictionary with an key equivalent to the first parameter. If an equivalent element is found, a pointer to the element Value is returned. The reference to a Key passed as the second parameter is assigned the found element's key. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCPtrSkipListDict<Key,Value>::forAll()

invoke a function for each element in the dictionary

Synopsis:

#include <wcskip.h>
public:
void forAll(
      void (*user_fn)( Key *, Value *, void * ),
      void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every key-value pair in the dictionary. The user function has the prototype

    void user_func( Key * key, Value * value, 
                    void * data );

As the elements are visited, the user function is invoked with the Key and Value components of the element passed as the first two parameters. The second parameter of the forAll() function is passed as the third parameter to the user function. This value can be used to pass any appropriate data from the main program to the user function.

Results:

The elements in the dictionary are all visited, and the user function is invoked for each one.

WCPtrSkipListDict<Key,Value>::insert()

insert a key and value into the dictionary

Synopsis:

#include <wcskip.h>
public:
int insert( Key *, Value * );

Semantics:

The insert() public member function inserts a key and value into the dictionary.

If allocation of the node to store the key-value pair fails, then the out_of_memory exception is thrown if it's enabled. If it isn't enabled, the insertion isn't completed.

Results:

The insert() public member function inserts a key and value into the dictionary. If the insertion is successful, a non-zero value is returned. A zero is returned if the insertion fails.

WCPtrSkipListDict<Key,Value>::isEmpty()

determine whether or not the dictionary is empty

Synopsis:

#include <wcskip.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if the dictionary is empty.

Results:

The isEmpty() public member function returns zero if the dictionary contains at least one entry, non-zero if it's empty.

WCPtrSkipListDict<Key,Value>::operator [ ]()

index into the dictionary to get the entry for a given Key

Synopsis:

#include <wcskip.h>
public:
Value * & operator[ ]( const Key * );
Value * const & operator[ ]( const Key * ) const;

Semantics:

operator [ ]() is the dictionary index operator; there are two forms of it:

The first form returns a reference to the object stored in the dictionary with the given Key.
If no equivalent element is found, then a new key-value pair is created with the specified Key value, and initialized with the default constructor. The returned reference can then be assigned to, so that insertions can be made with the operator.
If an allocation error occurs while inserting a new key-value pair, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.
The second form of the operator [ ]() returns a constant reference to the object stored in the dictionary with the given Key.
If no equivalent element is found, then the index_range exception is thrown if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.

Results:

The first form of the operator [ ]() public member function returns a reference to the element at the given key value. If the key doesn't exist, a reference to a created element is returned. The result of the operator may be assigned to.
The second form returns a constant reference to the element at the given key value.The result of the operator may not be assigned to.

WCPtrSkipListDict<Key,Value>::operator =()

assign one dictionary to another

Synopsis:

#include <wcskip.h>
public:
WCPtrSkipListDict & operator =( 
        const WCPtrSkipListDict & );

Semantics:

The operator =() public member function is the assignment operator for the WCPtrSkipListDict<Key,Value> class. The left hand side dictionary is first cleared using the clear() member function, and then the right hand side dictionary is copied. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.

The element is removed from the dictionary if it's found.

WCPtrSkipListSet<Type> and WCPtrSkipList<Type> Classes

Declared:

wcskip.h

The WCPtrSkipListSet<Type> and WCPtrSkipList<Type> classes are templated classes used to store objects in a skip list. A skip list is a probabilistic alternative to balanced trees, and provides a reasonable performance balance to insertion, search, and deletion. A skip list allows more than one copy of an element that is equivalent, while the skip list set allows only one copy. The equality operator of the element's type is used to locate the value.

In the description of each member function, the text Type is used to indicate the template parameter defining the type of the data pointed to by the pointers stored in the list.

Pointers to the elements are stored in the list. Destructors aren't called on the elements pointed to. The data values pointed to in the list shouldn't be changed such that the equivalence to the old value is modified.

The iterator classes for skip lists have the same function and operator interface as the hash iterators classes. See the chapter on Hash Iterators for more information.

The WCExcept class is a base class of the WCPtrSkipListSet<Type> and WCPtrSkipList<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCPtrSkipListSet<Type> and WCPtrSkipList<Type> objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCPtrSkipListSet<Type> and WCPtrSkipList<Type> classes require Type to have the following:

a well defined equivalence operator

    int operator ==( const Type & ) const

a well defined less-than operator

    int operator <( const Type & ) const

Public Member Functions

The following member functions are declared in the public interface:

WCPtrSkipList( unsigned = WCSKIPLIST_PROB_QUARTER, 
               unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCPtrSkipList( unsigned = WCSKIPLIST_PROB_QUARTER, 
               unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS, 
               void * (*user_alloc)( size_t size ), 
               void (*user_dealloc)( void *old, 
                                     size_t size ) );
WCPtrSkipList( const WCPtrSkipList & );
virtual ~WCPtrSkipList();

WCPtrSkipListSet( unsigned = WCSKIPLIST_PROB_QUARTER, 
                  unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCPtrSkipListSet( unsigned = WCSKIPLIST_PROB_QUARTER, 
                  unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
                  void * (*user_alloc)( size_t size ),
                  void (*user_dealloc)( void *old,
                                        size_t size ) );
WCPtrSkipListSet( const WCPtrSkipListSet & );
virtual ~WCPtrSkipListSet();

void clear();
void clearAndDestroy();
int contains( const Type * ) const;
unsigned entries() const;
Type * find( const Type * ) const;
void forAll( void (*user_fn)( Type *, void * ) , void * );
int insert( Type * );
int isEmpty() const;
Type * remove( const Type * );

The following public member functions are available for the WCPtrSkipList class only:

unsigned occurrencesOf( const Type * ) const;
unsigned removeAll( const Type * );

Public Member Operators

The following member operators are declared in the public interface:

WCPtrSkipList & operator =( const WCPtrSkipList & );
int operator ==( const WCPtrSkipList & ) const;
WCPtrSkipListSet & operator =( const WCPtrSkipListSet & );
int operator ==( const WCPtrSkipListSet & ) const;

WCPtrSkipListSet<Type>::WCPtrSkipListSet()

create a WCPtrSkipListSet<Type> object

Synopsis:

#include <wcskip.h>
public:
WCPtrSkipListSet( 
    unsigned = WCSKIPLIST_PROB_QUARTER,
    unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCPtrSkipListSet( 
    unsigned = WCSKIPLIST_PROB_QUARTER,
    unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
    void * (*user_alloc)( size_t ),
    void (*user_dealloc)( void *, size_t ) );
WCPtrSkipListSet( const WCPtrSkipListSet & );

Semantics:

There are three forms of the WCPtrSkipListSet<Type> constructor:

The first creates a WCPtrSkipListSet object with no entries.
The first optional parameter, which defaults to the constant WCSKIPLIST_PROB_QUARTER, determines the probability of having a certain number of pointers in each skip list node. The second optional parameter, which defaults to the constant WCDEFAULT_SKIPLIST_MAX_PTRS, determines the maximum number of pointers that are allowed in any skip list node. WCDEFAULT_SKIPLIST_MAX_PTRS is the maximum effective value of the second parameter.
If an allocation failure occurs while creating the skip list, the out_of_memory exception is thrown if it's enabled.
The second form also constructor creates a WCPtrSkipListSet object with no entries. Allocator and deallocator functions are specified for use when entries are inserted and removed from the list. The semantics of this constructor are the same as the constructor without the memory management functions.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a skip list. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
```
    WCPtrSkipListSetItemSize( Type, num_of_pointers )
    
```
The third form of the WCPtrSkipListSet<Type> constructor is the copy constructor for the WCPtrSkipListSet class. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.
If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The WCPtrSkipListSet<Type> constructor creates an initialized WCPtrSkipListSet object.

WCPtrSkipListSet<Type>::~WCPtrSkipListSet()

destroy a WCPtrSkipListSet<Type> object

Synopsis:

#include <wcskip.h>
public:
virtual ~WCPtrSkipListSet();

Semantics:

The WCPtrSkipListSet<Type> destructor is the destructor for the WCPtrSkipListSet class.

If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the list elements are cleared using the clear() member function.

The objects to which the list elements point aren't deleted unless the clearAndDestroy() member function is explicitly called before the destructor is called.

The call to this destructor is inserted implicitly by the compiler at the point where the WCPtrSkipListSet object goes out of scope.

Results:

The WCPtrSkipListSet object is destroyed.

WCPtrSkipList<Type>::WCPtrSkipList()

create a WCPtrSkipList<Type> object

Synopsis:

#include <wcskip.h>
public:
WCPtrSkipList( unsigned = WCSKIPLIST_PROB_QUARTER,
          unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCPtrSkipList( unsigned = WCSKIPLIST_PROB_QUARTER,
          unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
          void * (*user_alloc)( size_t ),
          void (*user_dealloc)( void *, size_t ) );
WCPtrSkipList( const WCPtrSkipList & );

Semantics:

There are three forms of the WCPtrSkipList<Type> constructor:

The first creates a WCPtrSkipList object with no entries.
The first optional parameter, which defaults to the constant WCSKIPLIST_PROB_QUARTER, determines the probability of having a certain number of pointers in each skip list node. The second optional parameter, which defaults to the constant WCDEFAULT_SKIPLIST_MAX_PTRS, determines the maximum number of pointers that are allowed in any skip list node. WCDEFAULT_SKIPLIST_MAX_PTRS is the maximum effective value of the second parameter.
If an allocation failure occurs while creating the skip list, the out_of_memory exception is thrown if it's enabled.
The second form also creates a WCPtrSkipList object with no entries. Allocator and deallocator functions are specified for use when entries are inserted and removed from the list. The semantics of this constructor are the same as the constructor without the memory management functions.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a skip list. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
```
    WCPtrSkipListItemSize( Type, num_of_pointers )
    
```
The third form is the copy constructor for the WCPtrSkipList class. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.
If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The WCPtrSkipList<Type> constructor creates an initialized WCPtrSkipList object.

WCPtrSkipList<Type>::~WCPtrSkipList()

destroy a WCPtrSkipList<Type> object

Synopsis:

#include <wcskip.h>
public:
virtual ~WCPtrSkipList();

Semantics:

The WCPtrSkipList<Type> destructor is the destructor for the WCPtrSkipList class.

If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the list elements are cleared using the clear() member function.

The objects to which the list elements point aren't deleted unless the clearAndDestroy() member function is explicitly called before the destructor is called.

The call to this destructor is inserted implicitly by the compiler at the point where the WCPtrSkipList object goes out of scope.

Results:

The WCPtrSkipList object is destroyed.

WCPtrSkipListSet<Type>::clear(), WCPtrSkipList<Type>::clear()

clear the list of all entries

Synopsis:

#include <wcskip.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the list so that it has no entries. Objects pointed to by the list elements aren't deleted. The list object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

The clear() public member function clears the list to have no elements.

WCPtrSkipListSet<Type>::clearAndDestroy(), WCPtrSkipList<Type>::clearAndDestroy()

clear the list, destroying all the entries in it

Synopsis:

#include <wcskip.h>
public:
void clearAndDestroy();

Semantics:

The clearAndDestroy() public member function is used to clear the list and delete the objects pointed to by the list elements. The list object isn't destroyed and re-created by this function, so the list object destructor isn't invoked.

Results:

The clearAndDestroy() public member function clears the list by deleting the objects pointed to by the list elements, and then removing the list elements from the list.

WCPtrSkipListSet<Type>::contains(), WCPtrSkipList<Type>::contains()

determine whether or not a given entry is in the list

Synopsis:

#include <wcskip.h>
public:
int contains( const Type * ) const;

Semantics:

The contains() public member function returns non-zero if the element is stored in the list, or zero if there's no equivalent element. Note that equivalence is based on the equivalence operator of the element type.

Results:

The contains() public member function returns a non-zero value if the element is found in the list.

WCPtrSkipListSet<Type>::entries(), WCPtrSkipList<Type>::entries()

count the entries in the list

Synopsis:

#include <wcskip.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the list.

Results:

The entries() public member function returns the number of elements in the list.

WCPtrSkipListSet<Type>::find(), WCPtrSkipList<Type>::find()

find an entry in the list

Synopsis:

#include <wcskip.h>
public:
Type * find( const Type * ) const;

Semantics:

The find() public member function is used to find an element with an equivalent value in the list. If an equivalent element is found, a pointer to the element is returned. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the element type.

Results:

The element equivalent to the passed value is located in the list.

WCPtrSkipListSet<Type>::forAll(), WCPtrSkipList<Type>::forAll()

invoke a function for each entry in the list

Synopsis:

#include <wcskip.h>
public:
void forAll(void (*user_fn)( Type *, void * ),
            void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every value in the list. The user function has the prototype

    void user_func( Type * value, void * data );

As the elements are visited, the user function is invoked with the element passed as the first parameter. The second parameter of the forAll() function is passed as the second parameter to the user function. This value can be used to pass any appropriate data from the main program to the user function.

Results:

The elements in the list are all visited, and the user function is invoked for each one.

WCPtrSkipListSet<Type>::insert(), WCPtrSkipList<Type>::insert()

insert an entry into the list

Synopsis:

#include <wcskip.h>
public:
int insert( Type * );

Semantics:

The insert() public member function inserts a value into the list.

If allocation of the node to store the value fails, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

With a WCPtrSkipListSet, there must be only one equivalent element in the set. If an element equivalent to the inserted element is already in the list set, the list set remains unchanged, and the not_unique exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

Results:

The insert() public member function inserts a value into the list. If the insertion is successful, a non-zero value is returned; zero is returned if it fails.

WCPtrSkipListSet<Type>::isEmpty(), WCPtrSkipList<Type>::isEmpty()

determine whether or not the list is empty

Synopsis:

#include <wcskip.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if the list is empty.

Results:

The isEmpty() public member function returns zero if the list contains at least one entry, non-zero if it's empty.

WCPtrSkipList<Type>::occurrencesOf()

count the occurrences of the given value in the list

Synopsis:

#include <wcskip.h>
public:
unsigned occurrencesOf( const Type * ) const;

Semantics:

The occurrencesOf() public member function is used to return the current number of elements stored in the list that are equivalent to the passed value. Note that equivalence is based on the equivalence operator of the element type.

Results:

The occurrencesOf() public member function returns the number of elements in the list that are equivalent to the passed value.

WCPtrSkipListSet<Type>::operator =(), WCPtrSkipList<Type>::operator =()

assign one list to another

Synopsis:

#include <wcskip.h>
public:
WCPtrSkipList & operator =( 
    const WCPtrSkipList & );
WCPtrSkipListSet & operator =( 
    const WCPtrSkipListSet & );

Semantics:

The operator =() public member function is the assignment operator for the WCPtrSkipListSet<Type> and WCPtrSkipList<Type> classes. The left hand side list is first cleared using the clear() member function, and then the right hand side list is copied. The list function, exception trap states, and all of the list elements are copied.

If there isn't enough memory to copy all of the values or pointers in the list, then only some are copied, and the out_of_memory exception is thrown if it's enabled. The number of entries correctly reflects the number copied.

Results:

The operator =() public member function assigns the left hand side list to be a copy of the right hand side.

WCPtrSkipListSet<Type>::operator ==(), WCPtrSkipList<Type>::operator ==()

determine whether or not two lists are equivalent

Synopsis:

#include <wcskip.h>
public:
int operator ==( const WCPtrSkipList & ) const;
int operator ==( const WCPtrSkipListSet & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCPtrSkipListSet<Type> and WCPtrSkipList<Type> classes. Two list objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side and right hand side list are the same object. A FALSE (zero) value is returned otherwise.

WCPtrSkipListSet<Type>::remove(), WCPtrSkipList<Type>::remove()

remove an entry from the list

Synopsis:

#include <wcskip.h>
public:
Type * remove( const Type * );

Semantics:

The remove() public member function is used to remove the specified element from the list. If an equivalent element is found, the pointer value is returned. Zero is returned if the element isn't found. If the list is a WCPtrSkipList and there's more than one element equivalent to the specified element, then the last equivalent element added to the skip list is removed. Note that equivalence is based on the equivalence operator of the element type.

Results:

The element is removed from the list.

WCPtrSkipList<Type>::removeAll()

remove all occurences of an element from the list

Synopsis:

#include <wcskip.h>
public:
unsigned removeAll( const Type * );

Semantics:

The removeAll() public member function is used to remove all elements equivalent to the specified element from the list. Zero is returned if no equivalent elements are found. Note that equivalence is based on the equivalence operator of the element type.

Results:

All equivalent elements are removed from the list.

WCValSkipListDict<Key,Value> Class

Declared:

wcskip.h

The WCValSkipListDict<Key,Value> class is a templated class used to store objects in a dictionary. Dictionaries store values with an associated key, which may be of any type. One example of a dictionary used in everyday life is the phone book. The phone numbers are the data values, and the customer's name is the key. The equality operator of the key's type is used to locate the key-value pairs.

In the description of each member function, the text Key is used to indicate the template parameter defining the type of the indices used to store data in the dictionary. The text Value is used to indicate the template parameter defining the type of the data stored in the dictionary.

Values are copied into the dictionary, which could be undesirable if the stored objects are complicated and copying is expensive. Value dictionaries shouldn't be used to store objects of a base class if any derived types of different sizes would be stored in the dictionary, or if the destructor for a derived class must be called.

The iterator classes for skip lists have the same function and operator interface as the hash iterator classes. See the chapter on Hash Iterators for more information.

The WCExcept class is a base class of the WCValSkipListDict<Key,Value> class, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCValSkipListDict<Key,Value> object. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCValSkipListDict<Key,Value> class requires Key to have:

a default constructor
```
    Key::Key()
    
```
a well defined copy constructor
```
    Key::Key( const Key & )
    
```

a well defined assignment operator

    Key & operator =( const Key & )

a well defined equivalence operator with constant parameters
```
    int operator ==( const Key & ) const
    
```
a well defined less-than operator with constant parameters
```
    int operator <( const Key & ) const
    
```

The WCValSkipListDict<Key,Value> class requires Value to have:

a default constructor
```
    Value::Value()
    
```
a well defined copy constructor (
```
    Value::Value( const Value & )
    
```

a well defined assignment operator

    Value & operator =( const Value & )

Public Member Functions

The following member functions are declared in the public interface:

WCValSkipListDict( unsigned = WCSkipListDict_PROB_QUARTER, 
                   unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS);
WCValSkipListDict( unsigned = WCSkipListDict_PROB_QUARTER,
                   unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
                   void * (*user_alloc)( size_t size ),
                   void (*user_dealloc)( void *old,
                                         size_t size ) );
WCValSkipListDict( const WCValSkipListDict & );
virtual ~WCValSkipListDict();
void clear();
int contains( const Key & ) const;
unsigned entries() const;
int find( const Key &, Value & ) const;
int findKeyAndValue( const Key &, Key &, Value & ) const;
void forAll( void (*user_fn)( Key, Value, void * ),
             void * );
int insert( const Key &, const Value & );
int isEmpty() const;
int remove( const Key & );

Public Member Operators

The following member operators are declared in the public interface:

Value & operator [ ]( const Key & );
const Value & operator [ ]( const Key & ) const;
WCValSkipListDict & operator =( 
    const WCValSkipListDict & );
int operator ==( const WCValSkipListDict & ) const;

WCValSkipListDict<Key,Value>::WCValSkipListDict()

create a WCValSkipListDict<Key,Value> object

Synopsis:

#include <wcskip.h>
public:
WCValSkipListDict( 
    unsigned = WCSKIPLIST_PROB_QUARTER,
    unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCValSkipListDict( 
    unsigned = WCSKIPLIST_PROB_QUARTER,
    unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
    void * (*user_alloc)( size_t ),
    void (*user_dealloc)( void *, size_t ) );
WCValSkipListDict( const WCValSkipListDict & );

Semantics:

There are three forms of the public WCValSkipListDict<Key,Value> constructor:

The first creates an WCValSkipListDict<Key,Value> object with no entries.
The first optional parameter, which defaults to the constant WCSKIPLIST_PROB_QUARTER, determines the probability of having a certain number of pointers in each skip list node. The second optional parameter, which defaults to the constant WCDEFAULT_SKIPLIST_MAX_PTRS, determines the maximum number of pointers that are allowed in any skip list node. WCDEFAULT_SKIPLIST_MAX_PTRS is the maximum effective value of the second parameter.
If an allocation failure occurs while creating the skip list, the out_of_memory exception is thrown if it's enabled.
The second form also creates an WCValSkipListDict<Key,Value> object with no entries. Allocator and deallocator functions are specified for use when entries are inserted and removed from the list dictionary. The semantics of this constructor are the same as the constructor without the memory management functions.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a list dictionary. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
```
    WCValSkipListDictItemSize( Key, Value, num_of_pointers )
    
```
The third form is the copy constructor for the WCValSkipListDict<Key,Value> class. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.
If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The public WCValSkipListDict<Key,Value> constructor creates an initialized WCValSkipListDict<Key,Value> object.

WCValSkipListDict<Key,Value>::~WCValSkipListDict()

destroy a WCValSkipListDict<Key,Value> object

Synopsis:

#include <wcskip.h>
public:
virtual ~WCValSkipListDict();

Semantics:

The public WCValSkipListDict<Key,Value> destructor is the destructor for the WCValSkipListDict<Key,Value> class.

If the number of dictionary elements isn't zero and the not_empty exception is enabled, it's thrown. Otherwise, the dictionary elements are cleared using the clear() member function.

The call to this destructor is inserted implicitly by the compiler at the point where the WCValSkipListDict<Key,Value> object goes out of scope.

Results:

The WCValSkipListDict<Key,Value> object is destroyed.

WCValSkipListDict<Key,Value>::clear()

clear all the entries from the dictionary

Synopsis:

#include <wcskip.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the dictionary so that it has no entries. Elements stored in the dictionary are destroyed using the destructors of Key and of Value. The dictionary object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

The clear() public member function clears the dictionary to have no elements.

WCValSkipListDict<Key,Value>::contains()

determine whether or not a given element is in the dictionary

Synopsis:

#include <wcskip.h>
public:
int contains( const Key & ) const;

Semantics:

Results:

The contains() public member function returns a non-zero value if the Key is found in the dictionary.

WCValSkipListDict<Key,Value>::entries()

count the elements in the dictionary

Synopsis:

#include <wcskip.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the dictionary.

Results:

The entries() public member function returns the number of elements in the dictionary.

WCValSkipListDict<Key,Value>::find()

find an element in the dictionary

Synopsis:

#include <wcskip.h>
public:
int find( const Key &, Value & ) const;

Semantics:

The find() public member function is used to find an element with an equivalent key in the dictionary.

If an equivalent element is found, a non-zero value is returned. The reference to a Value passed as the second argument is assigned the found element's Value.
Zero is returned if the element isn't found.

Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCValSkipListDict<Key,Value>::findKeyAndValue()

find an element in the dictionary

Synopsis:

#include <wcskip.h>
public:
int findKeyAndValue( const Key &,
             Key &, Value & ) const;

Semantics:

The findKeyAndValue() public member function is used to find an element in the dictionary with an key equivalent to the first parameter.

If an equivalent element is found, a non-zero value is returned. The reference to a Key passed as the second parameter is assigned the found element's key. The reference to a Value passed as the third argument is assigned the found element's Value.
Zero is returned if the element isn't found.

Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCValSkipListDict<Key,Value>::forAll()

invoke a function for each element in the dictionary

Synopsis:

#include <wcskip.h>
public:
void forAll(
      void (*user_fn)( Key, Value, void * ),
      void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every key-value pair in the dictionary. The user function has the prototype

    void user_func( Key key, Value value, void * data );

Results:

The elements in the dictionary are all visited, and the user function is invoked for each one.

WCValSkipListDict<Key,Value>::insert()

insert an element into the dictionary

Synopsis:

#include <wcskip.h>
public:
int insert( const Key &, const Value & );

Semantics:

The insert() public member function inserts a key and value into the dictionary.

If allocation of the node to store the key-value pair fails, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

Results:

The insert() public member function inserts a key and value into the dictionary. If the insertion is successful, a non-zero value is returned. A zero is returned if the insertion fails.

WCValSkipListDict<Key,Value>::isEmpty()

determine whether or not the dictionary is empty

Synopsis:

#include <wcskip.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if the dictionary is empty.

Results:

The isEmpty() public member function returns zero if the dictionary contains at least one entry, non-zero if it's empty.

WCValSkipListDict<Key,Value>::operator [ ]()

index into the dictionary to find the element for the given Key

Synopsis:

#include <wcskip.h>
public:
Value & operator[ ]( const Key & );
const Value & operator[ ]( const Key & ) const;

Semantics:

operator [ ]() is the dictionary index operator; there are two forms of it:

The first form returns a reference to the object stored in the dictionary with the given Key.
If no equivalent element is found, then a new key-value pair is created with the specified Key value, and initialized with the default constructor. The returned reference can then be assigned to, so that insertions can be made with the operator.
If an allocation error occurs while inserting a new key-value pair, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.
The second form returns a constant reference to the object stored in the dictionary with the given Key.
If no equivalent element is found, then the index_range exception is thrown if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.

Results:

The first form of the operator [ ]() public member function returns a reference to the element at the given key value. If the key doesn't exist, a reference to a created element is returned. The result of the operator may be assigned to.
The second form returns a constant reference to the element at the given key value. The result of the operator may not be assigned to.

WCValSkipListDict<Key,Value>::operator =()

assign one dictionary to another

Synopsis:

#include <wcskip.h>
public:
WCValSkipListDict & operator =( 
    const WCValSkipListDict & );

Results:

The element is removed from the dictionary if it's found.

WCValSkipListSet<Type> and WCValSkipList<Type> Classes

Declared:

wcskip.h

The WCValSkipListSet<Type> and WCValSkipList<Type> classes are templated classes used to store objects in a skip list. A skip list is a probabilistic alternative to balanced trees, and provides a reasonable performance balance to insertion, search, and deletion. A skip list allows more than one copy of an element that's equivalent, while the skip list set allows only one copy. The equality operator of the element's type is used to locate the value.

In the description of each member function, the text Type is used to indicate the template parameter defining the type of the data to be stored in the list.

Values are copied into the list, which could be undesirable if the stored objects are complicated and copying is expensive. Value skip lists shouldn't be used to store objects of a base class if any derived types of different sizes would be stored in the list, or if the destructor for a derived class must be called.

The iterator classes for skip lists have the same function and operator interface as the hash iterator classes. See the chapter on Hash Iterators for more information.

The WCExcept class is a base class of the WCValSkipListSet<Type> and WCValSkipList<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCValSkipListSet<Type> and WCValSkipList<Type> objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCValSkipListSet<Type> and WCValSkipList<Type> classes require Type to have the following:

a default constructor
```
    Type::Type()
    
```
a well defined copy constructor
```
    Type::Type( const Type & )
    
```

a well defined equivalence operator

    int operator ==( const Type & ) const

a well defined less-than operator

    int operator <( const Type & ) const

Public Member Functions

The following member functions are declared in the public interface:

WCValSkipList( unsigned = WCSKIPLIST_PROB_QUARTER, 
               unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCValSkipList( unsigned = WCSKIPLIST_PROB_QUARTER,
               unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
               void * (*user_alloc)( size_t size ),
               void (*user_dealloc)( void *old,
                                     size_t size ) );
WCValSkipList( const WCValSkipList & );
virtual ~WCValSkipList();

WCValSkipListSet( unsigned = WCSKIPLIST_PROB_QUARTER,
                  unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCValSkipListSet( unsigned = WCSKIPLIST_PROB_QUARTER,
                  unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
                  void * (*user_alloc)( size_t size ),
                  void (*user_dealloc)( void *old,
                                        size_t size ) );
WCValSkipListSet( const WCValSkipListSet & );
virtual ~WCValSkipListSet();

void clear();
int contains( const Type & ) const;
unsigned entries() const;
int find( const Type &, Type & ) const;
void forAll( void (*user_fn)( Type, void * ), void * );
int insert( const Type & );
int isEmpty() const;
int remove( const Type & );

The following public member functions are available for the WCValSkipList class only:

unsigned occurrencesOf( const Type & ) const;
unsigned removeAll( const Type & );

Public Member Operators

The following member operators are declared in the public interface:

WCValSkipList & operator =( const WCValSkipList & );
int operator ==( const WCValSkipList & ) const;
WCValSkipListSet & operator =( const WCValSkipListSet & );
int operator ==( const WCValSkipListSet & ) const;

WCValSkipListSet<Type>::WCValSkipListSet()

create a WCValSkipListSet<Type> object

Synopsis:

#include <wcskip.h>
public:
WCValSkipListSet( 
        unsigned = WCSKIPLIST_PROB_QUARTER,
        unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCValSkipListSet( 
        unsigned = WCSKIPLIST_PROB_QUARTER,
        unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
        void * (*user_alloc)( size_t ),
        void (*user_dealloc)( void *, size_t ) );
WCValSkipListSet( const WCValSkipListSet & );

Semantics:

There are three forms of the WCValSkipListSet<Type> constructor:

The first creates a WCValSkipListSet object with no entries.
The first optional parameter, which defaults to the constant WCSKIPLIST_PROB_QUARTER, determines the probability of having a certain number of pointers in each skip list node. The second optional parameter, which defaults to the constant WCDEFAULT_SKIPLIST_MAX_PTRS, determines the maximum number of pointers that are allowed in any skip list node. WCDEFAULT_SKIPLIST_MAX_PTRS is the maximum effective value of the second parameter.
If an allocation failure occurs while creating the skip list, the out_of_memory exception is thrown if it's enabled.
The second form also creates a WCValSkipListSet object with no entries. Allocator and deallocator functions are specified for use when entries are inserted and removed from the list. The semantics of this constructor are the same as the constructor without the memory management functions.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a skip list. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
```
    WCValSkipListSetItemSize( Type, num_of_pointers )
    
```
The third form is the copy constructor for the WCValSkipListSet class. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.
If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The WCValSkipListSet<Type> constructor creates an initialized WCValSkipListSet object.

WCValSkipListSet<Type>::~WCValSkipListSet()

destroy a WCValSkipListSet<Type> object

Synopsis:

#include <wcskip.h>
public:
virtual ~WCValSkipListSet();

Semantics:

The WCValSkipListSet<Type> destructor is the destructor for the WCValSkipListSet class.

If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the list elements are cleared using the clear() member function.

The call to this destructor is inserted implicitly by the compiler at the point where the WCValSkipListSet object goes out of scope.

Results:

The WCValSkipListSet object is destroyed.

WCValSkipList<Type>::WCValSkipList()

create a WCValSkipList<Type> object

Synopsis:

#include <wcskip.h>
public:
WCValSkipList( 
        unsigned = WCSKIPLIST_PROB_QUARTER,
        unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS );
WCValSkipList( 
        unsigned = WCSKIPLIST_PROB_QUARTER,
        unsigned = WCDEFAULT_SKIPLIST_MAX_PTRS,
        void * (*user_alloc)( size_t ),
        void (*user_dealloc)( void *, size_t ) );
WCValSkipList( const WCValSkipList & );

Semantics:

There are three forms of the WCValSkipList<Type> constructor:

The first creates a WCValSkipList object with no entries.
The first optional parameter, which defaults to the constant WCSKIPLIST_PROB_QUARTER, determines the probability of having a certain number of pointers in each skip list node. The second optional parameter, which defaults to the constant WCDEFAULT_SKIPLIST_MAX_PTRS, determines the maximum number of pointers that are allowed in any skip list node. WCDEFAULT_SKIPLIST_MAX_PTRS is the maximum effective value of the second parameter.
If an allocation failure occurs while creating the skip list, the out_of_memory exception is thrown if it's enabled.
The second form also creates a WCValSkipList object with no entries. Allocator and deallocator functions are specified for use when entries are inserted and removed from the list. The semantics of this constructor are the same as the constructor without the memory management functions.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a skip list. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
```
    WCValSkipListItemSize( Type, num_of_pointers )
    
```
The third form is the copy constructor for the WCValSkipList class. The new skip list is created with the same probability and maximum pointers, all values or pointers stored in the list, and the exception trap states.
If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The WCValSkipList<Type> constructor creates an initialized WCValSkipList object.

WCValSkipList<Type>::~WCValSkipList()

destroy a WCValSkipList<Type> object

Synopsis:

#include <wcskip.h>
public:
virtual ~WCValSkipList();

Semantics:

The WCValSkipList<Type> destructor is the destructor for the WCValSkipList class.

If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the list elements are cleared using the clear() member function.

#include <wcskip.h>
public:
int find( const Type &, Type & ) const;

Semantics:

The find() public member function is used to find an element with an equivalent value in the list.

If an equivalent element is found, a non-zero value is returned. The reference to the element passed as the second argument is assigned the found element's value.
Zero is returned if the element isn't found.

Note that equivalence is based on the equivalence operator of the element type.

Results:

The element equivalent to the passed value is located in the list.

WCValSkipListSet<Type>::forAll(), WCValSkipList<Type>::forAll()

invoke a function for each element in the list

Synopsis:

#include <wcskip.h>
public:
void forAll(
      void (*user_fn)( Type, void * ),
      void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every value in the list. The user function has the prototype

    void user_func( Type & value, void * data );

As the elements are visited, the user function is invoked with the element passed as the first. The second parameter of the forAll() function is passed as the second parameter to the user function. This value can be used to pass any appropriate data from the main program to the user function.

Results:

The elements in the list are all visited, and the user function is invoked for each one.

WCValSkipListSet<Type>::insert(), WCValSkipList<Type>::insert()

insert an element into the list

Synopsis:

#include <wcskip.h>
public:
int insert( const Type & );

Semantics:

The insert() public member function inserts a value into the list. If allocation of the node to store the value fails, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

With a WCValSkipListSet, there must be only one equivalent element in the set. If an element equivalent to the inserted element is already in the list set, the list set remains unchanged, and the not_unique exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

Results:

The insert() public member function inserts a value into the list. If the insertion is successful, a non-zero value is returned; zero is returned if it fails.

WCValSkipListSet<Type>::isEmpty(), WCValSkipList<Type>::isEmpty()

determine whether or not the list is empty

Synopsis:

#include <wcskip.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if the list is empty.

Results:

The isEmpty() public member function returns zero if the list contains at least one entry, non-zero if it's empty.

WCValSkipList<Type>::occurrencesOf()

count the elements that are equvalent to the passed value

Synopsis:

#include <wcskip.h>
public:
unsigned occurrencesOf( const Type & ) const;

Semantics:

Results:

The occurrencesOf() public member function returns the number of elements in the list that are equivalent to the passed value.

WCValSkipListSet<Type>::operator =(), WCValSkipList<Type>::operator =()

assign one list to another

Synopsis:

#include <wcskip.h>
public:
WCValSkipList & operator =( 
        const WCValSkipList & );
WCValSkipListSet & operator =( 
        const WCValSkipListSet & );

Semantics:

The operator =() public member function is the assignment operator for the WCValSkipListSet<Type> and WCValSkipList<Type> classes. The left hand side list is first cleared using the clear() member function, and then the right hand side list is copied. The list function, exception trap states, and all of the list elements are copied.

Results:

The operator =() public member function sets the left hand side list to be a copy of the right hand side.

WCValSkipListSet<Type>::operator ==(), WCValSkipList<Type>::operator ==()

determine whether or not two lists are equivalent

Synopsis:

#include <wcskip.h>
public:
int operator ==( const WCValSkipList & ) const;
int operator ==( const WCValSkipListSet & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCValSkipListSet<Type> and WCValSkipList<Type> classes. Two list objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side and right hand side list are the same object. A FALSE (zero) value is returned otherwise.

WCValSkipListSet<Type>::remove(), WCValSkipList<Type>::remove()

remove an element from the list

Synopsis:

#include <wcskip.h>
public:
int remove( const Type & );

Semantics:

The remove() public member function is used to remove the specified element from the list.

If an equivalent element is found, a non-zero value is returned.
Zero is returned if the element isn't found.

If the list is a WCValSkipList and there's more than one element equivalent to the specified element, then the last equivalent element added to the list is removed. Note that equivalence is based on the equivalence operator of the element type.

Results:

The element is removed from the list.

WCValSkipList<Type>::removeAll()

remove all occurrences of an element from the list

Synopsis:

#include <wcskip.h>
public:
unsigned removeAll( const Type & );

Semantics:

Results:

All equivalent elements are removed from the list.

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

Synopsis:

Semantics:

Results:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics: