dawg.h

/*
	This is part of pydawg Python module.

	DAWG header -- basic operataions on graph.

	Author    : Wojciech Muła, wojciech_mula@poczta.onet.pl
	WWW       : http://0x80.pl/proj/pydawg/
	License   : 3-clauses BSD (see LICENSE)
*/

#ifndef dawg_h_included__
#define dawg_h_included__

#include "common.h"
#include "dawgnode.h"

#define	DAWG_OK 		(0)
#define DAWG_EXISTS		(1)
#define DAWG_NOT_EXISTS	(0)
#define DAWG_NO_MEM		(-1)
#define DAWG_WORD_LESS	(-2)
#define DAWG_FROZEN		(-3)

#define DAWG_DUMP_TRUNCATED			(-100)
#define DAWG_DUMP_INVALID_MAGICK	(-101)
#define DAWG_DUMP_INVALID_STATE		(-102)
#define DAWG_DUMP_INVALID_ROOT_ID	(-103)
#define DAWG_DUMP_CORRUPTED_1		(-104)
#define DAWG_DUMP_CORRUPTED_2		(-105)


static bool PURE
dawgnode_equivalence(DAWGNode* p, DAWGNode* q);

static uint32_t PURE
dawgnode_hash(const DAWGNode* p);

// setup hash table
#include "hash/hashtable_undefall.h"

#define	HASH_TYPE			uint32_t
#define	HASH_KEY_TYPE		DAWGNode*
//#define HASH_DATA_TYPE		-- no data
#define	HASH_EQ_FUN(a, b)	((a) == (b))
#define	HASH_GET_HASH(x)	(dawgnode_hash(x))
#define	HASH_STATIC			static
#define	HASH_ALLOC	malloc
#define	HASH_FREE	free

#define HASH_GET_UNUSED

#define HASHNAME(name)	name
#include "hash/hashtable.c"

// end setup hash table


typedef struct String {
	size_t	length;				///< length of string
	DAWG_LETTER_TYPE* chars;	///< array of chars
} String;


typedef enum {
	EMPTY,
	ACTIVE,
	CLOSED
} DAWGState;


typedef struct DAWGStatistics {
	size_t	nodes_count;
	size_t	edges_count;
	size_t	words_count;
	size_t	longest_word;

	size_t	sizeof_node;
	size_t	sizeof_edge;
	size_t	graph_size;
} DAWGStatistics;


typedef struct DAWGHashStatistics {
	size_t	table_size;
	size_t	element_size;
	size_t	items_count;
	size_t	item_size;
} DAWGHashStatistics;


typedef struct DAWG {
	DAWGNode*	q0;				///< start state
	uint64_t	count;			///< number of distinct words
	uint64_t	longest_word;	///< length of the longest word (useful when iterating through words, cheap to keep up to date)
	DAWGState	state;			///< DAWG state
	uint16_t	visited_marker;	///< visited marker (used by DAWG_traverse_DFS_once)

	HashTable	reg;			///< registry -- valid states
	String		prev_word;		///< previosuly added word
} DAWG;


/* init DAWG structure */
static int
DAWG_init(DAWG* dawg);


/* free all structures */
static int
DAWG_free(DAWG* dawg);


/* add new word, check if new word is larger then previosuly added */
static int
DAWG_add_word(DAWG* dawg, String word);


/* add new word, but do not check word order */
static int
DAWG_add_word_unchecked(DAWG* dawg, String word);


/* clear whole DAWG */
static int
DAWG_clear(DAWG* dawg);


/* minimize remaining states and then do not allow to add new words */
static int
DAWG_close(DAWG* dawg);


typedef int (*DAWG_traverse_callback)(DAWGNode* node, const size_t depth, void* extra);


/* traverse in DFS order, nodes might be visited many times;
   callback is called before visiting children
 */
static int
DAWG_traverse_DFS(DAWG* dawg, DAWG_traverse_callback callback, void* extra);


/* traverse in DFS order, nodes are visited exactly once
   callback is called after visiting children
 */
static int
DAWG_traverse_DFS_once(DAWG* dawg, DAWG_traverse_callback callback, void* extra);


/* calculate some graph statistics */
static void
DAWG_get_stats(DAWG* dawg, DAWGStatistics* stats);


/* get some statistics about hash table */
static void
DAWG_get_hash_stats(DAWG* dawg, DAWGHashStatistics* stats);


/* checks if word exists in DAWG */
static bool PURE
DAWG_exists(DAWG* dawg, const DAWG_LETTER_TYPE* word, const size_t wordlen);


/* returns longest prefix of word that exists in a DAWG */
static size_t PURE
DAWG_longest_prefix(DAWG* dawg, const DAWG_LETTER_TYPE* word, const size_t wordlen);


/**	Save DAWG in byte array.

	@param[in]	dawg		DAWG object
	@param[in]	stats		current statistics about DAWG

	@param[out]	array		address of array containg DAWG,
							array have to be freed manually
	@param[out]	size		size of array

	@returns
		DAWG_OK
		DAWG_NO_MEM
*/
static int
DAWG_save(DAWG* dawg, DAWGStatistics* stats, uint8_t** array, size_t* size);


/** Loads DAWG from data returned by DAWG_save.

	@param[in,out]	dawg		DAWG object
	@param[in]		array		data
	@param[in]		size		data size

	@returns
		DAWG_OK
		DAWG_NO_MEM
		DAWG_DUMP_TRUNCATED
		DAWG_DUMP_INVALID_MAGICK
		DAWG_DUMP_INVALID_STATE
		DAWG_DUMP_INVALID_ROOT_ID
		DAWG_DUMP_CORRUPTED_1
		DAWG_DUMP_CORRUPTED_2
*/
static int
DAWG_load(DAWG* dawg, uint8_t* array, size_t size);


#ifdef DAWG_PERFECT_HASHING
/*
	Count and save number of words reachable from each state
	This is required by DAWG_mph_get_word_index() and
	DAWG_mph_get_word_from_index().
*/
static void
DAWG_mph_numerate_nodes(DAWG* dawg);


/*
	Returns unique index of a word. Index is in a range
	(1 .. dawg->count) or 0 if word isn't not present in
	a dictionary.

	DAWG_mph_numerate_nodes() have to called once before
	call this function!
*/
static size_t
DAWG_mph_word2index(DAWG* dawg, const DAWG_LETTER_TYPE* word, const size_t wordlen);


/*
	Returns word that have index (1 .. dawg->count).
	If word exists, then returns DAWG_EXISTS and fills
	'word' and 'wordlen'. Array 'word' have to freed
	manually.

	Otherwise returns DAWG_NOT_EXISTS.

	DAWG_mph_numerate_nodes() have to called once before
	call this function!
*/
static int
DAWG_mph_index2word(DAWG* dawg, size_t index, DAWG_LETTER_TYPE** word, size_t* wordlen);
#endif


#endif