SbMap.h

Go to the documentation of this file.

/*
 *  SbMap is based on BinTree - Binary tree template class written by
 *  Per Nilsson, It is Freeware and not copyrighted.
 *
 _______________________________________________________________________
 _______________________________________________________________________
 |
 |
 |   Description:
 |   SbMap is a container that associates objects of type KeyType with
 |   objects of type ValueType. No two elements will have the same key.
 |   SbMap has the important property that inserting a new element into
 |   a map does not invalidate iterators that point to existing elements.
 |   Erasing an element from a map also does not invalidate any iterators,
 |   except, of course, for iterators that actually point to the element
 |   that is being erased.
 |
 |   Classes:
 |
 |      // The map item class.
 |      template <class KeyType, class ValueType> class SbMapItem
 |
 |      // The map class
 |      template <class KeyType, class ValueType> class SbMap
 |      {
 |         public:
 |
 |            // Regular low->high (++) and high->low (--) iterator
 |            class Iterator
 |
 |               // Top to bottom iterator
 |               class ParentFirstIterator
 |
 |               // Bottom to top iterator
 |               class ParentLastIterator
 |
 |               // Top to bottom, level by level iterator
 |               class ByLevelIterator
 |      }
 |
 |   Requirements:
 |
 |      The KeyType class must support:
 |         1. < and == operations.
 |         2. Copy construction.
 |
 |      The ValueType must support:
 |         1. Copy construction.
 |         2. Assignment operation (=) if SbMapItem::setValue is used
 |
 |
 |   Author(s)      :  Per Nilsson, Felix Ritter
 |
 _______________________________________________________________________
 _______________________________________________________________________
 */
 
#ifndef  _SB_MAP_
#define  _SB_MAP_
 
#include "SoShaderSystem.h"
 
template <class KeyType, class ValueType>
class SbMapItem
{
   public:
 
      // Constructor(Key, Value)
      SbMapItem(const KeyType &k, const ValueType &v)
         :mKey(k), mValue(v), mLeftChild(nullptr), mRightChild(nullptr), mParent(nullptr), mIsRed(true) {
      }
 
      // Destructor
      virtual ~SbMapItem() {
      }
 
      // Set methods
 
      // set*Child also updates the the child's parent attribute.
      void setLeftChild(SbMapItem *p) {
         mLeftChild = p;
         if(p)
            p->setParent(this);
      }
      void setRightChild(SbMapItem *p) {
         mRightChild = p;
         if(p)
            p->setParent(this);
      }
      void setParent(SbMapItem *p) {
         mParent = p;
      }
 
      void setValue(const ValueType &v) {
         mValue = v;
      }
      // Note: Deliberately no SetKey, that could easily screw up the tree.
      // If a key shall be changed, delete node from tree and insert a new one instead.
 
      void setRed() {
         mIsRed = true;
      }
      void setBlack() {
         mIsRed = false;
      }
 
      // Get methods
 
      SbMapItem *getLeftChild() const {
         return mLeftChild;
      }
      SbMapItem *getRightChild() const {
         return mRightChild;
      }
      SbMapItem *getParent() const {
         return mParent;
      }
 
      ValueType getValue() {
         return mValue;
      }
      const ValueType &getValue() const {
         return mValue;
      }
      KeyType getKey() {
         return mKey;
      }
      const KeyType &getKey() const {
         return mKey;
      }
 
      // Some more or less useful queries
      bool isRoot() const {
         return mParent == nullptr;
      }
      bool isLeftChild() const {
         return mParent != nullptr && mParent->getLeftChild() == this;
      }
      bool isRightChild() const {
         return mParent != nullptr && mParent->getRightChild() == this;
      }
      bool isLeaf() const {
         return mLeftChild == nullptr && mRightChild == nullptr;
      }
      unsigned int GetLevel() const {
         return (isRoot()) ? 1 : getParent()->GetLevel() + 1;
      }
 
      bool isRed() const {
         return mIsRed;
      };
      bool isBlack() const {
         return !mIsRed;
      };
 
   private:
 
      // Default constructor - deliberately not implemented
      SbMapItem();
 
      SbMapItem  *mLeftChild;
      SbMapItem  *mRightChild;
      SbMapItem  *mParent;
 
      KeyType     mKey;
      ValueType   mValue;
 
      bool        mIsRed;
};
 
template <class KeyType, class ValueType>
class SbMap
{
   public:
 
      typedef SbMapItem<KeyType,ValueType> Node;
 
      class Iterator
      {
         public:
 
            // Default Constructor
            Iterator() : mRoot(nullptr), mCur(nullptr) {
            }
 
            // Constructor(Node *)
            Iterator(Node *root) : mRoot(root) {
               reset();
            }
 
            // Copy constructor
            Iterator(const Iterator &src) : mRoot(src.mRoot), mCur(src.mCur) {
            }
 
            // reset the iterator
            // atLowest : true  - reset at lowest key value (and then ++ your way through)
            //            false - reset at highest key value (and then -- your way through)
            void reset(bool atLowest = true) {
               mCur = (atLowest) ? minNode(mRoot) : maxNode(mRoot);
            }
 
            // Has the iterator reached the end?
            bool atEnd() const {
               return mCur == nullptr;
            }
            Node *getNode() {
               return mCur;
            }
 
            // Assignment operator
            Iterator &operator =(const Iterator &src) {
               mRoot = src.mRoot;
               mCur  = src.mCur;
               return *this;
            }
 
            // Increment operator
            void operator ++(int) {
               Inc();
            }
 
            // Decrement operator
            void operator --(int) {
               Dec();
            }
 
            // Access operators
            Node *operator ->() {
               return getNode();
            }
            Node &operator  *() {
               if(atEnd()) {
                  throw "Iterator at end";
               }
               return *getNode();
            }
 
         private:
 
            // minNode: Returns node with lowest key from n and down.
            //      Ie the node all down to the left
            Node *minNode(Node *n) {
               while(n && n->getLeftChild())
                  n = n->getLeftChild();
               return n;
            }
            // maxNode: Returns node with highest key from n and down.
            //      Ie the node all down to the right
            Node *maxNode(Node *n) {
               while(n && n->getRightChild())
                  n = n->getRightChild();
               return n;
            }
 
            // ++
            void Inc() {
               // Already at end?
               if(mCur == nullptr)
                  return;
 
               if(mCur->getRightChild()) {
                  // If current node has a right child, the next higher node is the
                  // node with lowest key beneath the right child.
                  mCur = minNode(mCur->getRightChild());
               }
               else if(mCur->isLeftChild()) {
                  // No right child? Well if current node is a left child then
                  // the next higher node is the parent
                  mCur = mCur->getParent();
               }
               else {
                  // Current node neither is left child nor has a right child.
                  // Ie it is either right child or root
                  // The next higher node is the parent of the first non-right
                  // child (ie either a left child or the root) up in the
                  // hierarchy. Root's parent is 0.
                  while(mCur->isRightChild())
                     mCur = mCur->getParent();
                  mCur = mCur->getParent();
               }
            }
 
            // --
            void Dec() {
               // Already at end?
               if(mCur == nullptr)
                  return;
 
               if(mCur->getLeftChild()) {
                  // If current node has a left child, the next lower node is the
                  // node with highest key beneath the left child.
                  mCur = maxNode(mCur->getLeftChild());
               }
               else if(mCur->isRightChild()) {
                  // No left child? Well if current node is a right child then
                  // the next lower node is the parent
                  mCur = mCur->getParent();
               }
               else {
                  // Current node neither is right child nor has a left child.
                  // Ie it is either left child or root
                  // The next higher node is the parent of the first non-left
                  // child (ie either a right child or the root) up in the
                  // hierarchy. Root's parent is 0.
 
                  while(mCur->isLeftChild())
                     mCur = mCur->getParent();
                  mCur = mCur->getParent();
               }
            }
 
            Node *mRoot;
            Node *mCur;
         }; // Iterator
 
         // Traverses the tree from top to bottom. Typical usage is
         // when storing the tree structure, because when reading it
         // later (and inserting elements) the tree structure will
         // be the same.
         class ParentFirstIterator
         {
            public:
 
               // Default constructor
               ParentFirstIterator() : mRoot(nullptr), mCur(nullptr) {
               }
 
               // Constructor(Node*)
               explicit ParentFirstIterator(Node *root) : mRoot(root), mCur(nullptr) {
                  reset();
               }
 
               void reset() {
                  mCur = mRoot;
               };
 
               // Has the iterator reached the end?
               bool atEnd() const {
                  return mCur==nullptr;
               }
               Node *getNode() {
                  return mCur;
               }
 
               // Assignment operator
               ParentFirstIterator &operator =(const ParentFirstIterator &src) {
                  mRoot = src.mRoot;
                  mCur  = src.mCur;
                  return *this;
               }
 
               // Increment operator
               void operator ++(int) {
                  Inc();
               }
 
               // Access operators
               Node *operator ->() {
                  return getNode();
               }
               Node &operator  *() {
                  if(atEnd())
                     throw "ParentFirstIterator at end";
                  return *getNode();
               }
 
            private:
 
               void Inc() {
                  // Already at end?
                  if(mCur == nullptr)
                     return;
 
                  // First we try down to the left
                  if(mCur->getLeftChild()) {
                     mCur = mCur->getLeftChild();
                  }
                  else if(mCur->getRightChild()) {
                     // No left child? The we go down to the right.
                     mCur = mCur->getRightChild();
                  }
                  else {
                     // No children? Move up in the hierarcy until
                     // we either reach 0 (and are finished) or
                     // find a right uncle.
                     while(mCur != nullptr) {
                        // But if parent is left child and has a right "uncle" the parent
                        // has already been processed but the uncle hasn't. Move to
                        // the uncle.
                        if(mCur->isLeftChild() && mCur->getParent()->getRightChild()) {
                           mCur = mCur->getParent()->getRightChild();
                           return;
                        }
                        mCur = mCur->getParent();
                     }
                  }
               }
 
               Node *mRoot;
               Node *mCur;
 
         }; // ParentFirstIterator
 
         // Typical usage is when deleting all elements in the tree
         // because you must delete the children before you delete
         // their parent.
         class ParentLastIterator
         {
            public:
 
               // Default constructor
               ParentLastIterator() : mRoot(nullptr), mCur(nullptr) {
               }
 
               // Constructor(Node*)
               explicit ParentLastIterator(Node *root) : mRoot(root), mCur(nullptr) {
                  reset();
               }
 
               void reset() {
                  mCur = minNode(mRoot);
               }
 
               // Has the iterator reached the end?
               bool atEnd() const {
                  return mCur == nullptr;
               }
               Node *getNode() {
                  return mCur;
               }
 
               // Assignment operator
               ParentLastIterator &operator =(const ParentLastIterator &src) {
                  mRoot = src.mRoot;
                  mCur  = src.mCur;
                  return *this;
               }
 
               // Increment operator
               void operator ++(int) {
                  Inc();
               }
 
               // Access operators
               Node *operator ->() {
                  return getNode();
               }
               Node &operator  *() {
                  if(atEnd())
                     throw "ParentLastIterator at end";
                  return *getNode();
               }
 
            private:
 
               // minNode: Returns the node as far down to the left as possible.
               Node *minNode(Node *n) {
                  while(n != nullptr && (n->getLeftChild() != 0 || n->getRightChild() != 0)) {
                     n = (n->getLeftChild()) ? n->getLeftChild() : n->getRightChild();
                  }
                  return n;
               }
 
               void Inc() {
                  // Already at end?
                  if(mCur == nullptr)
                     return;
 
                  // Note: Starting point is the node as far down to the left as possible.
 
                  // If current node has an uncle to the right, go to the
                  // node as far down to the left from the uncle as possible
                  // else just go up a level to the parent.
                  if(mCur->isLeftChild() && mCur->getParent()->getRightChild()) {
                     mCur = minNode(mCur->getParent()->getRightChild());
                  }
                  else {
                     mCur = mCur->getParent();
                  }
               }
 
               Node *mRoot;
               Node *mCur;
         }; // ParentLastIterator
 
         // ByLevelIterator. Traverse tree top to bottom, level by level left to right.
         // Typical usage : I don't know. Perhaps if the tree should be displayed
         // in some fancy way.
         // It is the most memory consuming of all iterators as it will allocate an
         // array of (size()+1)/2 Node*s.
         // Impl. desc:
         //   mArray[0] is the current node we're looking at, initially set to mRoot.
         //   When ++:ing the children of mArray[0] (if any) are put last in the
         //   array and the array is shifted down 1 step
         class ByLevelIterator
         {
            public:
 
               // Default constructor
               ByLevelIterator() : mRoot(nullptr), mArray(nullptr), mSize(0) {
               }
 
               // Constructor(treeRoot, elementsInTree)
               ByLevelIterator(Node *root, unsigned int size) : mRoot(root), mSize(size), mArray(nullptr) {
                  reset();
               }
 
               // Copy constructor
               ByLevelIterator(const ByLevelIterator &src) : mRoot(src.mRoot), mSize(src.mSize), mEndPos(src.mEndPos) {
                  if(src.mArray != nullptr) {
                     mArray = new Node*[(mSize+1)/2];
                     memcpy(mArray, src.mArray, sizeof(Node*)*(mSize+1)/2);
                  }
                  else
                     mArray = 0;
               }
 
               // Destructor
               ~ByLevelIterator() {
                  if(mArray != nullptr) {
                     delete [] mArray;
                     mArray = 0;
                  }
               }
 
               void reset() {
                  if(mSize > 0) {
                     // Only allocate the first time reset is called
                     if(mArray == nullptr) {
                        // mArray must be able to hold the maximum "width" of the tree which
                        // at most can be (NumberOfNodesInTree + 1 ) / 2
                        mArray = new Node*[(mSize+1)/2];
                     }
                     // Initialize the array with 1 element, the mRoot.
                     mArray[0] = mRoot;
                     mEndPos = 1;
                  }
                  else
                     mEndPos=0;
               }
 
               // Has the iterator reached the end?
               bool atEnd() const {
                  return mEndPos == 0;
               }
               Node *getNode() {
                  return mArray[0];
               }
 
               // Assignment Operator
               ByLevelIterator &operator =(const ByLevelIterator &src) {
                  mRoot = src.mRoot;
                  mSize = src.mSize;
                  if(src.mArray != nullptr) {
                     mArray = new Node*[(mSize+1)/2];
                     memcpy(mArray, src.mArray, sizeof(Node*)*(mSize+1)/2);
                  }
                  else
                     mArray = 0;
 
                  return *this;
               }
 
               // Increment operator
               void operator ++(int) {
                  Inc();
               }
 
               // Access operators
               Node *operator ->() {
                  return getNode();
               }
               Node &operator  *() {
                  if(atEnd())
                     throw "ParentLastIterator at end";
                  return *getNode();
               }
 
            private:
 
               void Inc() {
                  if(mEndPos == 0)
                     return;
 
                  // Current node is mArray[0]
                  Node *pNode = mArray[0];
 
                  // Move the array down one notch, ie we have a new current node
                  // (the one than just was mArray[1])
                  for(unsigned int i = 0; i < mEndPos; i++) {
                     mArray[i] = mArray[i+1];
                  }
                  mEndPos--;
 
                  Node *pChild=pNode->getLeftChild();
                  if(pChild) { // Append the left child of the former current node
                     mArray[mEndPos] = pChild;
                     mEndPos++;
                  }
 
                  pChild = pNode->getRightChild();
                  if(pChild) { // Append the right child of the former current node
                     mArray[mEndPos] = pChild;
                     mEndPos++;
                  }
 
               }
 
               Node        **mArray;
               Node         *mRoot;
               unsigned int  mSize;
               unsigned int  mEndPos;
         }; // ByLevelIterator
 
         // It makes it possible to have different behavior in situations like:
         // myTree["Foo"] = 32;
         //   If "Foo" already exist, just update its value else insert a new
         //   element.
         // int i = myTree["Foo"]
         // If "Foo" exists return its value, else throw an exception.
         //
         class AccessClass
         {
            // Let SbMap be the only one who can instantiate this class.
            friend class SbMap<KeyType, ValueType>;
 
            public:
 
               // Assignment operator. Handles the myTree["Foo"] = 32; situation
               operator =(const ValueType &value) {
                  // Just use the set method, it handles already exist/not exist situation
                  mTree.set(mKey, value);
               }
 
               // ValueType operator
               operator ValueType() {
                  Node *node = mTree.find(mKey);
 
                  // Not found
                  if(node == nullptr) {
                     throw "Item not found";
                  }
 
                  return node->getValue();
               }
 
 
            private:
 
               // Private Construction
               AccessClass(SbMap &tree, const KeyType &key) : mTree(tree), mKey(key) {
               }
 
               // Default constructor
               AccessClass();
 
               SbMap         &mTree;
               const KeyType &mKey;
         }; // AccessClass
 
 
         // Constructor.
         SbMap() : mRoot(nullptr), mSize(0) {}
 
         // Copy constructor
         explicit SbMap(const SbMap &src) : mRoot(nullptr), mSize(0) {
            *this = src;
         }
 
         // Destructor
         ~SbMap() {
            clear();
         }
 
         // Assignment operator
         SbMap &operator = (const SbMap &src) {
            clear();
 
            for(ParentFirstIterator i(src.getParentFirstIterator()); !i.atEnd(); i++) {
               set(i->getKey(), i->getValue());
            }
         }
 
 
         bool insert(const KeyType &keyNew, const ValueType &v) {
            // First insert node the "usual" way (no fancy balance logic yet)
            Node *newNode = new Node(keyNew, v);
            if(!insert(newNode)) {
               delete newNode;
               return false;
            }
 
            // Then attend a balancing party
            while(!newNode->isRoot() && (newNode->getParent()->isRed())) {
               if(newNode->getParent()->isLeftChild()) {
                  // If newNode is a left child, get its right 'uncle'
                  Node *newNodesUncle = newNode->getParent()->getParent()->getRightChild();
                  if(newNodesUncle != nullptr && newNodesUncle->isRed()) {
                     // case 1 - change the colours
                     newNode->getParent()->setBlack();
                     newNodesUncle->setBlack();
                     newNode->getParent()->getParent()->setRed();
                     // Move newNode up the tree
                     newNode = newNode->getParent()->getParent();
                  }
                  else {
                     // newNodesUncle is a black node
                     if(newNode->isRightChild()) {
                        // and newNode is to the right
                        // case 2 - move newNode up and rotate
                        newNode = newNode->getParent();
                        RotateLeft(newNode);
                     }
                     // case 3
                     newNode->getParent()->setBlack();
                     newNode->getParent()->getParent()->setRed();
                     RotateRight(newNode->getParent()->getParent());
                  }
               }
               else {
                  // If newNode is a right child, get its left 'uncle'
                  Node *newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
                  if(newNodesUncle != nullptr && newNodesUncle->isRed()) {
                     // case 1 - change the colours
                     newNode->getParent()->setBlack();
                     newNodesUncle->setBlack();
                     newNode->getParent()->getParent()->setRed();
                     // Move newNode up the tree
                     newNode = newNode->getParent()->getParent();
                  }
                  else {
                     // newNodesUncle is a black node
                     if(newNode->isLeftChild()) {
                        // and newNode is to the left
                        // case 2 - move newNode up and rotate
                        newNode = newNode->getParent();
                        RotateRight(newNode);
                     }
                     // case 3
                     newNode->getParent()->setBlack();
                     newNode->getParent()->getParent()->setRed();
                     RotateLeft(newNode->getParent()->getParent());
                  }
               }
            }
            // Color the root black
            mRoot->setBlack();
            return true;
         }
 
         // set. If the key already exist just replace the value
         // else insert a new element.
         void set(const KeyType &k, const ValueType &v) {
            Node *p = find(k);
            if(p) {
               p->setValue(v);
            }
            else
               insert(k,v);
         }
 
         // Remove a node.Return true if the node could
         // be found (and was removed) in the tree.
         bool remove(const KeyType &k) {
            Node *p = find(k);
            if(p == nullptr)
               return false;
 
            // Rotate p down to the left until it has no right child, will get there
            // sooner or later.
            while(p->getRightChild()) {
               // "Pull up my right child and let it knock me down to the left"
               RotateLeft(p);
            }
            // p now has no right child but might have a left child
            Node *left = p->getLeftChild();
 
            // Let p's parent point to p's child instead of point to p
            if(p->isLeftChild()) {
               p->getParent()->setLeftChild(left);
            }
            else if(p->isRightChild()) {
               p->getParent()->setRightChild(left);
            }
            else {
               // p has no parent => p is the root.
               // Let the left child be the new root.
               setRoot(left);
            }
 
            // p is now gone from the tree in the sense that
            // no one is pointing at it. Let's get rid of it.
            delete p;
 
            mSize--;
            return true;
         }
 
         // Wipe out the entire tree.
         void clear() {
            ParentLastIterator i(getParentLastIterator());
 
            while(!i.atEnd()) {
               Node *p = i.getNode();
               i++; // Increment it before it is deleted
               // else iterator will get quite confused.
               delete p;
            }
            mRoot = 0;
            mSize = 0;
         }
 
         // Is the tree empty?
         bool isEmpty() const {
            return mRoot == nullptr;
         }
 
         // Search for the node.
         // Returns 0 if node couldn't be found.
         Node *find(const KeyType &keyToFind) const {
            Node *pNode = mRoot;
 
            while(pNode != nullptr) {
               KeyType key(pNode->getKey());
 
               if(keyToFind == key) {
                  // Found it! Return it! Wheee!
                  return pNode;
               }
               else if(keyToFind < key) {
                  pNode = pNode->getLeftChild();
               }
               else { // keyToFind > key
                  pNode = pNode->getRightChild();
               }
            }
 
            return nullptr;
         }
 
         // Get the root element. 0 if tree is empty.
         Node *getRoot() const {
            return mRoot;
         }
 
         // Number of nodes in the tree.
         unsigned int size() const {
            return mSize;
         }
 
         Iterator getIterator() {
            Iterator it(getRoot());
            return it;
         }
         ParentFirstIterator getParentFirstIterator() {
            ParentFirstIterator it(getRoot());
            return it;
         }
         ParentLastIterator getParentLastIterator() {
            ParentLastIterator it(getRoot());
            return it;
         }
         ByLevelIterator getByLevelIterator() {
            ByLevelIterator it(getRoot(),size());
            return it;
         }
 
         // operator [] for access to elements
         AccessClass operator [](const KeyType &k) {
            return AccessClass(*this, k);
         }
 
   private:
 
         void setRoot(Node *newRoot) {
            mRoot = newRoot;
            if(mRoot != nullptr)
               mRoot->setParent(0);
         }
 
         // insert a node into the tree without using any fancy balancing logic.
         // Returns false if that key already exist in the tree.
         bool insert(Node *newNode) {
            bool result = true; // Assume success
 
            if(mRoot == nullptr) {
               setRoot(newNode);
               mSize = 1;
            }
            else {
               Node *pNode = mRoot;
               KeyType keyNew = newNode->getKey();
               while(pNode) {
                  KeyType key(pNode->getKey());
 
                  if(keyNew == key) {
                     result = false;
                     pNode = 0;
                  }
                  else if(keyNew < key) {
                     if(pNode->getLeftChild() == 0) {
                        pNode->setLeftChild(newNode);
                        pNode = 0;
                     }
                     else {
                        pNode = pNode->getLeftChild();
                     }
                  }
                  else {
                     // keyNew > key
                     if(pNode->getRightChild() == 0) {
                        pNode->setRightChild(newNode);
                        pNode = 0;
                     }
                     else {
                        pNode = pNode->getRightChild();
                     }
                  }
               }
 
               if(result) {
                  mSize++;
               }
            }
 
            return result;
         }
 
         // Rotate left.
         // Pull up node's right child and let it knock node down to the left
         void RotateLeft(Node *p) {
            Node *right = p->getRightChild();
 
            p->setRightChild(right->getLeftChild());
 
            if(p->isLeftChild()) {
               p->getParent()->setLeftChild(right);
            }
            else if(p->isRightChild()) {
               p->getParent()->setRightChild(right);
            }
            else {
               setRoot(right);
            }
            right->setLeftChild(p);
         }
 
         // Rotate right.
         // Pull up node's left child and let it knock node down to the right
         void RotateRight(Node *p) {
            Node *left = p->getLeftChild();
 
            p->setLeftChild(left->getRightChild());
 
            if(p->isLeftChild()) {
               p->getParent()->setLeftChild(left);
            }
            else if(p->isRightChild()) {
               p->getParent()->setRightChild(left);
            }
            else {
               setRoot(left);
            }
            left->setRightChild(p);
         }
 
         Node         *mRoot; // The top node. 0 if empty.
         unsigned int  mSize; // Number of nodes in the tree
};
 
#endif  // _SB_MAP_