Support algorithms and datastructures
[Common functionality]
Classes | |
class | Gecode::Support::BlockAllocator< T, A, blocksize > |
Manage memory organized into block lists (allocator). More... | |
class | Gecode::Support::BlockClient< T, A, blocksize > |
Client for block allocator of type T. More... | |
class | Gecode::Support::DynamicArray< T, A > |
Array with arbitrary number of elements. More... | |
class | Gecode::Support::DynamicQueue< T, A > |
Queue with arbitrary number of elements. More... | |
class | Gecode::Support::DynamicStack< T, A > |
Stack with arbitrary number of elements. More... | |
class | Gecode::Support::LinearCongruentialGenerator< m, a, q, r > |
Template for linear congruential generators. More... | |
class | Gecode::Support::StaticStack< T, A > |
Stack with fixed number of elements. More... | |
class | Gecode::Support::Timer |
Timer More... | |
Modules | |
Simple thread and synchronization support | |
Typedefs | |
typedef LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > | Gecode::Support::RandomGenerator |
Default values for linear congruential generator. | |
Functions | |
template<class Type , class Less > | |
void | Gecode::Support::insertion (Type *x, int n, Less &l) |
Insertion sort. | |
template<class Type > | |
void | Gecode::Support::insertion (Type *x, int n) |
Insertion sort. | |
template<class Type , class Less > | |
void | Gecode::Support::quicksort (Type *x, int n, Less &l) |
Quicksort. | |
template<class Type > | |
void | Gecode::Support::quicksort (Type *x, int n) |
Quicksort. |
Detailed Description
These are some common datastructures used in the implementation of Gecode. Maybe they can be also useful to others.
In order to use them, one needs to include the appropriate header-file as described in the class and function documentation.
Typedef Documentation
typedef LinearCongruentialGenerator<2147483647, 48271, 44488, 3399> Gecode::Support::RandomGenerator |
Default values for linear congruential generator.
While this pseudo-random number generator is not a good source of randomness, it is still an acceptable choice for many applications. The choice of values is taken from D. E. Knuth, The Art of Computer Programming, Vol 2, Seminumerical Algorithms, 3rd edition.
Definition at line 120 of file random.hpp.
Function Documentation
void Gecode::Support::insertion | ( | Type * | x, | |
int | n, | |||
Less & | l | |||
) | [inline] |
Insertion sort.
Sorts by insertion the n first elements of array x according to the order l as instance of class Less. The class Less must implement the single member function
bool operator ()(const Type&, const Type&)
for comparing elements. Note that the order must be strict, that is: comparing an element with itself must return false.
The algorithm is largely based on the following book: Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.
void Gecode::Support::insertion | ( | Type * | x, | |
int | n | |||
) | [inline] |
void Gecode::Support::quicksort | ( | Type * | x, | |
int | n, | |||
Less & | l | |||
) | [inline] |
Quicksort.
Sorts with quicksort the n first elements of array x according to the order l as instance of class Less. The class Less must implement the single member function
bool operator ()(const Type&, const Type&)
for comparing elements. Note that the order must be strict, that is: comparing an element with itself must return false.
The algorithm is largely based on the following book: Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.
void Gecode::Support::quicksort | ( | Type * | x, | |
int | n | |||
) | [inline] |