HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stl.h
Go to the documentation of this file.
1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef PXR_BASE_TF_STL_H
25 #define PXR_BASE_TF_STL_H
26 
27 /// \file tf/stl.h
28 /// \ingroup group_tf_Stl
29 
30 #include "pxr/pxr.h"
31 
32 #include "pxr/base/tf/api.h"
33 #include "pxr/base/tf/tf.h"
34 #include "pxr/base/tf/hashmap.h"
35 #include "pxr/base/tf/hashset.h"
36 #include "pxr/base/tf/iterator.h"
37 
38 #include <algorithm>
39 #include <iterator>
40 #include <map>
41 #include <set>
42 #include <utility>
43 
45 
46 // Helper for TfMapLookup(). Uses std::map API to get a value by key.
47 template <class T>
49  typedef T Container;
50 
51  template <class Key, class Result>
52  static bool Lookup(Container const& map, Key const &key, Result* valuePtr)
53  {
54  typename Container::const_iterator i = map.find(key);
55  if (i == map.end()) {
56  return false;
57  }
58  else {
59  *valuePtr = i->second;
60  return true;
61  }
62  }
63 };
64 
65 /// Checks if an item exists in a \c map or a \c TfHashMap.
66 ///
67 /// If \p key exists in \p map, then this function returns \c true and the
68 /// value indexed by \p key is copied into \p *valuePtr. Otherwise,
69 /// \p *valuePtr is not modified, and \c false is returned.
70 ///
71 /// Example:
72 /// \code
73 /// TfHashMap<string, int, TfHash> m = ...;
74 /// int value;
75 ///
76 ///
77 /// if (TfMapLookup(m, "someKey", &value))
78 /// printf("Value found: %d\n", value);
79 /// else
80 /// printf("Value not found\n");
81 /// ...
82 /// \endcode
83 ///
84 /// \ingroup group_tf_Stl
85 template <class Container, class Key, class Result>
86 bool TfMapLookup(Container const &map, Key const &key, Result* valuePtr)
87 {
88  return Tf_MapLookupHelper<Container>::Lookup(map, key, valuePtr);
89 }
90 
91 /// Checks if an item exists in a \c map or a \c TfHashMap.
92 ///
93 /// If \p key exists in \p map, then this function returns the value index by
94 /// \p key. Otherwise, \p defaultValue is returned. Note that the result is
95 /// returned by value, so this is best used for types that are quick to copy.
96 ///
97 /// Example:
98 /// \code
99 /// TfHashMap<string, int, TfHash> m;
100 /// m["foo"] = 1;
101 ///
102 /// int value = TfMapLookupByValue(m, "someKey", -1);
103 /// TF_AXIOM(value == -1);
104 ///
105 /// int value = TfMapLookupByValue(m, "foo", -1);
106 /// TF_AXIOM(value == 1);
107 ///
108 /// \endcode
109 ///
110 /// \ingroup group_tf_Stl
111 template <class Container, class Key, class Result>
112 const Result TfMapLookupByValue(Container const &map,
113  Key const &key, const Result &defaultValue)
114 {
115  typename Container::const_iterator i = map.find(key);
116  if (i == map.end()) {
117  return defaultValue;
118  } else {
119  return i->second;
120  }
121 }
122 
123 /// Checks if an item exists in a \c map or \c TfHashMap, without copying it.
124 ///
125 /// If \p key exists in the \p map, then this function returns a pointer to
126 /// the value indexed by \p key. Otherwise, NULL is returned.
127 ///
128 /// Example:
129 /// \code
130 /// TfHashMap<string, BigData, TfHash> m = ...;
131 ///
132 /// if (BigData* bigPtr = TfMapLookupPtr(m, "someKey"))
133 /// bigPtr->ModifyStuff();
134 /// else
135 /// printf("Value not found\n");
136 /// \endcode
137 ///
138 /// \ingroup group_tf_Stl
139 template <class Container, class Key>
140 typename Container::mapped_type *
141 TfMapLookupPtr(Container &map, Key const &key)
142 {
143  typename Container::iterator i = map.find(key);
144  return (i != map.end()) ? &(i->second) : NULL;
145 }
146 
147 template <class Container, class Key>
148 typename Container::mapped_type const *
149 TfMapLookupPtr(Container const &map, Key const &key)
150 {
151  typename Container::const_iterator i = map.find(key);
152  return (i != map.end()) ? &(i->second) : NULL;
153 }
154 
155 /// Return an \c std::pair in sorted order.
156 ///
157 /// This call is a useful helper for maps whose key is an unordered pair of
158 /// elements. One can either define a new data type such that (a,b) is deemed
159 /// equivalent to (b,a), or more simply, adopt the convention that a key is
160 /// always written (a,b) with a < b.
161 ///
162 /// \ingroup group_tf_Stl
163 template <typename T>
164 inline std::pair<T,T>
166  return (a < b) ? std::pair<T,T>(a,b) : std::pair<T,T>(b,a);
167 }
168 
169 /// Reset \a obj to be an empty, space-optimized object.
170 ///
171 /// This can be used to clear c++ containers and reclaim their memory. For
172 /// instance, std::vector::clear() will not reclaim any memory, even if the
173 /// vector previously had a large number of elements. Often, this is what you
174 /// want because the vector is later filled again. But sometimes you want to
175 /// reclaim the memory, and this function will do that.
176 ///
177 /// As another example, gcc's hash_map and hash_set do not clear their bucket
178 /// lists when they themselves are cleared. This can lead to poor performance
179 /// due to ever-growing bucket lists for hashes that are repeatedly filled,
180 /// cleared, and filled again. TfReset will avoid this by effectively
181 /// clearing the bucket list.
182 ///
183 /// This function requires that the expression T().swap(obj) where obj is of
184 /// type T& be valid. This is true for many classes, including the standard
185 /// containers.
186 template <class T>
187 inline void TfReset(T &obj) {
188  T().swap(obj);
189 }
190 
192 
193 /// Specialize for TfHashMap to make minimally sized hashes.
194 template <class Key, class Value, class Hash, class Equal, class Alloc>
196  // If the implementation of the hash map allocates buckets when
197  // constructed asking for zero then only swap a constructed object
198  // if \p hash has more than that many buckets already, otherwise
199  // we just clear(). Note that this assumes that the number of
200  // buckets does not depend on the template parameter types which
201  // is reasonable.
202  static size_t emptyCount = Tf_GetEmptyHashMapBucketCount();
203 
204  if (hash.bucket_count() > emptyCount)
206  else if (!hash.empty())
207  hash.clear();
208 }
209 
211 
212 /// Specialize for TfHashSet to make minimally sized hashes.
213 template <class Value, class Hash, class Equal, class Alloc>
215  static size_t emptyCount = Tf_GetEmptyHashSetBucketCount();
216 
217  // See comment above about issues with TfHashSet(0).
218  if (hash.bucket_count() > emptyCount)
220  else if (!hash.empty())
221  hash.clear();
222 }
223 
224 /// Produce a sequence consisting of the set difference of [\a first1, \a
225 /// last1) and [\a first2, \a last2), while maintaining the relative order of
226 /// the first sequence. No particular order is required for either range, but
227 /// elements must have a strict weak order provided by operator<.
228 ///
229 /// If an element appears multiple times in either the first or second
230 /// sequence, the number of occurrences in the output is the difference
231 /// between the first sequence and the second (or zero if there are more
232 /// occurrences in the second sequence). For example, if the first sequence
233 /// is (1, 3, 3, 1) and the second sequence is (2, 3, 2), the result will be
234 /// (1, 3, 1).
235 template <class InputIterator1, class InputIterator2, class OutputIterator>
236 void
237 TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1,
238  InputIterator2 first2, InputIterator2 last2,
239  OutputIterator result)
240 {
241  typedef std::multiset<typename InputIterator2::value_type> SetType;
242  SetType set2(first2, last2);
243 
244  // Walk [first1, last1). If the element is in set2, skip it, and remove one
245  // of those elements from set2, otherwise output it.
246  for (InputIterator1 i = first1; i != last1; ++i) {
247  typename SetType::iterator j = set2.find(*i);
248  if (j != set2.end())
249  set2.erase(j);
250  else
251  *result++ = *i;
252  }
253 }
254 
255 /// Produce a sequence consisting of the set difference of [\a first1, \a
256 /// last1) and [\a first2, \a last2), while maintaining the relative order of
257 /// the first sequence. No particular order is required for either range, but
258 /// elements must have a strict weak order provided by operator<.
259 ///
260 /// If an element appears multiple times in either the first or second
261 /// sequence, the number of occurrences in the output is the difference
262 /// between the first sequence and the second (or zero if there are more
263 /// occurrences in the second sequence). For example, if the first sequence
264 /// is (1, 3, 3, 1) and the second sequence is (2, 3, 2), the result will be
265 /// (1, 3, 1).
266 template <class BackInsertionSequence,
267  class InputIterator1, class InputIterator2>
268 BackInsertionSequence
269 TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1,
270  InputIterator2 first2, InputIterator2 last2)
271 {
272  BackInsertionSequence result;
273  TfOrderedSetDifference(first1, last1, first2, last2,
274  std::back_inserter(result));
275  return result;
276 }
277 
278 /// Produce a sequence consisting of the set difference of the unique elements
279 /// in [\a first1, \a last1) and [\a first2, \a last2), while maintaining the
280 /// relative order of the first sequence. No particular order is required for
281 /// either range, but elements must have a strict weak order provided by
282 /// operator<.
283 ///
284 /// If an element appears multiple times in the first sequence, it appears
285 /// either zero or one times in the output. It appears zero times if it
286 /// appears in the second sequence, and one time if it does not. For example,
287 /// if the first sequence is (1, 3, 3, 1) and the second sequence is (2, 3,
288 /// 2), the result will be (1).
289 template <class InputIterator1, class InputIterator2, class OutputIterator>
290 void
291 TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1,
292  InputIterator2 first2, InputIterator2 last2,
293  OutputIterator result)
294 {
295  typedef std::set<typename InputIterator1::value_type> Set1Type;
296  typedef std::set<typename InputIterator2::value_type> Set2Type;
297 
298  Set1Type set1;
299  Set2Type set2(first2, last2);
300 
301  // Walk [first1, last1). If the element is in set1, skip it. Else insert
302  // it into set1, and if the element is not in set2, output it.
303  for (InputIterator1 i = first1; i != last1; ++i)
304  if (set1.insert(*i).second && !set2.count(*i))
305  *result++ = *i;
306 }
307 
308 /// Produce a sequence consisting of the set difference of the unique elements
309 /// in [\a first1, \a last1) and [\a first2, \a last2), while maintaining the
310 /// relative order of the first sequence. No particular order is required for
311 /// either range, but elements must have a strict weak order provided by
312 /// operator<.
313 ///
314 /// If an element appears multiple times in the first sequence, it appears
315 /// either zero or one times in the output. It appears zero times if it
316 /// appears in the second sequence, and one time if it does not. For example,
317 /// if the first sequence is (1, 3, 3, 1) and the second sequence is (2, 3,
318 /// 2), the result will be (1).
319 template <class BackInsertionSequence,
320  class InputIterator1, class InputIterator2>
321 BackInsertionSequence
323  InputIterator1 last1,
324  InputIterator2 first2,
325  InputIterator2 last2)
326 {
327  BackInsertionSequence result;
328  TfOrderedUniquingSetDifference(first1, last1, first2, last2,
329  std::back_inserter(result));
330  return result;
331 }
332 
333 /// A version of binary search that finds the boundary in a partitioned
334 /// sequence. The Predicate pred should return true for objects on the
335 /// 'first' side (or left-hand) side of the boundary.
336 ///
337 /// More precisely, given a range [first, last) and a Predicate pred for which
338 /// there is exactly one iterator called mid in that range such that pred(x)
339 /// is true for every x in [first, mid) and false for every x in [mid, last),
340 /// return mid.
341 template <class ForwardIterator, class Predicate>
342 static inline ForwardIterator
343 TfFindBoundary(ForwardIterator first, ForwardIterator last,
344  Predicate const &pred)
345 {
346  size_t len = std::distance(first, last);
347  size_t half;
348  ForwardIterator middle;
349 
350  while (len > 0) {
351  half = len >> 1;
352  middle = first;
353  std::advance(middle, half);
354  if (pred(*middle)) {
355  first = middle;
356  ++first;
357  len = len - half - 1;
358  }
359  else
360  len = half;
361  }
362  return first;
363 }
364 
365 /// Function object for retrieving the N'th element of a std::pair
366 /// or std::tuple. This is similar to std::get<N>, but wrapped up in a
367 /// function object suitable for use with STL algorithms.
368 ///
369 /// Example:
370 /// \code
371 /// const std::vector<std::pair<int, std::string>> pairs = { ... }
372 /// std::vector<int> intsOnly(pairs.size());
373 /// std::transform(pairs.begin(), pairs.end(), intsOnly.begin(), TfGet<0>());
374 /// \endcode
375 ///
376 /// \ingroup group_tf_Stl
377 template <size_t N>
378 class TfGet
379 {
380 public:
381  template <class PairOrTuple>
383 
384  template <class PairOrTuple>
385  constexpr return_type<PairOrTuple>& operator()(PairOrTuple& p) const
386  {
387  return std::get<N>(p);
388  }
389 
390  template <class PairOrTuple>
392  const PairOrTuple& p) const
393  {
394  return std::get<N>(p);
395  }
396 
397  template <class PairOrTuple>
398  constexpr return_type<PairOrTuple>&& operator()(PairOrTuple&& p) const
399  {
400  return std::get<N>(std::move(p));
401  }
402 };
403 
405 
406 #endif // PXR_BASE_TF_STL_H
GLint first
Definition: glcorearb.h:405
static bool Lookup(Container const &map, Key const &key, Result *valuePtr)
Definition: stl.h:52
void TfReset(T &obj)
Definition: stl.h:187
#define TF_API
Definition: api.h:40
imath_half_bits_t half
if we're in a C-only context, alias the half bits type to half
Definition: half.h:266
void swap(TfHashMap &other)
Definition: hashmap.h:348
void swap(TfHashSet &other)
Definition: hashset.h:343
TF_API size_t Tf_GetEmptyHashSetBucketCount()
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1222
std::pair< T, T > TfOrderedPair(T a, T b)
Definition: stl.h:165
**But if you need a result
Definition: thread.h:613
void TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Definition: stl.h:237
constexpr return_type< PairOrTuple > && operator()(PairOrTuple &&p) const
Definition: stl.h:398
BackInsertionSequence TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: stl.h:269
bool TfMapLookup(Container const &map, Key const &key, Result *valuePtr)
Definition: stl.h:86
constexpr const return_type< PairOrTuple > & operator()(const PairOrTuple &p) const
Definition: stl.h:391
BackInsertionSequence TfOrderedUniquingSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: stl.h:322
void TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Definition: stl.h:291
Container::mapped_type * TfMapLookupPtr(Container &map, Key const &key)
Definition: stl.h:141
Definition: stl.h:378
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1222
GLint j
Definition: glad.h:2733
constexpr return_type< PairOrTuple > & operator()(PairOrTuple &p) const
Definition: stl.h:385
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1441
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
SIM_API const UT_StringHolder distance
typename std::tuple_element< N, PairOrTuple >::type return_type
Definition: stl.h:382
type
Definition: core.h:1059
TF_API size_t Tf_GetEmptyHashMapBucketCount()
const Result TfMapLookupByValue(Container const &map, Key const &key, const Result &defaultValue)
Definition: stl.h:112