hash_set.h

// Copyright (c) Electronic Arts Inc. All rights reserved.
 
// This file is based on the TR1 (technical report 1) reference implementation
// of the unordered_set/unordered_map C++ classes as of about 4/2005. Most likely
// many or all C++ library vendors' implementations of this classes will be 
// based off of the reference version and so will look pretty similar to this
// file as well as other vendors' versions. 
 
 
#ifndef EASTL_HASH_SET_H
#define EASTL_HASH_SET_H
 
 
#include <EASTL/internal/config.h>
#include <EASTL/internal/hashtable.h>
#include <EASTL/functional.h>
#include <EASTL/utility.h>
 
#if defined(EA_PRAGMA_ONCE_SUPPORTED)
    #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result.
#endif
 
 
 
namespace eastl
{
 
    #ifndef EASTL_HASH_SET_DEFAULT_NAME
        #define EASTL_HASH_SET_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_set" // Unless the user overrides something, this is "EASTL hash_set".
    #endif
 
 
    #ifndef EASTL_HASH_MULTISET_DEFAULT_NAME
        #define EASTL_HASH_MULTISET_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_multiset" // Unless the user overrides something, this is "EASTL hash_multiset".
    #endif
 
 
    #ifndef EASTL_HASH_SET_DEFAULT_ALLOCATOR
        #define EASTL_HASH_SET_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_SET_DEFAULT_NAME)
    #endif
 
    #ifndef EASTL_HASH_MULTISET_DEFAULT_ALLOCATOR
        #define EASTL_HASH_MULTISET_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MULTISET_DEFAULT_NAME)
    #endif
 
 
 
    template <typename Value, typename Hash = eastl::hash<Value>, typename Predicate = eastl::equal_to<Value>, 
              typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false>
    class hash_set
        : public hashtable<Value, Value, Allocator, eastl::use_self<Value>, Predicate,
                           Hash, mod_range_hashing, default_ranged_hash, 
                           prime_rehash_policy, bCacheHashCode, false, true>
    {
    public:
        typedef hashtable<Value, Value, Allocator, eastl::use_self<Value>, Predicate, 
                          Hash, mod_range_hashing, default_ranged_hash,
                          prime_rehash_policy, bCacheHashCode, false, true>       base_type;
        typedef hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>       this_type;
        typedef typename base_type::size_type                                     size_type;
        typedef typename base_type::value_type                                    value_type;
        typedef typename base_type::allocator_type                                allocator_type;
        typedef typename base_type::node_type                                     node_type;
 
    public:
        explicit hash_set(const allocator_type& allocator = EASTL_HASH_SET_DEFAULT_ALLOCATOR)
            : base_type(0, Hash(), mod_range_hashing(), default_ranged_hash(), Predicate(), eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        explicit hash_set(size_type nBucketCount, const Hash& hashFunction = Hash(), const Predicate& predicate = Predicate(), 
                          const allocator_type& allocator = EASTL_HASH_SET_DEFAULT_ALLOCATOR)
            : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), predicate, eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        hash_set(const this_type& x)
          : base_type(x)
        {
        }
 
 
        hash_set(this_type&& x)
          : base_type(eastl::move(x))
        {
        }
 
 
        hash_set(this_type&& x, const allocator_type& allocator)
          : base_type(eastl::move(x), allocator)
        {
        }
 
 
        hash_set(std::initializer_list<value_type> ilist, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 
                   const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_SET_DEFAULT_ALLOCATOR)
            : base_type(ilist.begin(), ilist.end(), nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), predicate, eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        template <typename FowardIterator>
        hash_set(FowardIterator first, FowardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 
                 const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_SET_DEFAULT_ALLOCATOR)
            : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), predicate, eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        this_type& operator=(const this_type& x)
        {
            return static_cast<this_type&>(base_type::operator=(x));
        }
 
 
        this_type& operator=(std::initializer_list<value_type> ilist)
        {
            return static_cast<this_type&>(base_type::operator=(ilist));
        }
 
 
        this_type& operator=(this_type&& x)
        {
            return static_cast<this_type&>(base_type::operator=(eastl::move(x)));
        }
 
    }; // hash_set
 
    template <typename Value, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode, typename UserPredicate>
    void erase_if(eastl::hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>& c, UserPredicate predicate)
    {
        // Erases all elements that satisfy the predicate pred from the container.
        for (auto i = c.begin(), last = c.end(); i != last;)
        {
            if (predicate(*i))
            {
                i = c.erase(i);
            }
            else
            {
                ++i;
            }
        }
    }
 
 
    template <typename Value, typename Hash = eastl::hash<Value>, typename Predicate = eastl::equal_to<Value>, 
              typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false>
    class hash_multiset
        : public hashtable<Value, Value, Allocator, eastl::use_self<Value>, Predicate,
                           Hash, mod_range_hashing, default_ranged_hash,
                           prime_rehash_policy, bCacheHashCode, false, false>
    {
    public:
        typedef hashtable<Value, Value, Allocator, eastl::use_self<Value>, Predicate,
                          Hash, mod_range_hashing, default_ranged_hash,
                          prime_rehash_policy, bCacheHashCode, false, false>          base_type;
        typedef hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>      this_type;
        typedef typename base_type::size_type                                         size_type;
        typedef typename base_type::value_type                                        value_type;
        typedef typename base_type::allocator_type                                    allocator_type;
        typedef typename base_type::node_type                                         node_type;
 
    public:
        explicit hash_multiset(const allocator_type& allocator = EASTL_HASH_MULTISET_DEFAULT_ALLOCATOR)
            : base_type(0, Hash(), mod_range_hashing(), default_ranged_hash(), Predicate(), eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        explicit hash_multiset(size_type nBucketCount, const Hash& hashFunction = Hash(), 
                               const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTISET_DEFAULT_ALLOCATOR)
            : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), predicate, eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        hash_multiset(const this_type& x)
          : base_type(x)
        {
        }
 
 
        hash_multiset(this_type&& x)
          : base_type(eastl::move(x))
        {
        }
 
 
        hash_multiset(this_type&& x, const allocator_type& allocator)
          : base_type(eastl::move(x), allocator)
        {
        }
 
 
        hash_multiset(std::initializer_list<value_type> ilist, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 
                   const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTISET_DEFAULT_ALLOCATOR)
            : base_type(ilist.begin(), ilist.end(), nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), predicate, eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        template <typename FowardIterator>
        hash_multiset(FowardIterator first, FowardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(), 
                      const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTISET_DEFAULT_ALLOCATOR)
            : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(), predicate, eastl::use_self<Value>(), allocator)
        {
            // Empty
        }
 
 
        this_type& operator=(const this_type& x)
        {
            return static_cast<this_type&>(base_type::operator=(x));
        }
 
 
        this_type& operator=(std::initializer_list<value_type> ilist)
        {
            return static_cast<this_type&>(base_type::operator=(ilist));
        }
 
 
        this_type& operator=(this_type&& x)
        {
            return static_cast<this_type&>(base_type::operator=(eastl::move(x)));
        }
 
    }; // hash_multiset
 
    template <typename Value, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode, typename UserPredicate>
    void erase_if(eastl::hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>& c, UserPredicate predicate)
    {
        // Erases all elements that satisfy the predicate pred from the container.
        for (auto i = c.begin(), last = c.end(); i != last;)
        {
            if (predicate(*i))
            {
                i = c.erase(i);
            }
            else
            {
                ++i;
            }
        }
    }
 
 
 
    // global operators
 
    template <typename Value, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode>
    inline bool operator==(const hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>& a, 
                           const hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>& b)
    {
        typedef typename hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>::const_iterator const_iterator;
 
        // We implement branching with the assumption that the return value is usually false.
        if(a.size() != b.size())
            return false;
 
        // For set (with its unique keys), we need only test that each element in a can be found in b,
        // as there can be only one such pairing per element. multiset needs to do a something more elaborate.
        for(const_iterator ai = a.begin(), aiEnd = a.end(), biEnd = b.end(); ai != aiEnd; ++ai)
        {
            const_iterator bi = b.find(*ai);
 
            if((bi == biEnd) || !(*ai == *bi)) // We have to compare values in addition to making sure the lookups succeeded. This is because the lookup is done via the user-supplised Predicate
                return false;                  // which isn't strictly required to be identical to the Value operator==, though 99% of the time it will be so.  
        }
 
        return true;
    }
 
    template <typename Value, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode>
    inline bool operator!=(const hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>& a, 
                           const hash_set<Value, Hash, Predicate, Allocator, bCacheHashCode>& b)
    {
        return !(a == b);
    }
 
 
    template <typename Value, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode>
    inline bool operator==(const hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>& a, 
                           const hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>& b)
    {
        typedef typename hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>::const_iterator const_iterator;
        typedef typename eastl::iterator_traits<const_iterator>::difference_type difference_type;
 
        // We implement branching with the assumption that the return value is usually false.
        if(a.size() != b.size())
            return false;
 
        // We can't simply search for each element of a in b, as it may be that the bucket for 
        // two elements in a has those same two elements in b but in different order (which should 
        // still result in equality). Also it's possible that one bucket in a has two elements which 
        // both match a solitary element in the equivalent bucket in b (which shouldn't result in equality).
        eastl::pair<const_iterator, const_iterator> aRange;
        eastl::pair<const_iterator, const_iterator> bRange;
 
        for(const_iterator ai = a.begin(), aiEnd = a.end(); ai != aiEnd; ai = aRange.second) // For each element in a...
        {
            aRange = a.equal_range(*ai); // Get the range of elements in a that are equal to ai.
            bRange = b.equal_range(*ai); // Get the range of elements in b that are equal to ai.
 
            // We need to verify that aRange == bRange. First make sure the range sizes are equivalent...
            const difference_type aDistance = eastl::distance(aRange.first, aRange.second);
            const difference_type bDistance = eastl::distance(bRange.first, bRange.second);
 
            if(aDistance != bDistance)
                return false;
 
            // At this point, aDistance > 0 and aDistance == bDistance.
            // Implement a fast pathway for the case that there's just a single element.
            if(aDistance == 1)
            {
                if(!(*aRange.first == *bRange.first))   // We have to compare values in addition to making sure the distance (element count) was equal. This is because the lookup is done via the user-supplised Predicate
                    return false;                       // which isn't strictly required to be identical to the Value operator==, though 99% of the time it will be so. Ditto for the is_permutation usage below.
            }
            else
            {
                // Check to see if these aRange and bRange are any permutation of each other. 
                // This check gets slower as there are more elements in the range.
                if(!eastl::is_permutation(aRange.first, aRange.second, bRange.first))
                    return false;
            }
        }
 
        return true;
    }
 
    template <typename Value, typename Hash, typename Predicate, typename Allocator, bool bCacheHashCode>
    inline bool operator!=(const hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>& a, 
                           const hash_multiset<Value, Hash, Predicate, Allocator, bCacheHashCode>& b)
    {
        return !(a == b);
    }
 
} // namespace eastl
 
 
#endif // Header include guard