Loading...
Searching...
No Matches
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
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"
37
38#include <algorithm>
39#include <iterator>
40#include <map>
41#include <set>
42#include <utility>
43
44PXR_NAMESPACE_OPEN_SCOPE
45
46// Helper for TfMapLookup(). Uses std::map API to get a value by key.
47template <class T>
48struct Tf_MapLookupHelper {
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
85template <class Container, class Key, class Result>
86bool TfMapLookup(Container const &map, Key const &key, Result* valuePtr)
87{
88 return Tf_MapLookupHelper<Container>::Lookup(map, key, valuePtr);
89}
90
111template <class Container, class Key, class Result>
112const 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
139template <class Container, class Key>
140typename Container::mapped_type *
141TfMapLookupPtr(Container &map, Key const &key)
142{
143 typename Container::iterator i = map.find(key);
144 return (i != map.end()) ? &(i->second) : NULL;
145}
146
147template <class Container, class Key>
148typename Container::mapped_type const *
149TfMapLookupPtr(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
163template <typename T>
164inline std::pair<T,T>
165TfOrderedPair(T a, T b) {
166 return (a < b) ? std::pair<T,T>(a,b) : std::pair<T,T>(b,a);
167}
168
186template <class T>
187inline void TfReset(T &obj) {
188 T().swap(obj);
189}
190
191TF_API size_t Tf_GetEmptyHashMapBucketCount();
192
194template <class Key, class Value, class Hash, class Equal, class Alloc>
195inline void TfReset(TfHashMap<Key, Value, Hash, Equal, Alloc> &hash){
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)
205 TfHashMap<Key, Value, Hash, Equal, Alloc>(0).swap(hash);
206 else if (!hash.empty())
207 hash.clear();
208}
209
210TF_API size_t Tf_GetEmptyHashSetBucketCount();
211
213template <class Value, class Hash, class Equal, class Alloc>
214inline void TfReset(TfHashSet<Value, Hash, Equal, Alloc> &hash) {
215 static size_t emptyCount = Tf_GetEmptyHashSetBucketCount();
216
217 // See comment above about issues with TfHashSet(0).
218 if (hash.bucket_count() > emptyCount)
219 TfHashSet<Value, Hash, Equal, Alloc>(0).swap(hash);
220 else if (!hash.empty())
221 hash.clear();
222}
223
235template <class InputIterator1, class InputIterator2, class OutputIterator>
236void
237TfOrderedSetDifference(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
266template <class BackInsertionSequence,
267 class InputIterator1, class InputIterator2>
268BackInsertionSequence
269TfOrderedSetDifferenceToContainer(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
289template <class InputIterator1, class InputIterator2, class OutputIterator>
290void
291TfOrderedUniquingSetDifference(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
319template <class BackInsertionSequence,
320 class InputIterator1, class InputIterator2>
321BackInsertionSequence
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
341template <class ForwardIterator, class Predicate>
342static inline ForwardIterator
343TfFindBoundary(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
377template <size_t N>
378class TfGet
379{
380public:
381 template <class PairOrTuple>
382 using return_type = typename std::tuple_element<N, PairOrTuple>::type;
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>
391 constexpr const return_type<PairOrTuple>& operator()(
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
404PXR_NAMESPACE_CLOSE_SCOPE
405
406#endif // PXR_BASE_TF_STL_H
A simple iterator adapter for STL containers.
Function object for retrieving the N'th element of a std::pair or std::tuple.
Definition: stl.h:379
std::pair< T, T > TfOrderedPair(T a, T b)
Return an std::pair in sorted order.
Definition: stl.h:165
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:141
bool TfMapLookup(Container const &map, Key const &key, Result *valuePtr)
Checks if an item exists in a map or a TfHashMap.
Definition: stl.h:86
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:112
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,...
Definition: stl.h:237
BackInsertionSequence TfOrderedUniquingSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Produce a sequence consisting of the set difference of the unique elements in [first1,...
Definition: stl.h:322
void TfReset(T &obj)
Reset obj to be an empty, space-optimized object.
Definition: stl.h:187
BackInsertionSequence TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Produce a sequence consisting of the set difference of [first1, last1) and [first2,...
Definition: stl.h:269
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,...
Definition: stl.h:291
A file containing basic constants and definitions.