Node.h
Go to the documentation of this file.
1 /* Copyright (C) 2008 National Institute For Space Research (INPE) - Brazil.
2 
3  This file is part of the TerraLib - a Framework for building GIS enabled applications.
4 
5  TerraLib is free software: you can redistribute it and/or modify
6  it under the terms of the GNU Lesser General Public License as published by
7  the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  TerraLib is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU Lesser General Public License for more details.
14 
15  You should have received a copy of the GNU Lesser General Public License
16  along with TerraLib. See COPYING. If not, write to
17  TerraLib Team at <terralib-team@terralib.org>.
18  */
19 
20 /*!
21  \file terralib/sam/kdtree/Node.h
22 
23  \brief A class that represents an Kd-tree node.
24 */
25 
26 #ifndef __TERRALIB_SAM_KDTREE_INTERNAL_NODE_H
27 #define __TERRALIB_SAM_KDTREE_INTERNAL_NODE_H
28 
29 namespace te
30 {
31  namespace sam
32  {
33  namespace kdtree
34  {
35  /*! \brief Kd-tree node type for nodes with single elements (used by template instantiation). */
37 
38  /*! \brief Kd-Tree node type for nodes with multuple elements (used by template instantiation). */
40 
41  /*!
42  \class Node
43 
44  \brief A class that represents an Kd-tree node.
45 
46  Each node contains a pointer to its left and right subtree (NULL if it is not set),
47  one key used for insertion of the data into the tree.
48 
49  \note The key must have methods called getX() and getY().
50 
51  \note These kind of node stores the data in each node.
52 
53  \note The nodes may contains one single element (kd_node_m_datasingle_tag) or a set of values (kd_node_m_dataset_tag).
54 
55  \note If the node type is kd_node_m_datasingle_tag than NodeData and NodeDataItem are the same types.
56  And if one entry with the same key already exist, so they will be overwrite.
57 
58  \note If the node type is kd_node_m_dataset_tag than NodeData mus have a method called push_back(NodeDataItem)
59  that permits to store elements with the same key in the node.
60  */
61  template<class NodeKey, class NodeData, class NodeDataItem, class NodeDataTag = kd_node_m_datasingle_tag> class Node
62  {
63  public:
64 
65  //! Export key type.
66  typedef NodeKey kdKey;
67 
68  //! Export data type.
69  typedef NodeData kdData;
70 
71  //! Export data item type.
72  typedef NodeDataItem kdDataItem;
73 
74  //! Export data type.
75  typedef NodeDataTag kdDataTag;
76 
77  /*! \brief Constructor. */
78  Node(const NodeKey& k)
79  : m_key(k),
80  m_left(0),
81  m_right(0)
82  {
83  }
84 
85  /*! \brief It sets the key to the node. */
86  void setKey(const NodeKey& k)
87  {
88  m_key = k;
89  }
90 
91  /*! \brief It returns a reference to node key. */
92  const NodeKey& getKey() const
93  {
94  return m_key;
95  }
96 
97  /*! \brief It sets the data in the node. */
98  void setData(const NodeData& data)
99  {
100  m_data = data;
101  }
102 
103  /*! \brief It returns a reference to data node. */
104  NodeData& getData()
105  {
106  return m_data;
107  }
108 
109  /*! \brief It sets the left child pointer. */
110  void setLeft(Node* node)
111  {
112  m_left = node;
113  }
114 
115  /*! \brief It sets the right child pointer. */
116  void setRight(Node* node)
117  {
118  m_right = node;
119  }
120 
121  /*! \brief It gets the left child. */
122  Node* getLeft() const
123  {
124  return m_left;
125  }
126 
127  /*! \brief It gets the right child. */
128  Node* getRight() const
129  {
130  return m_right;
131  }
132 
133  /*! \brief It checks if this node has a left child. */
134  bool hasLeft() const
135  {
136  return m_left != 0;
137  }
138 
139  /*! \brief It checks if this node has a right child. */
140  bool hasRight() const
141  {
142  return m_right != 0;
143  }
144 
145  /*! \brief It returns true if this node is a leaf node. */
146  bool isLeaf() const
147  {
148  return !(hasLeft() || hasRight());
149  }
150 
151  /*! \brief It counts the number of nodes below this. */
152  std::size_t descendants() const
153  {
154  std::size_t totalLeft = 0;
155  std::size_t totalRight = 0;
156 
157  if(hasLeft())
158  totalLeft = 1 + getLeft()->descendants();
159 
160  if(hasRight())
161  totalRight = 1 + getRight()->descendants();
162 
163  return totalLeft + totalRight;
164  }
165 
166  private:
167 
168  /*!
169  \brief No copy constructor allowed.
170 
171  \param rhs The other node.
172  */
173  Node(const Node& rhs);
174 
175  /*!
176  \brief No assignment operator allowed.
177 
178  \param rhs The other node.
179 
180  \return A reference for this.
181  */
182  Node& operator=(const Node& rhs);
183 
184  protected:
185 
186  NodeKey m_key; //!< The key used to access this record.
187  NodeData m_data; //!< The data stored in this record.
188  Node* m_left; //!< Pointer to the left sub-tree.
189  Node* m_right; //!< Pointer to the right sub-tree.
190  };
191 
192  /*!
193  \class AdaptativeNode
194 
195  \brief A class that represents an Kd-tree node.
196 
197  Each node contains a pointer to its left and right subtree (NULL if it is not set),
198  a discriminator that indicates the axis of partition, the partition key and a set of data-items.
199 
200  \note The key must have methods called getX() and getY().
201 
202  \note These kind of node stores the data only in the leafs.
203 
204  \note The leaf nodes contains a set of values that forms a bucket (the size is controlled by the tree methods tha use this class).
205  */
206  template<class NodeKey, class NodeData, class NodeDataItem> class AdaptativeNode
207  {
208  public:
209 
210  //! Export key type.
211  typedef NodeKey kdKey;
212 
213  //! Export data type.
214  typedef NodeData kdData;
215 
216  //! Export data item type.
217  typedef NodeDataItem kdDataItem;
218 
219  /*! \brief Constructor. */
220  AdaptativeNode(const double& k)
221  : m_key(k),
222  m_discriminator('x'),
223  m_left(0),
224  m_right(0)
225  {
226  }
227 
228  /*! \brief It sets the key to the node. */
229  void setKey(const double& k)
230  {
231  m_key = k;
232  }
233 
234  /*! \brief It returns a reference to node key. */
235  const double& getKey() const
236  {
237  return m_key;
238  }
239 
240  /*! \brief It sets the data in the node. */
241  void setData(const NodeData& data)
242  {
243  m_data = data;
244  }
245 
246  /*! \brief It returns a reference to data node. */
247  NodeData& getData()
248  {
249  return m_data;
250  }
251 
252  /*! \brief It sets the data in the node. */
253  void setDiscriminator(const char& d)
254  {
255  m_discriminator = d;
256  }
257 
258  /*! \brief It returns a reference to discriminator. */
259  const char& getDiscriminator() const
260  {
261  return m_discriminator;
262  }
263 
264  /*! \brief It sets the left child pointer. */
266  {
267  m_left = node;
268  }
269 
270  /*! \brief It sets the right child pointer. */
272  {
273  m_right = node;
274  }
275 
276  /*! \brief It gets the left child. */
278  {
279  return m_left;
280  }
281 
282  /*! \brief It gets the right child. */
284  {
285  return m_right;
286  }
287 
288  /*! \brief It checks if this node has a left child. */
289  bool hasLeft() const
290  {
291  return m_left != 0;
292  }
293 
294  /*! \brief It checks if this node has a right child. */
295  bool hasRight() const
296  {
297  return m_right != 0;
298  }
299 
300  /*! \brief It returns true if this node is a leaf node. */
301  bool isLeaf() const
302  {
303  return !(hasLeft() || hasRight());
304  }
305 
306  /*! \brief It counts the number of nodes below this. */
307  std::size_t descendants() const
308  {
309  std::size_t totalLeft = 0;
310  std::size_t totalRight = 0;
311 
312  if(hasLeft())
313  totalLeft = 1 + getLeft()->descendants();
314 
315  if(hasRight())
316  totalRight = 1 + getRight()->descendants();
317 
318  return totalLeft + totalRight;
319  }
320 
321  private:
322 
323  /*!
324  \brief No copy constructor allowed.
325 
326  \param rhs The other node.
327  */
328  AdaptativeNode(const AdaptativeNode& rhs);
329 
330  /*!
331  \brief No assignment operator allowed.
332 
333  \param rhs The other node.
334 
335  \return A reference for this.
336  */
338 
339  protected:
340 
341  double m_key; //!< The key used to access this record.
342  NodeData m_data; //!< The data stored in this record.
343  char m_discriminator; //!< The discriminator used in partition.
344  AdaptativeNode* m_left; //!< Pointer to the left sub-tree.
345  AdaptativeNode* m_right; //!< Pointer to the right sub-tree.
346  };
347 
348  } // end namespace kdtree
349  } // end namespace sam
350 } // end namespace te
351 
352 #endif // __TERRALIB_SAM_KDTREE_INTERNAL_NODE_H
double m_key
The key used to access this record.
Definition: Node.h:341
char m_discriminator
The discriminator used in partition.
Definition: Node.h:343
NodeDataItem kdDataItem
Export data item type.
Definition: Node.h:72
void setKey(const double &k)
It sets the key to the node.
Definition: Node.h:229
AdaptativeNode * m_right
Pointer to the right sub-tree.
Definition: Node.h:345
NodeKey m_key
The key used to access this record.
Definition: Node.h:186
const NodeKey & getKey() const
It returns a reference to node key.
Definition: Node.h:92
bool isLeaf() const
It returns true if this node is a leaf node.
Definition: Node.h:301
Node * m_left
Pointer to the left sub-tree.
Definition: Node.h:188
AdaptativeNode * m_left
Pointer to the left sub-tree.
Definition: Node.h:344
const double & getKey() const
It returns a reference to node key.
Definition: Node.h:235
std::size_t descendants() const
It counts the number of nodes below this.
Definition: Node.h:152
void setRight(Node *node)
It sets the right child pointer.
Definition: Node.h:116
bool hasRight() const
It checks if this node has a right child.
Definition: Node.h:140
Node & operator=(const Node &rhs)
No assignment operator allowed.
const char & getDiscriminator() const
It returns a reference to discriminator.
Definition: Node.h:259
URI C++ Library.
void setLeft(AdaptativeNode *node)
It sets the left child pointer.
Definition: Node.h:265
AdaptativeNode(const double &k)
Constructor.
Definition: Node.h:220
void setKey(const NodeKey &k)
It sets the key to the node.
Definition: Node.h:86
std::size_t descendants() const
It counts the number of nodes below this.
Definition: Node.h:307
bool hasLeft() const
It checks if this node has a left child.
Definition: Node.h:289
NodeData m_data
The data stored in this record.
Definition: Node.h:342
NodeData kdData
Export data type.
Definition: Node.h:214
void setLeft(Node *node)
It sets the left child pointer.
Definition: Node.h:110
bool hasLeft() const
It checks if this node has a left child.
Definition: Node.h:134
Kd-Tree node type for nodes with multuple elements (used by template instantiation).
Definition: Node.h:39
void setData(const NodeData &data)
It sets the data in the node.
Definition: Node.h:241
NodeData kdData
Export data type.
Definition: Node.h:69
Kd-tree node type for nodes with single elements (used by template instantiation).
Definition: Node.h:36
A class that represents an Kd-tree node.
Definition: Node.h:61
NodeKey kdKey
Export key type.
Definition: Node.h:211
Node * getRight() const
It gets the right child.
Definition: Node.h:128
Node * getLeft() const
It gets the left child.
Definition: Node.h:122
Node(const NodeKey &k)
Constructor.
Definition: Node.h:78
bool hasRight() const
It checks if this node has a right child.
Definition: Node.h:295
void setDiscriminator(const char &d)
It sets the data in the node.
Definition: Node.h:253
bool isLeaf() const
It returns true if this node is a leaf node.
Definition: Node.h:146
Node * m_right
Pointer to the right sub-tree.
Definition: Node.h:189
NodeData m_data
The data stored in this record.
Definition: Node.h:187
AdaptativeNode * getRight() const
It gets the right child.
Definition: Node.h:283
void setRight(AdaptativeNode *node)
It sets the right child pointer.
Definition: Node.h:271
NodeDataItem kdDataItem
Export data item type.
Definition: Node.h:217
A class that represents an Kd-tree node.
Definition: Node.h:206
NodeData & getData()
It returns a reference to data node.
Definition: Node.h:104
NodeKey kdKey
Export key type.
Definition: Node.h:66
void setData(const NodeData &data)
It sets the data in the node.
Definition: Node.h:98
AdaptativeNode & operator=(const AdaptativeNode &rhs)
No assignment operator allowed.
NodeData & getData()
It returns a reference to data node.
Definition: Node.h:247
AdaptativeNode * getLeft() const
It gets the left child.
Definition: Node.h:277
NodeDataTag kdDataTag
Export data type.
Definition: Node.h:75