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 TF_STL_H
25 #define TF_STL_H
26 
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 <boost/call_traits.hpp>
39 
40 #include <algorithm>
41 #include <iterator>
42 #include <map>
43 #include <set>
44 #include <utility>
45 
46 PXR_NAMESPACE_OPEN_SCOPE
47 
48 // Helper for TfMapLookup(). Uses std::map API to get a value by key.
49 template <class T>
50 struct Tf_MapLookupHelper {
51  typedef T Container;
52 
53  template <class Key, class Result>
54  static bool Lookup(Container const& map, Key const &key, Result* valuePtr)
55  {
56  typename Container::const_iterator i = map.find(key);
57  if (i == map.end()) {
58  return false;
59  }
60  else {
61  *valuePtr = i->second;
62  return true;
63  }
64  }
65 };
66 
87 template <class Container, class Key, class Result>
88 bool TfMapLookup(Container const &map, Key const &key, Result* valuePtr)
89 {
90  return Tf_MapLookupHelper<Container>::Lookup(map, key, valuePtr);
91 }
92 
113 template <class Container, class Key, class Result>
114 const Result TfMapLookupByValue(Container const &map,
115  Key const &key, const Result &defaultValue)
116 {
117  typename Container::const_iterator i = map.find(key);
118  if (i == map.end()) {
119  return defaultValue;
120  } else {
121  return i->second;
122  }
123 }
124 
141 template <class Container, class Key>
142 typename Container::mapped_type *
143 TfMapLookupPtr(Container &map, Key const &key)
144 {
145  typename Container::iterator i = map.find(key);
146  return (i != map.end()) ? &(i->second) : NULL;
147 }
148 
149 template <class Container, class Key>
150 typename Container::mapped_type const *
151 TfMapLookupPtr(Container const &map, Key const &key)
152 {
153  typename Container::const_iterator i = map.find(key);
154  return (i != map.end()) ? &(i->second) : NULL;
155 }
156 
165 template <typename T>
166 inline std::pair<T,T>
167 TfOrderedPair(T a, T b) {
168  return (a < b) ? std::pair<T,T>(a,b) : std::pair<T,T>(b,a);
169 }
170 
188 template <class T>
189 inline void TfReset(T &obj) {
190  T().swap(obj);
191 }
192 
193 TF_API size_t Tf_GetEmptyHashMapBucketCount();
194 
196 template <class Key, class Value, class Hash, class Equal, class Alloc>
197 inline void TfReset(TfHashMap<Key, Value, Hash, Equal, Alloc> &hash){
198  // If the implementation of the hash map allocates buckets when
199  // constructed asking for zero then only swap a constructed object
200  // if \p hash has more than that many buckets already, otherwise
201  // we just clear(). Note that this assumes that the number of
202  // buckets does not depend on the template parameter types which
203  // is reasonable.
204  static size_t emptyCount = Tf_GetEmptyHashMapBucketCount();
205 
206  if (hash.bucket_count() > emptyCount)
207  TfHashMap<Key, Value, Hash, Equal, Alloc>(0).swap(hash);
208  else if (!hash.empty())
209  hash.clear();
210 }
211 
212 TF_API size_t Tf_GetEmptyHashSetBucketCount();
213 
215 template <class Value, class Hash, class Equal, class Alloc>
216 inline void TfReset(TfHashSet<Value, Hash, Equal, Alloc> &hash) {
217  static size_t emptyCount = Tf_GetEmptyHashSetBucketCount();
218 
219  // See comment above about issues with TfHashSet(0).
220  if (hash.bucket_count() > emptyCount)
221  TfHashSet<Value, Hash, Equal, Alloc>(0).swap(hash);
222  else if (!hash.empty())
223  hash.clear();
224 }
225 
226 
231 template <class T>
232 inline typename boost::call_traits<T>::param_type
233 TfIdentity(typename boost::call_traits<T>::param_type arg) {
234  return arg;
235 }
236 
248 template <class InputIterator1, class InputIterator2, class OutputIterator>
249 void
250 TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1,
251  InputIterator2 first2, InputIterator2 last2,
252  OutputIterator result)
253 {
254  typedef std::multiset<typename InputIterator2::value_type> SetType;
255  SetType set2(first2, last2);
256 
257  // Walk [first1, last1). If the element is in set2, skip it, and remove one
258  // of those elements from set2, otherwise output it.
259  for (InputIterator1 i = first1; i != last1; ++i) {
260  typename SetType::iterator j = set2.find(*i);
261  if (j != set2.end())
262  set2.erase(j);
263  else
264  *result++ = *i;
265  }
266 }
267 
279 template <class BackInsertionSequence,
280  class InputIterator1, class InputIterator2>
281 BackInsertionSequence
282 TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1,
283  InputIterator2 first2, InputIterator2 last2)
284 {
285  BackInsertionSequence result;
286  TfOrderedSetDifference(first1, last1, first2, last2,
287  std::back_inserter(result));
288  return result;
289 }
290 
302 template <class InputIterator1, class InputIterator2, class OutputIterator>
303 void
304 TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1,
305  InputIterator2 first2, InputIterator2 last2,
306  OutputIterator result)
307 {
308  typedef std::set<typename InputIterator1::value_type> Set1Type;
309  typedef std::set<typename InputIterator2::value_type> Set2Type;
310 
311  Set1Type set1;
312  Set2Type set2(first2, last2);
313 
314  // Walk [first1, last1). If the element is in set1, skip it. Else insert
315  // it into set1, and if the element is not in set2, output it.
316  for (InputIterator1 i = first1; i != last1; ++i)
317  if (set1.insert(*i).second && !set2.count(*i))
318  *result++ = *i;
319 }
320 
332 template <class BackInsertionSequence,
333  class InputIterator1, class InputIterator2>
334 BackInsertionSequence
336  InputIterator1 last1,
337  InputIterator2 first2,
338  InputIterator2 last2)
339 {
340  BackInsertionSequence result;
341  TfOrderedUniquingSetDifference(first1, last1, first2, last2,
342  std::back_inserter(result));
343  return result;
344 }
345 
354 template <class ForwardIterator, class Predicate>
355 static inline ForwardIterator
356 TfFindBoundary(ForwardIterator first, ForwardIterator last,
357  Predicate const &pred)
358 {
359  size_t len = std::distance(first, last);
360  size_t half;
361  ForwardIterator middle;
362 
363  while (len > 0) {
364  half = len >> 1;
365  middle = first;
366  std::advance(middle, half);
367  if (pred(*middle)) {
368  first = middle;
369  ++first;
370  len = len - half - 1;
371  }
372  else
373  len = half;
374  }
375  return first;
376 }
377 
390 template <size_t N>
391 class TfGet
392 {
393 public:
394  template <class PairOrTuple>
395  using return_type = typename std::tuple_element<N, PairOrTuple>::type;
396 
397  template <class PairOrTuple>
398  constexpr return_type<PairOrTuple>& operator()(PairOrTuple& p) const
399  {
400  return std::get<N>(p);
401  }
402 
403  template <class PairOrTuple>
404  constexpr const return_type<PairOrTuple>& operator()(
405  const PairOrTuple& p) const
406  {
407  return std::get<N>(p);
408  }
409 
410  template <class PairOrTuple>
411  constexpr return_type<PairOrTuple>&& operator()(PairOrTuple&& p) const
412  {
413  return std::get<N>(std::move(p));
414  }
415 };
416 
417 PXR_NAMESPACE_CLOSE_SCOPE
418 
419 #endif // TF_STL_H
void TfReset(T &obj)
Reset obj to be an empty, space-optimized object.
Definition: stl.h:189
void TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Produce a sequence consisting of the set difference of [first1, last1) and [first2, last2), while maintaining the relative order of the first sequence.
Definition: stl.h:250
std::pair< T, T > TfOrderedPair(T a, T b)
Return an std::pair in sorted order.
Definition: stl.h:167
BackInsertionSequence TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Produce a sequence consisting of the set difference of [first1, last1) and [first2, last2), while maintaining the relative order of the first sequence.
Definition: stl.h:282
BackInsertionSequence TfOrderedUniquingSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Produce a sequence consisting of the set difference of the unique elements in [first1, last1) and [first2, last2), while maintaining the relative order of the first sequence.
Definition: stl.h:335
void TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
Produce a sequence consisting of the set difference of the unique elements in [first1, last1) and [first2, last2), while maintaining the relative order of the first sequence.
Definition: stl.h:304
const Result TfMapLookupByValue(Container const &map, Key const &key, const Result &defaultValue)
Checks if an item exists in a map or a TfHashMap.
Definition: stl.h:114
bool TfMapLookup(Container const &map, Key const &key, Result *valuePtr)
Checks if an item exists in a map or a TfHashMap.
Definition: stl.h:88
Function object for retrieving the N&#39;th element of a std::pair or std::tuple.
Definition: stl.h:391
boost::call_traits< T >::param_type TfIdentity(typename boost::call_traits< T >::param_type arg)
An unary function that represents the identity function; it takes a single argument arg...
Definition: stl.h:233
Container::mapped_type * TfMapLookupPtr(Container &map, Key const &key)
Checks if an item exists in a map or TfHashMap, without copying it.
Definition: stl.h:143