#ifndef __rbtree_h_
#define __rbtree_h_

/**************************************************************************

This software is copyrighted by PHILIP SMOLEN.
The following terms apply to all files associated with the software unless 
explicitly disclaimed in individual files.

The authors hereby grant permission to use, copy, modify, distribute,
and license this software and its documentation for any purpose, provided
that existing copyright notices are retained in all copies and that this
notice is included verbatim in any distributions. No written agreement,
license, or royalty fee is required for any of the authorized uses.
Modifications to this software may be copyrighted by their authors
and need not follow the licensing terms described here, provided that
the new terms are clearly indicated on the first page of each file where
they apply.

IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY
FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
MODIFICATIONS.

GOVERNMENT USE: If you are acquiring this software on behalf of the
U.S. government, the Government shall have only "Restricted Rights"
in the software and related documentation as defined in the Federal 
Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
are acquiring the software on behalf of the Department of Defense, the
software shall be classified as "Commercial Computer Software" and the
Government shall have only "Restricted Rights" as defined in Clause
252.227-7013 (c) (1) of DFARs.  Notwithstanding the foregoing, the
authors grant the U.S. Government and others acting in its behalf
permission to use and distribute the software in accordance with the
terms specified in this license. 

**************************************************************************/


//*************************************************************************
// WAY OUT OF DATE.  BUT YOU GET THE IDEA.
// rbtree.h - code for a simple red-black tree.
//
// rbtreeType<X> is a red-black tree with elements of type X.  If X is
// a simple type, like int, then rbtreeType<X> forms a set with elements
// of type <X>.  If X is any ordered pair type, and only the first item
// in the pair is used in the comparison, then rbtreeType forms a lookup
// table.  All operations are O(log(n)), where n is the number of elements
// in the three, except as noted below.
//
// The type X must have a < and == operator.  If two items are == then only
// one of them may be in the tree at once.  If A < B, A will come before A
// when iterating with the next() function.
//
// The assumption is that < and == form a consistent ordering on type X.
// However, even if these operators give bogus results, the code will
// never dump core or run in an infinite loop.  In fact, the algorithms
// will still be O(log(n)), even in the worst case.  However, the size
// of the tree may be larger if the == operation always returns false.
// Iterating through the tree will still return all elements of the tree.
//
// < and == may safely throw exceptions.  These exceptions will not cause
// any memory leaks or damage to the tree.  All comparisons are done
// before any modifications, so an exception will cause the requested
// operation to abort without modifying the tree.
//
// The copies of the items, not pointers to the items, are stored in the
// tree.  If X is a class, is needs to have a valid copy constructor,
// assignment operator, and destructor.  References are used as much as
// possible to minimize the number of copies.
//
// The tree defines an iterator type.  The iterator is a constant
// pointer to a node.  A constant reference to the data is available 
// from here.  Overriding the const is perfectly acceptable as long as
// the new value == the original value.  (Note that the const on the
// iterator is more a consequence of some nasty implementation details
// than it is a suggestion of how to use the iterator.)  A NULL iterator
// indicates the end of the tree, or a non-existent element.  All 
// iterators are valid only as long as the tree does not changes; any
// additions or deletions invalidates all iterators for the given tree.
//
// Define UNIT_TEST to run tests on a simple instantiation of this
// datatype.  Also, the UNIT_TEST code provides a simple sample of how
// to use this tree.  Define RBTREE_WITH_DEBUG to compile methods which
// are used in development and debugging, but are not needed in a working
// system.  RBTREE_WITH_DEBUG requires console output, so the code is
// not applicable for all systems.
//
// The algorithms below were adapted from _Introduction_to_Algorithms_
// by Cormen, Leiserson, and Rivest, 1990.  This book is an excellent
// source for information on this data structure.
//
// All code below was written by Philip Smolen
// Contact info:  http://www.trade-ideas.com/home/phil/RBTree/

typedef void *rbKeyType;
typedef void *rbValueType;

struct rbDataType
{
  rbKeyType key;
  rbValueType value;
};

struct rbNodeType
{
  //public:
  struct rbDataType data;

  //private:
  struct rbNodeType *left, *right, *parent;
  int black;
};

enum rbCompareType {RBC_LESS, RBC_EQUAL, RBC_MORE, RBC_ERROR};
enum rbResultType {RBR_SUCCEED, RBR_COMPARE_FAIL, RBR_OTHER_FAIL};
enum rbDirectionType {RBD_BEFORE, RBD_EXACT, RBD_AFTER};

typedef enum rbCompareType (*rbCompareProc)(const rbKeyType a, const rbKeyType b, void *data);

struct rbTreeType
{
  // Set by client before use.
  void (*freeData)(struct rbDataType *data);
  void (*dupData)(struct rbDataType *dest, const struct rbDataType *src);
  rbCompareProc compareKeys;
  void *compareData;

  // Private
  struct rbNodeType null;
  struct rbNodeType *root;
};

extern struct rbTreeType *rbNewTree(void);
extern struct rbTreeType *rbCopy(const struct rbTreeType *tree);
extern void rbDeleteTree(struct rbTreeType *tree);

extern enum rbResultType rbAdd(struct rbTreeType *tree, 
			       struct rbDataType *data, 
			       int allowOverwrite);
extern enum rbResultType rbRemove(struct rbTreeType *tree, 
				  const rbKeyType key);
extern void rbRemoveNode(struct rbTreeType *tree, struct rbNodeType *node);
extern enum rbResultType rbExists(const struct rbTreeType *tree,
				  const rbKeyType key);
extern void rbClear(struct rbTreeType *tree);

extern struct rbNodeType *rbFirst(const struct rbTreeType *tree);
extern struct rbNodeType *rbLast(const struct rbTreeType *tree);
extern struct rbNodeType *rbNext(const struct rbTreeType *tree, 
				 const struct rbNodeType *node);
extern struct rbNodeType *rbPrev(const struct rbTreeType *tree, 
				 const struct rbNodeType *node);
extern enum rbResultType rbFind(const struct rbTreeType *tree,
				const rbKeyType key,
				enum rbDirectionType direction,
				struct rbNodeType **found);
				 
extern int rbEmpty(const struct rbTreeType *tree);
extern unsigned int rbCount(const struct rbTreeType *tree);


#endif