2
// Copyright 2016 Pixar
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:
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.
14
// You may obtain a copy of the Apache License at
16
// http://www.apache.org/licenses/LICENSE-2.0
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.
29
* \ingroup group_tf_Stl
32
#include "pxr/base/tf/tf.h"
33
#include "pxr/base/tf/iterator.h"
35
#include <boost/call_traits.hpp>
36
#include "pxr/base/tf/hashmap.h"
37
#include "pxr/base/tf/hashset.h"
44
// Helper for TfMapLookup(). Uses std::map API to get a value by key.
46
struct Tf_MapLookupHelper {
49
template <class Key, class Result>
50
static bool Lookup(Container const& map, Key const &key, Result* valuePtr)
52
typename Container::const_iterator i = map.find(key);
57
*valuePtr = i->second;
64
* \brief Checks if an item exists in a \c map or a \c TfHashMap.
65
* \ingroup group_tf_Stl
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.
73
* TfHashMap<string, int, TfHash> m = ...;
77
* if (TfMapLookup(m, "someKey", &value))
78
* printf("Value found: %d\n", value);
80
* printf("Value not found\n");
85
template <class Container, class Key, class Result>
86
bool TfMapLookup(Container const &map, Key const &key, Result* valuePtr)
88
return Tf_MapLookupHelper<Container>::Lookup(map, key, valuePtr);
92
* \brief Checks if an item exists in a \c map or a \c TfHashMap.
93
* \ingroup group_tf_Stl
95
* If \p key exists in \p map, then this function returns the value index
96
* by \p key. Otherwise, \p defaultValue is returned. Note that the result
97
* is returned by value, so this is best used for types that are quick to copy.
101
* TfHashMap<string, int, TfHash> m;
104
* int value = TfMapLookup(m, "someKey", -1);
105
* TF_AXIOM(value == -1);
107
* int value = TfMapLookup(m, "foo", -1);
108
* TF_AXIOM(value == 1);
112
template <class Container, class Key, class Result>
113
const Result TfMapLookupByValue(Container const &map,
114
Key const &key, const Result &defaultValue)
116
typename Container::const_iterator i = map.find(key);
117
if (i == map.end()) {
126
* \brief Checks if an item exists in a \c map or \c TfHashMap, without copying it.
127
* \ingroup group_tf_Stl
129
* If \p key exists in the \p map, then this function returns a pointer to the
130
* value indexed by \p key. Otherwise, NULL is returned.
134
* TfHashMap<string, BigData, TfHash> m = ...;
136
* if (BigData* bigPtr = TfMapLookupPtr(m, "someKey"))
137
* bigPtr->ModifyStuff();
139
* printf("Value not found\n");
143
template <class Container, class Key>
144
typename Container::mapped_type *
145
TfMapLookupPtr(Container &map, Key const &key)
147
typename Container::iterator i = map.find(key);
148
return (i != map.end()) ? &(i->second) : NULL;
151
template <class Container, class Key>
152
typename Container::mapped_type const *
153
TfMapLookupPtr(Container const &map, Key const &key)
155
typename Container::const_iterator i = map.find(key);
156
return (i != map.end()) ? &(i->second) : NULL;
161
* \brief Return an \c std::pair in sorted order.
162
* \ingroup group_tf_Stl
164
* This call is a useful helper for maps whose key is an unordered pair of
165
* elements. One can either define a new data type such that (a,b) is deemed
166
* equivalent to (b,a), or more simply, adopt the convention that a key is
167
* always written (a,b) with a < b.
169
template <typename T>
170
inline std::pair<T,T>
171
TfOrderedPair(T a, T b) {
172
return (a < b) ? std::pair<T,T>(a,b) : std::pair<T,T>(b,a);
177
* \brief Reset \a obj to be an empty, space-optimized object.
179
* This can be used to clear c++ containers and reclaim their memory. For
180
* instance, std::vector::clear() will not reclaim any memory, even if the
181
* vector previously had a large number of elements. Often, this is what you
182
* want because the vector is later filled again. But sometimes you want to
183
* reclaim the memory, and this function will do that.
185
* As another example, gcc's hash_map and hash_set do not clear their bucket
186
* lists when they themselves are cleared. This can lead to poor performance
187
* due to ever-growing bucket lists for hashes that are repeatedly filled,
188
* cleared, and filled again. TfReset will avoid this by effectively clearing
191
* This function requires that the expression T().swap(obj) where obj is of type
192
* T& be valid. This is true for many classes, including the standard
196
inline void TfReset(T &obj) {
201
* \brief Specialize for TfHashMap to make minimally sized hashes.
203
template <class Key, class Value, class Hash, class Equal, class Alloc>
204
inline void TfReset(TfHashMap<Key, Value, Hash, Equal, Alloc> &hash){
205
// If the implementation of the hash map allocates buckets when
206
// constructed asking for zero then only swap a constructed object
207
// if \p hash has more than that many buckets already, otherwise
208
// we just clear(). Note that this assumes that the number of
209
// buckets does not depend on the template parameter types which
211
extern size_t Tf_GetEmptyHashMapBucketCount();
212
static size_t emptyCount = Tf_GetEmptyHashMapBucketCount();
214
if (hash.bucket_count() > emptyCount)
215
TfHashMap<Key, Value, Hash, Equal, Alloc>(0).swap(hash);
216
else if (not hash.empty())
221
* \brief Specialize for TfHashSet to make minimally sized hashes.
223
template <class Value, class Hash, class Equal, class Alloc>
224
inline void TfReset(TfHashSet<Value, Hash, Equal, Alloc> &hash) {
225
extern size_t Tf_GetEmptyHashSetBucketCount();
226
static size_t emptyCount = Tf_GetEmptyHashSetBucketCount();
228
// See comment above about issues with TfHashSet(0).
229
if (hash.bucket_count() > emptyCount)
230
TfHashSet<Value, Hash, Equal, Alloc>(0).swap(hash);
231
else if (not hash.empty())
237
* \brief An unary function that represents the identity function; it takes
238
* a single argument \a arg, and returns \a arg.
240
* This is similar to the sgi extension std::identity<T>.
243
inline typename boost::call_traits<T>::param_type
244
TfIdentity(typename boost::call_traits<T>::param_type arg) {
252
* \brief Produce a sequence consisting of the set difference of [\a first1,
253
* \a last1) and [\a first2, \a last2), while maintaining the relative order of
254
* the first sequence. No particular order is required for either range, but
255
* elements must have a strict weak order provided by operator<.
257
* If an element appears multiple times in either the first or second sequence,
258
* the number of occurrences in the output is the difference between the first
259
* sequence and the second (or zero if there are more occurrences in the second
260
* sequence). For example, if the first sequence is (1, 3, 3, 1) and the second
261
* sequence is (2, 3, 2), the result will be (1, 3, 1).
263
template <class InputIterator1, class InputIterator2, class OutputIterator>
265
TfOrderedSetDifference(InputIterator1 first1, InputIterator1 last1,
266
InputIterator2 first2, InputIterator2 last2,
267
OutputIterator result)
269
typedef std::multiset<typename InputIterator2::value_type> SetType;
270
SetType set2(first2, last2);
272
// Walk [first1, last1). If the element is in set2, skip it, and remove one
273
// of those elements from set2, otherwise output it.
274
for (InputIterator1 i = first1; i != last1; ++i) {
275
typename SetType::iterator j = set2.find(*i);
284
* \brief Produce a sequence consisting of the set difference of [\a first1,
285
* \a last1) and [\a first2, \a last2), while maintaining the relative order of
286
* the first sequence. No particular order is required for either range, but
287
* elements must have a strict weak order provided by operator<.
289
* If an element appears multiple times in either the first or second sequence,
290
* the number of occurrences in the output is the difference between the first
291
* sequence and the second (or zero if there are more occurrences in the second
292
* sequence). For example, if the first sequence is (1, 3, 3, 1) and the second
293
* sequence is (2, 3, 2), the result will be (1, 3, 1).
295
template <class BackInsertionSequence,
296
class InputIterator1, class InputIterator2>
297
BackInsertionSequence
298
TfOrderedSetDifferenceToContainer(InputIterator1 first1, InputIterator1 last1,
299
InputIterator2 first2, InputIterator2 last2)
301
BackInsertionSequence result;
302
TfOrderedSetDifference(first1, last1, first2, last2,
303
std::back_inserter(result));
309
* \brief Produce a sequence consisting of the set difference of the unique
310
* elements in [\a first1, \a last1) and [\a first2, \a last2), while
311
* maintaining the relative order of the first sequence. No particular order is
312
* required for either range, but elements must have a strict weak order
313
* provided by operator<.
315
* If an element appears multiple times in the first sequence, it appears either
316
* zero or one times in the output. It appears zero times if it appears in the
317
* second sequence, and one time if it does not. For example, if the first
318
* sequence is (1, 3, 3, 1) and the second sequence is (2, 3, 2), the result
321
template <class InputIterator1, class InputIterator2, class OutputIterator>
323
TfOrderedUniquingSetDifference(InputIterator1 first1, InputIterator1 last1,
324
InputIterator2 first2, InputIterator2 last2,
325
OutputIterator result)
327
typedef std::set<typename InputIterator1::value_type> Set1Type;
328
typedef std::set<typename InputIterator2::value_type> Set2Type;
331
Set2Type set2(first2, last2);
333
// Walk [first1, last1). If the element is in set1, skip it. Else insert
334
// it into set1, and if the element is not in set2, output it.
335
for (InputIterator1 i = first1; i != last1; ++i)
336
if (set1.insert(*i).second and not set2.count(*i))
343
* \brief Produce a sequence consisting of the set difference of the unique
344
* elements in [\a first1, \a last1) and [\a first2, \a last2), while
345
* maintaining the relative order of the first sequence. No particular order is
346
* required for either range, but elements must have a strict weak order
347
* provided by operator<.
349
* If an element appears multiple times in the first sequence, it appears either
350
* zero or one times in the output. It appears zero times if it appears in the
351
* second sequence, and one time if it does not. For example, if the first
352
* sequence is (1, 3, 3, 1) and the second sequence is (2, 3, 2), the result
355
template <class BackInsertionSequence,
356
class InputIterator1, class InputIterator2>
357
BackInsertionSequence
358
TfOrderedUniquingSetDifferenceToContainer(InputIterator1 first1,
359
InputIterator1 last1,
360
InputIterator2 first2,
361
InputIterator2 last2)
363
BackInsertionSequence result;
364
TfOrderedUniquingSetDifference(first1, last1, first2, last2,
365
std::back_inserter(result));
370
* \brief A version of binary search that finds the boundary in a partitioned
371
* sequence. The Predicate pred should return true for objects on the 'first'
372
* side (or left-hand) side of the boundary.
374
* More precisely, given a range [first, last) and a Predicate pred for which
375
* there is exactly one iterator called mid in that range such that pred(x) is
376
* true for every x in [first, mid) and false for every x in [mid, last), return
379
template <class ForwardIterator, class Predicate>
380
static inline ForwardIterator
381
TfFindBoundary(ForwardIterator first, ForwardIterator last,
382
Predicate const &pred)
384
size_t len = std::distance(first, last);
386
ForwardIterator middle;
391
std::advance(middle, half);
395
len = len - half - 1;
added
removed
USD/pxr/base/lib/tf/stl.h
