16 #include <nn/pia/common/common_Definitions.h>
17 #include <nn/pia/common/common_TreeMapNode.h>
18 #include <nn/pia/common/common_TreeMapBase.h>
33 template <
typename Key_>
34 class TreeMap :
public common::TreeMapBase
38 typedef TreeMapNode<Key> Node;
46 Node* FindNode(
const Key& key)
const;
48 Node* FrontNode()
const
50 return static_cast<Node*
>(FrontNodeBase());
53 Node* BackNode()
const
55 return static_cast<Node*
>(BackNodeBase());
61 Node* LowerBoundNode(
const Key& key)
const;
65 bool IsIncludeNode(
const Node* cpNode)
const
67 return IsIncludeNodeBase(cpNode);
70 Node* InsertNode(
const Key& key, Node* pNode);
72 Node* EraseNode(
const Key& key)
74 Node* pNode = FindNode(key);
82 void EraseNode(Node* pNode);
86 TreeMap(
const TreeMap& rhs);
87 TreeMap& operator=(
const TreeMap& rhs);
90 Node* RotateRight(Node* pNode)
92 return static_cast<Node*
>(RotateRightBase(pNode));
94 Node* RotateLeft(Node* pNode)
96 return static_cast<Node*
>(RotateLeftBase(pNode));
101 return static_cast<Node*
>(GetRootBase());
104 void ClearNodeImpl(Node* pNode);
110 template <
typename Key>
111 void TreeMap<Key>::ClearNode()
113 ClearNodeImpl(GetRoot());
118 template <
typename Key>
119 void TreeMap<Key>::ClearNodeImpl(Node* pNode)
121 pNode->m_Key = Key();
122 if (pNode->GetLeft() != NULL)
124 ClearNodeImpl(pNode->GetLeft());
126 if (pNode->GetRight() != NULL)
128 ClearNodeImpl(pNode->GetRight());
133 template <
typename Key>
134 typename TreeMap<Key>::Node* TreeMap<Key>::FindNode(
const Key& key)
const
136 Node* pNode = GetRoot();
137 while (pNode != NULL)
139 if (key < pNode->m_Key)
141 pNode = pNode->GetLeft();
143 else if (key > pNode->m_Key)
145 pNode = pNode->GetRight();
157 template <
typename Key>
158 typename TreeMap<Key>::Node* TreeMap<Key>::LowerBoundNode(
const Key& key)
const
160 Node* pNode = GetRoot();
168 if (key < pNode->m_Key)
170 if (pNode->GetLeft() == NULL)
174 pNode = pNode->GetLeft();
176 else if (key > pNode->m_Key)
178 if (pNode->GetRight() == NULL)
180 return pNode->Next();
182 pNode = pNode->GetRight();
192 template <
typename Key>
193 typename TreeMap<Key>::Node* TreeMap<Key>::InsertNode(
const Key& key, Node* pNode)
197 if (GetRoot() == NULL)
200 InsertNodeRoot(pNode);
205 Node* pN = GetRoot();
210 if (pN->GetLeft() == NULL)
213 InsertNodeLeft(pNode, pN);
218 else if (key > pN->m_Key)
220 if (pN->GetRight() == NULL)
223 InsertNodeRight(pNode, pN);
232 ReplaceNode(pNode, pN);
240 template <
typename Key>
241 void TreeMap<Key>::EraseNode(Node* pNode)
243 EraseNodeBase(pNode);