CTR-Pia  5.4.3
Game Communication Engine
 全て クラス ネームスペース 関数 変数 型定義 列挙型 列挙型の値 ページ
common_TreeMap.h
1 /*--------------------------------------------------------------------------------*
2  Copyright (C)Nintendo All rights reserved.
3 
4  These coded instructions, statements, and computer programs contain proprietary
5  information of Nintendo and/or its licensed developers and are protected by
6  national and international copyright laws. They may not be disclosed to third
7  parties or copied or duplicated in any form, in whole or in part, without the
8  prior written consent of Nintendo.
9 
10  The content herein is highly confidential and should be handled accordingly.
11  *--------------------------------------------------------------------------------*/
12 
13 
14 #pragma once
15 
16 #include <nn/pia/common/common_Definitions.h>
17 #include <nn/pia/common/common_TreeMapNode.h>
18 #include <nn/pia/common/common_TreeMapBase.h>
19 
20 
21 namespace nn
22 {
23 namespace pia
24 {
25 namespace common
26 {
27 
28 
29 /*!
30  @cond PRIVATE
31  @brief AVL木を用いたツリーマップです。
32  */
33 template <typename Key_>
34 class TreeMap : public common::TreeMapBase
35 {
36 public:
37  typedef Key_ Key;
38  typedef TreeMapNode<Key> Node;
39 
40 protected:
41  TreeMap()
42  : TreeMapBase()
43  {
44  }
45 
46  Node* FindNode(const Key& key) const;
47 
48  Node* FrontNode() const
49  {
50  return static_cast<Node*>(FrontNodeBase());
51  }
52 
53  Node* BackNode() const
54  {
55  return static_cast<Node*>(BackNodeBase());
56  }
57 
58  /*!
59  @brief key 以上のキーを持つ最初の要素
60  */
61  Node* LowerBoundNode(const Key& key) const;
62 
63  void ClearNode();
64 
65  bool IsIncludeNode(const Node* cpNode) const
66  {
67  return IsIncludeNodeBase(cpNode);
68  }
69 
70  Node* InsertNode(const Key& key, Node* pNode);
71 
72  Node* EraseNode(const Key& key)
73  {
74  Node* pNode = FindNode(key);
75  if (pNode != NULL)
76  {
77  EraseNode(pNode);
78  }
79  return pNode;
80  }
81 
82  void EraseNode(Node* pNode);
83 
84 private:
85  // コピー禁止
86  TreeMap(const TreeMap& rhs);
87  TreeMap& operator=(const TreeMap& rhs);
88 
89 private:
90  Node* RotateRight(Node* pNode)
91  {
92  return static_cast<Node*>(RotateRightBase(pNode));
93  }
94  Node* RotateLeft(Node* pNode)
95  {
96  return static_cast<Node*>(RotateLeftBase(pNode));
97  }
98 
99  Node* GetRoot() const
100  {
101  return static_cast<Node*>(GetRootBase());
102  }
103 
104  void ClearNodeImpl(Node* pNode);
105 };
106 //! @endcond
107 
108 
109 //! @cond
110 template <typename Key>
111 void TreeMap<Key>::ClearNode()
112 {
113  ClearNodeImpl(GetRoot());
114  ClearNodeBase();
115 }
116 
117 
118 template <typename Key>
119 void TreeMap<Key>::ClearNodeImpl(Node* pNode)
120 {
121  pNode->m_Key = Key();
122  if (pNode->GetLeft() != NULL)
123  {
124  ClearNodeImpl(pNode->GetLeft());
125  }
126  if (pNode->GetRight() != NULL)
127  {
128  ClearNodeImpl(pNode->GetRight());
129  }
130 }
131 
132 
133 template <typename Key>
134 typename TreeMap<Key>::Node* TreeMap<Key>::FindNode(const Key& key) const
135 {
136  Node* pNode = GetRoot();
137  while (pNode != NULL)
138  {
139  if (key < pNode->m_Key)
140  {
141  pNode = pNode->GetLeft();
142  }
143  else if (key > pNode->m_Key)
144  {
145  pNode = pNode->GetRight();
146  }
147  else
148  {
149  return pNode;
150  }
151  }
152 
153  return NULL;
154 }
155 
156 
157 template <typename Key>
158 typename TreeMap<Key>::Node* TreeMap<Key>::LowerBoundNode(const Key& key) const
159 {
160  Node* pNode = GetRoot();
161  if (pNode == NULL)
162  {
163  return NULL;
164  }
165 
166  while (true)
167  {
168  if (key < pNode->m_Key)
169  {
170  if (pNode->GetLeft() == NULL)
171  {
172  return pNode;
173  }
174  pNode = pNode->GetLeft();
175  }
176  else if (key > pNode->m_Key)
177  {
178  if (pNode->GetRight() == NULL)
179  {
180  return pNode->Next();
181  }
182  pNode = pNode->GetRight();
183  }
184  else
185  {
186  return pNode;
187  }
188  }
189 }
190 
191 
192 template <typename Key>
193 typename TreeMap<Key>::Node* TreeMap<Key>::InsertNode(const Key& key, Node* pNode)
194 {
195  pNode->m_Key = key;
196 
197  if (GetRoot() == NULL)
198  {
199  // ルートに追加
200  InsertNodeRoot(pNode);
201  return NULL;
202  }
203 
204  // 入れる位置を探す
205  Node* pN = GetRoot();
206  while (true)
207  {
208  if (key < pN->m_Key)
209  {
210  if (pN->GetLeft() == NULL)
211  {
212  // 左に追加
213  InsertNodeLeft(pNode, pN);
214  return NULL;
215  }
216  pN = pN->GetLeft();
217  }
218  else if (key > pN->m_Key)
219  {
220  if (pN->GetRight() == NULL)
221  {
222  // 右に追加
223  InsertNodeRight(pNode, pN);
224  return NULL;
225  }
226  pN = pN->GetRight();
227  }
228  else
229  {
230  // 同じキーがあるので差し替え
231 
232  ReplaceNode(pNode, pN);
233  pN->InitNode();
234  return pN;
235  }
236  }
237 }
238 
239 
240 template <typename Key>
241 void TreeMap<Key>::EraseNode(Node* pNode)
242 {
243  EraseNodeBase(pNode);
244  pNode->InitNode();
245 }
246 //! @endcond
247 }
248 }
249 } // end of namespace nn::pia::common