Elm  1.0
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
elm::genstruct::FragTable< T > Class Template Reference

#include <elm/genstruct/FragTable.h>

Classes

class  Iterator
 

Public Member Functions

 FragTable (int size_pow=8)
 
 FragTable (const FragTable &tab)
 
 ~FragTable (void)
 
int count (void) const
 
bool isEmpty (void) const
 
 operator bool (void) const
 
bool contains (const T &item) const
 
void clear (void)
 
void add (const T &item)
 
template<template< class _ > class C>
void addAll (const C< T > &items)
 
void remove (const T &item)
 
void remove (const Iterator &iter)
 
template<template< class _ > class C>
void removeAll (const C< T > &items)
 
int length (void) const
 
const T & get (int index) const
 
int indexOf (const T &value, int start=0) const
 
int lastIndexOf (const T &value, int start=-1) const
 
const T & operator[] (int index) const
 
void shrink (int length)
 
void set (int index, const T &item)
 
void set (const Iterator &iter, const T &item)
 
T & get (int index)
 
T & operator[] (int index)
 
void insert (int index, const T &item)
 
void insert (const Iterator &iter, const T &item)
 
void removeAt (int index)
 
void removeAt (const Iterator &iter)
 
int alloc (int count)
 
void clean (void)
 
FragTable< T > & operator+= (T value)
 

Detailed Description

template<class T>
class elm::genstruct::FragTable< T >

This container class allows indexed access to its data. It is implemented as expandable fragmented table using a two-level table traversal. The first level table selects a sub-table that contains the actual stored items.

Consequently, the access time is a bit longer than a classic table but small and constant. Yet, the table may be expanded without inducing a copy of already stored content. According the granularity / size of the sub-tables, the place / item count ratio overhead is pretty small : this class is a good candidate for big tables requiring dynamic expansion.

Implemented concepts: concept::MutableArray.

Parameters
TType of stored items.

Constructor & Destructor Documentation

template<class T >
elm::genstruct::FragTable< T >::FragTable ( int  chunk_size = 8)

The constructor of a fragmented table.

Parameters
chunk_size2^chunk_size is the size of sub-tables (default to 256).
template<class T>
elm::genstruct::FragTable< T >::FragTable ( const FragTable< T > &  tab)

Build a fragmented table by copy.

Parameters
tabTable to copy.

References elm::genstruct::FragTable< T >::addAll().

template<class T >
elm::genstruct::FragTable< T >::~FragTable ( void  )

Member Function Documentation

template<class T >
void elm::genstruct::FragTable< T >::add ( const T &  value)

Add an item to the table.

Parameters
valueValue of the item to add.

References elm::value().

Referenced by elm::genstruct::FragTable< T >::addAll().

template<class T>
template<template< class _ > class C>
void elm::genstruct::FragTable< T >::addAll ( const C< T > &  items)

Add a collection of item to the table.

Parameters
itemsItems to add.

References elm::genstruct::FragTable< T >::add().

Referenced by elm::genstruct::FragTable< T >::FragTable().

template<class T >
int elm::genstruct::FragTable< T >::alloc ( int  count)

Allocate the given count of items in sequence in the table and return the index of the first item.

Parameters
countCount of items to allocate.
Returns
Index of the first item.
template<class T>
void elm::genstruct::FragTable< T >::clean ( void  )
template<class T >
void elm::genstruct::FragTable< T >::clear ( void  )

Remove all items from the fragmeted table and release as many memory as possible.

Referenced by elm::genstruct::FragTable< T >::clean().

template<class T>
bool elm::genstruct::FragTable< T >::contains ( const T &  item) const

Test if the table contains the given item.

Parameters
itemItem to look for.
Returns
True if the item is contained in the table, false else.

References elm::genstruct::FragTable< T >::length().

template<class T>
int elm::genstruct::FragTable< T >::count ( void  ) const
template<class T >
const T & elm::genstruct::FragTable< T >::get ( int  index) const

Get the item at the given index.

Warning
It is an error to pass an index greater or equal to the table length.
Parameters
indexIndex of the looked item.
Returns
Item matching the given index.
template<class T >
T & elm::genstruct::FragTable< T >::get ( int  index)

Same as but return a mutable reference.

Parameters
indexIndex of the looked item.
Returns
Reference on the matching item.
template<class T>
int elm::genstruct::FragTable< T >::indexOf ( const T &  value,
int  start = 0 
) const

Get the first index of a value in the array.

Parameters
valueValue to look for.
startStart index to look at (default to 0).
Returns
Index of the first value, -1 if the value is not found.
template<class T >
void elm::genstruct::FragTable< T >::insert ( int  index,
const T &  item 
)

Insert an item at the given position and move the following item in the next indexes.

Parameters
indexIndex to insert to.
itemItem to insert.

References elm::array::set().

Referenced by elm::genstruct::FragTable< T >::insert().

template<class T>
void elm::genstruct::FragTable< T >::insert ( const Iterator iter,
const T &  item 
)

Insert an item at the given position and move the following item in the next indexes.

Parameters
iterLocation to insert to.
itemItem to insert.

References elm::genstruct::FragTable< T >::Iterator::i, and elm::genstruct::FragTable< T >::insert().

template<class T>
bool elm::genstruct::FragTable< T >::isEmpty ( void  ) const

Test if the fragmented table is empty.

Returns
True if it is empty, false else.

References elm::genstruct::Vector< T >::count().

Referenced by elm::genstruct::FragTable< T >::operator bool().

template<class T>
int elm::genstruct::FragTable< T >::lastIndexOf ( const T &  value,
int  start = -1 
) const

Get the last index of a value in the array.

Parameters
valueValue to look for.
startStart index to look back (default to -1 for end of array).
Returns
Index of the last value, -1 if the value is not found.

References elm::genstruct::FragTable< T >::length().

template<class T >
int elm::genstruct::FragTable< T >::length ( void  ) const
template<class T>
elm::genstruct::FragTable< T >::operator bool ( void  ) const

Same as !isEmpty()/

References elm::genstruct::FragTable< T >::isEmpty().

template<class T >
FragTable< T > & elm::genstruct::FragTable< T >::operator+= ( value)

Operator implementing FragTable::add().

Deprecated:
template<class T>
const T& elm::genstruct::FragTable< T >::operator[] ( int  index) const
template<class T>
T & elm::genstruct::FragTable< T >::operator[] ( int  index)

Operator implementing FragTable::get().

template<class T>
void elm::genstruct::FragTable< T >::remove ( const T &  item)

Remove an item from the table.

Parameters
itemItem to remove.
template<class T>
void elm::genstruct::FragTable< T >::remove ( const Iterator iter)

Remove an item pointed by an iterator.

Parameters
iterIterator pointing to the item to remove.

References elm::genstruct::FragTable< T >::removeAt().

template<class T>
template<template< class _ > class C>
void elm::genstruct::FragTable< T >::removeAll ( const C< T > &  items)

Remove a collection of items.

Parameters
itemsItems to remove.
template<class T >
void elm::genstruct::FragTable< T >::removeAt ( int  index)

Remove the item at the given index and shift back following items.

Parameters
indexIndex of the item to remove.

References elm::array::set().

Referenced by elm::genstruct::FragTable< T >::remove().

template<class T>
void elm::genstruct::FragTable< T >::removeAt ( const Iterator iter)

Remove the item at the given location and shift back following items.

Parameters
iterLocation of the item to remove.

References elm::genstruct::FragTable< T >::Iterator::i, and elm::genstruct::FragTable< T >::removeAt().

Referenced by elm::genstruct::FragTable< T >::removeAt().

template<class T >
void elm::genstruct::FragTable< T >::set ( int  index,
const T &  item 
)

References elm::value().

template<class T>
void elm::genstruct::FragTable< T >::set ( const Iterator iter,
const T &  item 
)
template<class T >
void elm::genstruct::FragTable< T >::shrink ( int  length)

Shrink the size of the table.

Parameters
lengthNew length of the table.

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