/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
/*
 *  Copyright (C) 2008 Jeffrey Stedfast
 *
 *  Permission is hereby granted, free of charge, to any person
 *  obtaining a copy of this software and associated documentation
 *  files (the "Software"), to deal in the Software without
 *  restriction, including without limitation the rights to use, copy,
 *  modify, merge, publish, distribute, sublicense, and/or sell copies
 *  of the Software, and to permit persons to whom the Software is
 *  furnished to do so, subject to the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 *  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 *  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 *  DEALINGS IN THE SOFTWARE.
 */


#ifndef __TRIE_H__
#define __TRIE_H__

#include <vector>

extern "C" {
	typedef struct _TrieMatch TrieMatch;
	typedef struct _TrieState TrieState;
	
	struct _TrieState {
		TrieState *next;
		TrieState *fail;
		TrieMatch *match;
		size_t final;
		int id;
	};
	
	struct _TrieMatch {
		TrieMatch *next;
		TrieState *state;
		char c;
	};
}

class Trie {
	std::vector<TrieState*> fail_states;
	TrieState root;
	bool icase;
	
	TrieState *Insert (size_t depth, TrieState *q, char c);
	
 public:
	///
	/// Trie constructor:
	///   @icase: ignore case
	///
	Trie (bool icase);
	~Trie ();
	
	///
	/// AddPattern:
	///   @pattern: a pattern to match
	///   @pattern_id: a unique id for the pattern
	///
	/// Adds @pattern to the list of patterns to match against in
	/// a call to ::Search().
	///
	void AddPattern (const char *pattern, int pattern_id);
	
	///
	/// Search:
	///   @buf: a character buffer or string
	///   @buflen: the length of @buf
	///   @matched_id: an optional output parameter which will be set to the matched pattern id
	///
	/// Searches for any of the previously added patterns in the buffer.
	///
	/// Returns a character pointer to the offset at which the
	/// matched pattern starts or %NULL if no pattern is found.
	///
	/// If a pattern is found, @matched_id will be set to the
	/// pattern id given in ::AddPattern().
	///
	const char *Search (const char *buf, size_t buflen, int *matched_id = 0);
};

#endif /* __TRIE_H__ */