Data Structures

Classes
class	GenTree< T, K, C, A >
class	Set< T, C >
class	Map< K, T, C, E, A >
class	Queue< T, C, A >
class	StrictMapDelegate< C >
class	EquivManager< T, E, A >
class	CompareManager< T, C, E, A >
class	HashManager< K, H, A >
class	ArrayDelegate< C, I, T >
class	MapDelegate< C, I, T, D >
class	Bag< T >
class	Slice< C >
class	Array< T >
class	AllocArray< T >
class	BiDiList< T, E, A >
class	BinomialQueue< T, C, A >
class	FragTable< T, E, A >
class	HashTable< T, H, A >
class	HashMap< K, T, H, A, E >
class	HashSet< T, H, A >
class	List< T, E, A >
class	ListQueue< T, M >
class	class
class	SortedList< T, C, A >
class	ListSet< T, C, A >
class	ListMapManager
class	ListMap< K, T, C, E, A >
class	StaticStack< T, N >
class	Vector< T, E, A >
class	PreIterator< I, T >
class	InplacePreIterator< I, T >
class	PreIter< I, T >
class	ConstPreIter< I, T >
class	MutPreIter< I, T >

Functions
template<class A , class C = Comparator<typename A::t>>
void	quicksort (A &array, const C &c=Comparator< typename A::t >())
template<class C , class P >
int	count (const C &c, const P &p)
template<class C , class P >
bool	forall (const C &c, const P &p)
template<class C , class P >
bool	exists (const C &c, const P &p)
template<class C , class F , class D >
void	map (const C &c, const F &f, D &d)
template<class C , class F >
void	iter (const C &c, const F &f)
template<class C >
C::t	sum (const C &c)
template<class C >
C::t	product (const C &c)
template<class C >
void	fill (C &c, int n, const typename C::t v=type_info< typename C::t >::null)
template<class C1 , class C2 >
bool	equals (const C1 &c1, const C2 &c2)
template<class C1 , class C2 >
Pair< typename C1::Iter, typename C2::Iter >	mismatch (const C1 &c1, const C2 &c2)
template<class C >
void	deleteAll (const C &c)
template<class C1 , class C2 , class P >
Pair< typename C1::Iter, typename C2::Iter >	mismatch (const C1 &c1, const C2 &c2, P p)
template<class T >
Array< T >	_array (int n, T t[])
template<class I >
Range< I >	range (const I &begin, const I &end)

Detailed Description

Principles

This module groups together classes implementing storage data structure. It is new in ELM 2.0 and try to extend and to make easier the use of classes from the old Old Data Structures module. The main differences includes:

• shorter names for classes and for iterators,
• included in the main elm name space,
• more STL compliance,
• more operators overloading,
• versatile system for configuration (comparator, allocator, etc).

In addition, their documentation includes several topic allowing a better understanding of their work to help choosing the better data structure:

• complexity (average and worst) of basic operations like add and remove,
• basic memory and element relative memory foot print.

As for old data structures, the following topics applies:

• concepts implemented by the data structure are provided,
• a data structure must not be modified while an iterator is active on it unless specific methods are provided.

Selecting a data structure

This sections aims to help a developer to select a data structure fittings his needs. They are sorted according to different criteria: the right data structure to use is the one matching most of them. The criteria includes access type, collection size, etc.

Collection size:

• fixed – Array, BitVector, StaticStack
• small – Vector, VectorQueue
• medium – List, SortedList, BiDiList, TreeBag, TreeMap
• big – FragTable, avl::Tree, avl::Map, avl::Set, ListQueue, HashMap, HashSet

Access type:

• indexed – Vector, FragTable
• sequential – Vector, List, SortedList, BiDiList, FragTable, avl::Tree
• fast lookup – avl::Tree, TreeBag, SortedList
• key access – ListMap, HashMap, avl::Map, TreeMap

Modification type:

• append – Vector, FragTable, BiDiList
• prepend – List
• push / pop (stack) – StaticStack, Vector, List, BiDiList, FragTable
• append / remove first (queue) – BiDiList, VectorQueue, ListQueue
• random – List, BiDiList
• uniqueness of elements (set) – ListSet, avl::Set, HashSet
• key access (map) – ListMap, HashMap, avl::Map, TreeMap
• inter-set operation (efficient) – BitVector

Memory footprint:

• light – Array, Vector, VectorQueue, BitVector, StaticStack, List, ListQueue, SortedList, ListMap
• medium – BiDiList, TreeBag, TreeMap, avl::Tree, avl::Map, avl::Set, FragTable
• heavy at startup – HashTable, HashMap, HashSet

The array below sum up the complexity of operations for the data structures described above. When 2 complexity are give o1/o2, o1 is the average case and o2 the worst case.

For simple collections, we get:

Data Structure	adding	lookup	insertion	removal
Vector	O(1)	O(n)	O(n)	O(n)
List	O(1)	O(n)	O(1)	O(1)
BiDiList	O(1)	O(n)	O(1)	O(1)
ListBag	O(log(n))/O(n)	O(log(n))/O(n)	O(1)	O(1)
FragTable	O(1)	O(n)	O(n)	O(n)
HashTable	O(b)	O(b)	O(1)	O(1)
HashSet	O(b)	O(b)	O(1)	O(1)
avl::Tree	O(log(n))	O(log(n))	O(1)	O(log(n))
avl::Set	O(log(n))	O(log(n))	O(1)	O(log(n))

• n – number of elements in the data structure
• b – number of elements in a bucket of a hash table
• adding – simple addition any way in the data structure
• lookup – look up of a particular element
• insertion – insertion relative at an iterator position
• removal – removal relative of an element pointed by an iterator

Map operations:

Data Structure	lookup	insertion	removal
HashMap	O(b)	O(b)	O(b)
avl::Map	O(log(n))	O(log(n))	O(log(n))
TreeMap	O(log(n))/O(n)	O(log(n))/O(n)	O(log(n))/O(n)
ListMap	O(n)	O(n)	O(n)

• n – number of elements in the data structure
• b – number of elements in a bucket of a hash table
• lookup – look up of a particular element
• insertion – insertion in the map (including lookup)
• removal – removal from the map (including lookup)

Random access to array elements:

Data Structure	Indexed Access
Array	O(1)
FragTable	O(1)
Vector	O(1)
List	O(n)
BiDiList	O(n)

Stack (LIFO) operations:

Data Structure	push	pop
Vector	O(1)	O(1)
List	O(1)	O(1)
BiDiList	O(1)	O(1)
FragTable	O(1)	O(1)

Queue (FIFO) operations:

Data Structure	put	get
Vector	O(n)	O(1)
List	O(1)	O(n)
BiDiList	O(1)	O(1)
FragTable	O(n)	O(1)
VectorQueue	O(1)	O(1)
ListQueue	O(1)	O(1)
BinomialQueue	O(1)	O(log(n))

Set operations:

Data Structure	join	meet	difference
HashSet	O(bn)	O(bn)	O(bn)
avl::Set	O(n)	O(n)	O(n)
BitVector	O(n)	O(n)	O(n)

Priority queues:

Data Structure	put	get
BinomialQueue	O(1)	O(log(n))
SortedList	O(n)	O(1)

Iterator Helper Classes

#include <elm/PreIterator.h>

Basically, the PreIterator function avoids rewriting the large number of operator overloading. In fact, only the constructor and 3 functions need to be written:

• ended() tests if the iterator is ended,
• item() returns the currently pointer item,
• next() passes to the next item if iterated collection.

Therefore, an iterator must be written as below (with T the type of iterated items):

class MyIter: public PreIterator<MyIter, T> {
public:
    MyIter(...) { ... };
    inline bool ended(void) const { return ...; }
    inline const T& item(void) const { return ...; }
    inline void next(void) { ... }
    inline bool equals(const MyIter& i) { ... }
private:
    ...
};

And the use of such an iterator becomes:

for(MyIter i(...); i(); ++i)
    use(*i);

Notices that if T is a pointer, the arrow iterator may be used without a star:

for(MyIter i(...); i(); ++i)
    use(i->to_something);

Likely, PreIterator provides automatic conversion to T:

for(MyIter i(...); i(); ++i) {
    T v = i;
    ...
}

Beside, PreIterator provides also a way to use iterators as in the STL. You have to provide a equals() function to test for equality:

class MyIter: public PreIterator<MyIter, T> {
public:
    MyIter(...) { ... };
    inline bool ended(void) const { return ...; }
    inline const T& item(void) const { return ...; }
    inline void next(void) { ... }
    inline bool compare(const MyIter& i) { return ...; }
private:
    ...
};

And now the iteration can be written (with begin() the function returning the initial iterator and end() the end iterator):

for(auto i = begin(); i != end(); ++i)
   use(*i);

A very fast and intuitive way to perform iteration on a collection of items proposed by C++ 11 requires a couple of begin() and end() functions declared in a collection object coll:

for(auto i: coll)
use(i);

Notice that i is of type T, the type of iterated elements. As this is very convenient, all ELM data classes provide begin() and end() functions.

The following classes may help to work or to extend the concrete data structures:

• elm::Bag – a lightweight collection containing a fix number of elements,
• elm::Slice – provide an array view on a slice of a bigger array data structure.

Helper functions

<elm/data/quicksort.h> provides a quicksort implementation for data collections:

• void elm::quicksort(A<T>& array, const C& c)

Other functions provides very generic processing over the collection. They generically takes as parameter a collection, a class providing some specific computation and comes in two flavors, with or without an additional argument. To use them, one has to include <elm/data/util.h>:

• count(const C& c, const P& p) – count the number of items satisfying a predicate p,
• forall(const C& c, const P& p) – returns true if all items satisfy the predicate p,
• exists(const C& c, const P& p) – return true if at least one item satifies the predicate p,
• find(I i, const P& p) – starting from an iterator, move it to the end or the first item satisfying the predicate p,
• map(const C& c, const F& f, D& d) – copy collection c to d after transformation by f,
• fold(const C& c, const F& f, T t) – iterate over collection c and use f to accumulate the value of items,
• equals(const C1& c1, const C2& c2) – test if two collections are equal,
• mismatch(const C1& c1, const C2& c2) – find the first mismatch between two collections,
• mismatch(const C1& c1, const C2& c2, P p) – find the first mismatch between two collections according to predicate p,
• deleteAll(const C& c) – delete all items of pointer collection c,
• fill(C& c, int n, const typename C::t v) – fill the collection c with n items of value v,

Other functions provides specialized iterators:

• nrange(T i, T j, T s) – creates a pseudo- numeric collection ranging from b to e,
• select_iter(const I& i, const P& p) – creates a pseudo-collection containing values of p satisfying predicate p,
• subiter(const I& b, const I& e) – create a sub-iterator between the given begin iterator and ending iterator e (exclusive).

Other functions and classes are provided for easier combination:

• sum(const C& c) – compute sum of element of c,
• product(const C& c) – compute product of elements of c,
• Add – class providing addition in operator ()(x, y),
• Mul – class providing multiplication in operator ()(x, y),
• true_pred – predicate always evaluating to true.

Delegate Classes

Delegate class in ELM allows to get references on value managed by specific class functions to ensure their access or their assignment.

They support the same operations as the C++ references:

• to access the value, they may be used as is (automatic conversion) or with the star '*' operator,
• to change the value, the assignment '=' operator may be used.

The following delegates exists:

• elm::ArrayDelegate allows to use values from a elm::concept::MutableArray whose access is based on get()/set() methods and an index,

• elm::MapDelegate allows to use values from a elm::concept::MutableMap whose access is based on get()/put() methods and an identifier.

• elm::StrictMapDelegate is like MapDelegate but thow a KeyError exception if a non-existing key is used.

Customizing the work

Common customization of container classes includes the memory allocation, the element comparison or hashing.

Basically, the customization can be declared static and passed to the container using class templates:

class MyComparator { ... };
 
AContainer<int, MyComparator> container;

In this case, the memory cost for such a customization is zero.

If the customization requires an instance, the instance has to be passed also to the constructor of the container. In this case, the container inherits from the customization class and this one must support a copy constructor where is passed the instance:

class MyComparator {
public:
    MyComparator(const MyComparator& i) { ... }
};
MyComparator my_comparator_instance;
 
AContainer<int, MyComparator> container(my_comprator);

In this case, the container size grows according to the size of the instance customization class.

To support this behavior, delegate classes may help:. For instance, DefaultAllocator class provides access to OS allocation but it is passed by default to container as DefaultAllocatorDelegate that just propagate allocation to the default allocator.

The following delegate classes exist:

• DefaultAllocatorDelegate
• AllocatorDelegate
• HashKeyDelegate
• ComparatorDelegate
• EquivDelegate

Function Documentation

_array()

Array< T > _array ( int  n, T  t[]  )

inline

#include <include/elm/data/Array.h>

Short way to build an Array of type T.

Parameters

n	Array element count.
t	Array element buffer.

See also

Array

count()

int count ( const C &  c, const P &  p  )

inline

#include <include/elm/data/util.h>

Count the number of elements of c that matches the predicate p.

Parameters

c	Collection to count in (must implement concept::Collection).
p	Predicate to test element (must implement concept::Predicate).

References elm::io::p().

Referenced by Tree::count(), JobScheduler::setThreadCount(), and InstanceType::typeFor().

deleteAll()

void deleteAll ( const C &  c )

inline

#include <include/elm/data/util.h>

Consider that c is a collection of pointers and call the deletion on each of these pointers.

Parameters

c	Collection of pointers to delete.
C	Type of collection.

equals()

bool equals ( const C1 &  c1, const C2 &  c2  )

inline

#include <include/elm/data/util.h>

Test if two collections are equals.

Parameters

c1	First collection.
c2	Second collection.

Returns

True if both collection are equal, false else.

Parameters

C1	Type of first collection.
C2	Type of second collection.

Referenced by VectorQueue< elm::Pair >::contains(), ArrayList< T, E >::contains(), AssocEquiv< K, T, E >::equals(), Vector< elm::dtd::AbstractAttribute * >::equals(), ArrayList< T, E >::find(), Vector< elm::dtd::AbstractAttribute * >::find(), ArrayList< T, E >::indexOf(), EqualsEquiv< T >::isEqual(), HashKey< T * >::isEqual(), HashKey< const T * >::isEqual(), ArrayList< T, E >::lastIndexOf(), and ArrayList< T, E >::remove().

exists()

bool exists ( const C &  c, const P &  p  )

inline

#include <include/elm/data/util.h>

Test if the predicate p is true at least for one element of c.

Parameters

c	Collection to test (must implement concept::Collection).
p	Predicate to evaluate (must implement concept::Predicate).

Returns

True if at least one element is true for predicate p.

References elm::io::p().

fill()

void fill ( C &  c, int  n, const typename C::t  v = type_info<typename C::t>::null  )

inline

#include <include/elm/data/util.h>

Add n items of value v to to the collection c.

Parameters

c	Collection add values to.
n	Number of values to add.
v	Value to add (as a default, the null value).

Referenced by WAHVector::clear(), builder::fix(), builder::pushLite(), WAHVector::set(), and WAHVector::WAHVector().

forall()

bool forall ( const C &  c, const P &  p  )

inline

#include <include/elm/data/util.h>

Test if the predicate p is true for each element of c.

Parameters

c	Collection to test (must implement concept::Collection).
p	Predicate to evaluate (must implement concept::Predicate).

Returns

True if the predicate p is true for all element of c.

References elm::io::p().

iter()

void iter ( const C &  c, const F &  f  )

inline

#include <include/elm/data/util.h>

Apply the function f on the element of collection c (ignoring the result).

Parameters

c	Collection to iterate on (must implement concept::Collection).
f	Function to apply (must implement concept::Function).

Referenced by ArrayList< T, E >::addAll(), Tree::addAll(), BiDiList< T, E, A >::contains(), List< Pair< K, T >, CompareEquiv< AssocComparator< K, T, Comparator< K > > >, DefaultAlloc >::contains(), ArrayList< T, E >::containsAll(), Manager::displayHelp(), SortedList< Pair< string, Section * >, AssocComparator< string, Section *, Comparator< string > >, DefaultAlloc >::find(), MarkerBuilder< K, T, C >::make(), SegmentBuilder< K, T, C >::make(), ArrayList< T, E >::removeAll(), Tree::removeAll(), CollectionSerializer< Vector< T >, T >::serialize(), DataSerializer< Vector< T, M >, T >::serialize(), and CollecAC< Coll, T >::serialize().

map()

void map ( const C &  c, const F &  f, D &  d  )

inline

#include <include/elm/data/util.h>

Map the elements of a collection to element of another collection using the function f.

Parameters

c	Original collection (must implement concept::Collection).
f	Transforming function (must implement concept::Function).
d	Filled collection (must implement concept::MutableCollection).

Referenced by Map< Pair< K, K >, T, segment_comparator_t >::copy(), Map< Pair< K, K >, T, segment_comparator_t >::equals(), Map< Pair< K, K >, T, segment_comparator_t >::operator!=(), Map< Pair< K, K >, T, segment_comparator_t >::operator=(), and Map< Pair< K, K >, T, segment_comparator_t >::operator==().

mismatch() [1/2]

Pair< typename C1::Iter, typename C2::Iter > mismatch	(	const C1 &	c1,
		const C2 &	c2
	)

#include <include/elm/data/util.h>

Find the point of difference of two collection. Starting from the first element of the two collections, progress until either finding the end of a collection, or until the first different element of the collections.

Parameters

c1	First collection.
c2	Second collection.

Returns

Pair of iterators to the difference point (if any).

Parameters

C1	Type of first collection.
C2	Type of second collection.

References elm::pair().

mismatch() [2/2]

Pair< typename C1::Iter, typename C2::Iter > mismatch	(	const C1 &	c1,
		const C2 &	c2,
		P	p
	)

#include <include/elm/data/util.h>

Find the point of difference of two collection. Starting from the first element of the two collections, progress until either finding the end of a collection, or until the first different element of the collections. To test if two elements matches or not, the function p is used.

Parameters

c1	First collection.
c2	Second collection.
p	Match predicate to decide if two elements are different. Must support the call p(element1, element2).

Returns

Pair of iterators to the difference point (if any).

Parameters

C1	Type of first collection.
C2	Type of second collection.
P	Type of predicate.

References elm::io::p(), and elm::pair().

product()

typename C::t product ( const C &  c )

inline

#include <include/elm/data/util.h>

Perform the product of the items of collection c. An implementation of operator '*' must exist for these items.

Parameters

c	Collection to multiply together.

Returns

Result of item product.

References elm::fold(), and elm::io::p().

quicksort()

void quicksort	(	A &	array,
		const C &	c = Comparator<typename A::t>()
	)

#include <include/elm/data/quicksort.h>

s

Sort the given array using quicksort algorithm (average complexity O(N log(N)) ).

Parameters

array	Array containing the values to sort.
c	Comparator to use (rely on ELM default comparator if not provided).
T	Type of values.
A	Type of array (must implement Array concept).
C	Type of comparator (must implement Comparator or Compare concept).

References elm::max(), and elm::swap().

range()

Range< I > range	(	const I &	begin,
		const I &	end
	)

#include <include/elm/data/Range.h>

Creates a range from the iterator b to iterator e.

Parameters

b	First position of the range (inclusive).
e	One position after the last position of the range (exclusive).

Returns

Range from b to e.

Fast way to build a range.

Parameters

begin	Iterator on the first element of the collection.
end	End iterator past the last element of the collection (may be ended).

Returns

Built range.

See also

Range

Referenced by Plugger::available(), and elm::select().

sum()

typename C::t sum ( const C &  c )

inline

#include <include/elm/data/util.h>

Perform the sum of the items of collection c. An implementation of operator '+' must exist for these items.

Parameters

c	Collection to sum up.

Returns

Result of item sum.

References elm::fold().