FiveLoaves v1.0

// --------------------------------------------------------------------------
//					www.UnitedBusinessTechnologies.com
//			  Copyright (c) 1998 - 2002  All Rights Reserved.
//
// Source in this file is released to the public under the following license:
// --------------------------------------------------------------------------
// This toolkit may be used free of charge for any purpose including corporate
// and academic use.  For profit, and Non-Profit uses are permitted.
//
// This source code and any work derived from this source code must retain 
// this copyright at the top of each source file.
// 
// UBT welcomes any suggestions, improvements or new platform ports.
// email to: XMLFoundation@UnitedBusinessTechnologies.com
// --------------------------------------------------------------------------
#ifndef __GB_TREE_H__
#define __GB_TREE_H__

#include "GList.h"

typedef enum balanceState { leftTilt, noTilt, rightTilt };
class GBTree
{
private:

	typedef struct GBTreeStruct
	{
		GBTreeStruct    *m_leftPtr;
		GBTreeStruct    *m_rightPtr;
		GBTreeStruct	*m_Next;
		GBTreeStruct	*m_Prev;
		char			*m_szKey;
		void			*m_dataNode;
		balanceState m_balance;
	};
protected:

	bool m_insertedOK;

	// special node pointer used in deletion
	GBTreeStruct *m_nodeMarker;

	void rightRotate(GBTreeStruct * &rootPtr);
	void leftRotate(GBTreeStruct * &rootPtr);
	void rightBalance(GBTreeStruct * &rootPtr, bool &delOK);
	void leftBalance(GBTreeStruct * &rootPtr, bool &delOK);
	void deleteBothChildren(GBTreeStruct * &rootPtr, GBTreeStruct * &Ptr, bool &delOK);
	void insertNode(GBTreeStruct * &rootPtr, const char *szKey, void *value);
	void removeNode(GBTreeStruct * &rootPtr, unsigned &occur, bool &delOK, const char *szKey);
	void *searchTree(const char *szKey, unsigned occur = 1);
	bool delSubTree(GBTreeStruct * &rootPtr);

	unsigned m_numNodes;

	GBTreeStruct *m_nodePtr, *m_root, *m_Last, *m_First;
	friend class GBTreeIterator;

public:

	GBTree();
	~GBTree() { if (m_root) clear(); }

	unsigned getNodeCount() const { return m_numNodes; }

	void insert(const char *szKey, void *value);
	void *search(const char *szKey, unsigned occur = 1)	{ return searchTree(szKey, occur); }
	bool remove(const char *szKey, unsigned occur = 1);
	void clear();
	bool isEmpty(){return (m_numNodes == 0) ? true : false; }
};

class GBTreeIterator
{
	void *m_pLookAhead;
	int m_Direction;
	GBTree *m_pTree;
	GList m_strTreeStack;
	GList m_strFrameLocStack;
	GBTree::GBTreeStruct *m_pInsertionOrderCurrent;
public:
	// 1 = Alphabetical, 0 = Reverse Alphabetical, 2 = Insertion Order
	GBTreeIterator(GBTree *p = 0, int nDirection = 2);
	void Reset(GBTree *p, int nDirection);

	int operator () (void);
	void * operator ++ (int);
};



#endif //  __GB_TREE_H__