wcvbase.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 905 行 · 第 1/2 页

template<class Type>
void WCVectorBase<Type>::base_remove_at( int index ) {
    for( int i = index; i < num_entries - 1; i++ ) {
        vector[ i ] = vector[ i + 1 ];
    }
    // destruct the last element in the array, so that unused elements are
    // unitialized.
    vector[ num_entries - 1 ].~Type();
    num_entries--;
    num_init--;
}


template<class Type>
WCVectorBase<Type>::~WCVectorBase() {};


template<class Type>
WCbool WCVectorBase<Type>::contains( const Type &elem ) const {
    int index = 0;

    if( ( num_entries != 0 )
      &&( base_find( elem, find_any, &index ) ) ) {
        return( TRUE );
    } else {
        return( FALSE );
    }
}


template<class Type>
WCbool WCVectorBase<Type>::find( const Type &elem, Type &ret_val ) const {
    int index = 0;
    if( ( num_entries > 0 )
      &&( base_find( elem, find_first, &index ) ) ) {
        ret_val = vector[ index ];
        return( TRUE );
    } else {
        Type temp;
        ret_val = temp;
        return( FALSE );
    }
};


template<class Type>
int WCVectorBase<Type>::index( const Type & elem ) const {
    int ret_index = 0;

    if( ( num_entries > 0 )
      &&( base_find( elem, find_first, &ret_index ) ) ) {
        return( ret_index );
    } else {
        return( -1 );
    }
}


template<class Type>
int WCVectorBase<Type>::occurrencesOf( const Type & elem ) const {
    int index = 0;
    int count = 0;

    if( ( num_entries > 0 )
      &&( base_find( elem, find_first, &index ) ) ) {
        do {
            count++;
            index++;
        } while( base_find( elem, next_mult_find, &index ) );
    }
    return( count );
};


template<class Type>
WCbool WCVectorBase<Type>::remove( const Type & elem ) {
    int index = 0;

    if( ( num_entries > 0 )
      &&( base_find( elem, find_first, &index ) ) ) {
        base_remove_at( index );
        return( TRUE );
    } else {
        return( FALSE );
    }
};


template<class Type>
unsigned WCVectorBase<Type>::removeAll( const Type & elem ) {
    int found_index = 0;
    int count = 0;

    // make sure only elements which need to be moved are moved
    // no element is moved more than once
    if( ( num_entries > 0 )
      &&( base_find( elem, find_first, &found_index ) ) ) {
        // at least one element is being removed
        int curr_index = found_index;
        count++;
        found_index++;
        while( base_find( elem, next_mult_find, &found_index ) ) {
            // move entries which were between any occurrances of elem
            for( ;curr_index < found_index - count; curr_index++ ){
                vector[ curr_index ] = vector[ curr_index + count ];
            }
            count++;
            found_index++;
        };
        // move entries after any occurances of elem
        for( ;curr_index < num_entries - count; curr_index++ ){
            vector[ curr_index ] = vector[ curr_index + count ];
        }
        // destruct elements at the end of the vector which were copied or
        // removed, so that unused elements are unitialized
        for( ;curr_index < num_entries; curr_index++ ){
            vector[ curr_index ].~Type();
        }
        num_entries -= count;
        num_init -= count;
    }
    return( count );
}



template<class Type>
WCbool WCVectorBase<Type>::removeAt( int index ) {
    if( num_entries == 0 ) {
        base_throw_empty_container();
        return( FALSE );
    } else {
        index = base_index_check( index );
        base_remove_at( index );
        return( TRUE );
    }
};


template<class Type>
WCbool WCVectorBase<Type>::resize( size_t new_length ) {
    WCbool return_val = WCBareVectorBase<Type>::resize( new_length );
    if( return_val && num_entries > new_length ){
        num_entries = new_length;
    }
    return( return_val );
};




//
// WCOrderedVectorBase  - this is the base class for WCValOrderedVector and
//                        WCPtrOrderedVector.
//
// This is a abstract class to prevent objects of this type being created
//

template <class Type>
class WCOrderedVectorBase : public WCVectorBase<Type> {
protected:
    virtual WCbool base_find( const Type &, find_type, int * ) const;
public:
    inline WCOrderedVectorBase( size_t length, unsigned default_grow )
                        : WCVectorBase<Type>( length, default_grow ) {};

    inline virtual ~WCOrderedVectorBase() = 0;

    inline WCbool append( const Type& new_elem ){
        return( insert( new_elem ) );
    };

    inline WCbool insert( const Type& new_elem ){
        return( base_insert_at( num_entries, new_elem ) );
    };

    inline WCbool insertAt( int index, const Type& new_elem ){
        return( base_insert_at( index, new_elem ) );
    };

    inline WCbool prepend( const Type& new_elem ){
        return( base_insert_at( 0, new_elem ) );
    };

};


template <class Type>
WCOrderedVectorBase<Type>::~WCOrderedVectorBase() {};


template <class Type>
WCbool WCOrderedVectorBase<Type>::base_find( const Type &elem, find_type
                                , int *st_found_index ) const {
    int index = *st_found_index;

    while( index < num_entries ) {
         if( base_equivalent( vector[ index ], elem ) ) {
             *st_found_index = index;
             return( TRUE );
         }
         index++;
    }
    return( FALSE );
};




//
// WCSortedVectorBase   - this is the base class for WCValSortedVector and
//                        WCPtrSortedVector.
//
// This is a abstract class to prevent objects of this type being created
//

template <class Type>
class WCSortedVectorBase : public WCVectorBase<Type> {
protected:
    virtual WCbool base_find( const Type &, find_type, int * ) const;
    virtual int base_less_than( const Type& elem1
                              , const Type& elem2 ) const = 0;
public:
    inline WCSortedVectorBase( size_t length, unsigned default_grow )
                        : WCVectorBase<Type>( length, default_grow ) {};

    inline virtual ~WCSortedVectorBase() = 0;

    WCbool insert( const Type& );
};


template <class Type>
WCSortedVectorBase<Type>::~WCSortedVectorBase() {};


template <class Type>
WCbool WCSortedVectorBase<Type>::base_find( const Type &elem, find_type type
        , int * st_found_index ) const {
    // for multiple searches, check to see next element also matches
    if( type == next_mult_find ) {
        int index = *st_found_index;
        if( ( index < num_entries )
          &&( base_equivalent( vector[ index ], elem ) ) ) {
             return( TRUE );
        }
        return( FALSE );
    }

    // the binary search
    int low_bound = 0;
    int up_bound = num_entries - 1;
    int bisector;
    while( low_bound < up_bound ) {
        // bisector must be calculated so that it is less than up_bound
        bisector = ( up_bound - low_bound ) / 2 + low_bound;
        if( base_less_than( vector[ bisector ], elem ) ) {
            low_bound = bisector + 1;
        } else {
            up_bound = bisector;
        }
    }

    bisector = low_bound;
    // if we found elem, the first match is at index bisector

    if( base_equivalent( elem, vector[ bisector ] ) ) {
        // found match, bisector is the first match
        if( type == find_for_insert ) {
            while( ( bisector < num_entries )
                 &&( base_equivalent( vector[ bisector ], elem ) ) ) {
                bisector++;
            }
        }
        *st_found_index = bisector;
        return( TRUE );
    }

    // search failed, if find for insert make sure we are *after* elem
    if( type == find_for_insert ){
        if( base_less_than( vector[ bisector ], elem ) ) {
            bisector++;
        }
        *st_found_index = bisector;
    }
    return( FALSE );
}


template <class Type>
WCbool WCSortedVectorBase<Type>::insert( const Type& elem ) {
    int index = 0;

    if( num_entries > 0 ) {
        base_find( elem, find_for_insert, &index );
    }
    return( base_insert_at( index, elem ) );
};




//
// WCPtrVectorBase      - this is a base class for WCPtrOrderedVector and
//                        WCPtrSortedVector.
//
// This is a abstract class to prevent objects of this type being created
//
// Implementation note:
// All WCPtrOrdered vectors and WCPtrSorted vectors inherit from WCVectorBase
// templated over <void *>.  This saves most of the vector code being
// generated for pointer vectors templated over different types, speeding
// up compile time, and reducing code size.
//

template <class Type, class BaseClass>
class WCPtrVectorBase : public BaseClass {
protected:
    typedef Type * __Type_Ptr;
    typedef void * __Stored_Ptr;

    inline Type *base_ptr_remove_at( int index ) {
        Type *ret_ptr = (Type *)vector[ index ];
        base_remove_at( index );
        return( ret_ptr );
    }

    virtual void base_init_upto( int );

public:
    inline WCPtrVectorBase( size_t length, unsigned default_grow )
                        : BaseClass( length, default_grow ) {};

    inline virtual ~WCPtrVectorBase() = 0;

    void clearAndDestroy();

    inline WCbool contains( const Type * elem ) const {
        return( BaseClass::contains( (const __Type_Ptr)elem ) );
    };

    Type *find( const Type * elem ) const;

    inline Type *first() const {
        return( (Type *)BaseClass::first() );
    }

    inline int index( const Type * elem ) const {
        return( BaseClass::index( (const __Type_Ptr)elem ) );
    };

    inline Type *last() const {
        return( (Type *)BaseClass::last() );
    }

    int occurrencesOf( const Type * elem ) const {
        return( BaseClass::occurrencesOf( (const __Type_Ptr)elem ) );
    };

    Type *remove( const Type * elem );

    unsigned removeAll( const Type * elem ) {
        return( BaseClass::removeAll( (const __Type_Ptr)elem ) );
    };

    Type *removeAt( int index );

    inline Type *removeFirst() {
        return( removeAt( 0 ) );
    };

    inline Type *removeLast() {
        return( removeAt( num_entries - 1 ) );
    };

    inline Type * &operator[] ( int index ) {
        return( (Type * &)BaseClass::operator[]( index ) );
    };

    inline Type * const & operator[] ( int index ) const {
        return( (Type * const &)BaseClass::operator[]( index ) );
    };
};


template<class Type, class BaseClass>
void WCPtrVectorBase<Type, BaseClass>::base_init_upto( int index ) {
    if( index >= num_init ){
        // intialize the vector by NULLing out unitialized elements
        memset( &vector[ num_init ], 0
              , ( index + 1 - num_init ) * sizeof( void * ) );
        num_init = index + 1;
    }
}


template <class Type, class BaseClass>
WCPtrVectorBase<Type, BaseClass>::~WCPtrVectorBase() {};


template<class Type, class BaseClass>
void WCPtrVectorBase<Type, BaseClass>::clearAndDestroy() {
    for( unsigned i = 0; i < num_entries; i++ ) {
        delete( (Type *)vector[ i ] );
    }
    clear();
};


template<class Type, class BaseClass>
Type *WCPtrVectorBase<Type, BaseClass>::find( const Type * elem ) const {
    int index = 0;
    if( ( num_entries > 0 )
      &&( base_find( (const __Type_Ptr)elem, find_any, &index ) ) ) {
        return( (Type *)vector[ index ] );
    } else {
        return( 0 );
    }
};


template<class Type, class BaseClass>
Type *WCPtrVectorBase<Type, BaseClass>::remove( const Type *elem ) {
    int index = 0;

    if( ( num_entries > 0 )
      &&( base_find( (const __Type_Ptr)elem, find_first, &index ) ) ) {
        return( base_ptr_remove_at( index ) );
    } else {
        return( 0 );
    }
};


template<class Type, class BaseClass>
Type *WCPtrVectorBase<Type, BaseClass>::removeAt( int index ) {
    if( num_entries == 0 ) {
        base_throw_empty_container();
        return( 0 );
    } else {
        index = base_index_check( index );
        return( base_ptr_remove_at( index ) );
    }
};


:include redefnew.sp

#endif