/*
Author: Cam McKinnon
Description:
Implements the classic 'trie' datastructure in abstract form.
Keys must be lists of integers. Data can be of any type, but all data
must be of identical type in any given trie.
For example, to make a classic string/integer trie use lists of characters
for the keys, and numbers for the data.
*/
#ifndef _ABSTRACTTRIE_H_
#define _ABSTRACTTRIE_H_
//linked list library - this is required by for the Abstract Trie Library
#include "linkedlist.h"
//never use this directly
struct TrieAbstract;
//Tries are always of type 'Trie'.
typedef struct TrieAbstract* Trie;
/*
Creates an empty trie.
Parameters:
deleteData - A function that deletes data members from memory.
Suppose in your trie you are storing data of type X, then
deleteData should take in and delete a X*.
If you do not want the trie to free data members from memory,
provide 0 instead of a function pointer.
Returns: An empty trie.
Post Expectations:
You are expected to eventually call trieDelete on the returned Trie.
Time complexity: O(1)
*/
Trie trieCreate(void (*deleteData)(void* data));
/*
Deletes a trie from memory, including possibly all of its data members (see
preconditions).
Parameters:
trie - Trie to be deleted from memory.
Preconditions:
If this trie was not supplied with a deleteData function upon creation, you
must free all of its data members before calling trieDelete on it.
Expectations:
This trie is now deleted from memory - do not attempt to use it for any purposes.
Time complexity: O(s) where s is the sum of the lengths of all keys in the trie.
*/
void trieDelete(Trie trie);
/*
Returns the data associated with a given key.
Parameters:
trie - trie from which the data should be returns.
key - key for which a value should be returned.
Returns:
A void pointer to the data associated with the key, or
a null pointer if no such value was found.
Time complexity: O(keylength)
*/
void * trieGet(Trie trie, List key);
/*
Sets the data for a given key. If key exists in the trie already,
its data value is overwritten. Otherwise the key is inserted first.
Parameters:
trie - trie to be modified. Note: trie will be mutated.
key - key to associate with the data.
data - data to associate with the key.
Returns: the modified trie.
Time complexity: O(keylength)
*/
Trie trieSet(Trie trie, const List key, void * data);
/*
Removes a key and its data from the trie and from memory. If key does not
exist, the trie is not modified.
Parameters:
trie - trie to be modified. Note: trie will be mutated.
key - key to be removed.
Returns: the modified trie.
Preconditions:
If this trie was not supplied with a deleteData function upon creation, you
must free the key's data before calling trieRemove on it.
Time complexity: O(keylength)
*/
Trie trieRemove(Trie trie, const List key);
/*
Returns the lexographically greatest key from the trie.
Parameters:
trie - trie to be modified. Note: trie will be mutated.
key - key to be removed.
Returns: the modified trie.
Preconditions:
If this trie was not supplied with a deleteData function upon creation, you
must free the key's data before calling trieRemove on it.
Time complexity: O(keylength), where keylength is the length of the lexographically greatest key.
*/
List trieMaxKey(Trie trie);
//debug only
void printTrie(struct TrieAbstract * t, int printAsCharacters,int (*printData)(const void *));
#endif