Prefix tree
-----------
    This structure is an ordered tree data structure that is used to store a dynamic set or 
associative array where the keys are usually strings. Unlike a binary search tree, no node in 
the tree stores the key associated with that node; instead, its position in the tree defines 
the key with which it is associated. All the descendants of a node have a common prefix or suffix
of the string associated with that node, and the root is associated with the empty string.

    The Prefix tree can be used for storing strings which have same prefix or suffix. The tree 
structure has information about count of different (suf-pre)fixes of certain (suf-pre)fix. It can
be used for example for storing domain names or email address. You can specify the delimiter of string
and the tree automatically creates special (domain) node.

    For using the tree call the prefix_tree_initialize() function first. The function creates
all necessary structures for storing and accessing the data and return structure of tree. 
The parameters are: 
		Value "PREFIX" for prefix tree or SUFFIX for suffix tree.
		Size of value which will be allocated for each inserted string. 
		Delimiter.

    For inserting there is prefix_tree_insert() function. Parameters are pointer to the prefix 
tree structure, a string which should be added and length of string. The return value 
is a domain node of inserted string. If the item is not in the tree, it is created, if the item
is already in the tree, then the pointer to existing string is returned.

    For reading saved string, there is a function prefix_tree_read_string() with parameters:
		Pointer to the tree.
		Domain structure.
		Pointer, where the string should be saved.

    For destruction of a whole tree there is prefix_tree_destroy() function, parameter is
pointer to the prefix tree structure.


Example usage
-------------

#include "prefix_tree.h"

//structure for value
typedef struct info_t{
    unsigned int id;
} info_t;

int main(int argc, char *argv[])
{
	//pointer to the tree
	prefix_tree_t * tree;

	//any structure of value type. This structure should be defined in your code.
	info_t * info;

	//string - for reading saved string in the tree
	char str[200];

	/*
	* return value from function prefix_tree_insert() or prefix_tree_search()
	* in this structure is:
	*	- degree 
	*		Number of domain node in string (for example domain names have separator '.',
	*		for domain domain1.domain2.cz is degree = 3).
	*	- count_of_insert
	*		count of operation insert on certain string.
	* 	- count_of_different_subdomains
	*		Count of different descendants. 
	*		Example: You will insert 
	*			"domain1.cz", "domain2.cz"," domain3.domain1.cz", "domain4.cz", "domain5.domain4.cz"
	*			then for domain "cz" is  count_of_different_subdomains = 5
	*	- value
	*		User specified value saved created in every domain node
	*/
	prefix_tree_domain_t * domain = NULL;

	/*
	* Initial function, which return pointer to the created tree.
	* Parameters are:
	*	1. SUFFIX for suffix tree or PREFIX for prefix tree.
	*	2. size of structure, which will be saved for every domain node
	* 	3. delimiter.
	*		For example delimiter of domain name is '.'. for email it is '@'.
	*		For each delimiter in string will be created domain node (structure prefix_tree_domain_t).
	*		If you don't want to use delimiter, use value -1.
	* Return value is pointer to the tree.
	*/
	tree =  prefix_tree_initialize(SUFFIX ,sizeof(info_t),'.');

	/*
	* Function for inserting strings to the tree.
	* Parameters are:
	*	1. Pointer to the tree, where the string will be inserted.
	*	2. A String which witch will be added.
	* 	3. Size of the string.
	* Return value is pointer to structure prefix_tree_domain_t.
	*/	
	domain = prefix_tree_insert(tree, "google.com",10);

	domain = prefix_tree_insert(tree, "domain2.com",11);
	domain = prefix_tree_insert(tree, "translate.google.com",20);
	domain = prefix_tree_insert(tree, "prefix.com",10);
	domain = prefix_tree_insert(tree, "suffix.com",10);	
	domain = prefix_tree_insert(tree, "ok.prefix.com",13);

	/*
	* Created tree of this values is:

                            "."
                             |
                           "com"
                             |
                            "."
                         /   |  \
                       /     |    \
                     /       |      \
                "google" "domain2" "fix"
                    |                 |  \
                    |                 |   \
                   "."              "pre"  suff 
                    |                 |
                "translate"          "."
                                      |
                                     "ok"
	*/


	/*
	* Function for getting string from domain node.
	* Parameters are:
	*	1. Pointer to the tree.
	*	2. Pointer to the domain node.
	* 	3. Pointer to the string.
	* Return value is char*.
	*/
	prefix_tree_read_string(tree, domain, str);
	printf("%s\n", str);	

	/*
	* Function for searching string in tree.
	* Function is similar to prefix_tree_insert(), but if the string 
	* is not in the tree, it returns NULL.
	* Parameters are:
	*	1. Pointer to the tree, where the string will be inserted.
	*	2. A String which witch will be added.
	* 	3. Size of the string.
	* Return value is domain structure or NULL.
	*/	
	domain = prefix_tree_search(tree, "google.com",10);

	/*
	* You can find specified space for value of string in domain structure.
	*/
	if(domain != NULL){
		info = (info_t*)domain->value;
		info->id = 5; 	
	}

	/*
	* Function for destroying a tree.
	* Parameter is pointer to the tree. 
	*/
	prefix_tree_destroy(tree);
	return 0;
}
