Storage container for sorting keys(cross-compiler stl::map)

If you have a cool piece of software to share, but you are not hosting it officially yet, please dump it in here. If you have code snippets that are useful, please donate!
Post Reply
User avatar
Ryan Norton
Moderator
Moderator
Posts: 1319
Joined: Mon Aug 30, 2004 6:01 pm

Storage container for sorting keys(cross-compiler stl::map)

Post by Ryan Norton » 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]
Last edited by Ryan Norton on Thu Sep 23, 2004 9:03 am, edited 1 time in total.
[Mostly retired moderator, still check in to clean up some stuff]

eduardof
In need of some credit
In need of some credit
Posts: 9
Joined: Thu Sep 16, 2004 9:19 pm
Location: Curitiba - PR - BRAZIL
Contact:

Great stuff!

Post by eduardof » Fri Sep 17, 2004 12:54 pm

Great stuff. Very fast indeed.
Eduardo B. Fonseca
wxWidgets developer since 2001

KaReL
Experienced Solver
Experienced Solver
Posts: 78
Joined: Mon Aug 30, 2004 8:52 am
Contact:

Post by KaReL » Wed Jun 15, 2005 11:27 am

I modified the version of Ryan a little so it could work with const_iterators. I also speeded up (if the compiler accepts it ofcourse) by adding a lot of const's everywhere.

For examples: look below the code ;)

Code: Select all

#ifndef __WXMAP_H
#define __WXMAP_H

#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)                     \
    {                                                                          \
        return COMPARE()(n1.first, n2.first);                                  \
    }                                                                          \
                                                                               \
    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) const                                   \
    {                                                                          \
        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;                                                             \
    }                                                                          \
                                                                               \
    bool HasLeftLink(node_type const * pNode) const                            \
    {                                                                          \
        return pNode->bHasLeftLink;                                            \
    }                                                                          \
                                                                               \
    bool HasRightLink(node_type const * pNode) const                           \
    {                                                                          \
        return pNode->bHasRightLink;                                           \
    }                                                                          \
                                                                               \
    node_type* LeftChild(node_type const * pNode) const                        \
    {                                                                          \
      return (HasLeftLink(pNode) ? pNode->pLeftChild : NULL);                  \
    }                                                                          \
                                                                               \
    node_type* RightChild(node_type const * pNode) const                       \
    {                                                                          \
        return (HasRightLink(pNode) ? pNode->pRightChild : NULL);              \
    }                                                                          \
                                                                               \
    bool IsHeadNode(node_type const *& prNode) const                           \
    {                                                                          \
        return ((prNode)->pRightChild == (prNode));                            \
    }                                                                          \
                                                                               \
    node_type* Predeccessor(node_type const * pNode) const                     \
    {                                                                          \
        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 const * pNode) const                        \
    {                                                                          \
        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) const                             \
    {                                                                          \
        register node_type* p = HeadNode.pLeftChild;                           \
        register bool bLess;                                                   \
                                                                               \
        if (!HasLeftLink(&HeadNode))                                           \
            return NULL;                                                       \
                                                                               \
        for(;;)                                                                \
        {                                                                      \
            bLess = COMPARE(key , p->Key);                                     \
            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) ? p : NULL;                         \
    }                                                                          \
                                                                               \
                                                                               \
    node_type* Insert(const KEYTYPE& key, 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);                                 \
                                                                               \
                                                                               \
                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))                             \
            {                                                                  \
                                                                               \
                                                                               \
                                                                               \
                                                                               \
                       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);                                 \
                                                                               \
                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 WX_DECLARE_MAP(KEYTYPE, DATATYPE, COMPARE, NAME)                       \
                                                                               \
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 ++()                                              \
        {m_pKey = m_pTree->Successor(m_pKey); return *this;}                   \
        iterator&   operator ++(int)                                           \
        { return operator++(); }                                               \
                                                                               \
        iterator&   operator --()                                              \
        {m_pKey = m_pTree->Predeccessor(m_pKey); return *this;}                \
        iterator&   operator --(int)                                           \
        { return operator--(); }                                               \
                                                                               \
        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*/                                                               \
    class const_iterator                                                       \
    {                                                                          \
    public:                                                                    \
        const_iterator() : m_pKey(NULL) {}                                     \
        const_iterator(const const_iterator& it)                               \
            : m_pTree(it.m_pTree), m_pKey(it.m_pKey) {}                        \
        const_iterator(tree_type* pTree, node_type* pKey)                      \
            : m_pTree(pTree), m_pKey(pKey) {}                                  \
                                                                               \
        const_iterator&   operator ++()                                        \
        {m_pKey = m_pTree->Successor(m_pKey); return *this;}                   \
        const_iterator&   operator ++(int)                                     \
        { return operator++(); }                                               \
                                                                               \
        const_iterator&   operator --()                                        \
        {m_pKey = m_pTree->Predeccessor(m_pKey); return *this;}                \
        const_iterator&   operator --(int)                                     \
        { return operator--(); }                                               \
                                                                               \
        int operator == (const const_iterator& i) const {return this->m_pKey == i.m_pKey;} \
        int operator != (const const_iterator& i) const {return this->m_pKey != i.m_pKey;} \
Last edited by KaReL on Thu Jun 16, 2005 2:40 am, edited 3 times in total.
wxWidgets: SVN/trunk
OS: WinXP/2 + Ubuntu + Mac 10.4.11
Compiler: VS2005 + GCC 4.2 + GCC 4.0.1
-----
home: http://www.salvania.be

User avatar
Ryan Norton
Moderator
Moderator
Posts: 1319
Joined: Mon Aug 30, 2004 6:01 pm

Post by Ryan Norton » Wed Jun 15, 2005 3:59 pm

Looks like some of it got cut off :\.
[Mostly retired moderator, still check in to clean up some stuff]

KaReL
Experienced Solver
Experienced Solver
Posts: 78
Joined: Mon Aug 30, 2004 8:52 am
Contact:

Post by KaReL » Thu Jun 16, 2005 2:42 am

Code: Select all

                                                                               \
        const_iterator& operator = (const const_iterator& i)                   \
        { this->m_pTree = i.m_pTree; this->m_pKey = i.m_pKey;}                 \
                                                                               \
        value_type& operator * () const {return (m_pKey)->Key;}                \
    protected:                                                                 \
        tree_type* m_pTree;                                                    \
        node_type* m_pKey;                                                     \
    };                                                                         \
                                                                               \
    iterator begin()                                                           \
    {                                                                          \
        return iterator((tree_type*)this,                                      \
            FindMinNode(Successor(Reset())));                                  \
    }                                                                          \
                                                                               \
    const_iterator begin() const                                               \
    {                                                                          \
        return const_iterator((tree_type*)this,                                \
            FindMinNode(Successor(&HeadNode)));                                \
    }                                                                          \
                                                                               \
    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);                             \
    }                                                                          \
    const_iterator find(const KEYTYPE& key) const                              \
    {                                                                          \
        node_type* node = FindNode(key);                                       \
        if(!node)                                                              \
            return const_iterator();                                           \
        return const_iterator(((tree_type*)this), node);                       \
    }                                                                          \
                                                                               \
    const_iterator end() const                                                 \
    {                                                                          \
        return const_iterator();                                               \
    }                                                                          \
                                                                               \
    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;             \
    }                                                                          \
};
#include <wx/string.h> // wxString
class WXDLLIMPEXP_BASE wxStringCompare
{
public:
  wxStringCompare() {}

  bool operator() ( const wxString& a, const wxString& b ) const { return a.Cmp(b) < 0; }
  bool operator() ( const wxChar*   a, const wxChar*   b ) const { return wxStrcmp ( a, b ) < 0; }

#if wxUSE_UNICODE
  bool operator() ( const char*     a, const char*     b ) const { return strcmp ( a, b ) < 0; }
#endif // wxUSE_UNICODE

  wxStringCompare& operator=(const wxStringCompare&) { return *this; }
};

class WXDLLIMPEXP_BASE wxStringCompareNoCase
{
public:
  wxStringCompareNoCase() {}

  bool operator() ( const wxString& a, const wxString& b ) const { return a.CmpNoCase(b) < 0; }
  bool operator() ( const wxChar*   a, const wxChar*   b ) const { return wxStricmp ( a, b ) < 0; }

#if wxUSE_UNICODE
  bool operator() ( const char*     a, const char*     b ) const { return stricmp ( a, b ) < 0; }
#endif // wxUSE_UNICODE

  wxStringCompareNoCase& operator=(const wxStringCompareNoCase&) { return *this; }
};

class WXDLLIMPEXP_BASE wxIntegerCompare
{
public:
  wxIntegerCompare( ) {}

  bool operator() ( double         a, double         b ) const { return a < b; }
  bool operator() ( long           a, long           b ) const { return a < b; }
  bool operator() ( unsigned long  a, unsigned long  b ) const { return a < b; }
  bool operator() ( int            a, int            b ) const { return a < b; }
  bool operator() ( unsigned int   a, unsigned int   b ) const { return a < b; }
  bool operator() ( short          a, short          b ) const { return a < b; }
  bool operator() ( unsigned short a, unsigned short b ) const { return a < b; }

  wxIntegerCompare& operator=(const wxIntegerCompare&) { return *this; }
};

//////////////////////////////////////////////////////////////////////////
// Different maps
#define WX_DECLARE_STRING_MAP(DATATYPE, NAME)   WX_DECLARE_MAP(wxString, DATATYPE, wxStringCompare , NAME);
#define WX_DECLARE_INT_MAP(DATATYPE, NAME)      WX_DECLARE_MAP(int     , DATATYPE, wxIntegerCompare, NAME);
#define WX_DECLARE_LONG_MAP(DATATYPE, NAME)     WX_DECLARE_MAP(long    , DATATYPE, wxIntegerCompare, NAME);
#define WX_DECLARE_DOUBLE_MAP(DATATYPE, NAME)   WX_DECLARE_MAP(double  , DATATYPE, wxIntegerCompare, NAME);

#endif // __WXMAP_H
Usage:

Code: Select all

wx_DECLARE_MAP(key_type, value_type, comparer_function, name);
WX_DECLARE_STRING_MAP(value_type, name); // key = wxString
WX_DECLARE_INT_MAP(value_type, name); // key = int
WX_DECLARE_LONG_MAP(value_type, name); // key = long
WX_DECLARE_DOUBLE_MAP(value_type, name); // key = double
Code got cut off because too long :(
wxWidgets: SVN/trunk
OS: WinXP/2 + Ubuntu + Mac 10.4.11
Compiler: VS2005 + GCC 4.2 + GCC 4.0.1
-----
home: http://www.salvania.be

leio
Can't get richer than this
Can't get richer than this
Posts: 802
Joined: Mon Dec 27, 2004 10:46 am
Location: Estonia, Tallinn
Contact:

Post by leio » Thu Jun 16, 2005 11:18 pm

Sorry for asking, but what is actually the problem of using stl::map itself?
Compilers: gcc-3.3.6, gcc-3.4.5, gcc-4.0.2, gcc-4.1.0 and MSVC6
OS's: Gentoo Linux, WinXP; WX: CVS HEAD

Project Manager of wxMUD - http://wxmud.sf.net/
Developer of wxGTK;
gtk+ port maintainer of OMGUI - http://www.omgui.org/

User avatar
Ryan Norton
Moderator
Moderator
Posts: 1319
Joined: Mon Aug 30, 2004 6:01 pm

Post by Ryan Norton » Thu Jun 16, 2005 11:30 pm

leio wrote:Sorry for asking, but what is actually the problem of using stl::map itself?
Nothing if you don't mind using the STL. Of course, mine is faster :)
[Mostly retired moderator, still check in to clean up some stuff]

KaReL
Experienced Solver
Experienced Solver
Posts: 78
Joined: Mon Aug 30, 2004 8:52 am
Contact:

Post by KaReL » Fri Jun 17, 2005 4:29 am

And some compilers don't understand STL (which in fact? :p)... Mostly because of STL-thingies... Ryans macro's and my modifications should work on nearly all compilers.
wxWidgets: SVN/trunk
OS: WinXP/2 + Ubuntu + Mac 10.4.11
Compiler: VS2005 + GCC 4.2 + GCC 4.0.1
-----
home: http://www.salvania.be

leio
Can't get richer than this
Can't get richer than this
Posts: 802
Joined: Mon Dec 27, 2004 10:46 am
Location: Estonia, Tallinn
Contact:

Post by leio » Fri Jun 17, 2005 9:17 am

KaReL wrote:And some compilers don't understand STL (which in fact? :p)... Mostly because of STL-thingies... Ryans macro's and my modifications should work on nearly all compilers.
Yeah, that's the point (which compilers). I can say in a very justified way that I simply don't support ancient and non-standard compilers that don't even support the C++ standard. I don't know of any compilers that don't support STL though. I only know that VC6 has some problems in some rarer cases. And VC6 is what, 5 years old?, and shouldn't really be supported. We shouldn't stop the evolvment of our code due to compilers that are older than any other tool/library/OS we use. In the computer world 5 years is like a century for other stuff.
I'm actually not trying to use STL these days whenever I can, but also looking into boost, that will most likely be part of the new C++ standard due in some years (2010?).
Compilers: gcc-3.3.6, gcc-3.4.5, gcc-4.0.2, gcc-4.1.0 and MSVC6
OS's: Gentoo Linux, WinXP; WX: CVS HEAD

Project Manager of wxMUD - http://wxmud.sf.net/
Developer of wxGTK;
gtk+ port maintainer of OMGUI - http://www.omgui.org/

User avatar
Ryan Norton
Moderator
Moderator
Posts: 1319
Joined: Mon Aug 30, 2004 6:01 pm

Post by Ryan Norton » Fri Jun 17, 2005 9:27 am

leio wrote:Yeah, that's the point (which compilers).
Embedded C++ ones don't have a full STL (although I'm not 100% sure if WX supports those, although I imagine it does)
[Mostly retired moderator, still check in to clean up some stuff]

Post Reply