Page 1 of 1

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

Posted: Fri Sep 17, 2004 8:16 am
by Ryan Norton
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]

Great stuff!

Posted: Fri Sep 17, 2004 12:54 pm
by eduardof
Great stuff. Very fast indeed.

Posted: Wed Jun 15, 2005 11:27 am
by KaReL
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;} \

Posted: Wed Jun 15, 2005 3:59 pm
by Ryan Norton
Looks like some of it got cut off :\.

Posted: Thu Jun 16, 2005 2:42 am
by KaReL

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 :(

Posted: Thu Jun 16, 2005 11:18 pm
by leio
Sorry for asking, but what is actually the problem of using stl::map itself?

Posted: Thu Jun 16, 2005 11:30 pm
by Ryan Norton
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 :)

Posted: Fri Jun 17, 2005 4:29 am
by KaReL
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.

Posted: Fri Jun 17, 2005 9:17 am
by leio
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?).

Posted: Fri Jun 17, 2005 9:27 am
by Ryan Norton
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)