<commit_before>/**********************************************************\

  This file is distributed under the MIT License.
  See https://github.com/morzhovets/momo/blob/master/LICENSE
  for details.

  momo/DataColumn.h

  macros:
    MOMO_DATA_COLUMN_STRUCT
    MOMO_DATA_COLUMN_STRING_TAG
    MOMO_DATA_COLUMN_STRING

  namespace momo:
    class DataColumn
    class DataColumnInfo
    class DataSettings
    struct DataStructDefault
    class DataColumnTraits
    class DataItemTraits
    class DataColumnList
    class DataColumnListStatic

\**********************************************************/

#pragma once

#include "Array.h"
#include "HashSet.h"

#include <bitset>
#include <typeinfo>

#define MOMO_DATA_COLUMN_STRUCT(Struct, name) \
	constexpr momo::DataColumn<decltype(std::declval<Struct&>().name), Struct> \
	name(uint64_t{offsetof(Struct, name)}, #name)

#define MOMO_DATA_COLUMN_STRING_TAG(Tag, Type, name) \
	MOMO_STATIC_ASSERT(!std::is_class<Tag>::value || std::is_empty<Tag>::value); \
	constexpr momo::DataColumn<Type, Tag> name(momo::internal::StrHasher::GetHashCode64(#name), #name)

#define MOMO_DATA_COLUMN_STRING(Type, name) \
	MOMO_DATA_COLUMN_STRING_TAG(momo::DataStructDefault<>, Type, name)

namespace momo
{

namespace internal
{
	class StrHasher
	{
	private:
		static const uint64_t fnvBasis64 = 14695981039346656037ull;
		static const uint64_t fnvPrime64 = 1099511628211ull;

	public:
		// Fowler-Noll-Vo hash function (1a)
		constexpr static uint64_t GetHashCode64(const char* str) noexcept
		{
			return (*str == '\0') ? fnvBasis64
				: (GetHashCode64(str + 1) ^ uint64_t{static_cast<unsigned char>(*str)}) * fnvPrime64;
		}
	};

	template<typename Struct,
		typename = void>
	struct DataVisitableItemsGetter
	{
		typedef std::tuple<> VisitableItems;
	};

	template<typename Struct>
	struct DataVisitableItemsGetter<Struct, Void<typename Struct::VisitableItems>>
	{
		typedef typename Struct::VisitableItems VisitableItems;
	};

	template<typename TColumn, typename TItemArg>
	class DataOperator
	{
	public:
		typedef TColumn Column;
		typedef TItemArg ItemArg;

	public:
		explicit DataOperator(const Column& column, ItemArg&& itemArg) noexcept
			: mColumn(column),
			mItemArg(std::forward<ItemArg>(itemArg))
		{
		}

#ifndef MOMO_HAS_GUARANTEED_COPY_ELISION
		DataOperator(DataOperator&& oper) noexcept
			: mColumn(oper.mColumn),
			mItemArg(std::forward<ItemArg>(oper.mItemArg))
		{
			//MOMO_ASSERT(false);
		}
#endif

		DataOperator(const DataOperator&) = delete;

		~DataOperator() noexcept
		{
		}

		DataOperator& operator=(const DataOperator&) = delete;

		const Column& GetColumn() const noexcept
		{
			return mColumn;
		}

		ItemArg&& GetItemArg() const noexcept
		{
			return std::forward<ItemArg>(mItemArg);
		}

	private:
		const Column& mColumn;
		ItemArg&& mItemArg;
	};

	template<typename TColumn, typename TItemArg>
	class DataEqualer : public DataOperator<TColumn, TItemArg>
	{
	private:
		typedef DataOperator<TColumn, TItemArg> Operator;

	public:
		using Operator::Operator;
	};

	template<typename TColumn, typename TItemArg>
	class DataAssigner : public DataOperator<TColumn, TItemArg>
	{
	private:
		typedef DataOperator<TColumn, TItemArg> Operator;

	public:
		using Operator::Operator;
	};

	template<typename Item>
	struct DataMutable
	{
	};
}

template<typename TItem, typename TStruct>
class DataColumn : public DataColumn<internal::DataMutable<TItem>, TStruct>
{
public:
	typedef TItem Item;
	typedef TStruct Struct;

	typedef DataColumn BaseColumn;

	typedef DataColumn<internal::DataMutable<Item>, Struct> MutableColumn;

	typedef internal::DataEqualer<DataColumn, const Item&> Equaler;

	template<typename ItemArg>
	using Assigner = internal::DataAssigner<DataColumn, ItemArg>;

public:
	constexpr explicit DataColumn(uint64_t code, const char* name = "") noexcept
		: mCode(code),
		mName(name)
	{
	}

	const BaseColumn& GetBaseColumn() const noexcept
	{
		return *this;
	}

	constexpr uint64_t GetCode() const noexcept
	{
		return mCode;
	}

	constexpr const char* GetName() const noexcept
	{
		return mName;
	}

	constexpr const MutableColumn& Mutable() const noexcept
	{
		return *this;
	}

	constexpr bool IsMutable() const noexcept
	{
		return false;
	}

	Equaler operator==(const Item& item) const noexcept
	{
		return Equaler(*this, item);
	}

	template<typename ItemArg>
	Assigner<ItemArg> operator=(ItemArg&& itemArg) const noexcept
	{
		return Assigner<ItemArg>(*this, std::forward<ItemArg>(itemArg));
	}

private:
	uint64_t mCode;
	const char* mName;
};

template<typename TItem, typename TStruct>
class DataColumn<internal::DataMutable<TItem>, TStruct>
{
public:
	typedef TItem Item;
	typedef TStruct Struct;

	typedef DataColumn<Item, Struct> BaseColumn;

public:
	const BaseColumn& GetBaseColumn() const noexcept
	{
		return static_cast<const BaseColumn&>(*this);
	}

	constexpr bool IsMutable() const noexcept
	{
		return true;
	}

protected:
	constexpr explicit DataColumn() noexcept
	{
	}

	DataColumn(const DataColumn&) = default;

	~DataColumn() = default;

	DataColumn& operator=(const DataColumn&) = default;
};

template<typename TStruct>
class DataColumnInfo
{
public:
	typedef TStruct Struct;

	template<typename Item>
	using Column = DataColumn<Item, Struct>;

	typedef typename internal::DataVisitableItemsGetter<Struct>::VisitableItems VisitableItems;

public:
	template<typename Item>
	DataColumnInfo(const Column<Item>& column) noexcept
		: mCode(column.GetCode()),
		mName(column.GetName()),
		mTypeInfo(typeid(Item))
	{
	}

	uint64_t GetCode() const noexcept
	{
		return mCode;
	}

	const char* GetName() const noexcept
	{
		return mName;
	}

	const std::type_info& GetTypeInfo() const noexcept
	{
		return mTypeInfo;
	}

	template<typename PtrVisitor>
	void Visit(const void* item, const PtrVisitor& ptrVisitor) const
	{
		pvVisitRec<0>(item, ptrVisitor);
	}

	template<typename PtrVisitor>
	void Visit(void* item, const PtrVisitor& ptrVisitor) const
	{
		pvVisitRec<0>(item, ptrVisitor);
	}

private:
	template<size_t index, typename Void, typename PtrVisitor>
	internal::EnableIf<(index < std::tuple_size<VisitableItems>::value)> pvVisitRec(Void* item,
		const PtrVisitor& ptrVisitor) const
	{
		typedef typename std::tuple_element<index, VisitableItems>::type Item;
		typedef typename std::conditional<std::is_const<Void>::value,
			const Item*, Item*>::type ItemPtr;
		if (typeid(Item) == mTypeInfo)
			pvVisit(static_cast<ItemPtr>(item), ptrVisitor);
		else
			pvVisitRec<index + 1>(item, ptrVisitor);
	}

	template<size_t index, typename Void, typename PtrVisitor>
	internal::EnableIf<(index == std::tuple_size<VisitableItems>::value)> pvVisitRec(Void* item,
		const PtrVisitor& ptrVisitor) const
	{
		pvVisit(item, ptrVisitor);
	}

	template<typename Item, typename PtrVisitor>
	internal::EnableIf<internal::IsInvocable2<PtrVisitor, Item*, DataColumnInfo>::value>
	pvVisit(Item* item, const PtrVisitor& ptrVisitor) const
	{
		ptrVisitor(item, *this);
	}

	template<typename Item, typename PtrVisitor>
	internal::EnableIf<!internal::IsInvocable2<PtrVisitor, Item*, DataColumnInfo>::value>
	pvVisit(Item* item, const PtrVisitor& ptrVisitor) const
	{
		ptrVisitor(item);
	}

private:
	uint64_t mCode;
	const char* mName;
	const std::type_info& mTypeInfo;
};

template<bool tKeepRowNumber = true>
class DataSettings
{
public:
	static const CheckMode checkMode = CheckMode::bydefault;
	static const ExtraCheckMode extraCheckMode = ExtraCheckMode::bydefault;
	static const bool checkVersion = MOMO_CHECK_ITERATOR_VERSION;

	static const bool keepRowNumber = tKeepRowNumber;

	typedef ArraySettings<> TableRawsSettings;
	typedef ArraySettings<4, true, true> SelectionRawsSettings;
};

template<typename... TVisitableItems>
struct DataStructDefault
{
	typedef std::tuple<TVisitableItems...> VisitableItems;
};

template<typename TStruct = DataStructDefault<>>
class DataColumnTraits
{
public:
	typedef TStruct Struct;

	typedef DataColumnInfo<Struct> ColumnInfo;
	template<typename Item>
	using Column = typename ColumnInfo::template Column<Item>;

	typedef uint64_t ColumnCode;

	static const size_t logVertexCount = 8;
	static const size_t maxColumnCount = 200;
	static const size_t maxCodeParam = 255;

	typedef HashTraitsOpen<ColumnCode> ColumnCodeHashTraits;

public:
	static ColumnCode GetColumnCode(ColumnInfo columnInfo) noexcept
	{
		return columnInfo.GetCode();
	}

	static std::pair<size_t, size_t> GetVertices(ColumnCode code, size_t codeParam) noexcept
	{
		static const size_t vertexCount1 = (size_t{1} << logVertexCount) - 1;
		size_t shortCode = static_cast<size_t>(code + (code >> 32));
		shortCode ^= (codeParam >> 4) ^ ((codeParam & 15) << 28);
		shortCode += shortCode >> 16;
		size_t vertex1 = shortCode & vertexCount1;
		size_t vertex2 = (shortCode >> logVertexCount) & vertexCount1;
		vertex2 ^= (vertex1 == vertex2) ? 1 : 0;
		return std::make_pair(vertex1, vertex2);
	}
};

template<typename TMemManager>
class DataItemTraits
{
public:
	typedef TMemManager MemManager;

private:
	template<typename Item>
	using ItemManager = internal::ObjectManager<Item, MemManager>;

public:
	template<typename Item>
	static size_t GetSize() noexcept
	{
		return sizeof(Item);
	}

	template<typename Item>
	static size_t GetAlignment() noexcept
	{
		return ItemManager<Item>::alignment;
	}

	template<typename Item>
	static void Create(MemManager& memManager, Item* item)
	{
		(typename ItemManager<Item>::template Creator<>(memManager))(item);
	}

	template<typename Item>
	static void Destroy(MemManager* memManager, Item* item) noexcept
	{
		ItemManager<Item>::Destroyer::Destroy(memManager, *item);
	}

	template<typename Item>
	static void Copy(MemManager& memManager, const Item& srcItem, Item* dstItem)
	{
		ItemManager<Item>::Copy(memManager, srcItem, dstItem);
	}

	template<typename ItemArg, typename Item>
	static void Assign(ItemArg&& itemArg, Item& item)
	{
		item = std::forward<ItemArg>(itemArg);
	}
};

template<typename TColumnTraits = DataColumnTraits<>,
	typename TMemManager = MemManagerDefault,
	typename TItemTraits = DataItemTraits<TMemManager>,
	typename TSettings = DataSettings<>>
class DataColumnList
{
public:
	typedef TColumnTraits ColumnTraits;
	typedef TMemManager MemManager;
	typedef TItemTraits ItemTraits;
	typedef TSettings Settings;

	typedef typename ColumnTraits::ColumnInfo ColumnInfo;
	template<typename Item>
	using Column = typename ColumnTraits::template Column<Item>;

	template<typename Item>
	using QualifiedColumn = Column<Item>;

	typedef void Raw;

	class ColumnRecord : public ColumnInfo
	{
	public:
		explicit ColumnRecord(ColumnInfo columnInfo, size_t offset) noexcept	//?
			: ColumnInfo(columnInfo),
			mOffset(offset)
		{
		}

		size_t GetOffset() const noexcept
		{
			return mOffset;
		}

	private:
		size_t mOffset;
	};

private:
	static const size_t logVertexCount = ColumnTraits::logVertexCount;
	static const size_t maxColumnCount = ColumnTraits::maxColumnCount;
	static const size_t maxCodeParam = ColumnTraits::maxCodeParam;

	static const size_t vertexCount = size_t{1} << logVertexCount;

	class Graph
	{
	private:
		struct Edge
		{
			size_t vertex;
			size_t value;
			Edge* nextEdge;
		};

		static const size_t maxEdgeCount = 2 * maxColumnCount;

	public:
		explicit Graph() noexcept
			: mEdgeNumber(0)
		{
			std::fill(mEdges.begin(), mEdges.end(), nullptr);
		}

		Graph(const Graph&) = delete;

		~Graph() noexcept
		{
		}

		Graph& operator=(const Graph&) = delete;

		void AddEdges(size_t vertex1, size_t vertex2, size_t value) noexcept
		{
			MOMO_EXTRA_CHECK(vertex1 != vertex2);
			pvAddEdge(vertex1, vertex2, value);
			pvAddEdge(vertex2, vertex1, value);
		}

		bool HasEdge(size_t vertex) const noexcept
		{
			return mEdges[vertex] != nullptr;
		}

		bool FillAddends(size_t* addends, size_t vertex) const noexcept
		{
			size_t addend = addends[vertex];
			for (Edge* edge = mEdges[vertex]; edge != nullptr; edge = edge->nextEdge)
			{
				size_t vertex2 = edge->vertex;
				size_t& addend2 = addends[vertex2];
				if (addend2 == 0)
				{
					addend2 = edge->value - addend;
					if (!FillAddends(addends, vertex2))
						return false;
				}
				else
				{
					if (addend + addend2 != edge->value)
						return false;
				}
			}
			return true;
		}

	private:
		void pvAddEdge(size_t vertex1, size_t vertex2, size_t value) noexcept
		{
			MOMO_ASSERT(mEdgeNumber < vertexCount * 2);
			Edge* edge = &mEdgeStorage[mEdgeNumber];
			++mEdgeNumber;
			edge->vertex = vertex2;
			edge->value = value;
			edge->nextEdge = mEdges[vertex1];
			mEdges[vertex1] = edge;
		}

	private:
		size_t mEdgeNumber;
		std::array<Edge, maxEdgeCount> mEdgeStorage;
		std::array<Edge*, vertexCount> mEdges;
	};

	typedef std::array<size_t, vertexCount> Addends;

	typedef typename ColumnTraits::ColumnCode ColumnCode;

	typedef typename ColumnTraits::ColumnCodeHashTraits ColumnCodeHashTraits;

	typedef HashSet<ColumnCode, ColumnCodeHashTraits, MemManager,
		HashSetItemTraits<ColumnCode, MemManager>, internal::NestedHashSetSettings> ColumnCodeSet;

	typedef internal::MemManagerPtr<MemManager> MemManagerPtr;

	typedef internal::NestedArrayIntCap<0, ColumnRecord, MemManagerPtr> Columns;

	typedef std::function<void(MemManager&, const ColumnRecord*, const DataColumnList*,
		const Raw*, Raw*)> CreateFunc;
	typedef std::function<void(MemManager*, const ColumnRecord*, Raw*)> DestroyFunc;

	struct FuncRecord
	{
		size_t columnIndex;
		CreateFunc createFunc;
		DestroyFunc destroyFunc;
	};

	typedef internal::NestedArrayIntCap<0, FuncRecord, MemManagerPtr> FuncRecords;

	typedef internal::NestedArrayIntCap<0, uint8_t, MemManagerPtr> MutableOffsets;

public:
	typedef typename Columns::ConstIterator ConstIterator;
	typedef ConstIterator Iterator;

public:
	explicit DataColumnList(MemManager&& memManager = MemManager())
		: mCodeParam(0),
		mTotalSize(Settings::keepRowNumber ? sizeof(size_t) : 0),
		mAlignment(Settings::keepRowNumber ? internal::AlignmentOf<size_t>::value : 1),
		mColumnCodeSet(ColumnCodeHashTraits(), std::move(memManager)),
		mColumns(MemManagerPtr(GetMemManager())),
		mFuncRecords(MemManagerPtr(GetMemManager())),
		mMutableOffsets(MemManagerPtr(GetMemManager()))
	{
		std::fill(mAddends.begin(), mAddends.end(), 0);
	}

	template<typename Item, typename... Items>
	explicit DataColumnList(const QualifiedColumn<Item>& column,
		const QualifiedColumn<Items>&... columns)
		: DataColumnList()
	{
		Add(column, columns...);
	}

	DataColumnList(DataColumnList&& columnList) noexcept
		: mCodeParam(columnList.mCodeParam),
		mAddends(columnList.mAddends),
		mTotalSize(columnList.mTotalSize),
		mAlignment(columnList.mAlignment),
		mColumnCodeSet(std::move(columnList.mColumnCodeSet)),
		mColumns(std::move(columnList.mColumns)),
		mFuncRecords(std::move(columnList.mFuncRecords)),
		mMutableOffsets(std::move(columnList.mMutableOffsets))
	{
	}

	DataColumnList(const DataColumnList& columnList)
		: mCodeParam(columnList.mCodeParam),
		mAddends(columnList.mAddends),
		mTotalSize(columnList.mTotalSize),
		mAlignment(columnList.mAlignment),
		mColumnCodeSet(columnList.mColumnCodeSet),
		mColumns(columnList.mColumns, MemManagerPtr(GetMemManager())),
		mFuncRecords(columnList.mFuncRecords, MemManagerPtr(GetMemManager())),
		mMutableOffsets(columnList.mMutableOffsets, MemManagerPtr(GetMemManager()))
	{
	}

	~DataColumnList() noexcept
	{
	}

	DataColumnList& operator=(const DataColumnList&) = delete;

	ConstIterator GetBegin() const noexcept
	{
		return mColumns.GetBegin();
	}

	ConstIterator GetEnd() const noexcept
	{
		return mColumns.GetEnd();
	}

	MOMO_FRIENDS_BEGIN_END(const DataColumnList&, ConstIterator)

	const MemManager& GetMemManager() const noexcept
	{
		return mColumnCodeSet.GetMemManager();
	}

	MemManager& GetMemManager() noexcept
	{
		return mColumnCodeSet.GetMemManager();
	}

	size_t GetCount() const noexcept
	{
		return mColumns.GetCount();
	}

	template<typename Item, typename... Items>
	void Add(const QualifiedColumn<Item>& column, const QualifiedColumn<Items>&... columns)
	{
		static const size_t columnCount = 1 + sizeof...(columns);
		std::array<bool, columnCount> columnMutables = {{ column.IsMutable(),
			columns.IsMutable()... }};
		pvAdd(columnMutables.data(), column.GetBaseColumn(), columns.GetBaseColumn()...);
	}

	bool IsMutable(size_t offset) const noexcept
	{
		MOMO_ASSERT(offset < mTotalSize);
		if (offset / 8 >= mMutableOffsets.GetCount())
			return false;
		return (mMutableOffsets[offset / 8] & static_cast<uint8_t>(1 << (offset % 8))) != 0;
	}

	size_t GetTotalSize() const noexcept
	{
		return mTotalSize;
	}

	size_t GetAlignment() const noexcept
	{
		return mAlignment;
	}

	void CreateRaw(Raw* raw)
	{
		pvCreateRaw(nullptr, nullptr, raw);
	}

	void DestroyRaw(Raw* raw) const noexcept
	{
		pvDestroyRaw(nullptr, raw);
	}

	void DestroyRaw(Raw* raw) noexcept
	{
		pvDestroyRaw(&GetMemManager(), raw);
	}

	void ImportRaw(const DataColumnList& srcColumnList, const Raw* srcRaw, Raw* raw)
	{
		pvCreateRaw((&srcColumnList != this) ? &srcColumnList : nullptr, srcRaw, raw);
	}

	template<bool extraCheck = true>
	size_t GetOffset(ColumnInfo columnInfo) const
	{
		ColumnCode code = ColumnTraits::GetColumnCode(columnInfo);
		MOMO_EXTRA_CHECK(!extraCheck || mColumnCodeSet.ContainsKey(code));
		size_t offset = pvGetOffset(code);
		MOMO_ASSERT(offset < mTotalSize);
		//MOMO_ASSERT(offset % ItemTraits::template GetAlignment<Item>() == 0);
		return offset;
	}

	template<typename Item>
	static Item& GetByOffset(Raw* raw, size_t offset) noexcept
	{
		//MOMO_ASSERT(offset < mTotalSize);
		//MOMO_ASSERT(offset % ItemTraits::template GetAlignment<Item>() == 0);
		return *internal::BitCaster::PtrToPtr<Item>(raw, offset);
	}

	template<typename Item, typename ItemArg>
	void Assign(Raw* raw, size_t offset, ItemArg&& itemArg) const
	{
		ItemTraits::Assign(std::forward<ItemArg>(itemArg), GetByOffset<Item>(raw, offset));
	}

	size_t GetNumber(const Raw* raw) const noexcept
	{
		MOMO_STATIC_ASSERT(Settings::keepRowNumber);
		return *internal::BitCaster::PtrToPtr<const size_t>(raw, 0);
	}

	void SetNumber(Raw* raw, size_t number) const noexcept
	{
		MOMO_STATIC_ASSERT(Settings::keepRowNumber);
		*internal::BitCaster::PtrToPtr<size_t>(raw, 0) = number;
	}

	bool Contains(ColumnInfo columnInfo, size_t* resOffset = nullptr) const noexcept
	{
		ColumnCode code = ColumnTraits::GetColumnCode(columnInfo);
		std::pair<size_t, size_t> vertices = ColumnTraits::GetVertices(code, mCodeParam);
		size_t addend1 = mAddends[vertices.first];
		size_t addend2 = mAddends[vertices.second];
		if (addend1 == 0 || addend2 == 0)
			return false;
		if (!mColumnCodeSet.ContainsKey(code))
			return false;
		if (resOffset != nullptr)
			*resOffset = addend1 + addend2;
		return true;
	}

	template<typename PtrVisitor>
	void VisitPointers(const Raw* raw, const PtrVisitor& ptrVisitor) const
	{
		pvVisitPointers<const void>(raw, ptrVisitor);
	}

	template<typename PtrVisitor>
	void VisitPointers(Raw* raw, const PtrVisitor& ptrVisitor) const
	{
		pvVisitPointers<void>(raw, ptrVisitor);
	}

private:
	template<typename... Items>
	void pvAdd(const bool* columnMutables, const Column<Items>&... columns)
	{
		static const size_t columnCount = sizeof...(columns);
		size_t initColumnCount = GetCount();
		if (columnCount + initColumnCount > maxColumnCount)
			throw std::runtime_error("Too many columns");
		std::array<ColumnCode, columnCount> columnCodes = {{
			ColumnTraits::GetColumnCode(columns)... }};
		Addends addends;
		size_t offset;
		size_t alignment;
		size_t codeParam = mCodeParam;
		while (true)
		{
			std::fill(addends.begin(), addends.end(), 0);
			offset = mTotalSize;
			alignment = mAlignment;
			if (pvFillAddends<Items...>(addends, offset, alignment, codeParam, columnCodes.data()))
				break;<commit_msg>Refactoring<commit_after>/**********************************************************\

  This file is distributed under the MIT License.
  See https://github.com/morzhovets/momo/blob/master/LICENSE
  for details.

  momo/DataColumn.h

  macros:
    MOMO_DATA_COLUMN_STRUCT
    MOMO_DATA_COLUMN_STRING_TAG
    MOMO_DATA_COLUMN_STRING

  namespace momo:
    class DataColumn
    class DataColumnInfo
    class DataSettings
    struct DataStructDefault
    class DataColumnTraits
    class DataItemTraits
    class DataColumnList
    class DataColumnListStatic

\**********************************************************/

#pragma once

#include "Array.h"
#include "HashSet.h"

#include <bitset>
#include <typeinfo>

#define MOMO_DATA_COLUMN_STRUCT(Struct, name) \
	constexpr momo::DataColumn<decltype(std::declval<Struct&>().name), Struct> \
	name(uint64_t{offsetof(Struct, name)}, #name)

#define MOMO_DATA_COLUMN_STRING_TAG(Tag, Type, name) \
	MOMO_STATIC_ASSERT(!std::is_class<Tag>::value || std::is_empty<Tag>::value); \
	constexpr momo::DataColumn<Type, Tag> name(momo::internal::StrHasher::GetHashCode64(#name), #name)

#define MOMO_DATA_COLUMN_STRING(Type, name) \
	MOMO_DATA_COLUMN_STRING_TAG(momo::DataStructDefault<>, Type, name)

namespace momo
{

namespace internal
{
	class StrHasher
	{
	private:
		static const uint64_t fnvBasis64 = 14695981039346656037ull;
		static const uint64_t fnvPrime64 = 1099511628211ull;

	public:
		// Fowler-Noll-Vo hash function (1a)
		constexpr static uint64_t GetHashCode64(const char* str) noexcept
		{
			return (*str == '\0') ? fnvBasis64
				: (GetHashCode64(str + 1) ^ uint64_t{static_cast<unsigned char>(*str)}) * fnvPrime64;
		}
	};

	template<typename Struct,
		typename = void>
	struct DataVisitableItemsGetter
	{
		typedef std::tuple<> VisitableItems;
	};

	template<typename Struct>
	struct DataVisitableItemsGetter<Struct, Void<typename Struct::VisitableItems>>
	{
		typedef typename Struct::VisitableItems VisitableItems;
	};

	template<typename TColumn, typename TItemArg>
	class DataOperator
	{
	public:
		typedef TColumn Column;
		typedef TItemArg ItemArg;

	public:
		explicit DataOperator(const Column& column, ItemArg&& itemArg) noexcept
			: mColumn(column),
			mItemArg(std::forward<ItemArg>(itemArg))
		{
		}

#ifndef MOMO_HAS_GUARANTEED_COPY_ELISION
		DataOperator(DataOperator&& oper) noexcept
			: mColumn(oper.mColumn),
			mItemArg(std::forward<ItemArg>(oper.mItemArg))
		{
			//MOMO_ASSERT(false);
		}
#endif

		DataOperator(const DataOperator&) = delete;

		~DataOperator() noexcept
		{
		}

		DataOperator& operator=(const DataOperator&) = delete;

		const Column& GetColumn() const noexcept
		{
			return mColumn;
		}

		ItemArg&& GetItemArg() const noexcept
		{
			return std::forward<ItemArg>(mItemArg);
		}

	private:
		const Column& mColumn;
		ItemArg&& mItemArg;
	};

	template<typename TColumn, typename TItemArg>
	class DataEqualer : public DataOperator<TColumn, TItemArg>
	{
	private:
		typedef DataOperator<TColumn, TItemArg> Operator;

	public:
		using Operator::Operator;
	};

	template<typename TColumn, typename TItemArg>
	class DataAssigner : public DataOperator<TColumn, TItemArg>
	{
	private:
		typedef DataOperator<TColumn, TItemArg> Operator;

	public:
		using Operator::Operator;
	};

	template<typename Item>
	struct DataMutable
	{
	};
}

template<typename TItem, typename TStruct>
class DataColumn : public DataColumn<internal::DataMutable<TItem>, TStruct>
{
public:
	typedef TItem Item;
	typedef TStruct Struct;

	typedef DataColumn BaseColumn;

	typedef DataColumn<internal::DataMutable<Item>, Struct> MutableColumn;

	typedef internal::DataEqualer<DataColumn, const Item&> Equaler;

	template<typename ItemArg>
	using Assigner = internal::DataAssigner<DataColumn, ItemArg>;

public:
	constexpr explicit DataColumn(uint64_t code, const char* name = "") noexcept
		: mCode(code),
		mName(name)
	{
	}

	const BaseColumn& GetBaseColumn() const noexcept
	{
		return *this;
	}

	constexpr uint64_t GetCode() const noexcept
	{
		return mCode;
	}

	constexpr const char* GetName() const noexcept
	{
		return mName;
	}

	constexpr const MutableColumn& Mutable() const noexcept
	{
		return *this;
	}

	constexpr bool IsMutable() const noexcept
	{
		return false;
	}

	Equaler operator==(const Item& item) const noexcept
	{
		return Equaler(*this, item);
	}

	template<typename ItemArg>
	Assigner<ItemArg> operator=(ItemArg&& itemArg) const noexcept
	{
		return Assigner<ItemArg>(*this, std::forward<ItemArg>(itemArg));
	}

private:
	uint64_t mCode;
	const char* mName;
};

template<typename TItem, typename TStruct>
class DataColumn<internal::DataMutable<TItem>, TStruct>
{
public:
	typedef TItem Item;
	typedef TStruct Struct;

	typedef DataColumn<Item, Struct> BaseColumn;

public:
	const BaseColumn& GetBaseColumn() const noexcept
	{
		return static_cast<const BaseColumn&>(*this);
	}

	constexpr bool IsMutable() const noexcept
	{
		return true;
	}

protected:
	constexpr explicit DataColumn() noexcept
	{
	}

	DataColumn(const DataColumn&) = default;

	~DataColumn() = default;

	DataColumn& operator=(const DataColumn&) = default;
};

template<typename TStruct>
class DataColumnInfo
{
public:
	typedef TStruct Struct;

	template<typename Item>
	using Column = DataColumn<Item, Struct>;

	typedef typename internal::DataVisitableItemsGetter<Struct>::VisitableItems VisitableItems;

public:
	template<typename Item>
	DataColumnInfo(const Column<Item>& column) noexcept
		: mCode(column.GetCode()),
		mName(column.GetName()),
		mTypeInfo(typeid(Item))
	{
	}

	uint64_t GetCode() const noexcept
	{
		return mCode;
	}

	const char* GetName() const noexcept
	{
		return mName;
	}

	const std::type_info& GetTypeInfo() const noexcept
	{
		return mTypeInfo;
	}

	template<typename PtrVisitor>
	void Visit(const void* item, const PtrVisitor& ptrVisitor) const
	{
		pvVisitRec<0>(item, ptrVisitor);
	}

	template<typename PtrVisitor>
	void Visit(void* item, const PtrVisitor& ptrVisitor) const
	{
		pvVisitRec<0>(item, ptrVisitor);
	}

private:
	template<size_t index, typename Void, typename PtrVisitor>
	internal::EnableIf<(index < std::tuple_size<VisitableItems>::value)> pvVisitRec(Void* item,
		const PtrVisitor& ptrVisitor) const
	{
		typedef typename std::tuple_element<index, VisitableItems>::type Item;
		typedef typename std::conditional<std::is_const<Void>::value,
			const Item*, Item*>::type ItemPtr;
		if (typeid(Item) == mTypeInfo)
			pvVisit(static_cast<ItemPtr>(item), ptrVisitor);
		else
			pvVisitRec<index + 1>(item, ptrVisitor);
	}

	template<size_t index, typename Void, typename PtrVisitor>
	internal::EnableIf<(index == std::tuple_size<VisitableItems>::value)> pvVisitRec(Void* item,
		const PtrVisitor& ptrVisitor) const
	{
		pvVisit(item, ptrVisitor);
	}

	template<typename Item, typename PtrVisitor>
	internal::EnableIf<internal::IsInvocable2<PtrVisitor, Item*, DataColumnInfo>::value>
	pvVisit(Item* item, const PtrVisitor& ptrVisitor) const
	{
		ptrVisitor(item, *this);
	}

	template<typename Item, typename PtrVisitor>
	internal::EnableIf<!internal::IsInvocable2<PtrVisitor, Item*, DataColumnInfo>::value>
	pvVisit(Item* item, const PtrVisitor& ptrVisitor) const
	{
		ptrVisitor(item);
	}

private:
	uint64_t mCode;
	const char* mName;
	const std::type_info& mTypeInfo;
};

template<bool tKeepRowNumber = true>
class DataSettings
{
public:
	static const CheckMode checkMode = CheckMode::bydefault;
	static const ExtraCheckMode extraCheckMode = ExtraCheckMode::bydefault;
	static const bool checkVersion = MOMO_CHECK_ITERATOR_VERSION;

	static const bool keepRowNumber = tKeepRowNumber;

	typedef ArraySettings<> TableRawsSettings;
	typedef ArraySettings<4, true, true> SelectionRawsSettings;
};

template<typename... TVisitableItems>
struct DataStructDefault
{
	typedef std::tuple<TVisitableItems...> VisitableItems;
};

template<typename TStruct = DataStructDefault<>>
class DataColumnTraits
{
public:
	typedef TStruct Struct;

	typedef DataColumnInfo<Struct> ColumnInfo;
	template<typename Item>
	using Column = typename ColumnInfo::template Column<Item>;

	typedef uint64_t ColumnCode;

	static const size_t logVertexCount = 8;
	static const size_t maxColumnCount = 200;
	static const size_t maxCodeParam = 255;

	typedef HashTraitsOpen<ColumnCode> ColumnCodeHashTraits;

public:
	static std::pair<size_t, size_t> GetVertices(ColumnCode code, size_t codeParam) noexcept
	{
		static const size_t vertexCount1 = (size_t{1} << logVertexCount) - 1;
		size_t shortCode = static_cast<size_t>(code + (code >> 32));
		shortCode ^= (codeParam >> 4) ^ ((codeParam & 15) << 28);
		shortCode += shortCode >> 16;
		size_t vertex1 = shortCode & vertexCount1;
		size_t vertex2 = (shortCode >> logVertexCount) & vertexCount1;
		vertex2 ^= (vertex1 == vertex2) ? 1 : 0;
		return std::make_pair(vertex1, vertex2);
	}
};

template<typename TMemManager>
class DataItemTraits
{
public:
	typedef TMemManager MemManager;

private:
	template<typename Item>
	using ItemManager = internal::ObjectManager<Item, MemManager>;

public:
	template<typename Item>
	static size_t GetSize() noexcept
	{
		return sizeof(Item);
	}

	template<typename Item>
	static size_t GetAlignment() noexcept
	{
		return ItemManager<Item>::alignment;
	}

	template<typename Item>
	static void Create(MemManager& memManager, Item* item)
	{
		(typename ItemManager<Item>::template Creator<>(memManager))(item);
	}

	template<typename Item>
	static void Destroy(MemManager* memManager, Item* item) noexcept
	{
		ItemManager<Item>::Destroyer::Destroy(memManager, *item);
	}

	template<typename Item>
	static void Copy(MemManager& memManager, const Item& srcItem, Item* dstItem)
	{
		ItemManager<Item>::Copy(memManager, srcItem, dstItem);
	}

	template<typename ItemArg, typename Item>
	static void Assign(ItemArg&& itemArg, Item& item)
	{
		item = std::forward<ItemArg>(itemArg);
	}
};

template<typename TColumnTraits = DataColumnTraits<>,
	typename TMemManager = MemManagerDefault,
	typename TItemTraits = DataItemTraits<TMemManager>,
	typename TSettings = DataSettings<>>
class DataColumnList
{
public:
	typedef TColumnTraits ColumnTraits;
	typedef TMemManager MemManager;
	typedef TItemTraits ItemTraits;
	typedef TSettings Settings;

	typedef typename ColumnTraits::ColumnInfo ColumnInfo;
	template<typename Item>
	using Column = typename ColumnTraits::template Column<Item>;

	template<typename Item>
	using QualifiedColumn = Column<Item>;

	typedef void Raw;

	class ColumnRecord : public ColumnInfo
	{
	public:
		explicit ColumnRecord(ColumnInfo columnInfo, size_t offset) noexcept	//?
			: ColumnInfo(columnInfo),
			mOffset(offset)
		{
		}

		size_t GetOffset() const noexcept
		{
			return mOffset;
		}

	private:
		size_t mOffset;
	};

private:
	static const size_t logVertexCount = ColumnTraits::logVertexCount;
	static const size_t maxColumnCount = ColumnTraits::maxColumnCount;
	static const size_t maxCodeParam = ColumnTraits::maxCodeParam;

	static const size_t vertexCount = size_t{1} << logVertexCount;

	class Graph
	{
	private:
		struct Edge
		{
			size_t vertex;
			size_t value;
			Edge* nextEdge;
		};

		static const size_t maxEdgeCount = 2 * maxColumnCount;

	public:
		explicit Graph() noexcept
			: mEdgeNumber(0)
		{
			std::fill(mEdges.begin(), mEdges.end(), nullptr);
		}

		Graph(const Graph&) = delete;

		~Graph() noexcept
		{
		}

		Graph& operator=(const Graph&) = delete;

		void AddEdges(size_t vertex1, size_t vertex2, size_t value) noexcept
		{
			MOMO_EXTRA_CHECK(vertex1 != vertex2);
			pvAddEdge(vertex1, vertex2, value);
			pvAddEdge(vertex2, vertex1, value);
		}

		bool HasEdge(size_t vertex) const noexcept
		{
			return mEdges[vertex] != nullptr;
		}

		bool FillAddends(size_t* addends, size_t vertex) const noexcept
		{
			size_t addend = addends[vertex];
			for (Edge* edge = mEdges[vertex]; edge != nullptr; edge = edge->nextEdge)
			{
				size_t vertex2 = edge->vertex;
				size_t& addend2 = addends[vertex2];
				if (addend2 == 0)
				{
					addend2 = edge->value - addend;
					if (!FillAddends(addends, vertex2))
						return false;
				}
				else
				{
					if (addend + addend2 != edge->value)
						return false;
				}
			}
			return true;
		}

	private:
		void pvAddEdge(size_t vertex1, size_t vertex2, size_t value) noexcept
		{
			MOMO_ASSERT(mEdgeNumber < vertexCount * 2);
			Edge* edge = &mEdgeStorage[mEdgeNumber];
			++mEdgeNumber;
			edge->vertex = vertex2;
			edge->value = value;
			edge->nextEdge = mEdges[vertex1];
			mEdges[vertex1] = edge;
		}

	private:
		size_t mEdgeNumber;
		std::array<Edge, maxEdgeCount> mEdgeStorage;
		std::array<Edge*, vertexCount> mEdges;
	};

	typedef std::array<size_t, vertexCount> Addends;

	typedef typename ColumnTraits::ColumnCode ColumnCode;

	typedef typename ColumnTraits::ColumnCodeHashTraits ColumnCodeHashTraits;

	typedef HashSet<ColumnCode, ColumnCodeHashTraits, MemManager,
		HashSetItemTraits<ColumnCode, MemManager>, internal::NestedHashSetSettings> ColumnCodeSet;

	typedef internal::MemManagerPtr<MemManager> MemManagerPtr;

	typedef internal::NestedArrayIntCap<0, ColumnRecord, MemManagerPtr> Columns;

	typedef std::function<void(MemManager&, const ColumnRecord*, const DataColumnList*,
		const Raw*, Raw*)> CreateFunc;
	typedef std::function<void(MemManager*, const ColumnRecord*, Raw*)> DestroyFunc;

	struct FuncRecord
	{
		size_t columnIndex;
		CreateFunc createFunc;
		DestroyFunc destroyFunc;
	};

	typedef internal::NestedArrayIntCap<0, FuncRecord, MemManagerPtr> FuncRecords;

	typedef internal::NestedArrayIntCap<0, uint8_t, MemManagerPtr> MutableOffsets;

public:
	typedef typename Columns::ConstIterator ConstIterator;
	typedef ConstIterator Iterator;

public:
	explicit DataColumnList(MemManager&& memManager = MemManager())
		: mCodeParam(0),
		mTotalSize(Settings::keepRowNumber ? sizeof(size_t) : 0),
		mAlignment(Settings::keepRowNumber ? internal::AlignmentOf<size_t>::value : 1),
		mColumnCodeSet(ColumnCodeHashTraits(), std::move(memManager)),
		mColumns(MemManagerPtr(GetMemManager())),
		mFuncRecords(MemManagerPtr(GetMemManager())),
		mMutableOffsets(MemManagerPtr(GetMemManager()))
	{
		std::fill(mAddends.begin(), mAddends.end(), 0);
	}

	template<typename Item, typename... Items>
	explicit DataColumnList(const QualifiedColumn<Item>& column,
		const QualifiedColumn<Items>&... columns)
		: DataColumnList()
	{
		Add(column, columns...);
	}

	DataColumnList(DataColumnList&& columnList) noexcept
		: mCodeParam(columnList.mCodeParam),
		mAddends(columnList.mAddends),
		mTotalSize(columnList.mTotalSize),
		mAlignment(columnList.mAlignment),
		mColumnCodeSet(std::move(columnList.mColumnCodeSet)),
		mColumns(std::move(columnList.mColumns)),
		mFuncRecords(std::move(columnList.mFuncRecords)),
		mMutableOffsets(std::move(columnList.mMutableOffsets))
	{
	}

	DataColumnList(const DataColumnList& columnList)
		: mCodeParam(columnList.mCodeParam),
		mAddends(columnList.mAddends),
		mTotalSize(columnList.mTotalSize),
		mAlignment(columnList.mAlignment),
		mColumnCodeSet(columnList.mColumnCodeSet),
		mColumns(columnList.mColumns, MemManagerPtr(GetMemManager())),
		mFuncRecords(columnList.mFuncRecords, MemManagerPtr(GetMemManager())),
		mMutableOffsets(columnList.mMutableOffsets, MemManagerPtr(GetMemManager()))
	{
	}

	~DataColumnList() noexcept
	{
	}

	DataColumnList& operator=(const DataColumnList&) = delete;

	ConstIterator GetBegin() const noexcept
	{
		return mColumns.GetBegin();
	}

	ConstIterator GetEnd() const noexcept
	{
		return mColumns.GetEnd();
	}

	MOMO_FRIENDS_BEGIN_END(const DataColumnList&, ConstIterator)

	const MemManager& GetMemManager() const noexcept
	{
		return mColumnCodeSet.GetMemManager();
	}

	MemManager& GetMemManager() noexcept
	{
		return mColumnCodeSet.GetMemManager();
	}

	size_t GetCount() const noexcept
	{
		return mColumns.GetCount();
	}

	template<typename Item, typename... Items>
	void Add(const QualifiedColumn<Item>& column, const QualifiedColumn<Items>&... columns)
	{
		static const size_t columnCount = 1 + sizeof...(columns);
		std::array<bool, columnCount> columnMutables = {{ column.IsMutable(),
			columns.IsMutable()... }};
		pvAdd(columnMutables.data(), column.GetBaseColumn(), columns.GetBaseColumn()...);
	}

	bool IsMutable(size_t offset) const noexcept
	{
		MOMO_ASSERT(offset < mTotalSize);
		if (offset / 8 >= mMutableOffsets.GetCount())
			return false;
		return (mMutableOffsets[offset / 8] & static_cast<uint8_t>(1 << (offset % 8))) != 0;
	}

	size_t GetTotalSize() const noexcept
	{
		return mTotalSize;
	}

	size_t GetAlignment() const noexcept
	{
		return mAlignment;
	}

	void CreateRaw(Raw* raw)
	{
		pvCreateRaw(nullptr, nullptr, raw);
	}

	void DestroyRaw(Raw* raw) const noexcept
	{
		pvDestroyRaw(nullptr, raw);
	}

	void DestroyRaw(Raw* raw) noexcept
	{
		pvDestroyRaw(&GetMemManager(), raw);
	}

	void ImportRaw(const DataColumnList& srcColumnList, const Raw* srcRaw, Raw* raw)
	{
		pvCreateRaw((&srcColumnList != this) ? &srcColumnList : nullptr, srcRaw, raw);
	}

	template<bool extraCheck = true>
	size_t GetOffset(ColumnInfo columnInfo) const
	{
		ColumnCode code = columnInfo.GetCode();
		MOMO_EXTRA_CHECK(!extraCheck || mColumnCodeSet.ContainsKey(code));
		size_t offset = pvGetOffset(code);
		MOMO_ASSERT(offset < mTotalSize);
		//MOMO_ASSERT(offset % ItemTraits::template GetAlignment<Item>() == 0);
		return offset;
	}

	template<typename Item>
	static Item& GetByOffset(Raw* raw, size_t offset) noexcept
	{
		//MOMO_ASSERT(offset < mTotalSize);
		//MOMO_ASSERT(offset % ItemTraits::template GetAlignment<Item>() == 0);
		return *internal::BitCaster::PtrToPtr<Item>(raw, offset);
	}

	template<typename Item, typename ItemArg>
	void Assign(Raw* raw, size_t offset, ItemArg&& itemArg) const
	{
		ItemTraits::Assign(std::forward<ItemArg>(itemArg), GetByOffset<Item>(raw, offset));
	}

	size_t GetNumber(const Raw* raw) const noexcept
	{
		MOMO_STATIC_ASSERT(Settings::keepRowNumber);
		return *internal::BitCaster::PtrToPtr<const size_t>(raw, 0);
	}

	void SetNumber(Raw* raw, size_t number) const noexcept
	{
		MOMO_STATIC_ASSERT(Settings::keepRowNumber);
		*internal::BitCaster::PtrToPtr<size_t>(raw, 0) = number;
	}

	bool Contains(ColumnInfo columnInfo, size_t* resOffset = nullptr) const noexcept
	{
		ColumnCode code = columnInfo.GetCode();
		std::pair<size_t, size_t> vertices = ColumnTraits::GetVertices(code, mCodeParam);
		size_t addend1 = mAddends[vertices.first];
		size_t addend2 = mAddends[vertices.second];
		if (addend1 == 0 || addend2 == 0)
			return false;
		if (!mColumnCodeSet.ContainsKey(code))
			return false;
		if (resOffset != nullptr)
			*resOffset = addend1 + addend2;
		return true;
	}

	template<typename PtrVisitor>
	void VisitPointers(const Raw* raw, const PtrVisitor& ptrVisitor) const
	{
		pvVisitPointers<const void>(raw, ptrVisitor);
	}

	template<typename PtrVisitor>
	void VisitPointers(Raw* raw, const PtrVisitor& ptrVisitor) const
	{
		pvVisitPointers<void>(raw, ptrVisitor);
	}

private:
	template<typename... Items>
	void pvAdd(const bool* columnMutables, const Column<Items>&... columns)
	{
		static const size_t columnCount = sizeof...(columns);
		size_t initColumnCount = GetCount();
		if (columnCount + initColumnCount > maxColumnCount)
			throw std::runtime_error("Too many columns");
		std::array<ColumnCode, columnCount> columnCodes = {{ ColumnInfo(columns).GetCode()... }};
		Addends addends;
		size_t offset;
		size_t alignment;
		size_t codeParam = mCodeParam;
		while (true)
		{
			std::fill(addends.begin(), addends.end(), 0);
			offset = mTotalSize;
			alignment = mAlignment;
			if (pvFillAddends<Items...>(addends, offset, alignment, codeParam, columnCodes.data()))
				break;
{'fraction_non_alphanumeric': 0.11834394581293285, 'fraction_numerical': 0.008168649635962354, 'mean_word_length': 5.491025852132389, 'pattern_counts': {'":': 0, '<': 317, '<?xml version=': 0, '>': 325, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5958162', 'n_tokens_mistral': 14336, 'n_tokens_neox': 13019, 'n_words': 2872}