base::SortedArray

base::SortedArray< T, CONTAINER > Class Template Reference

Sorted array that provides read-only operator[]. More...

#include <base_types_array.hh>

List of all members.

Public Types

typedef T Type

Public Member Functions

 SortedArray (const uint size_=0)
 SortedArray (const SortedArray< T > &src)
 ~SortedArray ()
const T & operator[] (uint i) const
SortedArray< T > & operator= (const SortedArray< T > &src)
bool operator== (const SortedArray< T > &src) const
bool operator!= (const SortedArray< T > &src) const
bool operator< (const SortedArray< T > &src) const
uint size (void) const
void resize (const uint size_)
void clear (void)
bool empty (void) const
pair< bool, uint > find (const T item) const
pair< bool, uint > find_first (const T item) const
 
Returns:
Finds the FIRST equal item, (true,index), or (false,undefined).

pair< bool, uint > find_last (const T item) const
 
Returns:
Finds the LAST equal item, (true,index), or (false,undefined).

uint insert_last (const T item)
void remove_idx (const uint idx)
 Directly remove one item by its index.
pair< bool, uint > remove_first (const T item)

Private Attributes

CONTAINER mArray

Detailed Description

template<typename T, typename CONTAINER = vector<T>>
class base::SortedArray< T, CONTAINER >

Sorted array that provides read-only operator[].

This is implemented by a STL vector that stays sorted. Elements can be inserted and removed. Intentionally, only the const operator[] is provided, to encourage using insert() instead of writing by operator[].

insert() inserts a item in sorted order. The order of equal items is the chronological order they were inserted (the newest equal item will follow older equal items).

Graph depends on this order of insertion for younger sibling nodes to follow older siblings.

Member Typedef Documentation

template<typename T, typename CONTAINER = vector<T>>
typedef T base::SortedArray< T, CONTAINER >::Type

Constructor & Destructor Documentation

template<typename T, typename CONTAINER = vector<T>>
base::SortedArray< T, CONTAINER >::SortedArray ( const uint  size_ = 0  )  [inline]

template<typename T, typename CONTAINER = vector<T>>
base::SortedArray< T, CONTAINER >::SortedArray ( const SortedArray< T > &  src  )  [inline]

template<typename T, typename CONTAINER = vector<T>>
base::SortedArray< T, CONTAINER >::~SortedArray (  )  [inline]

Member Function Documentation

template<typename T, typename CONTAINER = vector<T>>
const T& base::SortedArray< T, CONTAINER >::operator[] ( uint  i  )  const [inline]

template<typename T, typename CONTAINER = vector<T>>
SortedArray<T>& base::SortedArray< T, CONTAINER >::operator= ( const SortedArray< T > &  src  )  [inline]

template<typename T, typename CONTAINER = vector<T>>
bool base::SortedArray< T, CONTAINER >::operator== ( const SortedArray< T > &  src  )  const [inline]

template<typename T, typename CONTAINER = vector<T>>
bool base::SortedArray< T, CONTAINER >::operator!= ( const SortedArray< T > &  src  )  const [inline]

template<typename T, typename CONTAINER = vector<T>>
bool base::SortedArray< T, CONTAINER >::operator< ( const SortedArray< T > &  src  )  const [inline]

template<typename T, typename CONTAINER = vector<T>>
uint base::SortedArray< T, CONTAINER >::size ( void   )  const [inline]

template<typename T, typename CONTAINER = vector<T>>
void base::SortedArray< T, CONTAINER >::resize ( const uint  size_  )  [inline]

template<typename T, typename CONTAINER = vector<T>>
void base::SortedArray< T, CONTAINER >::clear ( void   )  [inline]

template<typename T, typename CONTAINER = vector<T>>
bool base::SortedArray< T, CONTAINER >::empty ( void   )  const [inline]

template<typename T, typename CONTAINER = vector<T>>
pair<bool,uint> base::SortedArray< T, CONTAINER >::find ( const T  item  )  const [inline]

Returns:
Finds WHICHEVER equal item, (true,index), or (false,undefined). Which equal item binary search will choose is unpredictable (varies with size/values of haystack). --------------------------------------------------------------------------------------- "Foolish hobbit! Binary search is a simple algorithm but difficult to code correctly!", said Gandalf to Frodo. ---------------------------------------------------------------------------------------
  • (a,z) defines the range same as STL (begin,end). Hence, (z - a == 1) means nothing, so (z - a > 1) breaks.
  • The loop which splits the range requires the item to be inside.
  • An array with one item is a special-case (the while loop would never iterate).

template<typename T, typename CONTAINER = vector<T>>
pair<bool,uint> base::SortedArray< T, CONTAINER >::find_first ( const T  item  )  const [inline]

Returns:
Finds the FIRST equal item, (true,index), or (false,undefined).

template<typename T, typename CONTAINER = vector<T>>
pair<bool,uint> base::SortedArray< T, CONTAINER >::find_last ( const T  item  )  const [inline]

Returns:
Finds the LAST equal item, (true,index), or (false,undefined).

template<typename T, typename CONTAINER = vector<T>>
uint base::SortedArray< T, CONTAINER >::insert_last ( const T  item  )  [inline]

Insert item according to order.

Returns:
Index of inserted item. If existing items are equal, the incoming item is inserted after them (last). Thus, the order among equal items is the chronological order they were inserted.

template<typename T, typename CONTAINER = vector<T>>
void base::SortedArray< T, CONTAINER >::remove_idx ( const uint  idx  )  [inline]

Directly remove one item by its index.

template<typename T, typename CONTAINER = vector<T>>
pair<bool,uint> base::SortedArray< T, CONTAINER >::remove_first ( const T  item  )  [inline]

Removes the first item having an equal value.

Returns:
(bool,idx) if item was removed, (false,undefined) if item was absent.

Member Data Documentation

template<typename T, typename CONTAINER = vector<T>>
CONTAINER base::SortedArray< T, CONTAINER >::mArray [private]

The documentation for this class was generated from the following file: Palomino 3D Engine documents generated by doxygen 1.5.3 on Fri Nov 23 11:26:20 2007