//
//  wcskip.h    Definitions and implementation for the WATCOM Container Skip
//              List class
//
// =========================================================================
//
//                          Open Watcom Project
//
//    Copyright (c) 2002-2010 Open Watcom Contributors. All Rights Reserved.
//    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
//
//    This file is automatically generated. Do not edit directly.
//
// =========================================================================
//
#ifndef _WCSKIP_H_INCLUDED
#define _WCSKIP_H_INCLUDED

#ifndef _ENABLE_AUTODEPEND
 #pragma read_only_file;
#endif

#ifndef __cplusplus
 #error This header file requires C++
#endif

//
// Skip Lists are a probabilistic alternative to balanced trees, as
// described in the June 1990 issue of CACM and were invented by
// William Pugh in 1987.
//

#ifndef _WCDEFS_H_INCLUDED
 #include <wcdefs.h>
#endif

#ifndef _WCEXCEPT_H_INCLUDED
 #include <wcexcept.h>
#endif

#ifndef _WCSBASE_H_INCLUDED
 #include <wcsbase.h>
#endif

//
// WCValSkipList - the skip list value class which allows duplicates
//

template<class Type>
class WCValSkipList : public WCSkipListDuplicatesBase<Type> {
private:
    // define equivalence and less than for the base classes
    // second parameters are really typed (Type *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( (const Type)base_whole_node( elem1 )->data
                == *(const Type *)elem2 );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( (const Type)base_whole_node( lhs )->data
                < *(const Type *)rhs );
    };

public:
    inline WCValSkipList( unsigned prob = WCSKIPLIST_PROB_QUARTER
                        , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                        ) : WCSkipListDuplicatesBase( prob, max_ptrs ) {};

    inline WCValSkipList( unsigned prob, unsigned max_ptrs
                        , void * (*user_alloc)( size_t )
                        , void (*user_dealloc)( void *, size_t )
                        ) : WCSkipListDuplicatesBase( prob, max_ptrs
                                        , user_alloc, user_dealloc ) {};

    inline WCValSkipList( const WCValSkipList &orig )
                 : WCSkipListDuplicatesBase( orig.probability
                                           , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCValSkipList() {};

    inline WCbool find( const Type &search, Type &return_val ) const {
        return( base_val_find( search, return_val ) );
    }

    inline WCValSkipList &operator=( const WCValSkipList &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCPtrSkipList - the skip list pointer class which allows duplicates
//

template<class Type>
class WCPtrSkipList
        : public WCPtrSkipListBase<Type,WCSkipListDuplicatesBase<void *> > {
public:
    inline WCPtrSkipList( unsigned prob = WCSKIPLIST_PROB_QUARTER
                        , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                        ) : WCPtrSkipListBase( prob, max_ptrs ) {};

    inline WCPtrSkipList( unsigned prob, unsigned max_ptrs
                        , void * (*user_alloc)( size_t )
                        , void (*user_dealloc)( void *, size_t )
                        ) : WCPtrSkipListBase( prob, max_ptrs
                                             , user_alloc, user_dealloc ) {};

    inline WCPtrSkipList( const WCPtrSkipList &orig )
                         : WCPtrSkipListBase( orig.probability
                                            , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCPtrSkipList() {};

    inline unsigned occurrencesOf( const Type *elem ) const {
        return( WCSkipListDuplicatesBase
                        ::occurrencesOf( (const TypePtr) elem ) );
    };

    inline unsigned removeAll( const Type *elem ) {
        return( WCSkipListDuplicatesBase::removeAll( (const TypePtr) elem ) );
    };

    inline WCPtrSkipList &operator=( const WCPtrSkipList &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCValSkipListSet - the skip list value class which does not allow duplicates
//

template<class Type>
class WCValSkipListSet : public WCSkipListBase<Type> {
private:
    // defines equivalence and less than for the base class
    // second parameters are really typed (Type *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( (const Type)base_whole_node( elem1 )->data
                == *(const Type *)elem2 );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( (const Type)base_whole_node( lhs )->data
                < *(const Type *)rhs );
    };

public:
    inline WCValSkipListSet( unsigned prob = WCSKIPLIST_PROB_QUARTER
                           , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                           ) : WCSkipListBase( prob, max_ptrs ) {};

    inline WCValSkipListSet( unsigned prob, unsigned max_ptrs
                           , void * (*user_alloc)( size_t )
                           , void (*user_dealloc)( void *, size_t )
                           ) : WCSkipListBase( prob, max_ptrs
                                        , user_alloc, user_dealloc ) {};

    inline WCValSkipListSet( const WCValSkipListSet &orig )
                         : WCSkipListBase( orig.probability
                                         , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCValSkipListSet() {};

    inline WCbool find( const Type &search, Type &return_val ) const {
        return( base_val_find( search, return_val ) );
    }

    inline WCValSkipListSet &operator=( const WCValSkipListSet &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCPtrSkipListSet - the skip list pointer class which does not
// allow duplicates
//

template<class Type>
class WCPtrSkipListSet
        : public WCPtrSkipListBase<Type,WCSkipListBase<void *> > {
public:
    inline WCPtrSkipListSet( unsigned prob = WCSKIPLIST_PROB_QUARTER
                           , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                           ) : WCPtrSkipListBase( prob, max_ptrs ) {};

    inline WCPtrSkipListSet( unsigned prob, unsigned max_ptrs
                           , void * (*user_alloc)( size_t )
                           , void (*user_dealloc)( void *, size_t )
                           ) : WCPtrSkipListBase( prob, max_ptrs
                                             , user_alloc, user_dealloc ) {};

    inline WCPtrSkipListSet( const WCPtrSkipListSet &orig )
                         : WCPtrSkipListBase( orig.probability
                                            , orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCPtrSkipListSet() {};

    inline WCPtrSkipListSet &operator=( const WCPtrSkipListSet &orig ) {
        base_assign( &orig );
        return( *this );
    };
};




//
// WCValSkipListDict - the skip list value dictionary class.  Key-Value
// pairs are stored in a skip list, and all lookups are base on Key
//

template<class Key, class Value>
class WCValSkipListDict
        : public WCSkipListBase<WCSkipListDictKeyVal<Key, Value> > {
protected:
    typedef WCSkipListDictKeyVal<Key, Value> KeyVal;
    // for const member functions which modify temp_key_val, but not the
    // skip list
    typedef WCValSkipListDict *const NonConstThis;

    // temp_key_val is used in finds, removes, etc., where only the key is
    // given. it is also used by the operator[] to insert.  The value must
    // remain default initialized
    KeyVal temp_key_val;

    // second parameters are really typed (KeyVal *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( (const Key)base_whole_node( elem1 )->data.key
                == ( (const KeyVal *)elem2 )->key );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( (const Key)base_whole_node( lhs )->data.key
                < ( (const KeyVal *)rhs )->key );
    };

public:
    inline WCValSkipListDict( unsigned prob = WCSKIPLIST_PROB_QUARTER
                            , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                            ) : WCSkipListBase( prob, max_ptrs ) {};

    inline WCValSkipListDict( unsigned prob, unsigned max_ptrs
                            , void * (*user_alloc)( size_t )
                            , void (*user_dealloc)( void *, size_t )
                            ) : WCSkipListBase( prob, max_ptrs
                                              , user_alloc, user_dealloc ) {};

    inline WCValSkipListDict( const WCValSkipListDict &orig )
                 : WCSkipListBase( orig.probability, orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCValSkipListDict() {};

    inline WCbool contains( const Key &key ) const {
        NonConstThis This = (NonConstThis)this;
        This->temp_key_val.key = key;
        return( base_find( temp_key_val ) != 0 );
    };

    WCbool find( const Key &search, Value &ret_value ) const;

    WCbool findKeyAndValue( const Key &search, Key &ret_key
                          , Value &ret_value ) const;

    void forAll( void(*)( Key, Value, void * ), void * ) const;

    inline WCbool insert( const Key &key, const Value &value ) {
        KeyVal temp( key, value );
        return( WCSkipListBase::insert( temp ) );
    };

    inline WCbool remove( const Key &key ) {
        temp_key_val.key = key;
        return( WCSkipListBase::remove( temp_key_val ) );
    };

    inline WCValSkipListDict &operator=( const WCValSkipListDict &orig ) {
        base_assign( &orig );
        return( *this );
    };

    Value &operator[]( const Key &key );

    const Value &operator[]( const Key &key ) const;
};


template<class Key, class Value>
WCbool WCValSkipListDict<Key, Value>::find( const Key &search
                                         , Value &ret_value ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        ret_value = base_whole_node( node )->data.value;
        return( TRUE );
    } else {
        return( FALSE );
    }
};


template<class Key, class Value>
WCbool WCValSkipListDict<Key, Value>::findKeyAndValue( const Key &search
                                , Key &ret_key, Value &ret_value ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        ret_key = base_whole_node( node )->data.key;
        ret_value = base_whole_node( node )->data.value;
        return( TRUE );
    } else {
        return( FALSE );
    }
};


template<class Key, class Value>
void WCValSkipListDict<Key, Value>
                ::forAll( void(*user_fn)( Key, Value, void * )
                        , void * data) const {
    register node_ptr curr;

    curr = header->forward[ 0 ];
    while ( curr != 0 ) {
        user_fn( base_whole_node( curr )->data.key
               , base_whole_node( curr )->data.value, data );
        curr = curr->forward[ 0 ];
    }
};


template<class Key, class Value>
Value &WCValSkipListDict<Key, Value>::operator[]( const Key &key ) {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = key;
    node_ptr node = base_find( temp_key_val );
    if( node == 0 ) {
        node = base_insert( temp_key_val );
        if( !node ) {
            // insert failed because allocation failed and out_of_memory
            // exception disabled
            return( *(Value *)0 );
        }
    }
    return( base_whole_node( node )->data.value );
};


template<class Key, class Value>
const Value &WCValSkipListDict<Key, Value>
                ::operator[]( const Key &key ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = key;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        return( base_whole_node( node )->data.value );
    } else {
        base_throw_index_range();
        // find failed, index_range exception off, but must return reference
        return( *(Value *)0 );
    }
};




//
// WCPtrSkipListDict - the skip list value dictionary class.  Key-Value
// pairs are stored in a skip list, and all lookups are base on Key
//

template<class Key, class Value>
class WCPtrSkipListDict
        : public WCValSkipListDict<void *, void *> {
protected:
    // for const member functions which modify temp_key_val, but not the
    // skip list
    typedef WCPtrSkipListDict *const NonConstThis;
    // the pointer stored by WCValSkipListDict
    typedef void *Stored_Ptr;
    // the user function passed to the forAll member function is passed
    // to WCValSkipListDict::forAll using this cast type
    typedef void (*_ForAllFnCast)( void *, void *, void * );

    // defines equivalence and less than based on the keys pointed to
    // second parameters are really typed (KeyVal *)
    virtual int base_equiv( node_ptr elem1, TTypePtr elem2 ) const {
        return( *(const Key *)base_whole_node( elem1 )->data.key
                == *(const Key *)( (const KeyVal *)elem2 )->key );
    };

    virtual int base_less( node_ptr lhs, TTypePtr rhs ) const {
        return( *(const Key *)base_whole_node( lhs )->data.key
                < *(const Key *)( (const KeyVal *)rhs )->key );
    };

    // for the clearAndDestroy member function
    static void base_destroy( Key *key, Value *value, void * ) {
        delete( key );
        delete( value );
    };

public:
    inline WCPtrSkipListDict( unsigned prob = WCSKIPLIST_PROB_QUARTER
                            , unsigned max_ptrs = WCDEFAULT_SKIPLIST_MAX_PTRS
                            ) : WCValSkipListDict( prob, max_ptrs ) {};

    inline WCPtrSkipListDict( unsigned prob, unsigned max_ptrs
                            , void * (*user_alloc)( size_t )
                            , void (*user_dealloc)( void *, size_t )
                            ) : WCValSkipListDict( prob, max_ptrs
                                              , user_alloc, user_dealloc ) {};

    inline WCPtrSkipListDict( const WCPtrSkipListDict &orig )
             : WCValSkipListDict( orig.probability, orig.max_ptrs_in_node ) {
        base_construct( &orig );
    };

    inline virtual ~WCPtrSkipListDict() {};

    inline void clearAndDestroy() {
        forAll( base_destroy, 0 );
        clear();
    };

    inline WCbool contains( const Key *key ) const {
        return( WCValSkipListDict::contains( (const Stored_Ptr)key ) );
    };

    Value *find( const Key *search ) const;

    Value *findKeyAndValue( const Key *search, Key * &ret_key ) const;

    void forAll( void(*fn)( Key *, Value *, void * ), void * data ) const {
        WCValSkipListDict::forAll( (_ForAllFnCast)fn, data );
    };

    inline WCbool insert( Key *key, Value *value ) {
        return( WCValSkipListDict::insert( (const Stored_Ptr)key
                                         , (const Stored_Ptr)value ) );
    };

    Value* remove( const Key *key );

    inline WCPtrSkipListDict &operator=( const WCPtrSkipListDict &orig ) {
        base_assign( &orig );
        return( *this );
    };

    inline Value * &operator[]( const Key *key ) {
        return( (Value * &)WCValSkipListDict
                                ::operator[]( (const Stored_Ptr)key ) );
    };

    inline Value * const &operator[]( const Key *key ) const {
        return( (Value * const &)WCValSkipListDict
                                ::operator[]( (const Stored_Ptr)key ) );
    };
};


template<class Key, class Value>
Value *WCPtrSkipListDict<Key, Value>::find( const Key *search ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = (Stored_Ptr)search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        return( (Value *)base_whole_node( node )->data.value );
    } else {
        return( 0 );
    }
};


template<class Key, class Value>
Value *WCPtrSkipListDict<Key, Value>::findKeyAndValue( const Key *search
                                , Key * &ret_key ) const {
    NonConstThis This = (NonConstThis)this;
    This->temp_key_val.key = (Stored_Ptr)search;
    node_ptr node = base_find( temp_key_val );
    if( node != 0 ) {
        ret_key = (Key *)base_whole_node( node )->data.key;
        return( (Value *)base_whole_node( node )->data.value );
    } else {
        return( 0 );
    }
};


template<class Key, class Value>
Value *WCPtrSkipListDict<Key, Value>::remove( const Key *elem ) {
    int num_ptrs_in_node;

    temp_key_val.key = (Stored_Ptr)elem;
    node_ptr node = base_remove_but_not_delete( temp_key_val
                                         , num_ptrs_in_node );
    if( node ) {
        Value *ret_ptr = (Value *)base_whole_node( node )->data.value;
        base_delete_node( node, num_ptrs_in_node );
        return( ret_ptr );
    } else {
        return( 0 );
    }
}

#endif