#include <elm/data/FragTable.h>

Inheritance diagram for FragTable< T, E, A >:

Classes
class	BaseIter

class	Iter

class	MutIter

Public Types
typedef T	t

typedef FragTable< T, E, A >	self_t

Public Types inherited from Equiv< T >
typedef T	t

Public Member Functions
	FragTable (int size_pow=8)

	FragTable (const FragTable &t)

	~FragTable (void)

int	pageSize () const

int	pagePower () const

bool	pageFull () const

Iter	begin () const

Iter	end () const

int	count (void) const

bool	contains (const T &v) const

template<class C >
bool	containsAll (const C &c) const

bool	isEmpty () const

	operator bool (void) const

Iter	items (void) const

Iter	operator* (void) const

	operator Iter (void) const

bool	equals (const self_t &t) const

bool	operator== (const self_t &t) const

bool	operator!= (const self_t &t) const

MutIter	begin ()

MutIter	end ()

void	clear (void)

void	add (const T &value)

template<template< class _ > class C>
void	addAll (const C< T > &items)

void	remove (const T &item)

template<template< class _ > class C>
void	removeAll (const C< T > &items)

void	remove (const Iter &iter)

self_t &	operator+= (const T &v)

self_t &	operator-= (const T &v)

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 &value)

void	set (const Iter &iter, const T &item)

T &	get (int index)

T &	operator[] (int index)

void	insert (int index, const T &item)

void	insert (const Iter &iter, const T &item)

void	removeAt (int index)

void	removeAt (const Iter &iter)

int	alloc (int count)

Public Member Functions inherited from Equiv< T >
bool	isEqual (const T &v1, const T &v2) const

Public Member Functions inherited from DefaultAllocatorDelegate
t::ptr	allocate (t::size size) const

void	free (t::ptr p) const

template<class T >
T *	alloc () const

Additional Inherited Members
Static Public Member Functions inherited from Equiv< T >
static bool	equals (const T &v1, const T &v2)

Static Public Attributes inherited from Equiv< T >
static Equiv< T >	def

Detailed Description

template<class T, class E = Equiv<T>, class A = DefaultAlloc>
class elm::FragTable< T, E, A >

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.

Complexity information (N items, chunks of size S):

access time: O(0)
addition time: O(0)
insertion time: O(N/2) average, O(N) worst case
removal time: O(N/2) average, O(N) worst case
object memory footprint: 6 ints + 8 pointers
per-item memory foot print: |N / S| pointers

Implemented concepts:

Parameters

T	Type of stored items.
M	Type of the data structure manager (default to EquivManager).

Member Typedef Documentation

◆ self_t

typedef FragTable<T, E, A> self_t

◆ t

typedef T t

Constructor & Destructor Documentation

◆ FragTable() [1/2]

FragTable ( int chunk_size = 8 )

inline

The constructor of a fragmented table.

Parameters

chunk_size 2^chunk_size is the size of sub-tables (default to 256).

◆ FragTable() [2/2]

FragTable ( const FragTable< T, E, A > & tab )

inline

Build a fragmented table by copy.

Parameters

tab	Table to copy.

References FragTable< T, E, A >::addAll().

◆ ~FragTable()

~FragTable ( void )

inline

References FragTable< T, E, A >::clear().

Member Function Documentation

◆ add()

void add ( const T & value )

inline

Add an item to the table.

Parameters

value Value of the item to add.

Referenced by FragTable< T, E, A >::addAll(), and FragTable< T, E, A >::operator+=().

◆ addAll()

void addAll ( const C< T > & items )

inline

Add a collection of item to the table.

Parameters

items Items to add.

References FragTable< T, E, A >::add(), and FragTable< T, E, A >::items().

Referenced by FragTable< T, E, A >::FragTable().

◆ alloc()

int alloc ( int count )

inline

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

Parameters

count Count of items to allocate.

Returns: Index of the first item.

References FragTable< T, E, A >::count(), and FragTable< T, E, A >::length().

◆ begin() [1/2]

MutIter begin ( )

inline

◆ begin() [2/2]

Iter begin ( ) const

inline

References FragTable< T, E, A >::items().

Referenced by FragTable< T, E, A >::equals().

◆ clear()

void clear ( void )

inline

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

Referenced by FragTable< T, E, A >::~FragTable().

◆ contains()

bool contains ( const T & item ) const

inline

Test if the table contains the given item.

Parameters

item	Item to look for.

Returns: True if the item is contained in the table, false else.

References FragTable< T, E, A >::get(), and FragTable< T, E, A >::length().

Referenced by FragTable< T, E, A >::containsAll(), and elm::operator<=().

◆ containsAll()

bool containsAll ( const C & c ) const

inline

References FragTable< T, E, A >::contains().

◆ count()

int count ( void ) const

inline

Same as @length().

References FragTable< T, E, A >::length().

Referenced by FragTable< T, E, A >::alloc(), and FragTable< T, E, A >::end().

◆ end() [1/2]

MutIter end ( )

inline

References FragTable< T, E, A >::count().

◆ end() [2/2]

Iter end ( ) const

inline

References FragTable< T, E, A >::count().

◆ equals()

bool equals ( const self_t & t ) const

inline

References FragTable< T, E, A >::begin().

Referenced by FragTable< T, E, A >::operator!=(), and FragTable< T, E, A >::operator==().

◆ get() [1/2]

T & get ( int index )

inline

Same as FragTable::get() const but return a mutable reference.

Parameters

index Index of the looked item.

Returns: Reference on the matching item.

References FragTable< T, E, A >::length().

◆ get() [2/2]

const T & get ( int index ) const

inline

Get the item at the given index.

Warning: It is an error to pass an index greater or equal to the table length.

Parameters

index Index of the looked item.

Returns: Item matching the given index.

References FragTable< T, E, A >::length().

Referenced by FragTable< T, E, A >::contains(), FragTable< T, E, A >::insert(), FragTable< T, E, A >::BaseIter::item(), FragTable< T, E, A >::Iter::item(), FragTable< T, E, A >::MutIter::item(), FragTable< T, E, A >::lastIndexOf(), FragTable< T, E, A >::operator[](), and FragTable< T, E, A >::removeAt().

◆ indexOf()

int indexOf	(	const T &	value,
		int	start = `0`
	)		const

inline

Get the first index of a value in the array.

Parameters

value	Value to look for.
start	Start index to look at (default to 0).

Returns: Index of the first value, -1 if the value is not found.

◆ insert() [1/2]

void insert	(	const Iter &	iter,
		const T &	item
	)

inline

References FragTable< T, E, A >::insert().

◆ insert() [2/2]

void insert	(	int	index,
		const T &	item
	)

inline

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

Parameters

index	Index to insert to.
item	Item to insert.

References DefaultAllocatorDelegate::alloc(), FragTable< T, E, A >::get(), FragTable< T, E, A >::length(), and FragTable< T, E, A >::set().

Referenced by FragTable< T, E, A >::insert().

◆ isEmpty()

bool isEmpty ( ) const

inline

Test if the fragmented table is empty.

Returns: True if it is empty, false else.

Referenced by FragTable< T, E, A >::operator bool().

◆ items()

Iter items ( void ) const

inline

Referenced by FragTable< T, E, A >::addAll(), FragTable< T, E, A >::begin(), FragTable< T, E, A >::operator Iter(), FragTable< T, E, A >::operator*(), and FragTable< T, E, A >::removeAll().

◆ lastIndexOf()

int lastIndexOf	(	const T &	value,
		int	start = `-1`
	)		const

inline

Get the last index of a value in the array.

Parameters

value	Value to look for.
start	Start 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 FragTable< T, E, A >::get(), and FragTable< T, E, A >::length().

◆ length()

int length ( void ) const

inline

Get the length / item count of the table.

Returns: Table length.

Referenced by FragTable< T, E, A >::alloc(), FragTable< T, E, A >::contains(), FragTable< T, E, A >::count(), FragTable< T, E, A >::get(), FragTable< T, E, A >::insert(), FragTable< T, E, A >::lastIndexOf(), FragTable< T, E, A >::removeAt(), FragTable< T, E, A >::set(), and FragTable< T, E, A >::shrink().

◆ operator bool()

operator bool ( void ) const

inline

Same as !isEmpty().

Same as !isEmpty()/

References FragTable< T, E, A >::isEmpty().

◆ operator Iter()

operator Iter ( void ) const

inline

References FragTable< T, E, A >::items().

◆ operator!=()

bool operator!= ( const self_t & t ) const

inline

References FragTable< T, E, A >::equals().

◆ operator*()

Iter operator* ( void ) const

inline

References FragTable< T, E, A >::items().

◆ operator+=()

FragTable< T > & operator+= ( const T & v )

inline

Operator implementing FragTable::add().

Deprecated:

Operator implementing FragTable::add().

Deprecated:

References FragTable< T, E, A >::add().

◆ operator-=()

self_t& operator-= ( const T & v )

inline

References FragTable< T, E, A >::remove().

◆ operator==()

bool operator== ( const self_t & t ) const

inline

References FragTable< T, E, A >::equals().

◆ operator[]() [1/2]

T & operator[] ( int index )

inline

Operator implementing FragTable::get().

References FragTable< T, E, A >::get().

◆ operator[]() [2/2]

const T& operator[] ( int index ) const

inline

References FragTable< T, E, A >::get().

◆ pageFull()

bool pageFull ( ) const

inline

Test if the current page is full.

Returns: True if the page is full, false else.

◆ pagePower()

int pagePower ( ) const

inline

Get the page size as a power of 2.

Returns: Power of 2 page size.

◆ pageSize()

int pageSize ( ) const

inline

Get the page size (in elements).

Returns: Page size (in elements).

◆ remove() [1/2]

void remove ( const Iter & iter )

inline

References FragTable< T, E, A >::removeAt().

◆ remove() [2/2]

void remove ( const T & item )

inline

Remove an item from the table.

Parameters

item	Item to remove.

Referenced by FragTable< T, E, A >::operator-=(), and FragTable< T, E, A >::removeAll().

◆ removeAll()

void removeAll ( const C< T > & items )

inline

Remove a collection of items.

Parameters

items Items to remove.

References FragTable< T, E, A >::items(), and FragTable< T, E, A >::remove().

◆ removeAt() [1/2]

void removeAt ( const Iter & iter )

inline

References FragTable< T, E, A >::removeAt().

Referenced by FragTable< T, E, A >::removeAt().

◆ removeAt() [2/2]

void removeAt ( int index )

inline

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

Parameters

index Index of the item to remove.

References FragTable< T, E, A >::get(), FragTable< T, E, A >::length(), and FragTable< T, E, A >::set().

Referenced by FragTable< T, E, A >::remove().

◆ set() [1/2]

void set	(	const Iter &	iter,
		const T &	item
	)

inline

References FragTable< T, E, A >::set().

Referenced by FragTable< T, E, A >::set().

◆ set() [2/2]

void set	(	int	index,
		const T &	value
	)

inline

References FragTable< T, E, A >::length().

Referenced by FragTable< T, E, A >::insert(), and FragTable< T, E, A >::removeAt().

◆ shrink()

void shrink ( int length )

inline

Shrink the size of the table.

Parameters

length New length of the table.

References FragTable< T, E, A >::length().

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

include/elm/data/FragTable.h
src/data_FragTable.cpp
src/genstruct_FragTable.cpp

Classes

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

template<class T, class E = Equiv<T>, class A = DefaultAlloc> class elm::FragTable< T, E, A >

Member Typedef Documentation

◆ self_t

◆ t

Constructor & Destructor Documentation

◆ FragTable() [1/2]

◆ FragTable() [2/2]

◆ ~FragTable()

Member Function Documentation

◆ add()

◆ addAll()

◆ alloc()

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ contains()

◆ containsAll()

◆ count()

◆ end() [1/2]

◆ end() [2/2]

◆ equals()

◆ get() [1/2]

◆ get() [2/2]

◆ indexOf()

◆ insert() [1/2]

◆ insert() [2/2]

◆ isEmpty()

◆ items()

◆ lastIndexOf()

◆ length()

◆ operator bool()

◆ operator Iter()

◆ operator!=()

◆ operator*()

◆ operator+=()

◆ operator-=()

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pageFull()

◆ pagePower()

◆ pageSize()

◆ remove() [1/2]

◆ remove() [2/2]

◆ removeAll()

◆ removeAt() [1/2]

◆ removeAt() [2/2]

◆ set() [1/2]

◆ set() [2/2]

◆ shrink()

template<class T, class E = Equiv<T>, class A = DefaultAlloc>
class elm::FragTable< T, E, A >