24 #ifndef PXR_BASE_TF_DENSE_HASH_SET_H
25 #define PXR_BASE_TF_DENSE_HASH_SET_H
30 #include "pxr/base/tf/hashmap.h"
35 #include <boost/compressed_pair.hpp>
36 #include <boost/iterator/iterator_facade.hpp>
37 #include <boost/utility.hpp>
39 PXR_NAMESPACE_OPEN_SCOPE
55 class EqualElement = std::equal_to<Element>,
56 unsigned Threshold = 128
62 typedef Element value_type;
69 typedef std::vector<Element> _Vector;
72 typedef TfHashMap<Element, size_t, HashFn, EqualElement> _HashMap;
81 typedef typename _Vector::const_iterator
iterator;
94 const HashFn &hashFn = HashFn(),
95 const EqualElement &equalElement = EqualElement())
98 _equ() = equalElement;
104 : _vectorHashFnEqualFn(rhs._vectorHashFnEqualFn) {
106 _h.reset(
new _HashMap(*rhs._h));
116 template <
class Iterator>
124 insert(l.begin(), l.end());
145 insert(l.begin(), l.end());
160 if (!rhs.
count(*iter))
168 return !(*
this == rhs);
181 _vectorHashFnEqualFn.swap(rhs._vectorHashFnEqualFn);
188 return _vec().empty();
194 return _vec().size();
200 return _vec().begin();
214 typename _HashMap::const_iterator iter = _h->find(k);
215 if (iter == _h->end())
218 return _vec().begin() + iter->second;
221 typename _Vector::const_iterator iter,
end = _vec().end();
223 for(iter = _vec().
begin(); iter !=
end; ++iter)
224 if (_equ()(*iter, k))
232 size_t count(
const Element &k)
const {
246 std::pair<typename _HashMap::iterator, bool> res =
247 _h->insert(std::make_pair(v,
size()));
262 _CreateTableIfNeeded();
270 template<
class IteratorType>
271 void insert(IteratorType i0, IteratorType i1) {
276 if (
size() + std::distance(i0, i1) >= Threshold)
280 for (IteratorType iter = i0; iter != i1; ++iter)
287 template <
class Iterator>
291 _vec().assign(begin, end);
292 _CreateTableIfNeeded();
320 if (iter != std::prev(
end())) {
326 swap(*const_cast<Element *>(&(*iter)), _vec().back());
330 (*_h)[*iter] = iter - _vec().begin();
342 _h->erase(iter->first);
348 for(; vremain != _vec().end(); ++vremain)
349 (*_h)[*vremain] = vremain - _vec().begin();
358 _vec().shrink_to_fit();
366 if (sz < Threshold) {
373 _h.reset(
new _HashMap(sz, _hash(), _equ()));
374 for(
size_t i=0; i<sz; ++i)
375 (*_h)[_vec()[i]] = i;
383 return _vec()[index];
392 return _vectorHashFnEqualFn.first().first();
397 return _vectorHashFnEqualFn.first().second();
401 EqualElement &_equ() {
402 return _vectorHashFnEqualFn.second();
406 const _Vector &_vec()
const {
407 return _vectorHashFnEqualFn.first().first();
411 const HashFn &_hash()
const {
412 return _vectorHashFnEqualFn.first().second();
416 const EqualElement &_equ()
const {
417 return _vectorHashFnEqualFn.second();
421 inline void _CreateTableIfNeeded() {
422 if (
size() >= Threshold) {
429 inline void _CreateTable() {
431 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
432 for(
size_t i=0; i <
size(); ++i)
433 (*_h)[_vec()[i]] = i;
442 boost::compressed_pair<
443 boost::compressed_pair<_Vector, HashFn>,
445 _VectorHashFnEqualFn;
447 _VectorHashFnEqualFn _vectorHashFnEqualFn;
450 std::unique_ptr<_HashMap> _h;
453 PXR_NAMESPACE_CLOSE_SCOPE
455 #endif // PXR_BASE_TF_DENSE_HASH_SET_H
_Vector::const_iterator const_iterator
A const_iterator type for this set.
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
TfDenseHashSet(const HashFn &hashFn=HashFn(), const EqualElement &equalElement=EqualElement())
Ctor.
std::pair< const_iterator, bool > insert_result
Return type for insert() method.
size_t size() const
Returns the size of the set.
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the set.
size_t count(const Element &k) const
Returns the number of elements with key k.
const_iterator find(const Element &k) const
Finds the element with key k.
TfDenseHashSet & operator=(const TfDenseHashSet &rhs)
Copy assignment operator.
insert_result insert(const value_type &v)
Returns a pair of <iterator, bool> where iterator points to the element in the list and bool is true ...
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
#define TF_VERIFY(cond, format,...)
Checks a condition and reports an error if it evaluates false.
void swap(TfDenseHashSet &rhs)
Swaps the contents of two sets.
void erase(const iterator &i0, const iterator &i1)
Erases a range from the set.
size_t erase(const Element &k)
Erase element with key k.
TfDenseHashSet & operator=(std::initializer_list< Element > l)
Assignment from an initializer_list.
A path value used to locate objects in layers or scenegraphs.
TfDenseHashSet(std::initializer_list< Element > l)
Construct from an initializer_list.
_Vector::const_iterator iterator
An iterator type for this set.
const_iterator end() const
Returns an const_iterator pointing to the end of the set.
void shrink_to_fit()
Optimize storage space.
TfDenseHashSet(Iterator begin, Iterator end)
Construct from range.
TfDenseHashSet(const TfDenseHashSet &rhs)
Copy Ctor.
const Element & operator[](size_t index) const
Index into set via index.
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash set.
void clear()
Erases all of the elements.
bool empty() const
true if the set's size is 0.
This is a space efficient container that mimics the TfHashSet API that uses a vector for storage when...
bool operator==(const TfDenseHashSet &rhs) const
Equality operator.
void erase(const iterator &iter)
Erases element pointed to by iter.