CTR Pia  4.11.3
Game Communication Engine
common_TreeMap.h
1 /*---------------------------------------------------------------------------*
2  Project: Pia
3  File: common_TreeMap.h
4 
5  Copyright Nintendo. All rights reserved.
6 
7  These coded instructions, statements, and computer programs contain
8  proprietary information of Nintendo of America Inc. and/or Nintendo
9  Company Ltd., and are protected by Federal copyright law. They may
10  not be disclosed to third parties or copied or duplicated in any form,
11  in whole or in part, without the prior written consent of Nintendo.
12  *---------------------------------------------------------------------------*/
13 
14 
15 #pragma once
16 
17 #include <pia/common/common_definitions.h>
18 #include <pia/common/common_TreeMapNode.h>
19 #include <pia/common/common_TreeMapBase.h>
20 
21 
22 namespace nn
23 {
24 namespace pia
25 {
26 namespace common
27 {
28 
29 
30 /*!
31 @cond PRIVATE
32 @brief Represents a treemap that uses an AVL tree.
33 */
34 template <typename Key_>
35 class TreeMap : public common::TreeMapBase
36 {
37 public:
38  typedef Key_ Key;
39  typedef TreeMapNode<Key> Node;
40 
41 protected:
42  TreeMap()
43  : TreeMapBase()
44  {
45  }
46 
47  Node* FindNode(const Key& key) const;
48 
49  Node* FrontNode() const
50  {
51  return static_cast<Node*>(FrontNodeBase());
52  }
53 
54  Node* BackNode() const
55  {
56  return static_cast<Node*>(BackNodeBase());
57  }
58 
59 /*!
60 @brief Specifies the first element with <span class="argument">key</span> or more keys.
61 */
62  Node* LowerBoundNode(const Key& key) const;
63 
64  void ClearNode();
65 
66  bool IsIncludeNode(const Node* cpNode) const
67  {
68  return IsIncludeNodeBase(cpNode);
69  }
70 
71  Node* InsertNode(const Key& key, Node* pNode);
72 
73  Node* EraseNode(const Key& key)
74  {
75  Node* pNode = FindNode(key);
76  if (pNode != NULL)
77  {
78  EraseNode(pNode);
79  }
80  return pNode;
81  }
82 
83  void EraseNode(Node* pNode);
84 
85 private:
86  // Copying is prohibited.
87  TreeMap(const TreeMap& rhs);
88  TreeMap& operator=(const TreeMap& rhs);
89 
90 private:
91  Node* RotateRight(Node* pNode)
92  {
93  return static_cast<Node*>(RotateRightBase(pNode));
94  }
95  Node* RotateLeft(Node* pNode)
96  {
97  return static_cast<Node*>(RotateLeftBase(pNode));
98  }
99 
100  Node* GetRoot() const
101  {
102  return static_cast<Node*>(GetRootBase());
103  }
104 
105  void ClearNodeImpl(Node* pNode);
106 };
107 //! @endcond
108 
109 
110 //! @cond
111 template <typename Key>
112 void TreeMap<Key>::ClearNode()
113 {
114  ClearNodeImpl(GetRoot());
115  ClearNodeBase();
116 }
117 
118 
119 template <typename Key>
120 void TreeMap<Key>::ClearNodeImpl(Node* pNode)
121 {
122  pNode->m_Key = Key();
123  if (pNode->GetLeft() != NULL)
124  {
125  ClearNodeImpl(pNode->GetLeft());
126  }
127  if (pNode->GetRight() != NULL)
128  {
129  ClearNodeImpl(pNode->GetRight());
130  }
131 }
132 
133 
134 template <typename Key>
135 typename TreeMap<Key>::Node* TreeMap<Key>::FindNode(const Key& key) const
136 {
137  Node* pNode = GetRoot();
138  while (pNode != NULL)
139  {
140  if (key < pNode->m_Key)
141  {
142  pNode = pNode->GetLeft();
143  }
144  else if (key > pNode->m_Key)
145  {
146  pNode = pNode->GetRight();
147  }
148  else
149  {
150  return pNode;
151  }
152  }
153 
154  return NULL;
155 }
156 
157 
158 template <typename Key>
159 typename TreeMap<Key>::Node* TreeMap<Key>::LowerBoundNode(const Key& key) const
160 {
161  Node* pNode = GetRoot();
162  if (pNode == NULL)
163  {
164  return NULL;
165  }
166 
167  while (true)
168  {
169  if (key < pNode->m_Key)
170  {
171  if (pNode->GetLeft() == NULL)
172  {
173  return pNode;
174  }
175  pNode = pNode->GetLeft();
176  }
177  else if (key > pNode->m_Key)
178  {
179  if (pNode->GetRight() == NULL)
180  {
181  return pNode->Next();
182  }
183  pNode = pNode->GetRight();
184  }
185  else
186  {
187  return pNode;
188  }
189  }
190 }
191 
192 
193 template <typename Key>
194 typename TreeMap<Key>::Node* TreeMap<Key>::InsertNode(const Key& key, Node* pNode)
195 {
196  pNode->m_Key = key;
197 
198  if (GetRoot() == NULL)
199  {
200  // Add to root.
201  InsertNodeRoot(pNode);
202  return NULL;
203  }
204 
205  // Find the insert position.
206  Node* pN = GetRoot();
207  while (true)
208  {
209  if (key < pN->m_Key)
210  {
211  if (pN->GetLeft() == NULL)
212  {
213  // Add to the left.
214  InsertNodeLeft(pNode, pN);
215  return NULL;
216  }
217  pN = pN->GetLeft();
218  }
219  else if (key > pN->m_Key)
220  {
221  if (pN->GetRight() == NULL)
222  {
223  // Add to the right.
224  InsertNodeRight(pNode, pN);
225  return NULL;
226  }
227  pN = pN->GetRight();
228  }
229  else
230  {
231  // The same key exists. Replace the existing key.
232 
233  ReplaceNode(pNode, pN);
234  pN->InitNode();
235  return pN;
236  }
237  }
238 }
239 
240 
241 template <typename Key>
242 void TreeMap<Key>::EraseNode(Node* pNode)
243 {
244  EraseNodeBase(pNode);
245  pNode->InitNode();
246 }
247 //! @endcond
248 }
249 }
250 } // end of namespace nn::pia::common
Definition: assert.h:115