Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
Support algorithms and datastructures

Topics

 Simple thread and synchronization support

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...

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

◆ RandomGenerator

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

◆ insertion() [1/2]

template<class Type, class Less>
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&)
View & operator()(View &x)
Integer-precision integer scale view.
Definition view.hpp:632

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.

Definition at line 185 of file sort.hpp.

◆ insertion() [2/2]

template<class Type>
void Gecode::Support::insertion ( Type * x,
int n )
inline

Insertion sort.

Sorts by insertion the n first elements of array x according to the order <.

The algorithm is largely based on the following book: Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.

Definition at line 205 of file sort.hpp.

◆ quicksort() [1/2]

template<class Type, class Less>
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.

Definition at line 230 of file sort.hpp.

◆ quicksort() [2/2]

template<class Type>
void Gecode::Support::quicksort ( Type * x,
int n )
inline

Quicksort.

Sorts with quicksort the n first elements of array x according to the order <.

The algorithm is largely based on the following book: Robert Sedgewick, Algorithms in C++, 3rd edition, 1998, Addison Wesley.

Definition at line 252 of file sort.hpp.