Shadowrun: Awakened 29 September 2011 - Build 871
Public Member Functions | Static Public Member Functions | Protected Attributes
DataStructures::OrderedList< key_type, data_type, default_comparison_function > Class Template Reference

#include <DS_OrderedList.h>

Inheritance diagram for DataStructures::OrderedList< key_type, data_type, default_comparison_function >:

List of all members.

Public Member Functions

void Clear (bool doNotDeallocate, const char *file, unsigned int line)
data_type GetElementFromKey (const key_type &key, int(*cf)(const key_type &, const data_type &)=default_comparison_function) const
bool GetElementFromKey (const key_type &key, data_type &element, int(*cf)(const key_type &, const data_type &)=default_comparison_function) const
unsigned GetIndexFromKey (const key_type &key, bool *objectExists, int(*cf)(const key_type &, const data_type &)=default_comparison_function) const
bool HasData (const key_type &key, int(*cf)(const key_type &, const data_type &)=default_comparison_function) const
unsigned Insert (const key_type &key, const data_type &data, bool assertOnDuplicate, const char *file, unsigned int line, int(*cf)(const key_type &, const data_type &)=default_comparison_function)
void InsertAtEnd (const data_type &data, const char *file, unsigned int line)
void InsertAtIndex (const data_type &data, const unsigned index, const char *file, unsigned int line)
OrderedList & operator= (const OrderedList &original_copy)
data_type & operator[] (const unsigned int position) const
 OrderedList ()
 OrderedList (const OrderedList &original_copy)
unsigned Remove (const key_type &key, int(*cf)(const key_type &, const data_type &)=default_comparison_function)
void RemoveAtIndex (const unsigned index)
void RemoveFromEnd (const unsigned num=1)
unsigned RemoveIfExists (const key_type &key, int(*cf)(const key_type &, const data_type &)=default_comparison_function)
unsigned Size (void) const
 ~OrderedList ()

Static Public Member Functions

static void IMPLEMENT_DEFAULT_COMPARISON (void)

Protected Attributes

DataStructures::List< data_type > orderedList

Detailed Description

template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function = defaultOrderedListComparison<key_type, data_type>>
class DataStructures::OrderedList< key_type, data_type, default_comparison_function >

Note:
IMPORTANT! If you use defaultOrderedListComparison then call IMPLEMENT_DEFAULT_COMPARISON or you will get an unresolved external linker error.

Definition at line 29 of file DS_OrderedList.h.

Constructor & Destructor Documentation

template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
DataStructures::OrderedList< key_type, data_type, default_comparison_function >::OrderedList ( )

Definition at line 62 of file DS_OrderedList.h.

    {
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
DataStructures::OrderedList< key_type, data_type, default_comparison_function >::~OrderedList ( )

Definition at line 67 of file DS_OrderedList.h.

References _FILE_AND_LINE_.

    {
        Clear(false, _FILE_AND_LINE_);
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
DataStructures::OrderedList< key_type, data_type, default_comparison_function >::OrderedList ( const OrderedList< key_type, data_type, default_comparison_function > &  original_copy)

Definition at line 73 of file DS_OrderedList.h.

References DataStructures::OrderedList< key_type, data_type, default_comparison_function >::orderedList.

    {
        orderedList=original_copy.orderedList;
    }

Member Function Documentation

template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
void DataStructures::OrderedList< key_type, data_type, default_comparison_function >::Clear ( bool  doNotDeallocate,
const char *  file,
unsigned int  line 
)

Definition at line 245 of file DS_OrderedList.h.

    {
        orderedList.Clear(doNotDeallocate, file, line);
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
data_type DataStructures::OrderedList< key_type, data_type, default_comparison_function >::GetElementFromKey ( const key_type &  key,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
) const

Definition at line 94 of file DS_OrderedList.h.

References RakAssert.

    {
        bool objectExists;
        unsigned index;
        index = GetIndexFromKey(key, &objectExists, cf);
        RakAssert(objectExists);
        return orderedList[index];
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
bool DataStructures::OrderedList< key_type, data_type, default_comparison_function >::GetElementFromKey ( const key_type &  key,
data_type &  element,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
) const

Definition at line 103 of file DS_OrderedList.h.

    {
        bool objectExists;
        unsigned index;
        index = GetIndexFromKey(key, &objectExists, cf);
        if (objectExists)
            element = orderedList[index];
        return objectExists;
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
unsigned DataStructures::OrderedList< key_type, data_type, default_comparison_function >::GetIndexFromKey ( const key_type &  key,
bool *  objectExists,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
) const

Definition at line 113 of file DS_OrderedList.h.

    {
        int index, upperBound, lowerBound;
        int res;

        if (orderedList.Size()==0)
        {
            *objectExists=false;
            return 0;
        }

        upperBound=(int)orderedList.Size()-1;
        lowerBound=0;
        index = (int)orderedList.Size()/2;

#ifdef _MSC_VER
    #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
        while (1)
        {
            res = cf(key,orderedList[index]);
            if (res==0)
            {
                *objectExists=true;
                return index;
            }
            else if (res<0)
            {
                upperBound=index-1;
            }
            else// if (res>0)
            {
                lowerBound=index+1;
            }

            index=lowerBound+(upperBound-lowerBound)/2;

            if (lowerBound>upperBound)
            {
                *objectExists=false;
                return lowerBound; // No match
            }
        }
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
bool DataStructures::OrderedList< key_type, data_type, default_comparison_function >::HasData ( const key_type &  key,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
) const

comparisonFunction must take a key_type and a data_type and return <0, ==0, or >0 If the data type has comparison operators already defined then you can just use defaultComparison

Definition at line 86 of file DS_OrderedList.h.

    {
        bool objectExists;
        GetIndexFromKey(key, &objectExists, cf);
        return objectExists;
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function = defaultOrderedListComparison<key_type, data_type>>
static void DataStructures::OrderedList< key_type, data_type, default_comparison_function >::IMPLEMENT_DEFAULT_COMPARISON ( void  ) [inline, static]

Definition at line 32 of file DS_OrderedList.h.

{DataStructures::defaultOrderedListComparison<key_type, data_type>(key_type(),data_type());}
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
unsigned DataStructures::OrderedList< key_type, data_type, default_comparison_function >::Insert ( const key_type &  key,
const data_type &  data,
bool  assertOnDuplicate,
const char *  file,
unsigned int  line,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
)

Definition at line 159 of file DS_OrderedList.h.

References RakAssert.

    {
        (void) assertOnDuplicate;
        bool objectExists;
        unsigned index;
        index = GetIndexFromKey(key, &objectExists, cf);

        // Don't allow duplicate insertion.
        if (objectExists)
        {
            // This is usually a bug!
            RakAssert(assertOnDuplicate==false);
            return (unsigned)-1;
        }

        if (index>=orderedList.Size())
        {
            orderedList.Insert(data, file, line);
            return orderedList.Size()-1;
        }
        else
        {
            orderedList.Insert(data,index, file, line);
            return index;
        }       
    }
template<class key_type , class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
void DataStructures::OrderedList< key_type, data_type, default_comparison_function >::InsertAtEnd ( const data_type &  data,
const char *  file,
unsigned int  line 
)

Definition at line 233 of file DS_OrderedList.h.

    {
        orderedList.Insert(data, file, line);
    }
template<class key_type , class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
void DataStructures::OrderedList< key_type, data_type, default_comparison_function >::InsertAtIndex ( const data_type &  data,
const unsigned  index,
const char *  file,
unsigned int  line 
)

Definition at line 227 of file DS_OrderedList.h.

    {
        orderedList.Insert(data, index, file, line);
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
OrderedList< key_type, data_type, default_comparison_function > & DataStructures::OrderedList< key_type, data_type, default_comparison_function >::operator= ( const OrderedList< key_type, data_type, default_comparison_function > &  original_copy)

Definition at line 79 of file DS_OrderedList.h.

References DataStructures::OrderedList< key_type, data_type, default_comparison_function >::orderedList.

    {
        orderedList=original_copy.orderedList;
        return *this;
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
data_type & DataStructures::OrderedList< key_type, data_type, default_comparison_function >::operator[] ( const unsigned int  position) const

Definition at line 251 of file DS_OrderedList.h.

    {
        return orderedList[position];
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
unsigned DataStructures::OrderedList< key_type, data_type, default_comparison_function >::Remove ( const key_type &  key,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
)

Definition at line 187 of file DS_OrderedList.h.

References RakAssert.

    {
        bool objectExists;
        unsigned index;
        index = GetIndexFromKey(key, &objectExists, cf);

        // Can't find the element to remove if this assert hits
    //  RakAssert(objectExists==true);
        if (objectExists==false)
        {
            RakAssert(objectExists==true);
            return 0;
        }

        orderedList.RemoveAtIndex(index);
        return index;
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
void DataStructures::OrderedList< key_type, data_type, default_comparison_function >::RemoveAtIndex ( const unsigned  index)

Definition at line 221 of file DS_OrderedList.h.

    {
        orderedList.RemoveAtIndex(index);
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
void DataStructures::OrderedList< key_type, data_type, default_comparison_function >::RemoveFromEnd ( const unsigned  num = 1)

Definition at line 239 of file DS_OrderedList.h.

    {
        orderedList.RemoveFromEnd(num);
    }
template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function>
unsigned DataStructures::OrderedList< key_type, data_type, default_comparison_function >::RemoveIfExists ( const key_type &  key,
int(*)(const key_type &, const data_type &)  cf = default_comparison_function 
)

Definition at line 206 of file DS_OrderedList.h.

    {
        bool objectExists;
        unsigned index;
        index = GetIndexFromKey(key, &objectExists, cf);

        // Can't find the element to remove if this assert hits
        if (objectExists==false)
            return 0;

        orderedList.RemoveAtIndex(index);
        return index;
    }
template<class key_type , class data_type , int(*)(const key_type &, const data_type &) default_comparison_function>
unsigned DataStructures::OrderedList< key_type, data_type, default_comparison_function >::Size ( void  ) const

Definition at line 257 of file DS_OrderedList.h.

    {
        return orderedList.Size();
    }

Member Data Documentation

template<class key_type, class data_type, int(*)(const key_type &, const data_type &) default_comparison_function = defaultOrderedListComparison<key_type, data_type>>
DataStructures::List<data_type> DataStructures::OrderedList< key_type, data_type, default_comparison_function >::orderedList [protected]

Definition at line 58 of file DS_OrderedList.h.

Referenced by DataStructures::OrderedList< key_type, data_type, default_comparison_function >::operator=(), and DataStructures::OrderedList< key_type, data_type, default_comparison_function >::OrderedList().

The documentation for this class was generated from the following file:

Copyright © 2007-2010 by The Shadowrun: Awakened Team. This work is licensed under the GNU Lesser General Public License 3.

GNU Lesser General Public License 3 Sourceforge.net