sethash.h

Go to the documentation of this file.

// Evo C++ Library
/* Copyright 2019 Justin Crowell
Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
*/

#pragma once
#ifndef INCL_evo_sethash_h
#define INCL_evo_sethash_h

#include "set.h"
#include "array.h"
#include "ptrlist.h"
#include "impl/hash.h"

namespace evo {


template<class TKey, class THash=CompareHash<TKey>, class TSize=SizeT>
class SetHash : public Set<TKey,TSize> {
protected:
    using Set<TKey,TSize>::size_;

public:
    EVO_CONTAINER_TYPE;
#if defined(_MSC_VER) || defined(EVO_OLDCC) // avoid errors with older compilers and MSVC
    typedef Set<TKey,TSize> SetBaseType;                        
    typedef typename SetBaseType::Size Size;
    typedef typename SetBaseType::Key Key;
    typedef typename SetBaseType::Value Value;
    typedef typename SetBaseType::Item Item;
    typedef typename SetBaseType::IterKey IterKey;
    typedef typename SetBaseType::IterItem IterItem;
#else
    using typename Set<TKey,TSize>::SetBaseType;
    using typename Set<TKey,TSize>::Size;
    using typename Set<TKey,TSize>::Key;
    using typename Set<TKey,TSize>::Value;
    using typename Set<TKey,TSize>::Item;
    using typename Set<TKey,TSize>::IterKey;
    using typename Set<TKey,TSize>::IterItem;
#endif
    typedef SetHash<TKey,THash,TSize> ThisType;                 
    typedef THash Hash;                                         

    typedef typename IteratorBi<ThisType>::Const Iter;          
    typedef IteratorBi<ThisType>                 IterM;         

    SetHash()
        { }

    SetHash(const SetBaseType& src) {
        for (typename SetBaseType::Iter iter(src); iter; ++iter)
            add(*iter);
    }

    SetHash(const ThisType& src)
        { set(src); }

#if defined(EVO_CPP11)

    SetHash(std::initializer_list<Value> init) : SetHash() {
        assert( init.size() < IntegerT<Size>::MAX );
        capacitymin((Size)init.size());
        for (const auto& val : init)
            add(val);
    }

    SetHash(ThisType&& src) : buckets_(std::move(src.buckets_)), data_(std::move(src.data_)) {
        SetBaseType::size_ = src.SetBaseType::size_;
        src.SetBaseType::size_ = 0;
    }

    ThisType& operator=(ThisType&& src) {
        buckets_ = std::move(src.buckets_);
        data_ = std::move(src.data_);
        SetBaseType::size_ = src.SetBaseType::size_;
        src.SetBaseType::size_ = 0;
        return *this;
    }
#endif

    const ThisType& asconst() const {
        return *this;
    }

    // SET

    ThisType& operator=(const SetBaseType& src)
        { set(src); return *this; }

    ThisType& operator=(const ThisType& src)
        { set(src); return *this; }

    ThisType& set()
        { buckets_.set(); size_ = 0; return *this; }

    ThisType& set(const SetBaseType& src) {
        clear();
        for (typename SetBaseType::Iter iter(src); iter; ++iter)
            add(*iter);
        return *this;
    }

    ThisType& set(const ThisType& src) {
        buckets_.set(src.buckets_);
        data_ = src.data_;
        size_ = src.size_;
        return *this;
    }

    ThisType& setempty()
        { buckets_.setempty(); size_ = 0; return *this; }

    ThisType& clear()
        { buckets_.clear(); size_ = 0; return *this; }

    // INFO

    bool null() const
        { return buckets_.null(); }

    bool shared() const
        { return buckets_.shared(); }

    Size capacity() const
        { return buckets_.size(); }

    bool ordered() const
        { return false; }

    // COMPARE

    const Hash& get_compare() const
        { return data_; }

    Hash& get_compare()
        { return data_; }

    using SetBaseType::operator==;
    using SetBaseType::operator!=;

    bool operator==(const ThisType& set) const {
        if (this == &set)
            return true;
        if (buckets_.size() == set.buckets_.size())
            return (buckets_ == set.buckets_);
        return SetBaseType::operator==(set);
    }

    bool operator!=(const ThisType& set) const
        { return !(*this == set); }

    // FIND

    Iter cbegin() const
        { return Iter(*this); }

    Iter cend() const
        { return Iter(); }

    IterM begin()
        { return IterM(*this); }

    Iter begin() const
        { return Iter(*this); }

    IterM end()
        { return IterM(); }

    Iter end() const
        { return Iter(); }

    bool contains(const Value& value) const
        { return (search(value) != NULL); }

    Iter iter(const Value& value) const {
        if (size_ > 0) {
            IterKey iterkey( data_.hash(value) & data_.sizemask );
            const Bucket* bucket = buckets_.item(iterkey.a);
            if (bucket != NULL) {
                if (data_(bucket->first, value) == 0) {
                    return Iter(*this, iterkey, (IterItem*)&bucket->first);
                } else {
                    const IterItem* item = (IterItem*)bucket->search(iterkey.b, value, data_);
                    if (item != NULL) {
                        ++iterkey.b;
                        return Iter(*this, iterkey, item);
                    }
                }
            }
        }
        return Iter(*this, iterEND);
    }

    IterM iterM(const Value& value) {
        if (size_ > 0) {
            IterKey iterkey( data_.hash(value) & data_.sizemask );
            Bucket* bucket = buckets_.itemM(iterkey.a);
            if (bucket != NULL) {
                if (data_(bucket->first, value) == 0) {
                    return IterM(*this, iterkey, (IterItem*)&bucket->first);
                } else {
                    IterItem* item = (IterItem*)bucket->search(iterkey.b, value, data_);
                    if (item != NULL) {
                        ++iterkey.b;
                        return IterM(*this, iterkey, item);
                    }
                }
            }
        }
        return IterM(*this, iterEND);
    }

    Value& get(const Value& value, bool* created=NULL) {
        if (size_ == 0 || data_.threshold == 0)
            // Empty, use init size
            rehash(SIZE_INIT);
        else if (size_ >= data_.threshold)
            // Reached size threshold, time to grow
            rehash(buckets_.size() << 1);

        // Get item, create if needed
        bool created_item;
        Value* item;
        Bucket* bucket = buckets_.getitem((data_.hash(value) & data_.sizemask), &created_item);
        if (created_item) {
            ++size_;
            item = &bucket->first;
            *item = value;
        } else if (data_(bucket->first, value) == 0) {
            item = &bucket->first;
        } else {
            Size index;
            item = (Value*)bucket->search(index, value, data_);
            if (item == NULL) {
                created_item = true;
                ++size_;
                item = (Value*)&(bucket->others[bucket->others.insert(index, value)]);
            }
        }
        if (created != NULL)
            *created = created_item;
        return *item;
    }

    // INFO_SET

    ThisType& unshare()
        { buckets_.unshare(); return *this; }

    ThisType& capacity(Size size) {
        const Size cursize = buckets_.size();

        if (size != cursize) {
            // Find new size (must be power of 2)
            Size newsize = SIZE_INIT;
            while (newsize < size)  newsize <<= 1;
            while (newsize < size_) newsize <<= 1;

            if (newsize != cursize)
                // Rehash with new size
                rehash(newsize);
        }
        return *this;
    }

    ThisType& capacitymin(Size min) {
        if (min > buckets_.size())
            capacity(min);
        return *this;
    }

    ThisType& reserve(Size size)
        { return capacitymin(size_ + size); }

    // ADD

    Value& add(const Value& value, bool update=false) {
        bool created_val;
        Value& upditem = get(value, &created_val);
        if (!created_val && update)
            upditem = value;
        return upditem;
    }

    // REMOVE

    bool remove(const Value& value) {
        bool result;
        Size bucket_index = data_.hash(value) & data_.sizemask;
        Bucket* bucket = buckets_.itemM(bucket_index);
        if (bucket != NULL) {
            Size index;
            if (data_(bucket->first, value) == 0) {
                if (bucket->others.size() > 0) {
                    // Remove "first" and replace with last item in "others"
                    Value* item1 = &bucket->first;
                    Value* item2 = bucket->others.data();
                    EVO_IMPL_CONTAINER_SWAP(item1, item2, Item);
                    bucket->others.remove(0);
                } else
                    // Remove bucket since "first" is only item
                    buckets_.remove(bucket_index);
                result = true;
                --size_;
            } else if (bucket->search(index, value, data_) != NULL) {
                // Remove from "others"
                bucket->others.remove(index);
                result = true;
                --size_;
            } else
                result = false;
        } else
            result = false;
        return result;
    }

    bool remove(typename SetBaseType::IterM& iter, IteratorDir dir=iterNONE)
        { return remove((IterM&)iter, dir); }

    bool remove(IterM& iter, IteratorDir dir=iterNONE) {
        if (iter && this == &iter.getParent()) {
            IterKey& iterkey = iter.getKey();
            assert( iterkey.a < buckets_.size() );
            Bucket* bucket = buckets_.itemM(iterkey.a);
            assert( bucket != NULL );
            if (iterkey.b > 0) {
                // Remove from "others"
                bucket->others.remove(iterkey.b-1);
            } else {
                if (bucket->others.size() > 0) {
                    // Remove "first" and replace with last item in "others"
                    Value* item1 = &bucket->first;
                    Value* item2 = bucket->others.data();
                    EVO_IMPL_CONTAINER_SWAP(item1, item2, Item);
                    bucket->others.remove(0);
                } else {
                    // Remove bucket since "first" is only item
                    buckets_.remove(iterkey.a);
                    bucket = NULL;
                }
            }

            // Update size and iterator
            if (--size_ > 0 && dir != iterNONE) {
                if (dir == iterRV) {
                    // Previous
                    if (iterkey.b > 0 && bucket != NULL) {
                        iter.setData( (IterItem*)(--iterkey.b == 0 ? &(bucket->first) : &(bucket->others[iterkey.b-1])) );
                    } else {
                        bucket = (Bucket*)buckets_.iterPrev(iterkey.a);
                        if (bucket != NULL) {
                            iterkey.b = bucket->others.size();
                            iter.setData( (IterItem*)(iterkey.b == 0 ? &bucket->first : &(bucket->others[iterkey.b-1])) );
                        } else
                            iter = iterEND;
                    }
                } else {
                    // Next
                    if (bucket != NULL && iterkey.b <= bucket->others.size()) {
                        iter.setData( (IterItem*)(iterkey.b == 0 ? &bucket->first : &(bucket->others[iterkey.b-1])) );
                    } else {
                        iterkey.b = 0;
                        if ((bucket=(Bucket*)buckets_.iterNext(iterkey.a)) != NULL)
                            iter.setData( (IterItem*)&bucket->first );
                        else
                            iter = iterEND;
                    }
                }
            } else
                iter = iterEND;
            return true;
        }
        return false;
    }

    // INTERNAL

    // Iterator support methods
    void iterInitMutable()
        { buckets_.unshare(); }
    const IterItem* iterFirst(IterKey& key) const {
        key.b = 0;
        if (size_ > 0)
            return (IterItem*)&(buckets_.iterFirst(key.a)->first);
        key.a = END;
        return NULL;
    }
    const IterItem* iterNext(IterKey& key) const {
        if (key.a != END) {
            const Bucket* bucket = buckets_.item(key.a);
            if (++key.b <= bucket->others.size())
                return (IterItem*)&(bucket->others[key.b-1]);
            key.b = 0;
            if ((bucket=buckets_.iterNext(key.a)) != NULL)
                return (IterItem*)&bucket->first;
        }
        return NULL;
    }
    const IterItem* iterLast(IterKey& key) const {
        if (size_ > 0) {
            const Bucket* bucket = buckets_.iterLast(key.a);
            assert( bucket != NULL );
            key.b = bucket->others.size();
            return (IterItem*)(key.b == 0 ? &bucket->first : &(bucket->others[key.b-1]));
        }
        key.a = END;
        key.b = 0;
        return NULL;

    }
    const IterItem* iterPrev(IterKey& key) const {
        if (key.a != END) {
            if (key.b > 0) {
                return (IterItem*)(--key.b == 0 ? &(buckets_.item(key.a)->first) : &(buckets_.item(key.a)->others[key.b-1]));
            } else {
                const Bucket* bucket = buckets_.iterPrev(key.a);
                if (bucket != NULL) {
                    key.b = bucket->others.size();
                    return (IterItem*)(key.b == 0 ? &bucket->first : &(bucket->others[key.b-1]));
                }
            }
            key.a = END;
        }
        return NULL;
    }
protected:
    const Value* getiter(IterKey& iterkey, const Value& value) const {
        if (size_ > 0) {
            iterkey.a = (data_.hash(value) & data_.sizemask);
            const Bucket* bucket = buckets_.item(iterkey.a);
            if (bucket != NULL) {
                if (data_(bucket->first, value) == 0) {
                    iterkey.b = 0;
                    return &bucket->first;
                } else {
                    const Value* item = bucket->search(iterkey.b, value, data_);
                    if (item != NULL) {
                        ++iterkey.b;
                        return item;
                    }
                }
            }
        }
        iterkey.a = END;
        iterkey.b = 0;
        return NULL;
    }

private:
    static const Size SIZE_INIT = 64;   // initial hash size -- must be power of 2
    static const Size MIN_SIZE  = 8;    // minimum hash size -- must be power of 2

    struct Bucket {
        Value first;
        Array<Value> others;

        Bucket()
            { others.setempty(); }
        Bucket(const Bucket& src) : first(src.first), others(src.others)
            { }
        bool operator==(const Bucket& data)
            { return (first == data.first && others == data.others); }

        // Search "others" for key, using compare, set index (insertion point if not found)
        const Value* search(Size& index, const Value& key, const THash& compare) const {
            int cmp;
            Size left = 0, right = others.size(), mid = 0;
            const Value* items = others.data();
            while (left < right) {
                mid = left + ((right-left) / 2);
                const Value* item = items + mid;
                cmp = compare(key, *item);
                if (cmp < 0) {
                    right = mid;
                } else if (cmp == 0) {
                    index = mid;
                    return item;
                } else
                    left = mid + 1;
            }
            index = left;
            return NULL;
        }

    private:
        // Copying is done via copy constructor
        Bucket& operator=(const Bucket&) EVO_ONCPP11(= delete);
    };

    typedef PtrList<Bucket,Size> Buckets;

    Buckets buckets_;

    // Use inheritance to reduce size bloat with empty Hash
    struct Data : public THash {
        Size sizemask;
        Size threshold;

        Data() : sizemask(0), threshold(0) {
        }
        Data& operator=(const Data& src) {
            THash::operator=(src);
            sizemask  = src.sizemask;
            threshold = src.threshold;
            return *this;
        }

    #if defined(EVO_CPP11)
        Data(Data&& src) {
            THash::operator=(std::move(src));
            sizemask  = src.sizemask;
            threshold = src.threshold;
            src.sizemask  = 0;
            src.threshold = 0;
        }

        Data& operator=(Data&& src) {
            THash::operator=(std::move(src));
            sizemask  = src.sizemask;
            threshold = src.threshold;
            src.sizemask  = 0;
            src.threshold = 0;
            return *this;
        }
    #endif
    private:
        // Copying is done via assignment operator
        Data(const Data&);
    };

    Data data_;

    void rehash(Size newsize) {
        const float THRESHOLD = 0.7f;
        data_.sizemask  = newsize - 1;
        data_.threshold = (Size)(newsize * THRESHOLD);
        if (size_ == 0) {
            // Empty, just resize buckets if needed
            buckets_.resize(newsize);
        } else {
            // Grow and rehash
            Buckets oldbuckets;
            evo::swap(buckets_, oldbuckets);
            buckets_.resize(newsize);

            bool created;
            const Bucket* bucket;
            const Bucket** cur = (const Bucket**)oldbuckets.data();
            for (const Bucket** end=cur+oldbuckets.size(); cur < end; ++cur) {
                if ((bucket=*cur) != NULL) {
                    for (Size i=0, iend=bucket->others.size(); i <= iend; ++i) {
                        const Value* item = (i == 0 ? &bucket->first : &bucket->others[i-1]);
                        Bucket* newbucket = buckets_.getitem(data_.hash(*item) & data_.sizemask, &created);
                        if (created) {
                            newbucket->first = *item;
                        } else {
                            Size index;
                            Value* newitem = (Value*)newbucket->search(index, *item, data_);
                            if (newitem == NULL)
                                newbucket->others.insert(index, *item);
                        }
                    }
                }
            }
        }
    }

    const Value* search(const Value& value) const {
        if (size_ > 0) {
            const Bucket* bucket = buckets_.item( data_.hash(value) & data_.sizemask );
            if (bucket != NULL) {
                if (data_(value, bucket->first) == 0) {
                    return &bucket->first;
                } else {
                    Size index;
                    const Value* item = bucket->search(index, value, data_);
                    if (item != NULL)
                        return item;
                }
            }
        }
        return NULL;
    }
};


#if defined(INCL_evo_string_h) || defined(DOXYGEN)

typedef SetHash<String> StrSetHash;
#endif


}
#endif