GEOS  3.11.0
TemplateSTRNode.h
1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2020-2021 Daniel Baston
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU Lesser General Public Licence as published
10  * by the Free Software Foundation.
11  * See the COPYING file for more information.
12  *
13  **********************************************************************/
14 
15 #pragma once
16 
17 namespace geos {
18 namespace index {
19 namespace strtree {
20 
21 template<typename ItemType, typename BoundsTraits>
22 class TemplateSTRNode {
23 private:
24  using BoundsType = typename BoundsTraits::BoundsType;
25 
26  BoundsType bounds;
27 
28  union Body {
29  ItemType item;
30  const TemplateSTRNode* childrenEnd;
31 
32  explicit Body (ItemType&& p_item) : item(std::forward<ItemType>(p_item)) {}
33 
34  explicit Body (const ItemType& p_item) : item(p_item) {}
35 
36  explicit Body (const TemplateSTRNode<ItemType, BoundsTraits>* p_childrenEnd) : childrenEnd(p_childrenEnd) {}
37 
38  ~Body() = default;
39  } data;
40  const TemplateSTRNode* children;
41 
42 public:
43  ~TemplateSTRNode() {
44  if (isLeaf()) {
45  data.item.~ItemType();
46  }
47  }
48 
49  TemplateSTRNode(ItemType&& p_item, const BoundsType& env) :
50  bounds(env),
51  data(std::forward<ItemType>(p_item)),
52  children(nullptr)
53  {}
54 
55  TemplateSTRNode(const ItemType& p_item, const BoundsType& env) :
56  bounds(env),
57  data(p_item),
58  children(nullptr)
59  {}
60 
61  TemplateSTRNode(const TemplateSTRNode* begin, const TemplateSTRNode* end) :
62  bounds(boundsFromChildren(begin, end)),
63  data(end),
64  children(begin)
65  {}
66 
67  const TemplateSTRNode* beginChildren() const {
68  return children;
69  }
70 
71  const TemplateSTRNode* endChildren() const {
72  return data.childrenEnd;
73  }
74 
75  bool isDeleted() const {
76  return children == this;
77  }
78 
79  bool isLeaf() const {
80  return children == nullptr || children == this;
81  }
82 
83  bool isComposite() const {
84  return !isLeaf();
85  }
86 
87  bool boundsIntersect(const BoundsType& queryBounds) const {
88  return BoundsTraits::intersects(getBounds(), queryBounds);
89  }
90 
91  double getSize() const {
92  return BoundsTraits::size(getBounds());
93  }
94 
95  static BoundsType boundsFromChildren(const TemplateSTRNode* from, const TemplateSTRNode* to) {
96  BoundsType bnds = from->getBounds();
97 
98  for (auto *child = from + 1; child < to; ++child) {
99  BoundsTraits::expandToInclude(bnds, child->getBounds());
100  }
101 
102  return bnds;
103  }
104 
105  BoundsType boundsFromChildren() const {
106  return boundsFromChildren(children, data.childrenEnd);
107  }
108 
109  const BoundsType& getBounds() const {
110  return bounds;
111  }
112 
113  std::size_t getNumNodes() const
114  {
115  if (isLeaf()) {
116  return isDeleted() ? 0 : 1;
117  }
118 
119  std::size_t count = 1;
120  for (const auto* child = beginChildren(); child != endChildren(); ++child) {
121  count += child->getNumNodes();
122  }
123 
124  return count;
125  }
126 
127  std::size_t getNumLeafNodes() const
128  {
129  if (isLeaf()) {
130  return isDeleted() ? 0 : 1;
131  }
132 
133  std::size_t count = 0;
134  for (const auto* child = beginChildren(); child != endChildren(); ++child) {
135  count += child->getNumNodes();
136  }
137  return count;
138  }
139 
140  const ItemType& getItem() const {
141  assert(!isDeleted());
142  return data.item;
143  }
144 
145  void removeItem() {
146  children = this;
147  }
148 
149 };
150 
151 }
152 }
153 }
154 
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25