Generic Sparse Set implementation (WIP)

pixl_sparse_set.hpp

#pragma once

#include <deque>
#include <vector>
#include <type_traits>

#include "common.hpp"

//inspired by https://gist.github.com/sjgriffiths/06732c6076b9db8a7cf4dfe3a7aed43a

#ifndef PIXL_NODISCARD
#if __cplusplus > 201703L
#define PIXL_NODISCARD [[nodiscard]]
#else
#define PIXL_NODISCARD
#endif
#endif




namespace pixl::util {

#define AS_HASHED(V,F) { return (F)((V),Hasher()((V))); }


	template <class T>
	class hash_container
	{
		std::unordered_map<T,std::size_t> hash_table;
	public:
		void resize(std::size_t){}
		void resize(std::size_t,int){}
		
		std::size_t size() { return std::numeric_limits<std::size_t>::max();}

		std::size_t& operator[](T s) { return hash_table[s];}
		std::size_t  operator[](T s) const { if(auto idx = hash_table.find(s); idx != hash_table.end()) return idx->second; else return 0;}
	};

	
	

	template < typename ValueType,
			   typename Hasher,
			   template<typename> typename Dense = std::vector,
			   template<typename> typename Sparse = std::deque
	>
	class hash_sparse_set
	{
	public:
		static_assert(std::is_invocable_v<Hasher,ValueType>,"hasher must be an invocable");
		using hash_type = std::invoke_result_t<Hasher,ValueType>;
		static_assert(std::is_unsigned_v<hash_type>,"invoke result of Hasher must be unsigned");

		
		
		using value_type = ValueType;
		using value_ref = ValueType&;
		using const_value_ref = const ValueType&;

		
		using sparse_container_t = Sparse<hash_type>;
		using dense_container_t = Dense<value_type>;


		using iterator       = typename dense_container_t::const_iterator;
		using const_iterator = typename dense_container_t::const_iterator;
		using reverse_iterator = typename dense_container_t::const_reverse_iterator;
		using const_reverse_iterator = typename dense_container_t::const_reverse_iterator;
		
		using size_type = std::size_t;
		const size_type growth = 10;
		
		PIXL_NODISCARD iterator begin() 		                { return m_dense.begin();   }
		PIXL_NODISCARD const_iterator begin() const 	        { return m_dense.cbegin();  }

		PIXL_NODISCARD reverse_iterator rbegin()                { return m_dense.rend() - m_size;  }
		PIXL_NODISCARD const_reverse_iterator rbegin() const    { return m_dense.crend() - m_size; }

		PIXL_NODISCARD iterator end() 			                { return m_dense.begin() + m_size; }
		PIXL_NODISCARD const_iterator end() const 	            { return m_dense.cbegin() + m_size; }

		PIXL_NODISCARD reverse_iterator rend()                  { return m_dense.rend();  }
		PIXL_NODISCARD const_reverse_iterator rend() const      { return m_dense.crend(); }

		PIXL_NODISCARD size_type size() const noexcept	        { return m_size; }
		PIXL_NODISCARD size_type max_size() const
																noexcept(std::is_nothrow_invocable_r_v<sparse_container_t,&sparse_container_t::max_size>)
																{ return m_sparse.max_size(); }
		PIXL_NODISCARD size_type capacity() const noexcept		{ return m_capacity; }

		PIXL_NODISCARD bool empty() const noexcept              { return m_size == 0; }

		void clear() noexcept	                                { m_size = 0; }
		void reserve(size_type size)
		{
			if (size > m_capacity)
			{
				m_dense.resize(std::min(size,m_dense.size()));
				m_capacity = m_dense.size();
			}
		}
		void grow(hash_type grow_size)
		{
			m_size++;

			if(grow_size > m_sparse.size())
			{
				m_sparse.resize(grow_size+1,0);
			}
			
			if(m_size > capacity())
			{
				m_dense.resize(m_size + growth);
				
				m_capacity = m_size + growth;
			}
		}
		

		PIXL_NODISCARD bool contains(const_value_ref val) const AS_HASHED(val,contains);
		
		
		PIXL_NODISCARD bool contains(const_value_ref val,hash_type hash) const
		{
						
			return hash < m_sparse.size() && m_sparse[hash] < m_size &&	m_dense[m_sparse[hash]] == val;
		}

		const_iterator insert(const_value_ref val) AS_HASHED(val,insert);
		
		
		const_iterator insert(const_value_ref val,hash_type hash)
		{
			if (!contains(val,hash))
			{
				grow(hash);

				m_dense[m_size-1] = val;
				m_sparse[hash] = m_size-1;
				return m_dense.begin() + m_size;
			}
			return m_dense.end();
			
		}

		bool erase(const_value_ref val) AS_HASHED(val,erase);
		
		
		bool erase(const_value_ref val,hash_type hash)
		{
			if (contains(val,hash))
			{
				m_dense[m_sparse[hash]] = m_dense[m_size - 1];
				m_sparse[Hasher()(m_dense[m_size - 1])] = m_sparse[hash];
				--m_size;
				return true;
			}
			return false;
		}

	private:
		dense_container_t m_dense;
		mutable sparse_container_t m_sparse;

		size_type m_size = 0;
		size_type m_capacity = 0;
		
	};


	template <class T>
	struct Assigner
	{
		static T assigner(const T& v) {return v;}
		T operator ()(const T& v) const  { return assigner(v);}
		operator decltype(&Assigner::assigner) () const { return &Assigner::assigner;}
	};
	template <class T>
	struct Hasher16
	{
		static std::uint16_t hasher(const T& v) { return std::uint16_t(std::hash<T>()(v) & 0XFFFF); }
		std::uint16_t operator ()(const T& v) const { return hasher(v);}
		operator decltype(&Hasher16::hasher) () const { return &Hasher16::hasher;}
	};

	template <class T>
	struct Hasher24
	{
		static std::uint32_t hasher(const T& v) { return std::uint32_t(std::hash<T>()(v) & 0XFFFFFF); }
		std::uint32_t operator ()(const T& v) const { return hasher(v);}
		operator decltype(&Hasher24::hasher) () const { return &Hasher24::hasher;}
	};

	
	template <class T>
	struct Hasher32
	{
		static std::uint32_t hasher(const T& v) { return std::uint32_t(std::hash<T>()(v) & 0XFFFFFFFF); }
		std::uint32_t operator ()(const T& v) const { return hasher(v);}
		operator decltype(&Hasher32::hasher) () const { return &Hasher32::hasher;}
	};

	template<class T,
			 typename = std::enable_if_t<std::is_unsigned_v<T>>>
	using unsigned_sparse_set = hash_sparse_set<T,Assigner<T>>;

	template<class T>
	using generic_sparse_set = hash_sparse_set<T,Hasher24<T>>;


	template<class T>
	using experimental_sparse_set = hash_sparse_set<T,std::hash<T>,std::vector,hash_container>;
	

	template <class T>
	struct auto_sparse_set
	{
		static auto constexpr make_set() {
			if constexpr(std::is_unsigned_v<T>)
			{
				return unsigned_sparse_set<T>{};
			}
			else return generic_sparse_set<T>{};
		}
		using type = typename std::conditional<std::is_unsigned_v<T>,unsigned_sparse_set<T>,generic_sparse_set<T>>::type;
	};

	template<class T>
	using auto_sparse_set_t = typename auto_sparse_set<T>::type;

	template<class T>
	inline auto make_set = [](std::initializer_list<T>&& list)
	{
		auto set = auto_sparse_set<T>::make_set();
		std::for_each(list.begin(), list.end(),[&](auto x)
		{
			set.insert(x);
		});
		return set;
	};
	
	template <typename T,
	template<typename> typename Dense = std::vector,
	template<typename> typename Sparse = std::deque
	>
	class easy_sparse_set
	{
		static_assert(std::is_unsigned_v<T>, "T must satisfy is_unsigned");
	public:
		using value_type = T;
		using value_ref = T&;
		using const_value_ref = const T&;

		using sparse_container_t = Sparse<value_type>;
		using dense_container_t  = Dense<value_type>;

		using iterator       = typename dense_container_t::const_iterator;
		using const_iterator = typename dense_container_t::const_iterator;
		using reverse_iterator = typename dense_container_t::const_reverse_iterator;
		using const_reverse_iterator = typename dense_container_t::const_reverse_iterator;
		

		
		using size_type = std::size_t;


		PIXL_NODISCARD iterator begin() 		                { return m_dense.begin();   }
		PIXL_NODISCARD const_iterator begin() const 	        { return m_dense.cbegin();  }

		PIXL_NODISCARD reverse_iterator rbegin()                { return m_dense.rend() - m_size;  }
		PIXL_NODISCARD const_reverse_iterator rbegin() const    { return m_dense.crend() - m_size; }

		PIXL_NODISCARD iterator end() 			                { return m_dense.begin() + m_size; }
		PIXL_NODISCARD const_iterator end() const 	            { return m_dense.cbegin() + m_size; }

		PIXL_NODISCARD reverse_iterator rend()                  { return m_dense.rend();  }
		PIXL_NODISCARD const_reverse_iterator rend() const      { return m_dense.crend(); }

		PIXL_NODISCARD size_type size() const noexcept	        { return m_size; }
		PIXL_NODISCARD size_type max_size() const
																noexcept(std::is_nothrow_invocable_r_v<sparse_container_t,&sparse_container_t::max_size>)
																{ return m_sparse.max_size(); }
		PIXL_NODISCARD size_type capacity() const noexcept		{ return m_capacity; }

		PIXL_NODISCARD bool empty() const noexcept              { return m_size == 0; }

		void clear() noexcept	                                { m_size = 0; }
		void reserve(size_type size)
		{
			if (m_size > m_capacity)
			{
				m_dense.resize(size, 0);
				m_sparse.resize(size, 0);
				m_capacity = size;
			}
		}


		bool contains(const_value_ref val) const
		{
			return val < m_capacity &&
				m_sparse[val] < m_size &&
				m_dense[m_sparse[val]] == val;
		}

		const_iterator insert(const_value_ref val)
		{
			if (!contains(val))
			{
				if (val >= m_capacity)
					reserve(val + 1);

				m_dense[m_size - 1] = val;
				m_sparse[val] = m_size - 1;
				++m_size;
				return m_dense.begin() + m_size;
			}
			return m_dense.end();
			
		}

		
		bool erase(const_value_ref val)
		{
			if (contains(val))
			{
				m_dense[m_sparse[val]] = m_dense[m_size - 1];
				m_sparse[m_dense[m_size - 1]] = m_sparse[val];
				--m_size;
				return true;
			}
			return false;
		}
	private:
		dense_container_t m_dense;
		sparse_container_t m_sparse;

		size_type m_size = 0;
		size_type m_capacity = 0;
	};

#undef AS_HASHED
}