Storage container for sorting keys(cross-compiler stl::map)
Posted: Fri Sep 17, 2004 8:16 am
You can use a wxSortedArray for sorting values, but what storage container is there to sort keys?
There is nothing in wx that sorts keys in a general way like std::map does. Note that keys in wxHashMap are _not_ sorted.
You can try the following - it's not 100% complete, but its fast (faster than most stl implementations) and supports the most common stl::map functions.
DECLARE_MAP(NAME, KEYTYPE, DATATYPE, COMPARE)
NAME=Name of class
KEYTYPE=Key type
DATATYPE=Element type
COMPARE=Compare function - usually want something like
bool mycompare(T e1, T e2, void*){return e1 < e2;}
[syntax="c"]
//(c) (wxWidgets) by Ryan Norton
#define RED 0
#define BLACK 1
#define THREAD 0
#define LINK 1
#include <stddef.h>
#define DECLARE_PAIR(NAME,KEYTYPE,DATATYPE, COMPARE)\
class NAME \
{\
typedef KEYTYPE t1;\
typedef DATATYPE t2;\
public:\
NAME(){}\
NAME(const KEYTYPE& key) : first(t1(key)){}\
NAME(const KEYTYPE& key, const DATATYPE& data) : first(t1(key)), second(t2(data)) {}\
\
static bool KeyCompare(const NAME& n1, const NAME& n2, void* parm) {return COMPARE(n1.first, n2.first, parm);}\
KEYTYPE first; DATATYPE second;\
};
#define DECLARE_REDBLACKTREE(NAME,KEYTYPE,COMPARE) \
struct NAME##Node \
{ \
public: \
NAME##Node ( const KEYTYPE& crKey, \
NAME##Node*& prLeftChild, NAME##Node*& prRightChild, \
const bool& cbrIsRightChild, const bool& cbrHasLeftLink, \
const bool& cbrHasRightLink, const bool& cbrColor ) : \
Key(crKey), \
pLeftChild(prLeftChild), pRightChild(prRightChild), \
bIsRightChild(cbrIsRightChild), \
bHasLeftLink(cbrHasLeftLink), \
bHasRightLink(cbrHasRightLink), \
bColor(cbrColor) \
{ \
} \
\
NAME##Node ( const KEYTYPE& crKey, \
NAME##Node*& prLeftChild, NAME##Node* prRightChild, \
const bool& cbrHasLeftLink, const bool& cbrHasRightLink, \
const bool& cbrColor ) : \
Key(crKey), \
pLeftChild(prLeftChild), pRightChild(prRightChild), \
bIsRightChild(false), bHasLeftLink(cbrHasLeftLink), \
bHasRightLink(cbrHasRightLink), bColor(cbrColor) \
{ \
} \
\
NAME##Node ( NAME##Node* pLeftChild, NAME##Node* pRightChild, \
const bool& cbrHasLeftLink, const bool& cbrHasRightLink, \
const bool& cbrColor ) : \
pLeftChild(pLeftChild), pRightChild(pRightChild), \
bIsRightChild(false), bHasLeftLink(cbrHasLeftLink), \
bHasRightLink(cbrHasRightLink), bColor(cbrColor) \
{ \
} \
\
~NAME##Node() \
{ \
} \
\
KEYTYPE Key; \
NAME##Node* pLeftChild; \
NAME##Node* pRightChild; \
bool bIsRightChild; \
bool bHasLeftLink; \
bool bHasRightLink; \
bool bColor; \
}; \
class NAME \
{ \
public: \
typedef NAME##Node node_type; \
NAME() : \
HeadNode(&HeadNode, &HeadNode, THREAD, LINK, BLACK) \
{ \
} \
\
~NAME() \
{ \
Clear(); \
} \
\
bool Delete(const KEYTYPE& rKey) \
{ \
register node_type* pFoundNode = FindNode(rKey); \
\
return (pFoundNode ? DeleteNode(pFoundNode), true : false); \
} \
\
void DeleteAll() \
{ \
Clear(); \
\
HeadNode.bHasLeftLink = THREAD; \
HeadNode.pLeftChild = &HeadNode; \
} \
\
KEYTYPE& Find(const KEYTYPE& rKey) \
{ \
node_type* pFoundNode = FindNode(rKey); \
return pFoundNode == NULL ? (KEYTYPE&) rKey : pFoundNode->Key; \
} \
\
\
static inline int Max(const int& x, const int& y) \
{ \
return x > y ? x : y; \
} \
\
static inline void Swap (size_t& x, size_t& y) \
{ \
x = x ^ y; \
y = x ^ y; \
x = x ^ y; \
} \
\
\
static const bool& HasLeftLink(node_type* pNode) \
{ \
return pNode->bHasLeftLink; \
} \
\
static const bool& HasRightLink(node_type* pNode) \
{ \
return pNode->bHasRightLink; \
} \
\
node_type* LeftChild(node_type* pNode) \
{ \
return (HasLeftLink(pNode) ? pNode->pLeftChild : NULL); \
} \
\
node_type* RightChild(node_type* pNode) \
{ \
return (HasRightLink(pNode) ? pNode->pRightChild : NULL); \
} \
\
bool IsHeadNode(node_type*& prNode) \
{ \
return ((prNode)->pRightChild == (prNode)); \
} \
\
node_type* Predeccessor(node_type* pNode) \
{ \
if (!pNode) \
return NULL; \
\
register node_type* pRetNode; \
pRetNode = pNode->pLeftChild; \
\
if (HasLeftLink(pNode)) \
while (HasRightLink(pRetNode)) \
pRetNode = pRetNode->pRightChild; \
\
return (IsHeadNode(pRetNode) ? NULL : pRetNode); \
} \
\
node_type* Successor(node_type* pNode) \
{ \
if (!pNode) \
return NULL; \
\
register node_type* pRetNode; \
pRetNode = pNode->pRightChild; \
\
if (HasRightLink(pNode)) \
while (HasLeftLink(pRetNode)) \
pRetNode = pRetNode->pLeftChild; \
\
return (IsHeadNode(pRetNode) ? NULL : pRetNode); \
} \
\
node_type* FindMinNode(node_type* pNode) const \
{ \
while (HasLeftLink(pNode)) \
pNode = pNode->pLeftChild; \
\
return pNode; \
} \
\
node_type* FindMaxNode(node_type* pNode) const \
{ \
while (HasRightLink(pNode)) \
pNode = pNode->pRightChild; \
\
return pNode; \
} \
\
node_type* FindParentNode(node_type*& pNode) const \
{ \
if(pNode->bIsRightChild) \
return FindMinNode(pNode)->pLeftChild; \
else \
return FindMaxNode(pNode)->pRightChild; \
} \
\
void Clear() \
{ \
register node_type* pNodeToDelete; \
register node_type* pSuccessorNode = Successor(Reset()); \
\
while (pSuccessorNode != NULL) \
{ \
pSuccessorNode = Successor(pNodeToDelete = pSuccessorNode); \
delete pNodeToDelete; \
} \
\
HeadNode.bHasLeftLink = false; \
HeadNode.pLeftChild = &HeadNode; \
} \
\
\
node_type* FindNode (const KEYTYPE& key) \
{ \
register node_type* p = HeadNode.pLeftChild; \
register bool bLess; \
\
if (!HasLeftLink(&HeadNode)) \
return NULL; \
\
for(;;) \
{ \
bLess = COMPARE(key , p->Key, this); \
if (bLess) \
{ \
if(!HasLeftLink(p)) \
break; \
else \
p = p->pLeftChild; \
} \
else \
{ \
if(!HasRightLink(p)) \
break; \
else \
p = p->pRightChild; \
} \
} \
\
if(bLess) \
p = Predeccessor(p); \
\
return p && !COMPARE(p->Key, key, this) ? p : NULL; \
} \
\
\
node_type* Insert(const KEYTYPE& key, \
const bool& bReplace = false) \
{ \
\
if (!HasLeftLink(&HeadNode)) \
{ \
HeadNode.bHasLeftLink = LINK; \
return HeadNode.pLeftChild = \
new node_type(key, HeadNode.pLeftChild, &HeadNode, \
THREAD, THREAD, BLACK); \
} \
else \
{ \
register node_type* p = HeadNode.pLeftChild; \
register node_type* y; \
register bool bLess; \
for(;;) \
{ \
\
\
bLess = COMPARE(key , p->Key, this); \
\
\
if (bLess) \
{ \
if(!HasLeftLink(p)) \
break; \
else \
p = p->pLeftChild; \
} \
\
else \
{ \
if(!HasRightLink(p)) \
break; \
else \
p = p->pRightChild; \
} \
\
} \
\
if (bLess) \
y = Predeccessor(p); \
else \
y = p; \
\
if (y && !COMPARE(y->Key, key, this)) \
{ \
\
\
\
\
if (bReplace) \
{ \
p->Key = key; \
} \
else \
\
p = NULL; \
\
return p; \
} \
\
if(bLess) \
{ \
p->bHasLeftLink = LINK; \
p->pLeftChild = y = \
new node_type(key, p->pLeftChild, p, 0, \
THREAD, THREAD, RED); \
} \
else \
{ \
p->bHasRightLink = LINK; \
p->pRightChild = y = \
new node_type(key, p, p->pRightChild, 1, \
THREAD, THREAD, RED); \
} \
\
\
p = y; \
\
\
\
Rebalance(p); \
\
return y; \
} \
} \
\
node_type* InsertMulti(const KEYTYPE& key) \
{ \
\
if (!HasLeftLink(&HeadNode)) \
{ \
HeadNode.bHasLeftLink = LINK; \
return HeadNode.pLeftChild = \
new node_type(key, HeadNode.pLeftChild, &HeadNode, \
THREAD, THREAD, BLACK); \
} \
else \
{ \
register node_type* p = HeadNode.pLeftChild; \
register node_type* y; \
register bool bLess; \
for(;;) \
{ \
bLess = COMPARE(key , p->Key, this); \
\
if (bLess) \
{ \
if(!HasLeftLink(p)) \
break; \
else \
p = p->pLeftChild; \
} \
\
else \
{ \
if(!HasRightLink(p)) \
break; \
else \
p = p->pRightChild; \
} \
\
} \
\
if(bLess) \
{ \
p->bHasLeftLink = LINK; \
p->pLeftChild = y = \
new node_type(key, p->pLeftChild, p, 0, \
THREAD, THREAD, RED); \
} \
else \
{ \
p->bHasRightLink = LINK; \
p->pRightChild = y = \
new node_type(key, p, p->pRightChild, 1, \
THREAD, THREAD, RED); \
} \
\
\
p = y; \
\
Rebalance(p); \
\
return y; \
} \
} \
\
void Rebalance(node_type*& p) \
{ \
register node_type* f; \
register node_type* q; \
\
while ( p != HeadNode.pLeftChild && \
(q=FindParentNode(p))->bColor == RED) \
{ \
f = FindParentNode(q); \
wxASSERT((!IsHeadNode(f)) && (f->bColor == BLACK)); \
\
if (q->bIsRightChild) \
{ \
if (HasLeftLink(f) && f->pLeftChild->bColor == RED) \
{ \
q->bColor = f->pLeftChild->bColor = BLACK; \
f->bColor = RED; \
p = f; \
} \
else \
{ \
if (!p->bIsRightChild) \
{ \
RotateRight(q); \
Swap((size_t&) q, (size_t&) p); \
} \
\
q->bColor = BLACK; \
f->bColor = RED; \
RotateLeft(f); \
break; \
} \
} \
else \
{ \
if (HasRightLink(f) && f->pRightChild->bColor == RED) \
{ \
q->bColor = f->pRightChild->bColor = BLACK; \
f->bColor = RED; \
p = f; \
} \
else \
{ \
if (p->bIsRightChild) \
{ \
RotateLeft(q); \
Swap((size_t&)q, (size_t&) p); \
} \
\
q->bColor = BLACK; \
f->bColor = RED; \
RotateRight(f); \
break; \
} \
} \
} \
\
HeadNode.pLeftChild->bColor = BLACK; \
} \
\
void DeleteNode(node_type* pNode) \
{ \
node_type* pTempNode; \
\
if (!pNode || IsHeadNode(pNode)) \
return; \
\
\
for (;;) \
{ \
if (HasRightLink(pNode)) \
{ \
pTempNode = FindMinNode(pNode->pRightChild); \
pNode->Key = pTempNode->Key; \
} \
else if (HasLeftLink(pNode)) \
{ \
pTempNode = FindMaxNode(pNode->pLeftChild); \
pNode->Key = pTempNode->Key; \
} \
else \
break; \
\
pNode = pTempNode; \
} \
\
pTempNode = FindParentNode(pNode); \
\
if (pNode->bIsRightChild) \
{ \
pTempNode->pRightChild = pNode->pRightChild; \
pTempNode->bHasRightLink = THREAD; \
} \
else \
{ \
pTempNode->pLeftChild = pNode->pLeftChild; \
pTempNode->bHasLeftLink = THREAD; \
} \
\
\
\
\
if (pNode->bColor == BLACK) \
Restructure(pNode); \
\
\
delete (pNode); \
} \
\
inline void Restructure(node_type* p) \
{ \
node_type* q; \
\
while ((p->bColor == BLACK) && !(q = FindParentNode(p),IsHeadNode(q))) \
{ \
if (p->bIsRightChild) \
{ \
wxASSERT(HasLeftLink(q)); \
if (q->pLeftChild->bColor == RED) \
{ \
q->bColor = RED; \
q->pLeftChild->bColor = BLACK; \
RotateRight(q); \
} \
if ( \
(!HasLeftLink(q->pLeftChild) || \
q->pLeftChild->pLeftChild->bColor == BLACK) && \
(!HasRightLink(q->pLeftChild) || \
q->pLeftChild->pRightChild->bColor == BLACK) \
) \
{ \
q->pLeftChild->bColor = RED; \
p = q; \
} \
else \
{ \
if (!HasLeftLink(q->pLeftChild) || \
q->pLeftChild->pLeftChild->bColor == BLACK) \
{ \
q->pLeftChild->pRightChild->bColor = BLACK; \
q->pLeftChild->bColor = RED; \
RotateLeft(q->pLeftChild); \
} \
q->pLeftChild->bColor = q->bColor; \
q->bColor = BLACK; \
q->pLeftChild->pLeftChild->bColor = BLACK; \
RotateRight(q); \
break; \
} \
} \
else \
{ \
wxASSERT(HasRightLink(q)); \
if (q->pRightChild->bColor == RED) \
{ \
q->bColor = RED; \
q->pRightChild->bColor = BLACK; \
RotateLeft(q); \
} \
if ( \
(!HasLeftLink(q->pRightChild) || \
q->pRightChild->pLeftChild->bColor == BLACK) && \
(!HasRightLink(q->pRightChild) || \
q->pRightChild->pRightChild->bColor == BLACK) \
) \
{ \
q->pRightChild->bColor = RED; \
p = q; \
} \
else \
{ \
if (!HasRightLink(q->pRightChild) || \
q->pRightChild->pRightChild->bColor == BLACK) \
{ \
q->pRightChild->pLeftChild->bColor = BLACK; \
q->pRightChild->bColor = RED; \
RotateRight(q->pRightChild); \
} \
q->pRightChild->bColor = q->bColor; \
q->bColor = BLACK; \
q->pRightChild->pRightChild->bColor = BLACK; \
RotateLeft(q); \
break; \
} \
} \
} \
p->bColor = BLACK; \
} \
\
\
node_type* Reset() \
{ \
return &HeadNode; \
} \
\
void RotateLeft(node_type* pNode) \
{ \
node_type* pRightChildOfNode = pNode->pRightChild; \
node_type* pParentOfNode = FindParentNode(pNode); \
\
if (pNode->bIsRightChild) \
{ \
pParentOfNode->pRightChild = pRightChildOfNode; \
pNode->bIsRightChild = false; \
} \
else \
{ \
pParentOfNode->pLeftChild = pRightChildOfNode; \
pRightChildOfNode->bIsRightChild = false; \
} \
\
if (HasLeftLink(pRightChildOfNode)) \
{ \
pNode->pRightChild = pRightChildOfNode->pLeftChild; \
pNode->pRightChild->bIsRightChild = true; \
pRightChildOfNode->pLeftChild = pNode; \
} \
else \
{ \
pRightChildOfNode->bHasLeftLink = LINK; \
pNode->bHasRightLink = THREAD; \
} \
} \
\
void RotateRight(node_type* pNode) \
{ \
node_type* pLeftChildOfNode = pNode->pLeftChild; \
node_type* pParentOfNode = FindParentNode(pNode); \
\
if (pNode->bIsRightChild) \
{ \
pParentOfNode->pRightChild = pLeftChildOfNode; \
pLeftChildOfNode->bIsRightChild = true; \
} \
else \
{ \
pParentOfNode->pLeftChild = pLeftChildOfNode; \
pNode->bIsRightChild = true; \
} \
\
if (HasRightLink(pLeftChildOfNode)) \
{ \
pNode->pLeftChild = pLeftChildOfNode->pRightChild; \
pNode->pLeftChild->bIsRightChild = false; \
pLeftChildOfNode->pRightChild = pNode; \
} \
else \
{ \
pLeftChildOfNode->bHasRightLink = LINK; \
pNode->bHasLeftLink = THREAD; \
} \
} \
\
node_type HeadNode; \
};
#define DECLARE_MAP(NAME, KEYTYPE, DATATYPE, COMPARE)\
\
DECLARE_PAIR(NAME##PAIR, KEYTYPE, DATATYPE, COMPARE);\
DECLARE_REDBLACKTREE(NAME##RBT, NAME##PAIR, NAME##PAIR::KeyCompare);\
\
class NAME : protected NAME##RBT \
{ \
public: \
NAME(){}~NAME(){} \
\
/*stl typedefs*/ \
typedef size_t difference_type; \
typedef KEYTYPE key_type;\
typedef DATATYPE mapped_type;\
typedef size_t size_type;\
typedef NAME##PAIR value_type; \
typedef NAME##RBT tree_type; \
\
/*internal typedefs*/\
typedef NAME##RBT::node_type node_type; \
\
/*iterator*/ \
class iterator \
{ \
public: \
iterator() : m_pKey(NULL) {} \
iterator(const iterator& it) \
: m_pTree(it.m_pTree), m_pKey(it.m_pKey) {} \
iterator(tree_type* pTree, node_type* pKey) \
: m_pTree(pTree), m_pKey(pKey) {} \
\
iterator operator ++(int nIncrement) \
{iterator iRet = *this; ++*this; return iRet;} \
\
iterator operator --(int nIncrement) \
{iterator iRet = *this; --*this; return iRet;} \
\
iterator& operator ++() \
{m_pKey = m_pTree->Successor(m_pKey); return *this;} \
\
iterator& operator --() \
{m_pKey = m_pTree->Predeccessor(m_pKey); return *this;} \
\
int operator == (const iterator& i) {return this->m_pKey == i.m_pKey;} \
int operator != (const iterator& i) {return this->m_pKey != i.m_pKey;} \
\
iterator& operator = (const iterator& i) \
{ this->m_pTree = i.m_pTree; this->m_pKey = i.m_pKey;} \
\
value_type& operator * () {return (m_pKey)->Key;} \
protected: \
tree_type* m_pTree; \
node_type* m_pKey; \
}; \
\
iterator begin() \
{ \
return iterator((tree_type*)this, \
FindMinNode(Successor(Reset()))); \
} \
\
void clear() \
{ \
DeleteAll(); \
} \
\
size_t count(const KEYTYPE& Key) \
{ \
if(FindNode(Key)) \
return 1; \
return 0; \
} \
bool empty() {return !HasLeftLink(&HeadNode);} \
iterator find(const KEYTYPE& key) \
{\
node_type* node = FindNode(key);\
if(!node)\
return iterator();\
return iterator(((tree_type*)this), node);\
}\
\
\
iterator end() \
{ \
return iterator(); \
} \
\
bool insert(const value_type& v){Insert(v); return true;}\
bool erase(const value_type& v){DeleteNode(FindNode(v)); return true;}\
\
DATATYPE& operator[] (const KEYTYPE& key) \
{ \
node_type* node = FindNode(value_type(key)); \
if (node)\
return node->Key.second;\
else\
return tree_type::Insert(value_type(key))->Key.second;\
} \
};
int CS_Compare(const char* s1, const char* s2, const bool& bCaseInsensitive = false);
#define DECLARE_DICTIONARY(NAME, DATATYPE)\
static bool NAME##COMPARE(const char* s1, const char* s2, void*);\
DECLARE_MAP(NAME##MAP, char*, DATATYPE, NAME##COMPARE);\
\
class NAME : public NAME##MAP \
{\
public:\
NAME() : CompareMode(false) {} ~NAME(){}\
\
/*typedef*/\
typedef NAME##MAP map_type;\
typedef map_type::value_type value_type;\
\
/*members*/\
bool CompareMode;\
\
DATATYPE& operator () (const char* key) {return (*this)[key];}\
};\
\
static bool NAME##COMPARE(const char* s1, const char* s2, void* pThis)\
{\
return CS_Compare(s1,s2,((NAME*)pThis)->CompareMode)< 0;\
}
#define DECLARE_WXDICTIONARY(NAME, DATATYPE)\
static bool NAME##COMPARE(const wxString& s1, const wxString& s2, void*);\
DECLARE_MAP(NAME##MAP, wxString, DATATYPE, NAME##COMPARE);\
\
class NAME : public NAME##MAP \
{\
public:\
NAME() : CompareMode(false) {} ~NAME(){}\
\
/*typedef*/\
typedef NAME##MAP map_type;\
typedef map_type::value_type value_type;\
\
/*members*/\
bool CompareMode;\
\
DATATYPE& operator () (const wxString& key) {return (*this)[key];}\
};\
\
static bool NAME##COMPARE(const wxString& s1, const wxString& s2, void* pThis)\
{\
if(((NAME*)pThis)->CompareMode)\
return s1.CmpNoCase(s2)< 0;\
else\
return s1.Cmp(s2)< 0;\
}
[/syntax]
There is nothing in wx that sorts keys in a general way like std::map does. Note that keys in wxHashMap are _not_ sorted.
You can try the following - it's not 100% complete, but its fast (faster than most stl implementations) and supports the most common stl::map functions.
DECLARE_MAP(NAME, KEYTYPE, DATATYPE, COMPARE)
NAME=Name of class
KEYTYPE=Key type
DATATYPE=Element type
COMPARE=Compare function - usually want something like
bool mycompare(T e1, T e2, void*){return e1 < e2;}
[syntax="c"]
//(c) (wxWidgets) by Ryan Norton
#define RED 0
#define BLACK 1
#define THREAD 0
#define LINK 1
#include <stddef.h>
#define DECLARE_PAIR(NAME,KEYTYPE,DATATYPE, COMPARE)\
class NAME \
{\
typedef KEYTYPE t1;\
typedef DATATYPE t2;\
public:\
NAME(){}\
NAME(const KEYTYPE& key) : first(t1(key)){}\
NAME(const KEYTYPE& key, const DATATYPE& data) : first(t1(key)), second(t2(data)) {}\
\
static bool KeyCompare(const NAME& n1, const NAME& n2, void* parm) {return COMPARE(n1.first, n2.first, parm);}\
KEYTYPE first; DATATYPE second;\
};
#define DECLARE_REDBLACKTREE(NAME,KEYTYPE,COMPARE) \
struct NAME##Node \
{ \
public: \
NAME##Node ( const KEYTYPE& crKey, \
NAME##Node*& prLeftChild, NAME##Node*& prRightChild, \
const bool& cbrIsRightChild, const bool& cbrHasLeftLink, \
const bool& cbrHasRightLink, const bool& cbrColor ) : \
Key(crKey), \
pLeftChild(prLeftChild), pRightChild(prRightChild), \
bIsRightChild(cbrIsRightChild), \
bHasLeftLink(cbrHasLeftLink), \
bHasRightLink(cbrHasRightLink), \
bColor(cbrColor) \
{ \
} \
\
NAME##Node ( const KEYTYPE& crKey, \
NAME##Node*& prLeftChild, NAME##Node* prRightChild, \
const bool& cbrHasLeftLink, const bool& cbrHasRightLink, \
const bool& cbrColor ) : \
Key(crKey), \
pLeftChild(prLeftChild), pRightChild(prRightChild), \
bIsRightChild(false), bHasLeftLink(cbrHasLeftLink), \
bHasRightLink(cbrHasRightLink), bColor(cbrColor) \
{ \
} \
\
NAME##Node ( NAME##Node* pLeftChild, NAME##Node* pRightChild, \
const bool& cbrHasLeftLink, const bool& cbrHasRightLink, \
const bool& cbrColor ) : \
pLeftChild(pLeftChild), pRightChild(pRightChild), \
bIsRightChild(false), bHasLeftLink(cbrHasLeftLink), \
bHasRightLink(cbrHasRightLink), bColor(cbrColor) \
{ \
} \
\
~NAME##Node() \
{ \
} \
\
KEYTYPE Key; \
NAME##Node* pLeftChild; \
NAME##Node* pRightChild; \
bool bIsRightChild; \
bool bHasLeftLink; \
bool bHasRightLink; \
bool bColor; \
}; \
class NAME \
{ \
public: \
typedef NAME##Node node_type; \
NAME() : \
HeadNode(&HeadNode, &HeadNode, THREAD, LINK, BLACK) \
{ \
} \
\
~NAME() \
{ \
Clear(); \
} \
\
bool Delete(const KEYTYPE& rKey) \
{ \
register node_type* pFoundNode = FindNode(rKey); \
\
return (pFoundNode ? DeleteNode(pFoundNode), true : false); \
} \
\
void DeleteAll() \
{ \
Clear(); \
\
HeadNode.bHasLeftLink = THREAD; \
HeadNode.pLeftChild = &HeadNode; \
} \
\
KEYTYPE& Find(const KEYTYPE& rKey) \
{ \
node_type* pFoundNode = FindNode(rKey); \
return pFoundNode == NULL ? (KEYTYPE&) rKey : pFoundNode->Key; \
} \
\
\
static inline int Max(const int& x, const int& y) \
{ \
return x > y ? x : y; \
} \
\
static inline void Swap (size_t& x, size_t& y) \
{ \
x = x ^ y; \
y = x ^ y; \
x = x ^ y; \
} \
\
\
static const bool& HasLeftLink(node_type* pNode) \
{ \
return pNode->bHasLeftLink; \
} \
\
static const bool& HasRightLink(node_type* pNode) \
{ \
return pNode->bHasRightLink; \
} \
\
node_type* LeftChild(node_type* pNode) \
{ \
return (HasLeftLink(pNode) ? pNode->pLeftChild : NULL); \
} \
\
node_type* RightChild(node_type* pNode) \
{ \
return (HasRightLink(pNode) ? pNode->pRightChild : NULL); \
} \
\
bool IsHeadNode(node_type*& prNode) \
{ \
return ((prNode)->pRightChild == (prNode)); \
} \
\
node_type* Predeccessor(node_type* pNode) \
{ \
if (!pNode) \
return NULL; \
\
register node_type* pRetNode; \
pRetNode = pNode->pLeftChild; \
\
if (HasLeftLink(pNode)) \
while (HasRightLink(pRetNode)) \
pRetNode = pRetNode->pRightChild; \
\
return (IsHeadNode(pRetNode) ? NULL : pRetNode); \
} \
\
node_type* Successor(node_type* pNode) \
{ \
if (!pNode) \
return NULL; \
\
register node_type* pRetNode; \
pRetNode = pNode->pRightChild; \
\
if (HasRightLink(pNode)) \
while (HasLeftLink(pRetNode)) \
pRetNode = pRetNode->pLeftChild; \
\
return (IsHeadNode(pRetNode) ? NULL : pRetNode); \
} \
\
node_type* FindMinNode(node_type* pNode) const \
{ \
while (HasLeftLink(pNode)) \
pNode = pNode->pLeftChild; \
\
return pNode; \
} \
\
node_type* FindMaxNode(node_type* pNode) const \
{ \
while (HasRightLink(pNode)) \
pNode = pNode->pRightChild; \
\
return pNode; \
} \
\
node_type* FindParentNode(node_type*& pNode) const \
{ \
if(pNode->bIsRightChild) \
return FindMinNode(pNode)->pLeftChild; \
else \
return FindMaxNode(pNode)->pRightChild; \
} \
\
void Clear() \
{ \
register node_type* pNodeToDelete; \
register node_type* pSuccessorNode = Successor(Reset()); \
\
while (pSuccessorNode != NULL) \
{ \
pSuccessorNode = Successor(pNodeToDelete = pSuccessorNode); \
delete pNodeToDelete; \
} \
\
HeadNode.bHasLeftLink = false; \
HeadNode.pLeftChild = &HeadNode; \
} \
\
\
node_type* FindNode (const KEYTYPE& key) \
{ \
register node_type* p = HeadNode.pLeftChild; \
register bool bLess; \
\
if (!HasLeftLink(&HeadNode)) \
return NULL; \
\
for(;;) \
{ \
bLess = COMPARE(key , p->Key, this); \
if (bLess) \
{ \
if(!HasLeftLink(p)) \
break; \
else \
p = p->pLeftChild; \
} \
else \
{ \
if(!HasRightLink(p)) \
break; \
else \
p = p->pRightChild; \
} \
} \
\
if(bLess) \
p = Predeccessor(p); \
\
return p && !COMPARE(p->Key, key, this) ? p : NULL; \
} \
\
\
node_type* Insert(const KEYTYPE& key, \
const bool& bReplace = false) \
{ \
\
if (!HasLeftLink(&HeadNode)) \
{ \
HeadNode.bHasLeftLink = LINK; \
return HeadNode.pLeftChild = \
new node_type(key, HeadNode.pLeftChild, &HeadNode, \
THREAD, THREAD, BLACK); \
} \
else \
{ \
register node_type* p = HeadNode.pLeftChild; \
register node_type* y; \
register bool bLess; \
for(;;) \
{ \
\
\
bLess = COMPARE(key , p->Key, this); \
\
\
if (bLess) \
{ \
if(!HasLeftLink(p)) \
break; \
else \
p = p->pLeftChild; \
} \
\
else \
{ \
if(!HasRightLink(p)) \
break; \
else \
p = p->pRightChild; \
} \
\
} \
\
if (bLess) \
y = Predeccessor(p); \
else \
y = p; \
\
if (y && !COMPARE(y->Key, key, this)) \
{ \
\
\
\
\
if (bReplace) \
{ \
p->Key = key; \
} \
else \
\
p = NULL; \
\
return p; \
} \
\
if(bLess) \
{ \
p->bHasLeftLink = LINK; \
p->pLeftChild = y = \
new node_type(key, p->pLeftChild, p, 0, \
THREAD, THREAD, RED); \
} \
else \
{ \
p->bHasRightLink = LINK; \
p->pRightChild = y = \
new node_type(key, p, p->pRightChild, 1, \
THREAD, THREAD, RED); \
} \
\
\
p = y; \
\
\
\
Rebalance(p); \
\
return y; \
} \
} \
\
node_type* InsertMulti(const KEYTYPE& key) \
{ \
\
if (!HasLeftLink(&HeadNode)) \
{ \
HeadNode.bHasLeftLink = LINK; \
return HeadNode.pLeftChild = \
new node_type(key, HeadNode.pLeftChild, &HeadNode, \
THREAD, THREAD, BLACK); \
} \
else \
{ \
register node_type* p = HeadNode.pLeftChild; \
register node_type* y; \
register bool bLess; \
for(;;) \
{ \
bLess = COMPARE(key , p->Key, this); \
\
if (bLess) \
{ \
if(!HasLeftLink(p)) \
break; \
else \
p = p->pLeftChild; \
} \
\
else \
{ \
if(!HasRightLink(p)) \
break; \
else \
p = p->pRightChild; \
} \
\
} \
\
if(bLess) \
{ \
p->bHasLeftLink = LINK; \
p->pLeftChild = y = \
new node_type(key, p->pLeftChild, p, 0, \
THREAD, THREAD, RED); \
} \
else \
{ \
p->bHasRightLink = LINK; \
p->pRightChild = y = \
new node_type(key, p, p->pRightChild, 1, \
THREAD, THREAD, RED); \
} \
\
\
p = y; \
\
Rebalance(p); \
\
return y; \
} \
} \
\
void Rebalance(node_type*& p) \
{ \
register node_type* f; \
register node_type* q; \
\
while ( p != HeadNode.pLeftChild && \
(q=FindParentNode(p))->bColor == RED) \
{ \
f = FindParentNode(q); \
wxASSERT((!IsHeadNode(f)) && (f->bColor == BLACK)); \
\
if (q->bIsRightChild) \
{ \
if (HasLeftLink(f) && f->pLeftChild->bColor == RED) \
{ \
q->bColor = f->pLeftChild->bColor = BLACK; \
f->bColor = RED; \
p = f; \
} \
else \
{ \
if (!p->bIsRightChild) \
{ \
RotateRight(q); \
Swap((size_t&) q, (size_t&) p); \
} \
\
q->bColor = BLACK; \
f->bColor = RED; \
RotateLeft(f); \
break; \
} \
} \
else \
{ \
if (HasRightLink(f) && f->pRightChild->bColor == RED) \
{ \
q->bColor = f->pRightChild->bColor = BLACK; \
f->bColor = RED; \
p = f; \
} \
else \
{ \
if (p->bIsRightChild) \
{ \
RotateLeft(q); \
Swap((size_t&)q, (size_t&) p); \
} \
\
q->bColor = BLACK; \
f->bColor = RED; \
RotateRight(f); \
break; \
} \
} \
} \
\
HeadNode.pLeftChild->bColor = BLACK; \
} \
\
void DeleteNode(node_type* pNode) \
{ \
node_type* pTempNode; \
\
if (!pNode || IsHeadNode(pNode)) \
return; \
\
\
for (;;) \
{ \
if (HasRightLink(pNode)) \
{ \
pTempNode = FindMinNode(pNode->pRightChild); \
pNode->Key = pTempNode->Key; \
} \
else if (HasLeftLink(pNode)) \
{ \
pTempNode = FindMaxNode(pNode->pLeftChild); \
pNode->Key = pTempNode->Key; \
} \
else \
break; \
\
pNode = pTempNode; \
} \
\
pTempNode = FindParentNode(pNode); \
\
if (pNode->bIsRightChild) \
{ \
pTempNode->pRightChild = pNode->pRightChild; \
pTempNode->bHasRightLink = THREAD; \
} \
else \
{ \
pTempNode->pLeftChild = pNode->pLeftChild; \
pTempNode->bHasLeftLink = THREAD; \
} \
\
\
\
\
if (pNode->bColor == BLACK) \
Restructure(pNode); \
\
\
delete (pNode); \
} \
\
inline void Restructure(node_type* p) \
{ \
node_type* q; \
\
while ((p->bColor == BLACK) && !(q = FindParentNode(p),IsHeadNode(q))) \
{ \
if (p->bIsRightChild) \
{ \
wxASSERT(HasLeftLink(q)); \
if (q->pLeftChild->bColor == RED) \
{ \
q->bColor = RED; \
q->pLeftChild->bColor = BLACK; \
RotateRight(q); \
} \
if ( \
(!HasLeftLink(q->pLeftChild) || \
q->pLeftChild->pLeftChild->bColor == BLACK) && \
(!HasRightLink(q->pLeftChild) || \
q->pLeftChild->pRightChild->bColor == BLACK) \
) \
{ \
q->pLeftChild->bColor = RED; \
p = q; \
} \
else \
{ \
if (!HasLeftLink(q->pLeftChild) || \
q->pLeftChild->pLeftChild->bColor == BLACK) \
{ \
q->pLeftChild->pRightChild->bColor = BLACK; \
q->pLeftChild->bColor = RED; \
RotateLeft(q->pLeftChild); \
} \
q->pLeftChild->bColor = q->bColor; \
q->bColor = BLACK; \
q->pLeftChild->pLeftChild->bColor = BLACK; \
RotateRight(q); \
break; \
} \
} \
else \
{ \
wxASSERT(HasRightLink(q)); \
if (q->pRightChild->bColor == RED) \
{ \
q->bColor = RED; \
q->pRightChild->bColor = BLACK; \
RotateLeft(q); \
} \
if ( \
(!HasLeftLink(q->pRightChild) || \
q->pRightChild->pLeftChild->bColor == BLACK) && \
(!HasRightLink(q->pRightChild) || \
q->pRightChild->pRightChild->bColor == BLACK) \
) \
{ \
q->pRightChild->bColor = RED; \
p = q; \
} \
else \
{ \
if (!HasRightLink(q->pRightChild) || \
q->pRightChild->pRightChild->bColor == BLACK) \
{ \
q->pRightChild->pLeftChild->bColor = BLACK; \
q->pRightChild->bColor = RED; \
RotateRight(q->pRightChild); \
} \
q->pRightChild->bColor = q->bColor; \
q->bColor = BLACK; \
q->pRightChild->pRightChild->bColor = BLACK; \
RotateLeft(q); \
break; \
} \
} \
} \
p->bColor = BLACK; \
} \
\
\
node_type* Reset() \
{ \
return &HeadNode; \
} \
\
void RotateLeft(node_type* pNode) \
{ \
node_type* pRightChildOfNode = pNode->pRightChild; \
node_type* pParentOfNode = FindParentNode(pNode); \
\
if (pNode->bIsRightChild) \
{ \
pParentOfNode->pRightChild = pRightChildOfNode; \
pNode->bIsRightChild = false; \
} \
else \
{ \
pParentOfNode->pLeftChild = pRightChildOfNode; \
pRightChildOfNode->bIsRightChild = false; \
} \
\
if (HasLeftLink(pRightChildOfNode)) \
{ \
pNode->pRightChild = pRightChildOfNode->pLeftChild; \
pNode->pRightChild->bIsRightChild = true; \
pRightChildOfNode->pLeftChild = pNode; \
} \
else \
{ \
pRightChildOfNode->bHasLeftLink = LINK; \
pNode->bHasRightLink = THREAD; \
} \
} \
\
void RotateRight(node_type* pNode) \
{ \
node_type* pLeftChildOfNode = pNode->pLeftChild; \
node_type* pParentOfNode = FindParentNode(pNode); \
\
if (pNode->bIsRightChild) \
{ \
pParentOfNode->pRightChild = pLeftChildOfNode; \
pLeftChildOfNode->bIsRightChild = true; \
} \
else \
{ \
pParentOfNode->pLeftChild = pLeftChildOfNode; \
pNode->bIsRightChild = true; \
} \
\
if (HasRightLink(pLeftChildOfNode)) \
{ \
pNode->pLeftChild = pLeftChildOfNode->pRightChild; \
pNode->pLeftChild->bIsRightChild = false; \
pLeftChildOfNode->pRightChild = pNode; \
} \
else \
{ \
pLeftChildOfNode->bHasRightLink = LINK; \
pNode->bHasLeftLink = THREAD; \
} \
} \
\
node_type HeadNode; \
};
#define DECLARE_MAP(NAME, KEYTYPE, DATATYPE, COMPARE)\
\
DECLARE_PAIR(NAME##PAIR, KEYTYPE, DATATYPE, COMPARE);\
DECLARE_REDBLACKTREE(NAME##RBT, NAME##PAIR, NAME##PAIR::KeyCompare);\
\
class NAME : protected NAME##RBT \
{ \
public: \
NAME(){}~NAME(){} \
\
/*stl typedefs*/ \
typedef size_t difference_type; \
typedef KEYTYPE key_type;\
typedef DATATYPE mapped_type;\
typedef size_t size_type;\
typedef NAME##PAIR value_type; \
typedef NAME##RBT tree_type; \
\
/*internal typedefs*/\
typedef NAME##RBT::node_type node_type; \
\
/*iterator*/ \
class iterator \
{ \
public: \
iterator() : m_pKey(NULL) {} \
iterator(const iterator& it) \
: m_pTree(it.m_pTree), m_pKey(it.m_pKey) {} \
iterator(tree_type* pTree, node_type* pKey) \
: m_pTree(pTree), m_pKey(pKey) {} \
\
iterator operator ++(int nIncrement) \
{iterator iRet = *this; ++*this; return iRet;} \
\
iterator operator --(int nIncrement) \
{iterator iRet = *this; --*this; return iRet;} \
\
iterator& operator ++() \
{m_pKey = m_pTree->Successor(m_pKey); return *this;} \
\
iterator& operator --() \
{m_pKey = m_pTree->Predeccessor(m_pKey); return *this;} \
\
int operator == (const iterator& i) {return this->m_pKey == i.m_pKey;} \
int operator != (const iterator& i) {return this->m_pKey != i.m_pKey;} \
\
iterator& operator = (const iterator& i) \
{ this->m_pTree = i.m_pTree; this->m_pKey = i.m_pKey;} \
\
value_type& operator * () {return (m_pKey)->Key;} \
protected: \
tree_type* m_pTree; \
node_type* m_pKey; \
}; \
\
iterator begin() \
{ \
return iterator((tree_type*)this, \
FindMinNode(Successor(Reset()))); \
} \
\
void clear() \
{ \
DeleteAll(); \
} \
\
size_t count(const KEYTYPE& Key) \
{ \
if(FindNode(Key)) \
return 1; \
return 0; \
} \
bool empty() {return !HasLeftLink(&HeadNode);} \
iterator find(const KEYTYPE& key) \
{\
node_type* node = FindNode(key);\
if(!node)\
return iterator();\
return iterator(((tree_type*)this), node);\
}\
\
\
iterator end() \
{ \
return iterator(); \
} \
\
bool insert(const value_type& v){Insert(v); return true;}\
bool erase(const value_type& v){DeleteNode(FindNode(v)); return true;}\
\
DATATYPE& operator[] (const KEYTYPE& key) \
{ \
node_type* node = FindNode(value_type(key)); \
if (node)\
return node->Key.second;\
else\
return tree_type::Insert(value_type(key))->Key.second;\
} \
};
int CS_Compare(const char* s1, const char* s2, const bool& bCaseInsensitive = false);
#define DECLARE_DICTIONARY(NAME, DATATYPE)\
static bool NAME##COMPARE(const char* s1, const char* s2, void*);\
DECLARE_MAP(NAME##MAP, char*, DATATYPE, NAME##COMPARE);\
\
class NAME : public NAME##MAP \
{\
public:\
NAME() : CompareMode(false) {} ~NAME(){}\
\
/*typedef*/\
typedef NAME##MAP map_type;\
typedef map_type::value_type value_type;\
\
/*members*/\
bool CompareMode;\
\
DATATYPE& operator () (const char* key) {return (*this)[key];}\
};\
\
static bool NAME##COMPARE(const char* s1, const char* s2, void* pThis)\
{\
return CS_Compare(s1,s2,((NAME*)pThis)->CompareMode)< 0;\
}
#define DECLARE_WXDICTIONARY(NAME, DATATYPE)\
static bool NAME##COMPARE(const wxString& s1, const wxString& s2, void*);\
DECLARE_MAP(NAME##MAP, wxString, DATATYPE, NAME##COMPARE);\
\
class NAME : public NAME##MAP \
{\
public:\
NAME() : CompareMode(false) {} ~NAME(){}\
\
/*typedef*/\
typedef NAME##MAP map_type;\
typedef map_type::value_type value_type;\
\
/*members*/\
bool CompareMode;\
\
DATATYPE& operator () (const wxString& key) {return (*this)[key];}\
};\
\
static bool NAME##COMPARE(const wxString& s1, const wxString& s2, void* pThis)\
{\
if(((NAME*)pThis)->CompareMode)\
return s1.CmpNoCase(s2)< 0;\
else\
return s1.Cmp(s2)< 0;\
}
[/syntax]