//#####################################################################
// Copyright 2002-2008, Robert Bridson, Kevin Der, Ronald Fedkiw, Geoffrey Irving, Nipun Kwatra, Neil Molino, Craig Schroeder, Andrew Selle, Tamar Shinar, Joseph Teran.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class HASHTABLE
//#####################################################################
#ifndef __HASHTABLE__
#define __HASHTABLE__

#include <Core/Arrays/ARRAY.h>
#include <Core/Data_Structures/HASH_REDUCE.h>
#include <Core/Data_Structures/TUPLE.h>
#include <Core/Math_Tools/integer_log.h>
#include <Core/Utilities/EXCEPTIONS.h>
#include <bit>
namespace PhysBAM{

enum HASHTABLE_ENTRY_STATE{ENTRY_FREE,ENTRY_ACTIVE,ENTRY_DELETED};
template<class TK,class T=void>
class HASHTABLE
{
private:
    struct UNUSABLE{};
    typedef conditional_t<is_same_v<T,void>,UNUSABLE,T> T_UNLESS_VOID;
public:
    typedef TK KEY;
    typedef T ELEMENT;
    typedef conditional_t<is_same_v<T,void>,TK,std::pair<TK,T>> value_type;
    typedef std::pair<HASHTABLE_ENTRY_STATE,value_type> ENTRY;
    
private:
    ARRAY<ENTRY> table;
    int number_of_entries=0;
    int next_resize=0;
public:

    HASHTABLE()=default;
    HASHTABLE(int estimated_max_number_of_entries)
        :table(max(4,(int)std::bit_ceil((unsigned)(estimated_max_number_of_entries*4/3+1)))),
        next_resize(table.m*3/4)
    {
    }

    HASHTABLE(const HASHTABLE&) = default;
    HASHTABLE(HASHTABLE&& ht)
        :table(std::move(ht.table)),number_of_entries(ht.number_of_entries),
        next_resize(ht.next_resize)
    {
        ht.number_of_entries=0;
        ht.next_resize=0;
    }

    HASHTABLE(std::initializer_list<value_type> list)
        :HASHTABLE()
    {
        for(auto&i:list)
        {
            if constexpr(is_same_v<T,void>) Insert(i);
            else Insert(i.first,i.second);
        }
    }

    ~HASHTABLE() = default;
    HASHTABLE& operator=(const HASHTABLE&) = default;
    HASHTABLE& operator=(HASHTABLE&& ht)
    {
        table=std::move(ht.table);
        number_of_entries=ht.number_of_entries;
        next_resize=ht.next_resize;
        ht.number_of_entries=0;
        ht.next_resize=0;
        return *this;
    }

    HASHTABLE& operator=(std::initializer_list<value_type> list)
    {
        Clean_Memory();
        for(auto&i:list)
        {
            if constexpr(is_same_v<T,void>) Insert(i);
            else Insert(i.first,i.second);
        }
        return *this;
    }

    void Clean_Memory()
    {
        table.Clean_Memory();
        number_of_entries=0;
        next_resize=0;
    }

    int Size() const
    {return number_of_entries;}

    int Max_Size() const
    {return table.m;}

    int Next_Resize() const
    {return next_resize;}

private:
    void Resize_Table()
    {
        ARRAY<ENTRY> old_table(table.m?table.m*2:4);
        std::swap(table,old_table);
        number_of_entries=0;
        next_resize=table.m*3/4;
        for(auto&e:old_table)
            if(e.first==ENTRY_ACTIVE)
                Insert(e.second);
    }

    int Next_Index(const int h) const // linear probing
    {return ((h+1)&(table.m-1));} // power of two so mod is dropping high order bits

    int Hash_Index(const TK& v) const
    {return (Hash(v)&(table.m-1));} // power of two so mod is dropping high order bits

    static const TK& Key(const std::pair<TK,T_UNLESS_VOID>& v){return v.first;}
    static const TK& Key(const TK& v){return v;}
    
    // pair.first = location in hash where this entry is/should be be placed.
    // pair.second = true if the key is already present at pair.first
    // If table is empty, bool is valid, but int is bad.
    pair<int,bool> Search(const TK& v) const
    {
        if(!table.m) return {0,false};
        for(int h=Hash_Index(v);;h=Next_Index(h)){
            auto& e=table(h);
            if(e.first==ENTRY_FREE) return {h,false};
            if(e.first==ENTRY_ACTIVE && Key(e.second)==v)
                return {h,true};}
    }
    pair<int,bool> Search(const std::pair<TK,T_UNLESS_VOID>& v) const
    {return Search(v.first);}

    // pair.first = location in hash where this entry is
    // pair.second = true if the key was inserted at pair.first
    pair<int,bool> Insert_Helper(const value_type& v)
    {
        if(number_of_entries>=next_resize) Resize_Table();
        auto pr=Search(v);
        if(!pr.second){
            number_of_entries++;
            ENTRY& e=table(pr.first);
            e.second=v;
            e.first=ENTRY_ACTIVE;}
        pr.second=!pr.second;
        return pr;
    }
public:

    bool Insert(const TK& v)
    {
        static_assert((is_same_v<T,void>));
        return Insert_Helper(v).second;
    }

    // If v not already present, inserts {v,value}; returns {&data, true}
    // If already present, just return {&data, false}
    pair<T_UNLESS_VOID*,bool> Insert(const std::pair<TK,T_UNLESS_VOID>& v)
    {
        static_assert((!is_same_v<T,void>));
        auto pr=Insert_Helper(v);
        return {&table(pr.first).second.second,pr.second};
    }

    // If v not already present, inserts {v,value}; returns {&data, true}
    // If already present, just return {&data, false}
    pair<T_UNLESS_VOID*,bool> Insert(const TK& v,const T_UNLESS_VOID& value) // assumes no entry with v exists
    {return Insert(value_type{v,value});}

    // inserts the default if key not found
    T_UNLESS_VOID& Get_Or_Insert(const TK& v,const T_UNLESS_VOID& default_value=T_UNLESS_VOID())
    {return *Insert(v,default_value).first;}

    T* Get_Pointer(const TK& v) // returns NULL if key not found
    {
        auto pr=Search(v);
        if(pr.second) return &table(pr.first).second.second;
        return nullptr;
    }

    const T* Get_Pointer(const TK& v) const // returns NULL if key not found
    {
        auto pr=Search(v);
        if(pr.second) return &table(pr.first).second.second;
        return nullptr;
    }

    T_UNLESS_VOID& Get(const TK& v) // fails if key not found
    {
        auto pr=Search(v);
        if(pr.second) return table(pr.first).second.second;
        throw KEY_ERROR("HASHTABLE::Get");
    }

    const T_UNLESS_VOID& Get(const TK& v) const // fails if key not found
    {
        auto pr=Search(v);
        if(pr.second) return table(pr.first).second.second;
        throw KEY_ERROR("HASHTABLE::Get");
    }

    // returns default_value if key not found
    T Get_Default(const TK& v,const T_UNLESS_VOID& default_value=T_UNLESS_VOID()) const
    {
        auto pr=Search(v);
        if(pr.second) return table(pr.first).second.second;
        return default_value;
    }

    bool Contains(const TK& v) const
    {return Search(v).second;}

    bool Get(const TK& v,T_UNLESS_VOID& value) const
    {
        auto pr=Search(v);
        if(pr.second) value=table(pr.first).second.second;
        return pr.second;
    }

    // insert entry if doesn't already exists, returns whether it added a new entry
    bool Set(const TK& v)
    {return Insert(v);}

    // if v doesn't exist insert it.  Always sets value.  Returns whether it added a new entry
    bool Set(const TK& v,const T_UNLESS_VOID& value)
    {
        static_assert((!is_same_v<T,void>));
        auto pr=Insert_Helper({v,value});
        if(!pr.second) table(pr.first).second.second=value;
        return pr.second;
    }

    // if v doesn't exist insert it.  Always sets value.  Returns whether it added a new entry
    bool Set(const std::pair<TK,T_UNLESS_VOID>& p)
    {
        static_assert((!is_same_v<T,void>));
        auto pr=Insert_Helper(p);
        if(!pr.second) table(pr.first).second.second=p.second;
        return pr.second;
    }

    template<class T_ARRAY>
    void Set_All(const T_ARRAY& array)
    {
        static_assert(is_same_v<typename T_ARRAY::ELEMENT,value_type>);
        for(auto& a:array) Set(a);
    }

    template<class T_KEY,class T_ARRAY>
    void Set_All(const T_KEY& key,const T_ARRAY& array)
    {
        static_assert(is_same_v<typename T_ARRAY::ELEMENT,T>);
        static_assert(is_same_v<typename T_KEY::ELEMENT,TK>);
        for(typename T_ARRAY::INDEX i(0);i<array.Size();i++)
            Set(key(i),array(i));
    }

    bool Delete_If_Present(const TK& v)
    {
        auto pr=Search(v);
        if(pr.second)
        {
            table(pr.first).first=ENTRY_DELETED;
            number_of_entries--;
            next_resize--;
        }
        return pr.second;
    }

    void Delete(const TK& v)
    {
        if(!Delete_If_Present(v))
            throw KEY_ERROR("HASHTABLE::Delete");
    }

    void Remove_All()
    {
        for(auto&e:table) e.first=ENTRY_FREE;
        number_of_entries=0;
    }

    void Exchange(HASHTABLE& hash)
    {
        table.Exchange(hash.table);
        exchange(number_of_entries,hash.number_of_entries);
        exchange(next_resize,hash.next_resize);
    }

    void Append_Keys(ARRAY<TK>& keys) const
    {
        keys.Preallocate(keys.m+Size());
        for(auto&e:*this) keys.Append(Key(e));
    }

    void Get_Keys(ARRAY<TK>& keys) const
    {
        keys.Remove_All();
        Append_Keys(keys);
    }

    void Append_Data(ARRAY<T_UNLESS_VOID>& data) const
    {
        data.Preallocate(data.m+Size());
        for(auto&e:*this) data.Append(e.second);
    }

    void Get_Data(ARRAY<T_UNLESS_VOID>& data) const
    {
        data.Remove_All();
        Append_Data(data);
    }

    void Append_Pairs(ARRAY<value_type>& pairs) const
    {
        pairs.Preallocate(pairs.m+Size());
        for(auto&e:*this) pairs.Append(e);
    }

    void Get_Pairs(ARRAY<value_type>& pairs) const
    {
        pairs.Remove_All();
        Append_Pairs(pairs);
    }

    bool operator==(const HASHTABLE& h) const
    {
        if(Size()!=h.Size()) return false;
        for(auto&p:*this)
        {
            if constexpr(is_same_v<T,void>)
            {
                if(!h.Contains(p))
                    return false;
            }
            else
            {
                T data;
                if(!h.Get(p.first,data) || data!=p.second)
                    return false;
            }
        }
        return true;
    }

    template<class RW> void Read(UNTYPED_ISTREAM<RW>& input)
    {
        if constexpr(is_same_v<RW,char>)
        {
            ::PhysBAM::Get(input,'(');
            while(!Try_Get(input,')'))
            {
                TK key;
                Read_Binary(input,key);
                if constexpr(!is_same_v<T,void>)
                {
                    T data;
                    ::PhysBAM::Get(input,':');
                    Read_Binary(input,data);
                    Set(key,data);
                }
                else Set(key);
            }
        }
        else Read_Binary(input,number_of_entries,next_resize,table);
    }

    template<class RW> void Write(UNTYPED_OSTREAM<RW>& output) const
    {
        if constexpr(is_same_v<RW,char>)
        {
            Beg(output,'(');
            for(auto& p:*this)
            {
                if constexpr(!is_same_v<T,void>)
                {
                    Write_Binary(output,p.first);
                    Sep(output,':',false);
                    Write_Binary(output,p.second);
                }
                else Write_Binary(output,p);
            }
            End(output,')');
        }
        else Write_Binary(output,number_of_entries,next_resize,table);
    }

private:
    template<bool is_const>
    class HASHTABLE_ITERATOR
    {
        typedef conditional_t<is_const,const HASHTABLE,HASHTABLE> IT_HASHTABLE;
        typedef conditional_t<is_const,const ENTRY,ENTRY> IT_ENTRY;
        typedef conditional_t<is_const,const value_type,value_type> IT_VT;

        IT_ENTRY* cur=nullptr, *end=nullptr;
    public:
        class END_TAG{};
        
        HASHTABLE_ITERATOR(IT_HASHTABLE& h)
            :cur(h.table.begin()),end(h.table.end())
        {
            while(cur!=end && cur->first!=ENTRY_ACTIVE) cur++;
        }

        HASHTABLE_ITERATOR(IT_HASHTABLE& h,END_TAG)
            :cur(h.table.end()),end(cur)
        {}
        
        // stl
        HASHTABLE_ITERATOR& operator++()
        {
            assert(cur!=end);
            while(++cur!=end && cur->first!=ENTRY_ACTIVE){}
            return *this;
        }

        HASHTABLE_ITERATOR operator++(int)
        {
            HASHTABLE_ITERATOR it(*this);
            ++*this;
            return it;
        }

        IT_VT* operator->()
        {return &cur->second;}

        const value_type* operator->() const
        {return &cur->second;}

        IT_VT& operator*()
        {return cur->second;}

        const value_type& operator*() const
        {return cur->second;}

        template<bool isc> bool operator==(const HASHTABLE_ITERATOR<isc>& it) const
        {return cur==it.cur;}

        template<bool isc> bool operator!=(const HASHTABLE_ITERATOR<isc>& it) const
        {return cur!=it.cur;}
    };
public:

    typedef HASHTABLE_ITERATOR<false> iterator; // for stl
    typedef HASHTABLE_ITERATOR<true> const_iterator; // for stl

    // stl
    iterator begin()
    {return iterator(*this);}

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

    iterator end()
    {return iterator(*this,typename iterator::END_TAG());}

    const_iterator end() const
    {return const_iterator(*this,typename const_iterator::END_TAG());}
};

template<class K,class T>
std::ostream& operator<<(std::ostream& output,const HASHTABLE<K,T>& hashtable)
{
    output<<"(";
    bool first=true;
    for(const auto& it:hashtable){
        if(!first) output<<" ";
        first=false;
        output<<it.first<<":"<<it.second;}
    output<<")";
    return output;
}

template<class K>
std::ostream& operator<<(std::ostream& output,const HASHTABLE<K,void>& hashtable)
{
    output<<"(";
    bool first=true;
    for(const auto& data:hashtable){
        if(!first) output<<" ";
        first=false;
        output<<data;}
    output<<")";
    return output;
}
template<class T,class T_ARRAY>
ARRAY<T> Get_Unique(const ARRAY_BASE<T,T_ARRAY>& array)
{
    ARRAY<T> uniq;
    const T_ARRAY& self=array.Derived();
    HASHTABLE<T> hash(Value(self.Size())*3/2);
    for(auto& a:array)
        if(hash.Set(a))
            uniq.Append(a);
    return uniq;
}
template<class T>
void Prune_Duplicates(ARRAY<T>& array)
{
    HASHTABLE<T> hash(Value(array.Size())*3/2);
    int j=0;
    for(int i=0;i<array.Size();i++)
        if(hash.Set(array(i)))
            array(j++)=array(i);
    array.Resize(j);
}
}
#endif
