17 #include <pia/common/common_definitions.h> 18 #include <pia/common/common_TreeMapNode.h> 19 #include <pia/common/common_TreeMapBase.h> 34 template <
typename Key_>
35 class TreeMap :
public common::TreeMapBase
39 typedef TreeMapNode<Key> Node;
47 Node* FindNode(
const Key& key)
const;
49 Node* FrontNode()
const 51 return static_cast<Node*
>(FrontNodeBase());
54 Node* BackNode()
const 56 return static_cast<Node*
>(BackNodeBase());
62 Node* LowerBoundNode(
const Key& key)
const;
66 bool IsIncludeNode(
const Node* cpNode)
const 68 return IsIncludeNodeBase(cpNode);
71 Node* InsertNode(
const Key& key, Node* pNode);
73 Node* EraseNode(
const Key& key)
75 Node* pNode = FindNode(key);
83 void EraseNode(Node* pNode);
87 TreeMap(
const TreeMap& rhs);
88 TreeMap& operator=(
const TreeMap& rhs);
91 Node* RotateRight(Node* pNode)
93 return static_cast<Node*
>(RotateRightBase(pNode));
95 Node* RotateLeft(Node* pNode)
97 return static_cast<Node*
>(RotateLeftBase(pNode));
100 Node* GetRoot()
const 102 return static_cast<Node*
>(GetRootBase());
105 void ClearNodeImpl(Node* pNode);
111 template <
typename Key>
112 void TreeMap<Key>::ClearNode()
114 ClearNodeImpl(GetRoot());
119 template <
typename Key>
120 void TreeMap<Key>::ClearNodeImpl(Node* pNode)
122 pNode->m_Key = Key();
123 if (pNode->GetLeft() != NULL)
125 ClearNodeImpl(pNode->GetLeft());
127 if (pNode->GetRight() != NULL)
129 ClearNodeImpl(pNode->GetRight());
134 template <
typename Key>
135 typename TreeMap<Key>::Node* TreeMap<Key>::FindNode(
const Key& key)
const 137 Node* pNode = GetRoot();
138 while (pNode != NULL)
140 if (key < pNode->m_Key)
142 pNode = pNode->GetLeft();
144 else if (key > pNode->m_Key)
146 pNode = pNode->GetRight();
158 template <
typename Key>
159 typename TreeMap<Key>::Node* TreeMap<Key>::LowerBoundNode(
const Key& key)
const 161 Node* pNode = GetRoot();
169 if (key < pNode->m_Key)
171 if (pNode->GetLeft() == NULL)
175 pNode = pNode->GetLeft();
177 else if (key > pNode->m_Key)
179 if (pNode->GetRight() == NULL)
181 return pNode->Next();
183 pNode = pNode->GetRight();
193 template <
typename Key>
194 typename TreeMap<Key>::Node* TreeMap<Key>::InsertNode(
const Key& key, Node* pNode)
198 if (GetRoot() == NULL)
201 InsertNodeRoot(pNode);
206 Node* pN = GetRoot();
211 if (pN->GetLeft() == NULL)
214 InsertNodeLeft(pNode, pN);
219 else if (key > pN->m_Key)
221 if (pN->GetRight() == NULL)
224 InsertNodeRight(pNode, pN);
233 ReplaceNode(pNode, pN);
241 template <
typename Key>
242 void TreeMap<Key>::EraseNode(Node* pNode)
244 EraseNodeBase(pNode);