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  UT_Set(UT_Set const &other) : Base(other) {}
81 
82  // Note: This can be removed when C++11 support is enabled due to existence
83  // of initializer lists.
84  UT_Set(const K &k,
85  const Hasher &hf = Hasher(),
86  const Equal &eql = Equal())
87  : Base(hboost::unordered::detail::default_bucket_count, hf, eql)
88  {
89  this->insert(k);
90  }
91 
92  /// Constructs a set from an initializer list:
93  /// UT_Set<int> some_set({5,123,500});
94  UT_Set(std::initializer_list<K> init,
95  const Hasher &hf = Hasher(),
96  const Equal &eql = Equal())
97  : Base(hboost::unordered::detail::default_bucket_count, hf, eql)
98  {
99  for (auto &&p = init.begin(); p != init.end(); ++p) {
100  this->insert(*p);
101  }
102  }
103 
104  int64 getMemoryUsage(bool inclusive) const
105  {
106  int64 mem = inclusive ? sizeof(*this) : 0;
107  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
108  return mem;
109  }
110 
111  /// Determines membership in a set, a bit more semantically readable
112  /// than count() or find()
113  bool contains(const K &key) const
114  { return Base::count(key) > 0; }
115 
116  bool contains(const UT_Set<K> &src) const
117  { for (const_iterator it = src.begin(); it != src.end(); ++it)
118  if (!contains(*it))
119  return false;
120  return true; }
121 
122  /// Set-wise boolean operations.
124  { for (const_iterator it = src.begin(); it != src.end(); ++it)
125  this->insert(*it);
126  return *this; }
128  { UT_Set<K,H,P> result;
129  for (const_iterator it = src.begin(); it != src.end(); ++it)
130  if (contains(*it))
131  result.insert(*it);
132  *this = std::move(result);
133  return *this; }
135  { for (const_iterator it = src.begin(); it != src.end(); ++it)
136  this->erase(*it);
137  return *this; }
138 
139 public:
140  // Lowering of base types
141  typedef typename Base::key_type key_type;
142  typedef typename Base::value_type value_type;
143  typedef typename Base::hasher hasher;
144  typedef typename Base::key_equal key_equal;
145  typedef typename Base::iterator iterator;
146  typedef typename Base::const_iterator const_iterator;
147 };
148 
149 
150 
151 template<typename K, typename C = std::less<K> >
152 class UT_SortedSet : public std::set<K, C>
153 {
154 public:
155  typedef std::set<K, C> Base;
156  typedef C LessThan;
157 
159 
160  explicit UT_SortedSet(const LessThan& lt) : Base(lt) {}
161 
162  template<typename InputIt>
163  UT_SortedSet(InputIt first, InputIt last) : Base(first, last) {}
164 
165  template<typename InputIt>
166  UT_SortedSet(InputIt first, InputIt last, const LessThan &lt) :
167  Base(first, last, lt) {}
168 
169  UT_SortedSet(const UT_SortedSet &other) : Base(other) {}
170 
171  // Note: This can be removed when C++11 support is enabled due to existence
172  // of initializer lists.
173  UT_SortedSet(const K &k) : Base()
174  {
175  this->insert(k);
176  }
177 
178  int64 getMemoryUsage(bool inclusive) const
179  {
180  int64 mem = inclusive ? sizeof(*this) : 0;
181  mem += UTgetMemoryUsage(*static_cast<const Base *>(this), false);
182  return mem;
183  }
184 
185  /// Determines membership in a set, a bit more semantically readable
186  /// than count() or find()
187  bool contains(const K &key) const
188  { return this->count(key) > 0; }
189 
190  bool contains(const UT_SortedSet<K> &src) const
191  { for (const_iterator it = src.begin(); it != src.end(); ++it)
192  if (!contains(*it))
193  return false;
194  return true; }
195 
196  /// Set-wise boolean operations.
198  { for (const_iterator it = src.begin(); it != src.end(); ++it)
199  this->insert(*it);
200  return *this; }
202  { UT_SortedSet<K,C> result;
203  for (const_iterator it = src.begin(); it != src.end(); ++it)
204  if (contains(*it))
205  result.insert(*it);
206  *this = std::move(result);
207  return *this; }
209  { for (const_iterator it = src.begin(); it != src.end(); ++it)
210  this->erase(*it);
211  return *this; }
212 
213 public:
214  // Lowering of base types.
215  typedef typename Base::key_type key_type;
216  typedef typename Base::value_type value_type;
217  typedef typename Base::key_compare key_compare;
218  typedef typename Base::iterator iterator;
219  typedef typename Base::const_iterator const_iterator;
220 };
221 
222 template<typename OS, typename S>
223 inline OS &
224 operator<<(OS &os, const UT_Set<S> &d)
225 {
226  os << "UT_Set" << UT_ContainerPrinter<UT_Set<S> >(d);
227  return os;
228 }
229 
230 template<typename OS, typename S>
231 inline OS &
232 operator<<(OS &os, const UT_SortedSet<S> &d)
233 {
234  os << "UT_SortedSet" << UT_ContainerPrinter<UT_SortedSet<S> >(d);
235  return os;
236 }
237 
238 
239 #endif
GLint first
Definition: glcorearb.h:404
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:104
Base::key_type key_type
Definition: UT_Set.h:141
UT_Set(UT_Set const &other)
Definition: UT_Set.h:80
UT_SortedSet(const UT_SortedSet &other)
Definition: UT_Set.h:169
UT_Set< K, H, P > & operator|=(const UT_Set< K, H, P > &src)
Set-wise boolean operations.
Definition: UT_Set.h:123
bool contains(const UT_SortedSet< K > &src) const
Definition: UT_Set.h:190
Base::const_iterator const_iterator
Definition: UT_Set.h:146
hboost::unordered_set< K, H, P > Base
Definition: UT_Set.h:61
UT_SortedSet< K, C > & operator&=(const UT_SortedSet< K, C > &src)
Definition: UT_Set.h:201
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:158
Base::key_compare key_compare
Definition: UT_Set.h:217
Base::value_type value_type
Definition: UT_Set.h:216
long long int64
Definition: SYS_Types.h:107
H Hasher
Definition: UT_Set.h:62
UT_SortedSet(const LessThan &lt)
Definition: UT_Set.h:160
UT_Set(const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:65
Base::iterator iterator
Definition: UT_Set.h:218
bool contains(const K &key) const
Definition: UT_Set.h:187
UT_SortedSet(InputIt first, InputIt last)
Definition: UT_Set.h:163
Base::value_type value_type
Definition: UT_Set.h:142
bool contains(const UT_Set< K > &src) const
Definition: UT_Set.h:116
UT_SortedSet(const K &k)
Definition: UT_Set.h:173
int64 getMemoryUsage(bool inclusive) const
Definition: UT_Set.h:178
Base::const_iterator const_iterator
Definition: UT_Set.h:219
int64 UTgetMemoryUsage(const hboost::unordered_set< K, H, P > &set, bool inclusive)
Definition: UT_Set.h:23
GLint GLsizei count
Definition: glcorearb.h:404
Base::key_equal key_equal
Definition: UT_Set.h:144
UT_Set< K, H, P > & operator&=(const UT_Set< K, H, P > &src)
Definition: UT_Set.h:127
Base::key_type key_type
Definition: UT_Set.h:215
UT_SortedSet< K, C > & operator|=(const UT_SortedSet< K, C > &src)
Set-wise boolean operations.
Definition: UT_Set.h:197
UT_Set< K, H, P > & operator-=(const UT_Set< K, H, P > &src)
Definition: UT_Set.h:134
std::set< K, C > Base
Definition: UT_Set.h:155
UT_SortedSet(InputIt first, InputIt last, const LessThan &lt)
Definition: UT_Set.h:166
UT_Set(std::initializer_list< K > init, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:94
bool contains(const K &key) const
Definition: UT_Set.h:113
Base::hasher hasher
Definition: UT_Set.h:143
P Equal
Definition: UT_Set.h:63
UT_SortedSet< K, C > & operator-=(const UT_SortedSet< K, C > &src)
Definition: UT_Set.h:208
UT_Set(const K &k, const Hasher &hf=Hasher(), const Equal &eql=Equal())
Definition: UT_Set.h:84
GLenum src
Definition: glcorearb.h:1792
Base::iterator iterator
Definition: UT_Set.h:145