libsurf
Programmer's Documentation

dcedgetable.h (r6227/r5385)
1 
2 /* Copyright (C) 2015 David Eller <david@larosterna.com>
3  *
4  * Commercial License Usage
5  * Licensees holding valid commercial licenses may use this file in accordance
6  * with the terms contained in their respective non-exclusive license agreement.
7  * For further information contact david@larosterna.com .
8  *
9  * GNU General Public License Usage
10  * Alternatively, this file may be used under the terms of the GNU General
11  * Public License version 3.0 as published by the Free Software Foundation and
12  * appearing in the file gpl.txt included in the packaging of this file.
13  */
14 
15 #ifndef SURF_DCEDGETABLE_H
16 #define SURF_DCEDGETABLE_H
17 
18 #include "dcedge.h"
19 #include <genua/preshinghashtable.h>
20 #include <boost/static_assert.hpp>
21 #include <boost/functional/hash.hpp>
22 #include <boost/unordered/unordered_set.hpp>
23 
39 {
40 public:
41 
43  DcEdgeOpenTable(size_t initialSize = 512) : m_imap(initialSize)
44  {
45  BOOST_STATIC_ASSERT(sizeof(size_t) == sizeof(uint64_t));
46  }
47 
49  size_t size() const {return m_imap.size();}
50 
52  DcEdge *find(uint src, uint trg)
53  {
54  if (src > trg)
55  std::swap(src, trg);
56  PreshingTable::Cell *cell = m_imap.lookup(keyOf(src, trg));
57  return decode(cell);
58  }
59 
61  void insert(DcEdge *pe)
62  {
63  size_t key = keyOf(pe->source(), pe->target());
64  PreshingTable::Cell *cell = m_imap.insert(key);
65  assert(cell != nullptr);
66  cell->value = encode(pe);
67  }
68 
70  void erase(uint src, uint trg) {
71  if (src > trg)
72  std::swap(src, trg);
73  m_imap.erase(keyOf(src, trg));
74  }
75 
77  void clear() { m_imap.clear(); }
78 
79  friend class Iterator;
80 
81  class Iterator
82  {
83  public:
84 
86  Iterator(PreshingTable &table, bool toBegin = true) : m_iter(table, toBegin)
87  {
88  }
89 
91  inline Iterator &operator++()
92  {
93  m_iter.next();
94  return *this;
95  }
96 
98  inline DcEdge *operator*() const
99  {
100  PreshingTable::Cell *cell = *m_iter;
101  return DcEdgeOpenTable::decode(cell);
102  }
103 
105  inline DcEdge *operator->() const
106  {
107  PreshingTable::Cell *cell = *m_iter;
108  return DcEdgeOpenTable::decode(cell);
109  }
110 
112  bool operator==(const Iterator &other) const
113  {
114  return *m_iter == *(other.m_iter);
115  }
116 
118  bool operator!=(const Iterator &other) const
119  {
120  return *m_iter != *(other.m_iter);
121  }
122 
123  private:
126  };
127 
130 
133 
134 private:
135 
137  static inline uint64_t keyOf(uint src, uint trg)
138  {
139  return (uint64_t(src) << 32) | uint64_t(trg);
140  }
141 
143  static inline DcEdge *decode(const PreshingTable::Cell *c) {
144  if (c != nullptr) {
145  union { size_t s; DcEdge *p; } u;
146  u.s = c->value;
147  return u.p;
148  }
149  return nullptr;
150  }
151 
153  static inline size_t encode(const DcEdge *ptr) {
154  union { size_t s; const DcEdge *p; } u;
155  u.p = ptr;
156  return u.s;
157  }
158 
159 private:
160 
163 };
164 
166 {
167 public:
168 
170  typedef boost::unordered_set<DcEdge*, DcEdge::Hasher,
172 
174  typedef HashSet::iterator Iterator;
175 
177  DcEdgeHashTable(size_t initialSize = 512) { m_set.reserve(initialSize); }
178 
180  size_t size() const {return m_set.size();}
181 
183  DcEdge *find(uint src, uint trg)
184  {
185  DcEdge test(src, trg);
186  HashSet::const_iterator pos = m_set.find(&test);
187  return (pos != m_set.end()) ? *pos : nullptr;
188  }
189 
191  void insert(DcEdge *pe)
192  {
193  m_set.insert(pe);
194  }
195 
197  void erase(uint src, uint trg) {
198  DcEdge test(src, trg);
199  HashSet::const_iterator pos = m_set.find(&test);
200  if (pos != m_set.end())
201  m_set.erase(pos);
202  }
203 
205  void clear() { m_set.clear(); }
206 
208  Iterator begin() {return m_set.begin();}
209 
211  Iterator end() {return m_set.end();}
212 
213 private:
214 
217 };
218 
219 #ifdef GENUA_64BIT
221 #else
223 #endif
224 
225 #endif // DCEDGETABLE_H
Iterator(PreshingTable &table, bool toBegin=true)
create a &#39;begin&#39; iterator
Definition: dcedgetable.h:86
Compares two edges for equality with respect to vertex indices.
Definition: dcedge.h:229
Definition: dcedgetable.h:165
Iterator begin()
iterate over map
Definition: dcedgetable.h:208
DcEdge * operator*() const
dereference
Definition: dcedgetable.h:98
uint32_t source() const
access source vertex
Definition: dcedge.h:103
DcEdgeHashTable(size_t initialSize=512)
initialize with an guess for the size
Definition: dcedgetable.h:177
static size_t encode(const DcEdge *ptr)
encode content pointer
Definition: dcedgetable.h:153
Cell * insert(size_t key)
Iterator & operator++()
prefix increment
Definition: dcedgetable.h:91
Cell * lookup(size_t key)
PreshingTable::Iterator m_iter
iterator to integer map
Definition: dcedgetable.h:125
Computes hash value from vertex indices.
Definition: dcedge.h:218
Iterator end()
iteration over all edges
Definition: dcedgetable.h:132
DcEdge * find(uint src, uint trg)
lookup edge
Definition: dcedgetable.h:183
HashSet::iterator Iterator
iterator type
Definition: dcedgetable.h:174
void clear()
erase contents
Definition: dcedgetable.h:205
bool operator!=(const Iterator &other) const
inequality
Definition: dcedgetable.h:118
size_t size() const
number of edges presently stored in container
Definition: dcedgetable.h:49
DcEdge * find(uint src, uint trg)
lookup edge
Definition: dcedgetable.h:52
Edge hash table.
Definition: dcedgetable.h:38
DcEdgeOpenTable(size_t initialSize=512)
initialize with size guess
Definition: dcedgetable.h:43
void clear()
erase contents
Definition: dcedgetable.h:77
size_t size() const
number of edges presently stored in container
Definition: dcedgetable.h:180
static DcEdge * decode(const PreshingTable::Cell *c)
decode content pointer
Definition: dcedgetable.h:143
HashSet m_set
actual storage
Definition: dcedgetable.h:216
Iterator begin()
iteration over all edges
Definition: dcedgetable.h:129
boost::unordered_set< DcEdge *, DcEdge::Hasher, DcEdge::PtrEqual > HashSet
backend : hash set from boost
Definition: dcedgetable.h:171
DcEdge * operator->() const
dereference
Definition: dcedgetable.h:105
void erase(uint src, uint trg)
erase edge
Definition: dcedgetable.h:197
bool operator==(const Iterator &other) const
equality
Definition: dcedgetable.h:112
void insert(DcEdge *pe)
insert edge
Definition: dcedgetable.h:61
void erase(uint src, uint trg)
erase edge
Definition: dcedgetable.h:70
static uint64_t keyOf(uint src, uint trg)
compute key for src/target combination
Definition: dcedgetable.h:137
Butterfly edge for Delaunay algorithms.
Definition: dcedge.h:39
void erase(Cell *cell)
Definition: dcedgetable.h:81
PreshingTable m_imap
64bit integer key-value map
Definition: dcedgetable.h:162
Iterator end()
iterate over map
Definition: dcedgetable.h:211
size_t size() const
uint32_t target() const
access target vertex
Definition: dcedge.h:106
void insert(DcEdge *pe)
insert edge
Definition: dcedgetable.h:191
Generated on Wed Jan 19 2022 03:03:15 for libsurf by   doxygen 1.8.5