bitfield and graph structures from bnc, for priorityqueue and directedgraph amongst things like triangulation algorithms see: http://jonasfj.dk/blog/2010/12/triangulation-project/

bitfield.h

#ifndef CONFIG_H
#define CONFIG_H

#include <stdint.h>
#include <vector>
#include <string.h>
#ifndef __ICC
#include <tr1/unordered_map>
#else
#include <hash_map>
#endif /* __ICC */
#include <assert.h>
#include <string>
#include <limits.h>
using namespace std;

#define USE_BITSCAN

/** Representation of a BitField */
template<size_t size> class BitField {
private:
	/** Definition of underlying type for the bitfield*/
	typedef unsigned int _word;

	/** Number of bits per word */
	static const size_t _bitsPerWord = CHAR_BIT * sizeof(_word);
	
	/** Number of words for bitfield<size> */
	static const size_t _words = (size + _bitsPerWord - 1) / _bitsPerWord;

	/** Word offset for a given position */
	static size_t _wordOffset(size_t pos) {
		return pos / _bitsPerWord;
	}

	/** Bit offset offset for a given position */
	static size_t _bitOffset(size_t pos) {
		return pos % _bitsPerWord;
	}

	/** Bitmask for pos in a word */
	static _word _bitmask(size_t pos) {
		return ((_word)1)<<_bitOffset(pos);
	}

	/** Count trailing zeroes
	 * @remarks: Returns undefined if w == 0
	 */
	static size_t _bitscan(_word w){
		return __builtin_ctz(w);
	}

	static size_t _popcount(_word v){
		//A generalization of the best bit counting method from:
		//http://graphics.stanford.edu/~seander/bithacks.html
		//Please note: This only generalizes upto 128 bit
		assert(_bitsPerWord <= 128);
		v = v - ((v >> 1) & (_word)~(_word)0/3);
		v = (v & (_word)~(_word)0/15*3) + ((v >> 2) & (_word)~(_word)0/15*3);
		v = (v + (v >> 4)) & (_word)~(_word)0/255*15;
		return (_word)(v * ((_word)~(_word)0/255)) >> (sizeof(_word) - 1) * CHAR_BIT;
	}

	/** Underlying word array */
	_word _bits[_words];
public:
	/** Create a new empty bitfield */
	BitField(){
		clear();
	}
	/** Copy create a bitfield from another */
	BitField(const BitField<size>& bf){
		for(size_t i = 0; i < _words; i++)
			_bits[i] = bf._bits[i];
	}

	/** Clear all bits */
	BitField<size>& clear();
	/** Clear bit at position pos */
	BitField<size>& clear(size_t pos);
	/** Test bit at position pos */
	bool test(size_t pos) const;
	/** Set all bits */
	BitField<size>& set();
	/** Set bit a position pos */
	BitField<size>& set(size_t pos);
	/** Set bit a position pos to value */
	BitField<size>& set(size_t pos, bool value);
	/** Flip all bits */
	BitField<size>& flip();
	/** Flip bit at position pos */
	BitField<size>& flip(size_t pos);
	/** Test if any bit is set */
	bool any() const;
	/** Test if no bits are set */
	bool none() const;
	/** Count the number of high bits */
	size_t count() const;

	BitField<size>& operator&= (const BitField<size>& rhs);
	BitField<size>& operator|= (const BitField<size>& rhs);
	BitField<size>& operator^= (const BitField<size>& rhs);

	BitField<size> operator~() const;

	bool operator== (const BitField<size>& rhs) const;
	bool operator!= (const BitField<size>& rhs) const;

	/** Iterator over the high bits in a BitField */
	class BitIterator{
	private:
		const BitField<size>& _bf;
		size_t _pos;
	public:
		BitIterator(const BitField<size>& bf) : _bf(bf) {
			reset();
		}
		bool operator++(int){
		#ifdef USE_BITSCAN
			_pos++;
			_word w = _bf._bits[_wordOffset(_pos)];
			//Discard bits lower than _pos
			w &= (~(_word)0) << _bitOffset(_pos);
			//Check the first word
			if(w != (_word)0){
				_pos = _bitscan(w) + _wordOffset(_pos) * _bitsPerWord;
				return true;
			}
			//Check all the following words
			for(size_t i = _wordOffset(_pos) + 1; i < _words; i++){
				w = _bf._bits[i];
				if(w != 0){
					_pos = _bitscan(w) + i * _bitsPerWord ;
					return true;
				}
			}
			_pos = -1;
			return false;
		#else
			do
				_pos++;
			while(_pos < size && !_bf.test(_pos));
			return _pos < size;
		#endif /* USE_BITSCAN */
		}
		size_t operator*(){
			return _pos;
		}
		/** Reset the BitIterator */
		void reset(){
			_pos = -1;
		}
	};

#ifndef __ICC
	template<typename> friend struct std::tr1::hash;
#else
	template<size_t> friend struct BitFieldHasher;
#endif /* __ICC */
};

#ifndef __ICC

namespace std {
	namespace tr1{
		/** Template specialization of std::tr1::hash<> for BitField<size> */
		template<size_t size>
		struct hash< BitField<size> > : public unary_function<BitField<size>, size_t>{
			size_t operator()(const BitField<size>& bf) const{
				size_t hash = 0;
				for(size_t i = 0; i < BitField<size>::_words; i++)
					hash ^= bf._bits[i];
				return hash;
			}
		};
	}
}
/** Specialization of unordered_map for mapping from BitField to value */
template<size_t size, typename value>
struct BitFieldMap : public std::tr1::unordered_map<BitField<size>, value, std::tr1::hash< BitField<size> > > {};

#else

/** Creates a hash of a bitfield */
template<size_t size>
struct BitFieldHasher{
	size_t operator()(const BitField<size>& bf) const{
		size_t hash = 0;
		for(size_t i = 0; i < BitField<size>::_words; i++)
			hash ^= bf._bits[i];
		return hash;
	}
};
/** Specialization of hash_map for mapping from BitField to value*/
template<size_t size, typename value>
struct BitFieldMap : public __gnu_cxx::hash_map < BitField<size>, value, BitFieldHasher<size> > {};

#endif /* __ICC */


template<size_t size>
inline BitField<size> operator&(const BitField<size>& lhs, const BitField<size>& rhs){
	BitField<size> retval(lhs);
	retval &= rhs;
	return retval;
}

template<size_t size>
inline BitField<size> operator|(const BitField<size>& lhs, const BitField<size>& rhs){
	BitField<size> retval(lhs);
	retval |= rhs;
	return retval;
}

template<size_t size>
inline BitField<size> operator^(const BitField<size>& lhs, const BitField<size>& rhs){
	BitField<size> retval(lhs);
	retval ^= rhs;
	return retval;
}

template<size_t size>
inline BitField<size>& BitField<size>::clear(){
	memset(_bits, 0, sizeof(_word) * _words);
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::clear(size_t pos){
	assert(pos < size);
	_bits[_wordOffset(pos)] &= ~_bitmask(pos);
	return *this;
}

template<size_t size>
inline bool BitField<size>::test(size_t pos) const{
	assert(pos < size);
	return (_bits[_wordOffset(pos)] & _bitmask(pos)) != (_word)0;
}

template<size_t size>
inline BitField<size>& BitField<size>::set(){
	memset(_bits, 0xff, sizeof(_word) * _words);
	//Sanitize
	_bits[_words-1] = _bits[_words-1] & ~((~(_word)0)<< _bitOffset(size));
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::set(size_t pos){
	assert(pos < size);
	_bits[_wordOffset(pos)] |= _bitmask(pos);
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::set(size_t pos, bool value){
	assert(pos < size);
	if(value)
		set(pos);
	else
		clear(pos);
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::flip(){
	for(size_t i = 0; i < _words-1; i++)
		_bits[i] = ~_bits[i];
	//Sanitize
	_bits[_words-1] = ~_bits[_words-1] & ~((~(_word)0)<<_bitOffset(size));
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::flip(size_t pos){
	assert(pos < size);
	_bits[_wordOffset(pos)] ^= _bitmask(pos);
	return *this;
}

template<size_t size>
inline bool BitField<size>::any() const{
	for(size_t i = 0; i < _words; i++)
		if(_bits[i] != (_word)0)
			return true;
	return false;
}

template<size_t size>
inline bool BitField<size>::none() const{
	_word tmp = (_word)0;
	for(size_t i = 0; i < _words; i++)
		tmp |= _bits[i];
	return tmp == (_word)0;
}

template<size_t size>
inline size_t BitField<size>::count() const{
	size_t count = 0;
	for(size_t i = 0; i < _words; i++)
		count += _popcount(_bits[i]);
	return count;
}

template<size_t size>
inline BitField<size>& BitField<size>::operator&=(const BitField<size>& rhs){
	for(size_t i = 0; i < _words; i++)
		_bits[i] &= rhs._bits[i];
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::operator|=(const BitField<size>& rhs){
	for(size_t i = 0; i < _words; i++)
		_bits[i] |= rhs._bits[i];
	return *this;
}

template<size_t size>
inline BitField<size>& BitField<size>::operator^=(const BitField<size>& rhs){
	for(size_t i = 0; i < _words; i++)
		_bits[i] ^= rhs._bits[i];
	return *this;
}

template<size_t size>
inline BitField<size> BitField<size>::operator~() const{
	return BitField<size>(*this).flip();
}

template<size_t size>
bool BitField<size>::operator==(const BitField<size>& rhs) const{
	for(size_t i = 0; i < _words; i++)
		if(_bits[i] != rhs._bits[i])
			return false;
	return true;
}

template<size_t size>
bool BitField<size>::operator!=(const BitField<size>& rhs) const{
	for(size_t i = 0; i < _words; i++)
		if(_bits[i] != rhs._bits[i])
			return true;
	return false;
}

#endif /* CONFIG_H */

definitions.h

#ifndef DEFINITIONS_H
#define DEFINITIONS_H

#include <stdint.h>

/** Representation of a node (must be an integer type) */
typedef uint8_t Node;

/** Type for counting state space size */
typedef uint8_t StateSpaceSize;

/** Type for associating weights with nodes */
typedef StateSpaceSize* Weights;

/** Type for total table size **/
typedef uint64_t TableSize;

#endif /* DEFINITIONS_H */

graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include "bitfield.h"
#include "definitions.h"

#include <assert.h>
#include <vector>
using namespace std;

/** Representation of an undirected graph */
template<size_t size> class Graph {
private:
	BitField<size> _matrix[size];
public:
	/** Set an edge */
	void setEdge(Node x, Node y){
		assert(x != y);
		_matrix[x].set(y);
		_matrix[y].set(x);
	}
	/** Set an edge to true or false */
	void setEdge(Node x, Node y, bool value){
		assert(x != y || !value);
		_matrix[x].set(y, value);
		_matrix[y].set(x, value);
	}
	/** Clear all edges of the graph */
	void clear(){
		for(int i = 0; i < size; i++)
			_matrix[i].clear();
	}
	/** Perform a consistency check */
	bool isConsistent() const;
	/** Get neighbour bitfield */
	const BitField<size>& neighbours(Node x) const{
		return _matrix[x];
	}
	/** Method for hacking the raw matrix (use with caution) */
	BitField<size>* HackMatrix(){
		return _matrix;
	}
	/** Checks if the edge (x,y) exists */
	bool adjacent(Node x, Node y) const{
		return _matrix[x].test(y);
	}
	/** Iterator for iterating over neighbours */
	class NeighbourIterator : public BitField<size>::BitIterator {
	public:
		NeighbourIterator(const Graph<size>& graph, Node node)
		 : BitField<size>::BitIterator(graph.neighbours(node)) {}
	};
	/** Iterator for iterating over all nodes
	 * @remarks this is potentially stupid, consider just using a simple for-loop
	 */
	class NodeIterator{
	private:
		Node _i;
	public:
		NodeIterator(){
			_i = -1;
		}
		NodeIterator(const Graph<size>&){
			_i = -1;
		}
		/** Advance the iterator once */
		bool operator++(int){
			return ++_i < size;
		}
		/** Get the current node */
		Node operator*(){
			return _i;
		}
		/** Reset the iterator to start */
		void reset(){
			_i = -1;
		}
	};
	/** Compare two graphs */
	bool operator== (const Graph<size>& rhs) const{
		for(size_t i = 0; i < size; i++){
			if(rhs._matrix[i] != _matrix[i])
				return false;
		}
		return true;
	}
	/** Compare two graphs */
	bool operator!= (const Graph<size>& rhs) const{
		return !(*this == rhs);
	}
};

template<size_t size> bool Graph<size>::isConsistent() const{
	for(size_t i = 0; i < size; i++){
		for(size_t j = 0; j < size; j++){
			// Matrix must be symmetrical
			if(!_matrix[i].test(j) == _matrix[j].test(i))
				return false;
			// Diagonal must be set to 0
			if(i == j && _matrix[i].test(j))
				return false;
		}
	}
	return true;
}

/** Representation of a graph with dynamic size 
 * This strucutre is not fast, but nodes cat be added to the graph dynamically.
 */
template<>
class Graph<0>{
private:
	/** Underlying bit matrix */
	vector< vector<bool> > _matrix;
public:
	/** Get the number nodes in this graph */
	size_t size() const {
		return _matrix.size();
	}
	/** Add a new node, and get the number of the node */
	Node addNode() {
		Node node = size();
		_matrix[node] = vector<bool>();
		for(size_t i = 0; i < size(); i++){
			_matrix[node][i] = false;
			_matrix[i][node] = false;
		}
		return node;
	}
	/** Set an edge */
	void setEdge(Node x, Node y){
		assert(x != y);
		_matrix[x][y] = true;
		_matrix[y][x] = true;
	}
	/** Set an edge to true or false */
	void setEdge(Node x, Node y, bool value){
		assert(x != y || !value);
		_matrix[x][y] = value;
		_matrix[y][x] = value;
	}
	/** Clear all edges of the graph */
	void clear(){
		for(size_t i = 0; i < size(); i++)
			for(size_t j = 0; j < size(); j++)
				_matrix[i][j] = false;
	}
	/** Perform a consistency check */
	bool isConsistent() const;
	/** Checks if the edge (x,y) exists */
	bool adjacent(Node x, Node y) const{
		return _matrix[x][y];
	}
	/** Iterator for iterating over neighbours */
	class NeighbourIterator {
	private:
		const Graph<0>& _graph;
		size_t _offset;
		Node _node;
	public:
		NeighbourIterator(const Graph<0>& graph, Node node)
		 : _graph(graph) {
			_node = node;
			_offset = -1;
		}
		bool operator++(int){
			do
				_offset++;
			while(_offset < _graph.size() && !_graph.adjacent(_node, _offset));
			return _offset < _graph.size();
		}
		size_t operator*(){
			return _offset;
		}
		/** Reset iterator to start */
		void reset(){
			_offset = -1;
		}
	};
	/** Iterator for iterating over all nodes
	 * @remarks this is potentially stupid, consider just using a simple for-loop
	 */
	class NodeIterator{
	private:
		Node _i;
		const Graph<0>& _graph;
	public:
		NodeIterator(const Graph<0>& graph)
		 : _graph(graph) {
			_i = -1;
		}
		/** Advance the iterator once */
		bool operator++(int){
			return ++_i < _graph.size();
		}
		/** Get the current node */
		Node operator*(){
			return _i;
		}
		/** Reset the iterator to start */
		void reset(){
			_i = -1;
		}
	};
	template<size_t fixedsize>
	Graph<fixedsize> getFixedSize() const{
		assert(fixedsize == size());
		Graph<fixedsize> G;
		for(size_t i = 0; i < fixedsize; i++){
			for(size_t j = 0; j < fixedsize; j++)
				G.setEdge(i, j, adjacent(i, j));
		}
		return G;
	}
};

#endif /* GRAPH_H */