#ifndef KWQ_MAP_IMPL_H
#define KWQ_MAP_IMPL_H
#include <new>
#include "KWQRefPtr.h"
class KWQMapNodeImpl
{
protected:
typedef enum { Red = 0, Black = 1 } KWQMapNodeColor;
KWQMapNodeImpl();
KWQMapNodeImpl *left();
const KWQMapNodeImpl *left() const;
KWQMapNodeImpl *right();
const KWQMapNodeImpl *right() const;
KWQMapNodeImpl *predecessor();
const KWQMapNodeImpl *predecessor() const;
KWQMapNodeImpl *successor();
const KWQMapNodeImpl *successor() const;
KWQMapNodeImpl *prev;
KWQMapNodeImpl *next;
bool prevIsChild;
bool nextIsChild;
KWQMapNodeColor color;
friend class KWQMapImpl;
friend class KWQMapIteratorImpl;
#ifdef QMAP_TESTING
friend bool CheckRedBlackRules(KWQMapImpl *impl);
friend bool CheckRedBlackRulesAtNode(KWQMapImpl *impl, KWQMapNodeImpl *node, int &black_height);
#endif
};
class KWQMapIteratorImpl {
protected:
KWQMapNodeImpl *node;
KWQMapIteratorImpl();
void incrementInternal();
};
class KWQMapImpl {
protected:
typedef enum { Less = -1, Equal = 0, Greater = 1 } CompareResult;
KWQMapImpl(KWQMapNodeImpl *guard, void (*deleteNode)(KWQMapNodeImpl *));
virtual ~KWQMapImpl();
KWQMapImpl(const KWQMapImpl &);
KWQMapImpl &operator=(const KWQMapImpl &);
KWQMapNodeImpl *findInternal(KWQMapNodeImpl *target) const;
KWQMapNodeImpl *insertInternal(KWQMapNodeImpl *nodeToInsert, bool replaceExisting);
void removeEqualInternal(KWQMapNodeImpl *nodeToRemove, bool samePointer = false);
uint countInternal() const;
void clearInternal();
void swap(KWQMapImpl &map);
const KWQMapNodeImpl *beginInternal() const;
const KWQMapNodeImpl *endInternal() const;
KWQMapNodeImpl *beginInternal();
KWQMapNodeImpl *endInternal();
virtual CompareResult compareNodes(const KWQMapNodeImpl *a, const KWQMapNodeImpl *b) const = 0;
virtual void copyNode(const KWQMapNodeImpl *src, KWQMapNodeImpl *dst) const = 0;
virtual KWQMapNodeImpl *duplicateNode(const KWQMapNodeImpl *src) const = 0;
virtual void swapNodes(KWQMapNodeImpl *a, KWQMapNodeImpl *b) const = 0;
private:
static const int MAX_STACK = 64;
void copyOnWrite();
KWQMapNodeImpl *copyTree(const KWQMapNodeImpl *node,
KWQMapNodeImpl *subtreePredecessor,
KWQMapNodeImpl *subtreeSuccessor) const;
void rebalanceAfterInsert(KWQMapNodeImpl **nodes, bool *wentLeft, int height);
void rebalanceAfterRemove(KWQMapNodeImpl *nodeToRemove, KWQMapNodeImpl **nodes, bool *wentLeft, int height);
void rotateRight(KWQMapNodeImpl *node, KWQMapNodeImpl *parent, bool leftParent);
void rotateLeft(KWQMapNodeImpl *node, KWQMapNodeImpl *parent, bool leftParent);
class KWQMapPrivate;
KWQRefPtr<KWQMapPrivate> d;
#ifdef QMAP_TESTING
friend bool CheckRedBlackRules(KWQMapImpl *impl);
friend bool CheckRedBlackRulesAtNode(KWQMapImpl *impl, KWQMapNodeImpl *node, int &black_height);
#endif
};
#endif