HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_Set.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_Set.h (UT Library, C++)
7  *
8  * COMMENTS: Wrapper for an unordered set data structure. Prefer to use
9  * this to std::set since hboost::unordered_set is more
10  * efficient when order is not needed.
11  */
12 
13 #ifndef __UT_Set__
14 #define __UT_Set__
15 
16 #include "UT_ContainerPrinter.h"
17 
18 #include <set>
19 #include <hboost/unordered_set.hpp>
20 
21 template<typename K, typename H, typename P>
22 int64
23 UTgetMemoryUsage(const hboost::unordered_set<K, H, P> &set, bool inclusive)
24 {
25  int64 mem = inclusive ? sizeof(set) : 0;
26  // Buckets only contain a pointer to the node
27  mem += set.bucket_count() * sizeof(void*);
28  // Nodes contain the hash value, a pointer to the next node,
29  // and the key.
30  mem += set.size() * (sizeof(size_t) + sizeof(void*) + sizeof(K));
31  return mem;
32 }
33 
34 template<typename K, typename C>
35 int64
36 UTgetMemoryUsage(const std::set<K, C> &set, bool inclusive)
37 {
38  int64 mem = inclusive ? sizeof(set) : 0;
39 
40  // NOTE: If the comparator object of type C owns any memory
41  // (i.e. apart from itself) when default constructed
42  // or copy constructed, that memory won't be counted.
43 
44  // NOTE: This count is for the VC++ 2010 implementation
45  // of std::map, but others should be in the ballpark.
46  // Nodes contain pointers to the left, parent, and right,
47  // the key, a colour in a char (red or black),
48  // and a flag in a char indicating if the node is the head,
49  // (in which case the key is ignored).
50  // Round up to a multiple of 4 on the size of each node.
51  mem += (set.size() + 1) * ((3*sizeof(void*) + sizeof(K)
52  + 2*sizeof(char) + 3) & ~3);
53  return mem;
54 }
55 
56 template<typename K,
57  typename H = hboost::hash<K>, typename P = std::equal_to<K> >
58 class UT_Set : public hboost::unordered_set<K, H, P>
59 {
60 public:
61  typedef hboost::unordered_set<K, H, P> Base;
62  typedef H Hasher;
63  typedef P Equal;
64 
65  explicit UT_Set(
66  const Hasher &hf = Hasher(),
67  const Equal &eql = Equal()) :
68  Base(hboost::unordered::detail::default_bucket_count, hf, eql) {}
69 
70  template <typename InputIt>
71  UT_Set(InputIt first, InputIt last) : Base(first, last) {}
72 
73  template <typename InputIt>
74  UT_Set(InputIt first, InputIt last,
75  const Hasher &hf = Hasher(),
76  const Equal &eql = Equal()) :
77  Base(first, last, hboost::unordered::detail::default_bucket_count,
78  hf, eql) {}
79 
80  // Note: This can be removed when C++11 support is enabled due to existence
81  // of initializer lists.
82  UT_Set(const K &k,
83  const Hasher &hf = Hasher(),
84  const Equal &eql = Equal())
85  : Base(hboost::unordered::detail::default_bucket_count, hf, eql)
86  {
87  this->insert(k);
88  }
89 
90  /// Constructs a set from an initializer list:
91  /// UT_Set<int> some_set({5,123,500});
92  UT_Set(std::initializer_list<K> init,
93  const Hasher &hf = Hasher(),
94  const Equal &eql = Equal())
95  : Base(hboost::unordered::detail::default_bucket_count, hf, eql)
96  {
97  for (auto &&p = init.begin(); p != init.end(); ++p) {
98  this->insert(*p);
99  }
100  }
101 
102  int64 getMemoryUsage(bool inclusive) const
103  {
104  int64 mem = inclusive ? sizeof(*this) : 0;
105  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
106  return mem;
107  }
108 
109  /// Determines membership in a set, a bit more semantically readable
110  /// than count() or find()
111  bool contains(const K &key) const
112  { return Base::count(key) > 0; }
113 
114  bool contains(const UT_Set<K> &src) const
115  { for (const_iterator it = src.begin(); it != src.end(); ++it)
116  if (!contains(*it))
117  return false;
118  return true; }
119 
120  /// Set-wise boolean operations.
122  { for (const_iterator it = src.begin(); it != src.end(); ++it)
123  this->insert(*it);
124  return *this; }
127  for (const_iterator it = src.begin(); it != src.end(); ++it)
128  if (contains(*it))
129  result.insert(*it);
130  *this = std::move(result);
131  return *this; }
133  { for (const_iterator it = src.begin(); it != src.end(); ++it)
134  this->erase(*it);
135  return *this; }
136 
137 public:
138  // Lowering of base types
139  typedef typename Base::key_type key_type;
140  typedef typename Base::value_type value_type;
141  typedef typename Base::hasher hasher;
142  typedef typename Base::key_equal key_equal;
143  typedef typename Base::iterator iterator;
144  typedef typename Base::const_iterator const_iterator;
145 };
146 
147 
148 
149 template<typename K, typename C = std::less<K> >
150 class UT_SortedSet : public std::set<K, C>
151 {
152 public:
153  typedef std::set<K, C> Base;
154  typedef C LessThan;
155 
157 
158  explicit UT_SortedSet(const LessThan& lt) : Base(lt) {}
159 
160  template<typename InputIt>
161  UT_SortedSet(InputIt first, InputIt last) : Base(first, last) {}
162 
163  template<typename InputIt>
164  UT_SortedSet(InputIt first, InputIt last, const LessThan &lt) :
165  Base(first, last, lt) {}
166 
167  // Note: This can be removed when C++11 support is enabled due to existence
168  // of initializer lists.
169  UT_SortedSet(const K &k) : Base()
170  {
171  this->insert(k);
172  }
173 
174  int64 getMemoryUsage(bool inclusive) const
175  {
176  int64 mem = inclusive ? sizeof(*this) : 0;
177  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
178  return mem;
179  }
180 
181  /// Determines membership in a set, a bit more semantically readable
182  /// than count() or find()
183  bool contains(const K &key) const
184  { return this->count(key) > 0; }
185 
186  bool contains(const UT_SortedSet<K> &src) const
187  { for (const_iterator it = src.begin(); it != src.end(); ++it)
188  if (!contains(*it))
189  return false;
190  return true; }
191 
192  /// Set-wise boolean operations.
194  { for (const_iterator it = src.begin(); it != src.end(); ++it)
195  this->insert(*it);
196  return *this; }
199  for (const_iterator it = src.begin(); it != src.end(); ++it)
200  if (contains(*it))
201  result.insert(*it);
202  *this = std::move(result);
203  return *this; }
205  { for (const_iterator it = src.begin(); it != src.end(); ++it)
206  this->erase(*it);
207  return *this; }
208 
209 public:
210  // Lowering of base types.
211  typedef typename Base::key_type key_type;
212  typedef typename Base::value_type value_type;
213  typedef typename Base::key_compare key_compare;
214  typedef typename Base::iterator iterator;
215  typedef typename Base::const_iterator const_iterator;
216 };
217 
218 template<typename OS, typename S>
219 inline OS &
220 operator<<(OS &os, const UT_Set<S> &d)
221 {
222  os << "UT_Set" << UT_ContainerPrinter<UT_Set<S> >(d);
223  return os;
224 }
225 
226 template<typename OS, typename S>
227 inline OS &
228 operator<<(OS &os, const UT_SortedSet<S> &d)
229 {
230  os << "UT_SortedSet" << UT_ContainerPrinter<UT_SortedSet<S> >(d);
231  return os;
232 }
233 
234 
235 #endif
vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
Definition: simd.h:3340
UT_Set(InputIt first, InputIt last, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:74
Definition: UT_Set.h:58
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Set.h:102
GLenum src
Definition: glew.h:2410
Base::key_type key_type
Definition: UT_Set.h:139
UT_Set< K, H, P > & operator|=(const UT_Set< K, H, P > &src)
Set-wise boolean operations.
Definition: UT_Set.h:121
bool contains(const UT_SortedSet< K > &src) const
Definition: UT_Set.h:186
hboost::unordered_set< K, H, P > Base
Definition: UT_Set.h:61
const GLint * first
Definition: glew.h:1528
UT_SortedSet< K, C > & operator&=(const UT_SortedSet< K, C > &src)
Definition: UT_Set.h:197
GA_API const UT_StringHolder P
uint64 value_type
Definition: GA_PrimCompat.h:29
UT_Set(InputIt first, InputIt last)
Definition: UT_Set.h:71
UT_SortedSet()
Definition: UT_Set.h:156
Base::key_compare key_compare
Definition: UT_Set.h:213
Base::value_type value_type
Definition: UT_Set.h:212
H Hasher
Definition: UT_Set.h:62
UT_SortedSet(const LessThan &lt)
Definition: UT_Set.h:158
UT_Set(const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:65
Base::iterator iterator
Definition: UT_Set.h:214
bool contains(const K &key) const
Definition: UT_Set.h:183
UT_SortedSet(InputIt first, InputIt last)
Definition: UT_Set.h:161
Base::value_type value_type
Definition: UT_Set.h:140
bool contains(const UT_Set< K > &src) const
Definition: UT_Set.h:114
UT_SortedSet(const K &k)
Definition: UT_Set.h:169
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Set.h:174
long long int64
Definition: SYS_Types.h:116
Base::const_iterator const_iterator
Definition: UT_Set.h:215
int64 UTgetMemoryUsage(const hboost::unordered_set< K, H, P > &set, bool inclusive)
Definition: UT_Set.h:23
Base::key_equal key_equal
Definition: UT_Set.h:142
GLfloat GLfloat p
Definition: glew.h:16321
UT_Set< K, H, P > & operator&=(const UT_Set< K, H, P > &src)
Definition: UT_Set.h:125
Base::key_type key_type
Definition: UT_Set.h:211
GLuint GLuint GLsizei count
Definition: glew.h:1253
UT_SortedSet< K, C > & operator|=(const UT_SortedSet< K, C > &src)
Set-wise boolean operations.
Definition: UT_Set.h:193
UT_Set< K, H, P > & operator-=(const UT_Set< K, H, P > &src)
Definition: UT_Set.h:132
GLuint64EXT * result
Definition: glew.h:14007
std::set< K, C > Base
Definition: UT_Set.h:153
UT_SortedSet(InputIt first, InputIt last, const LessThan &lt)
Definition: UT_Set.h:164
UT_Set(std::initializer_list< K > init, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:92
bool contains(const K &key) const
Definition: UT_Set.h:111
Base::hasher hasher
Definition: UT_Set.h:141
P Equal
Definition: UT_Set.h:63
UT_SortedSet< K, C > & operator-=(const UT_SortedSet< K, C > &src)
Definition: UT_Set.h:204
UT_Set(const K &k, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:82
Base::iterator iterator
Definition: UT_Set.h:143