lasersquad/LogEngine2: Простая, быстрая и функциональная C++ библиотека для логирования. Проста в освоении, платформо-независимая, header-only, малое количество кода, работает из коробки.

include/DynamicArrays.h
1 221 строка36 KB
lasersquad0
Preparing to release - updated file headers
21 апр 2025, 13:45
21 апр 2025, 13:456ba4845
/*
 * DynamicArrays.h
 *
 * Copyright 2025, LogEngine2 Project. All rights reserved.
 *
 * See the COPYING file for the terms of usage and distribution.
 */

#ifndef DYNAMIC_ARRAYS_H
#define DYNAMIC_ARRAYS_H

#include <exception> 
#include <string>
#include "Compare.h"

#define valuemin(v1,v2) (((v1)<(v2))?(v1):(v2))
#define valuemax(v1,v2) (((v1)>(v2))?(v1):(v2))

#define DA_EXCEPTION_PREFIX "THArrayException : "
 /*!
  * Class for exceptions. Exceptions of this class are generated by
  * several methods of array classes.
  *
  */
class THArrayException :public std::exception
{
public:
	THArrayException(const char* Message) { Text = Message; whatText = DA_EXCEPTION_PREFIX + std::string(Message); }
	THArrayException(const std::string& Message) { Text = Message; whatText = DA_EXCEPTION_PREFIX + Message; }
	THArrayException(const THArrayException& ex) { Text = ex.Text; whatText = ex.whatText; }
	~THArrayException() noexcept override {} //throw () { }
	THArrayException& operator=(const THArrayException& rhs) { Text = rhs.Text; whatText = rhs.whatText; return *this; }
	virtual std::string getErrorMessage() const { return whatText; }
	const char* what() const noexcept override { return whatText.c_str(); } //throw();
protected:
	THArrayException() {}
private:
	std::string Text;
	std::string whatText; // this is what what() returns as char*
};


//////////////////////////////////////////////////////////////////////
//  AVariant Class Interface
//////////////////////////////////////////////////////////////////////
#ifdef _USE_AVARIANT_

enum AVariantType { vdNull, vdDouble, vdCurrency, vdString, vdInteger, vdDate };

class AVariant {
protected:
	void CopyFrom(const AVariant& v);
public:
	enum AVariantType DataType;
	double AsDouble;
	double AsCurrency;
	std::string AsString;
	int AsInteger;
	int AsDate;

	inline AVariant() { Clear(); }
	AVariant(const AVariant& v) { CopyFrom(v); }
	void operator =(const AVariant& v) { CopyFrom(v); }
	void operator =(const int& v) { SetAsInteger(v); }
	void operator =(const double& v) { SetAsDouble(v); }
	void operator =(const currency& v) { SetAsCurrency(v); }
	void operator =(const std::string& v) { SetAsString(v); }
	inline AVariant(const int v) { SetAsInteger(v); }
	inline AVariant(const double v) { SetAsDouble(v); }
	inline AVariant(const currency v) { SetAsCurrency(v); }
	inline AVariant(std::string& v) { SetAsString(v); }
	inline AVariant(char* v) { SetAsString(v); }
	inline void Clear();
	inline void SetAsDouble(double v);
	inline void SetAsCurrency(const currency v);
	inline void SetAsString(const std::string& v);
	inline void SetAsString(char* v);
	inline void SetAsInteger(const int v);
	inline void SetAsDate(int v);
	void operator +=(AVariant& v);
	bool HaveData();
};

#endif


/*! \brief Class for storing and manipulating raw data types
 * i.e. data which do not have explicit type or the type can be changed dynamically.
 * All that THArrayRaw need to know is ItemSize of stored data. All items should have the same size = ItemSize
 * Very useful to store fields from database table.
 */
class THArrayRaw
{
protected:
	uint	FCount;
	uint	FCapacity;
	uint	FItemSize;
	void*	FMemory;
	void	Error(const uint Value, const uint vmax) const;
	void	Grow();
	void	GrowTo(const uint ToCount);
	void*	CalcAddr(const uint num) const { return (void*)((uint8_t*)FMemory + static_cast<size_t>(num) * FItemSize); }
	[[noreturn]] void	ThrowZeroItemSize() const { throw THArrayException("Error in THArrayRaw: ItemSize cannot be zero!"); }
public:
	THArrayRaw(); // sets ItemSize to default value 1
	THArrayRaw(const uint ItemSize);
	virtual ~THArrayRaw() { ClearMem(); }
	//	void operator=(const THArrayRaw& a);
	void		SetItemSize(const uint ItemSize); 
	uint		GetItemSize() const { return FItemSize; }
	virtual void Clear() { FCount = 0; }
	void		ClearMem();
	uint		Add(const void* pValue) { return Insert(FCount, pValue); }
	void		AddMany(const void* pValue, const uint Count); // pValue should have at least Count*ItemSize bytes length  
	uint		Insert(const uint Index, const void* pValue);
	void		InsertMany(const uint Index, const void* pValue, const uint Count); // pValue should have at least Count*ItemSize bytes length  
	void		Update(const uint Index, const void* pValue);
	void		UpdateMany(const uint Index, const void* pValue, const uint Count); // pValue should have at least Count*ItemSize bytes length  
	void*		GetAddr(const uint num) const { Error(num, FCount); return CalcAddr(num); }
	virtual	void Delete(const uint Index);
	void		Get(const uint num, void* pValue) const;
	void*		GetPointer(const uint num) const { return GetAddr(num); }
	void		Hold() { SetCapacity(FCount); }
	//void		MoveData(const int FromPos, const int Count, const int Offset);
	uint		Count()    const { return FCount; }
	uint		Capacity() const { return FCapacity; }
	void*		Memory()  const { return FMemory; }
	void		Zero() { if (FCount > 0) memset(FMemory, 0, static_cast<size_t>(FCount) * FItemSize); }
	void		SetCapacity(const uint Value);
	void		AddFillValues(const uint Count);
	void		Swap(const uint Index1, const uint Index2);
};


/*!
 * The base for all  the classes in the library. THArrayBase is an
 * abstract class declaring only virtual methods manipulating arrays. It is
 * not a template class therefore it contains only type independent methods
 */

class THArrayBase
{
public:
	static const int NPOS = -1;  // return value that usually mean "item is not found", this value returned by functions like IndexOf()
	virtual ~THArrayBase() {}
	virtual void Error(const uint Value, const uint vmax) const { if (Value >= vmax) throw THArrayException("Element with index " + std::to_string(Value) + " not found!");	}
	virtual uint Add(const void*) = 0;
	//virtual	void	AddMany(const void* Values) = 0; not implememnted
	virtual void AddFillValues(const uint Num) = 0;
	virtual uint Capacity() const = 0;
	virtual uint Count() const = 0;
	virtual void Clear() = 0;
	virtual void ClearMem() = 0;
	virtual	void DeleteValue(const uint Index) = 0;
	virtual uint Insert(const uint Index, const void* Value) = 0;
	virtual uint ItemSize() const = 0;
	virtual void Hold() = 0;
	virtual void SetCapacity(const uint Value) = 0;
	virtual void Zero() = 0;
	virtual void Swap(const uint Index1, const uint Index2) = 0;
	/*	void	Reverse ();
		void	Reverse (int endIndex);*/

};


//////////////////////////////////////////////////////////////////////
//  THArrayStringFix Class Interface
//////////////////////////////////////////////////////////////////////

class THArrayStringFix : public THArrayBase
{
private:
	THArrayRaw data;
protected:
	char* GetAddr(const uint Index) const {	return static_cast<char*>(data.GetAddr(Index));	}
public:
	//	void operator=(const THArrayStringFix& a) {
	//		printf("THArrayStringFix =");
	//	}
	THArrayStringFix(uint Length) { data.SetItemSize(Length); }
	~THArrayStringFix() override { ClearMem(); }
	std::string GetValue(const uint Index) const { std::string s(GetAddr(Index), data.GetItemSize()); return s; }
	void	SetValue(const uint Index, const std::string& Value) { data.Update(Index, Value.c_str()); }
	std::string operator[](const uint Index) const { return GetValue(Index); }
	inline uint	Count() const override { return data.Count(); }
	void	Clear()    override { data.Clear(); }
	void	ClearMem() override { data.ClearMem(); }
	void	Zero()     override { data.Zero(); }
	void	Hold()     override { data.Hold(); }
	void	DeleteValue(const uint Index) override { data.Delete(Index); }
	uint	Add(const void* pValue) override       { return data.Add(pValue); }
	uint	AddValue(const std::string& Value)     { return data.Add(Value.c_str()); }
	void	AddFillValues(const uint Num) override { data.AddFillValues(Num); }
	uint	Insert(const uint Index, const void* Value) override { return data.Insert(Index, Value); }
	void	Swap(const uint Index1, const uint Index2) override { data.Swap(Index1, Index2); }
	uint	AddChars(const void* pValue, const uint len);
	void	Reverse();
};


//////////////////////////////////////////////////////////////////////
//  THArray Class Interface
//////////////////////////////////////////////////////////////////////

template<class T>
class THArray : public THArrayBase
{
private:
	// Cont is a type of container for what iterator is created
	template<class Cont>
	class THArrayIterator //: public std::iterator<std::input_iterator_tag, T>
	{		
		
	public:
		using value_type = typename Cont::item_type;
		using iterator_category = std::random_access_iterator_tag;
		using difference_type = ptrdiff_t;
		using pointer = typename Cont::pointer;
		using reference = typename Cont::reference;

		THArrayIterator(Cont* cont, pointer ptr) : FCont(cont), FPtr(ptr) {}
		THArrayIterator(const THArrayIterator& it) : FCont(it.FCont), FPtr(it.FPtr) {}

		bool operator!=(const THArrayIterator& other) const { return FCont != other.FCont || FPtr != other.FPtr; }
		bool operator==(const THArrayIterator& other) const { return FCont == other.FCont && FPtr == other.FPtr; }
		reference operator*() const { return *FPtr; }
		pointer operator->() const { return FPtr; }

		THArrayIterator& operator++() { /*if (FPtr != FCont->FBegin + FCont->FCount)*/ ++FPtr; return *this; } // Prefix increment
		THArrayIterator operator++(int) { THArrayIterator tmp = *this; ++(*this); return tmp; } // Postfix increment. Return value here should NOT be a reference.
		THArrayIterator& operator+=(const difference_type add) { FPtr += add; return *this; } 

		THArrayIterator& operator--() { /*if (FPtr != FCont->FBegin)*/ --FPtr; return *this; } // prefix decrement
		THArrayIterator operator--(int) { THArrayIterator tmp = *this; --(*this); return tmp; } // return value here should NOT be a reference.
		
		difference_type operator-(const THArrayIterator& right) const { return FPtr - right.FPtr; }
		THArrayIterator operator-(const difference_type diff) const { return THArrayIterator(FCont, FPtr - diff); /*if (FPtr < FCont->FBegin) FPtr = FCont->FBegin; return *this;*/ }
		THArrayIterator operator+(const difference_type diff) const { return THArrayIterator(FCont, FPtr + diff); /*if (FPtr > FCont->FBegin + FCont->FCount) FPtr = FCont->FBegin + FCont->FCount; return *this;*/ }
		
		bool operator<(const THArrayIterator& other) const { return FPtr < other.FPtr; }
	private:
		Cont* FCont{ nullptr };
		pointer FPtr{ nullptr };
	};

protected:
	uint 	FCount;
	uint 	FCapacity; 
	T*		FMemory;
	T*		FBegin;
	uint	GetGrowDelta();
	void	Grow();	/// Grow memory size allocated for elements
	inline bool	EnoughCapacity(const uint numItems) { return FBegin + numItems <= FMemory + FCapacity; }
	inline void	EnsureCapacity(const uint numItems) { if(!EnoughCapacity(numItems)) GrowTo(numItems); }
public:
	using iterator = THArrayIterator<THArray>;
	using const_iterator = THArrayIterator<const THArray>;
	using item_type = T;
	using pointer = T*;
	using reference = T&;


	iterator begin() { return iterator(this, FBegin); }
	iterator end() { return iterator(this, FBegin + FCount); }
	const_iterator cbegin() const { return const_iterator(this, FMemory); }
	const_iterator cend() const   { return const_iterator(this, FMemory + FCount); }

	THArray();
	THArray(std::initializer_list<T> list);
	THArray(const THArray<T>& a);
	~THArray() override { ClearMem(); }
	inline T& operator[](const uint Index) const { return GetValue(Index); }
	THArray<T>& operator=(const THArray<T>& a); // copy constructor
	bool operator==(const THArray<T>& a) const;
	bool operator>(const THArray<T>& a) const;

	//inline	 T* Memory() const { return FMemory; }
	inline uint ItemSize() const override { return sizeof(T); }
	inline uint Count() const override { return FCount; }
	void		Clear() override { FCount = 0; }
	uint		Capacity() const override { return FCapacity; }
	void		Hold() override { SetCapacity(FCount); }
	void		ClearMem() override;
	void		Zero() override;
	void		GrowTo(const uint ToCount);
	void		SetCapacity(const uint Value) override;
	void		SetCount(const uint Value);
	void		SetValue(const uint Index, const T& Value);
	T&			GetValue(const uint Index) const;
	virtual uint InsertValue(const uint Index, const T& Value);
	uint		Insert(const uint Index, const void* Value) override { return InsertValue(Index, *static_cast<const T*>(Value)); }
	void		DeleteValue(const uint Index) override;
	virtual uint AddValue(const T& Value) { return InsertValue(FCount, Value); }
	uint		Add(const void* pValue) override { return AddValue(*static_cast<const T*>(pValue)); }
	inline	 T* GetValuePointer(const uint Index) const;
	//virtual int IndexOf(const T& Value, const Compare<T>& cmp) const { return IndexOfFrom(Value, 0, cmp); }
	template<class Cmp> int IndexOf(const T& Value) const { return IndexOfFrom<Cmp>(Value, 0); }
	template<class Cmp> int	IndexOfFrom(const T& Value, const uint Start) const;
	virtual int IndexOf(const T& Value) const { return IndexOfFrom(Value, 0); }
	virtual int IndexOfFrom(const T& Value, const uint Start) const;
	void		AddFillValues(const uint Num) override;
	virtual inline void Push(const T& Value) { AddValue(Value); }
	virtual inline T    Pop();
	virtual inline T    PopFront();
	virtual T&			Last() const { return GetValue(FCount - 1); }
	inline void			Swap(const uint Index1, const uint Index2) override;
	virtual void		Reverse();
	virtual void		Reverse(uint endIndex); // Reverse till specified element
#ifdef _USE_STREAMS_
	void		SaveToStream(TStream& stre);
#endif

};



//////////////////////////////////////////////////////////////////////
//  THArraySorted Class Interface
//////////////////////////////////////////////////////////////////////

template<class T, class Cmp = Compare<T> >
class THArraySorted : public THArray<T>
{
protected:
	Cmp		FCompare;
private:
	void	SetValue(const uint Index, const T& Value) = delete;
	uint	Insert(const uint Index, const void* Value)   override { return THArray<T>::Insert(Index, Value); }
	void	AddFillValues(const uint Num) override { THArray<T>::AddFillValues(Num); }
	void	Push(const T& Value) override { THArray<T>::Push(Value); }
	T		Pop()	   override { return THArray<T>::Pop(); }
	T		PopFront() override { return THArray<T>::PopFront(); }
	void	Swap(const uint Index1, const uint Index2) override { THArray<T>::Swap(Index1, Index2); }
	void	Reverse() override { THArray<T>::Reverse(); }
	void	Reverse(uint endIndex) override { THArray<T>::Reverse(endIndex); }
	//uint	AddValue(const T& Value, const Compare<T>& Cmp) override { THArray<T>::AddValue(Value, Cmp); };
	//int		IndexOf(const T& Value, const Compare<T>& C) const override { return THArray<T>::IndexOfFrom(Value, 0, C); }
	//int		IndexOfFrom(const T& Value, const uint Start, const Compare<T>& C) const override { return THArray<T>::IndexOfFrom(Value, Start, C); }
protected:
	uint	InsertValue(const uint Index, const T& Value) override { return THArray<T>::InsertValue(Index, Value); }
	int		InternalIndexOfFrom(const T& Value, const uint Start) const;
public:
	uint	AddValue(const T& Value) override;
	int		IndexOfFrom(const T& Value, const uint Start) const override; // { return THArray<T>::IndexOfFrom(Value, Start); }
	int		IndexOf(const T& Value) const override { return this->IndexOfFrom(Value, 0); }

};


//////////////////////////////////////////////////////////////////////
//  THArrayAuto Class Interface
//////////////////////////////////////////////////////////////////////
/**
* This class never generates an exceptions like "Index out of bounds."
* When out of bounds index being requested (read of write), array just extended to the size that covers requested index.
* new space is filled by empty values T().
*/
template<class T>
class THArrayAuto :public THArray<T>
{
protected:
	void	EnsureValue(const int Index);
public:
	void    SetValue(const int Index, const T& Value) override;
	T& GetValue(const int Index) override;
	inline  T* GetValuePointer(const int Index) override;
};

//////////////////////////////////////////////////////////////////////
//  THash Class Interface
//////////////////////////////////////////////////////////////////////


template <class I, class V, class Cmp = Compare<I> >
class THash
{
private:
	template<class Hash>
	class THashIterator
	{
	public:
		using value_type = std::pair<typename Hash::KeyType&, typename Hash::ValueType&>;
		using iterator_category = std::random_access_iterator_tag;
		using difference_type = ptrdiff_t;
		using pointer = value_type*;
		using reference = value_type&;

		//THashIterator(const THashIterator& it) : FCont(it.FCont), FCurIndex(it.FCurIndex) {}
		THashIterator(Hash* cont, uint curr) : FCont(cont), FCurIndex(curr) {}

		bool operator!=(THashIterator const& other) const { return FCont != other.FCont || FCurIndex != other.FCurIndex; }
		bool operator==(THashIterator const& other) const { return FCont == other.FCont && FCurIndex == other.FCurIndex; }
		THashIterator& operator++() { if (FCurIndex < FCont->Count()) ++FCurIndex; return *this; }
		THashIterator& operator--() { if (FCurIndex > 0) --FCurIndex; return *this; }
		difference_type operator-(const THashIterator& right) const { return FCurIndex - right.FCurIndex; }
		THashIterator operator-(const difference_type diff) const { return THArrayIterator(FCont, FCurIndex - diff); }
		THashIterator operator+(const difference_type diff) const { return THArrayIterator(FCont, FCurIndex + diff); }

		value_type operator*() const { return value_type{ FCont->FAKeys[FCurIndex], FCont->FAValues[FCurIndex] }; }
		//value_type* operator->() const { ??? }
	private:
		Hash* FCont{ nullptr };
		uint FCurIndex{ 0 };
	};

	//friend class THashIterator<THash>;
public:
	using KeyType = I;
	using ValueType = V;
	using KeysType = THArraySorted<I, Cmp>;
	using ValuesType = THArray<V>;
	using iterator = THashIterator<THash>;
	//using const_iterator = THArrayIterator<const THash>;
protected:
	KeysType FAKeys;
	ValuesType FAValues;
	Cmp FACompare;
	//void replace(uint i1, uint i2);
public:
	THash() {}
	THash(const THash<I, V, Cmp>& a);
	//THash(uint Capacity) { FAKeys.SetCapacity(Capacity); FAValues.SetCapacity(Capacity); }
	virtual ~THash() {}

	iterator begin() { return iterator(this, 0); }
	iterator end() { return iterator(this, Count()); }

	bool operator==(const THash<I, V, Cmp>& a) const;
	bool operator> (const THash<I, V, Cmp>& a) const;
	V& operator[](const I& key) const { return GetValue(key); }

	I& GetKey(uint Index) const { return FAKeys.GetValue(Index); }
	void	Clear() { FAKeys.Clear(); FAValues.Clear(); }
	void	ClearMem() { FAKeys.ClearMem(); FAValues.ClearMem(); }
	uint	Count() const { return FAKeys.Count(); }
	KeysType& GetKeys() { return FAKeys; }
	ValuesType& GetValues() { return FAValues; }
	bool	IfExists(const I& Key) const;
	void	Delete(const I& Key);
	void	SetValue(const I& Key, const V& Value);
	V& GetValue(const I& Key) const;
	V* GetValuePointer(const I& Key) const;
	void	SetCapacity(const uint Value) { FAKeys.SetCapacity(Value); FAValues.SetCapacity(Value); }
	//void	Reverse();

/*	void Minus(THash<I, V> in);	*/
};


//////////////////////////////////////////////////////////////////////
//  THash2 Class Interface
//////////////////////////////////////////////////////////////////////

template <class I1, class I2, class V, class Cmp = Compare<I1>>
class THash2
{
public:
	using KeyType = I1;
	using KeysArray = THArray<I1>;
	using ValuesArray = THArray<THash<I2, V, Cmp> >;
	using ValuesHash = THash<I2, V, Cmp>;
protected:
	THash<I1, ValuesHash, Cmp> hash;
	uint FCount = 0;
	uint InternalGetCount();
public:
	void Clear() { hash.Clear(); FCount = 0; }
	void SetValue(const I1& Key1);  // use this method when Key2 and Values both empty or not defined
	void SetValue(const I1& Key1, const ValuesHash& Value);
	void SetValue(const I1& Key1, const I2& Key2, const V& Value);
	V& GetValue(const I1& Key1, const I2& Key2);
	ValuesHash& GetValue(const I1& Key1) { return hash.GetValue(Key1); }
	void Delete(const I1& Key1, const I2& Key2);
	void Delete(const I1& Key1);
	bool IfExists(const I1& Key1, const I2& Key2);
	bool IfExists(const I1& Key1) { return hash.IfExists(Key1); }
	inline uint Count() { return FCount; /*hash.Count();*/ }
	I1& GetKey(uint Index) { return hash.GetKey(Index); }
	V* GetValuePointer(const I1& Key1, const I2& Key2);
	ValuesHash* GetValuePointer(const I1& Key1) { return hash.GetValuePointer(Key1); }
	KeysArray& GetAIndexes() { return hash.GetKeys(); }
	ValuesArray& GetAValues() { return hash.GetValues(); }
	void SetCapacity(const uint Value) { hash.SetCapacity(Value); }

	//	void Minus(THash2<I1, I2, V>& in);

};


//////////////////////////////////////////////////////////////////////
//  Typedefs Defines
//////////////////////////////////////////////////////////////////////

typedef THash<std::string, std::string> TStringHash;
typedef THash<std::string, std::string, CompareStringNCase> TStringHashNCase;
typedef THArray<std::string> THArrayString;
typedef THArray<int>* PHArrayInt;
// Splits string to array of strings using Delim as delimiter
void StringToArray(const std::string& str, THArrayString& arr, const char Delim = '\n');
std::string toString(const THArrayString& array);


//////////////////////////////////////////////////////////////////////
//  THArray Class Implementation
//////////////////////////////////////////////////////////////////////

template<class T>
THArray<T>::THArray()
{
	FCount = 0;
	FCapacity = 0;
	FMemory = nullptr;
	FBegin = nullptr;
}

template<class T>
THArray<T>::THArray(const THArray<T>& a) :THArray()
{
	SetCapacity(a.FCount);
	for (uint i = 0; i < a.FCount; i++)
		FBegin[i] = a.FBegin[i];

	FCount = a.FCount;
}

template<class T>
THArray<T>::THArray(std::initializer_list<T> list) :THArray()
{
	for (T item : list)
		AddValue(item);
}

//template<class T>
//void THArray<T>::Error(const uint Value, const uint vmax) const
//{
//	if (Value >= vmax)
//	{
//		//throw THArrayException(std::format("Error in THArray: Element with index {} not found!", Value));
//		throw THArrayException("Error in THArray: Element with index " + IntToStr(Value) + " not found!");
//	}
//}

// calculate grow delta value depending on current array size
template<class T>
uint THArray<T>::GetGrowDelta()
{
	if (FCapacity > 64)
	{
		return FCapacity / 4; // increase by 25% for most cases
	}
	else
	{
		if (FCapacity > 8)
			return 16;
		else
			return 4;
	}
}

/// Grow allocated memory using a special algorithm 
template<class T>
void THArray<T>::Grow()
{
	uint Delta = GetGrowDelta();
	SetCapacity(FCapacity + Delta);
}

// Grows only if not enough Capacity for ToCount elements. if it is grows to either Capacity+25% or to ToCount what is bigger.
template<class T>
void THArray<T>::GrowTo(const uint ToCount)
{
	//if (ToCount <= FCapacity) return; 
	if (EnoughCapacity(ToCount)) return;

	uint Delta = GetGrowDelta();

	//if ((FCapacity + Delta) < ToCount)
	//	Delta = ToCount - FCapacity;
	//SetCapacity(FCapacity + Delta);

	if (FBegin + ToCount > FMemory + FCapacity + Delta)
		SetCapacity(ToCount);
	else
		SetCapacity(FCapacity + Delta);
}

template<class T>
void THArray<T>::SetCapacity(const uint Value)
{
	T* newMemory = nullptr;

	if (Value > 0)
	{
		newMemory = new T[Value];
		for (uint i = 0; i < valuemin(Value, FCount); i++)
			newMemory[i] = FBegin[i];
	}

	delete[] FMemory;
	FMemory = newMemory;
	FBegin  = newMemory;
	FCapacity = Value;
	if (FCapacity < FCount)
		FCount = FCapacity;
}

template<class T>
void THArray<T>::SetCount(const uint Value)
{
	if (Value > FCapacity) GrowTo(Value);
	FCount = Value;
}

template<class T>
void THArray<T>::Reverse()
{
	if (FCount < 2)
		return;

	for (uint i = 0; i < FCount / 2; i++)
	{
		Swap(i, FCount - 1 - i);
	}
}

// Reverse array till specified element
// Elements with index more than endIndex will not be reversed
// After Reverse element with index endIndex will have index 0,
// and element with index 0 will have index endIndex
template<class T>
void THArray<T>::Reverse(uint endIndex)
{
	if (FCount < 2) return;
	if (endIndex == 0) return;

	if (endIndex >= FCount)
		endIndex = FCount - 1;

	for (uint i = 0; i < (endIndex + 1) / 2; i++)
	{
		Swap(i, endIndex - i);
	}
}

template<class T>
THArray<T>& THArray<T>::operator=(const THArray<T>& a)
{
	ClearMem(); //TODO or it is better to call Clear() here to avoid memory reallocations
	SetCapacity(a.FCount);

	//memcpy(FMemory, a.FMemory, sizeof(T) * a.FCount);
	for (uint i = 0; i < a.FCount; i++)
		FBegin[i] = a.FBegin[i];

	FCount = a.FCount;

	return *this;
}

template<class T>
bool THArray<T>::operator==(const THArray<T>& a) const
{
	if (FCount == a.FCount)
		return memcmp(FBegin, a.FBegin, FCount * sizeof(T)) == 0;
	else
		return false;
}

template <class T>
bool THArray<T>::operator>(const THArray<T>& a) const
{
	for (uint i = 0; i < valuemin(FCount, a.Count()); i++)
	{
		if (FBegin[i] > a[i])
			return true;
		else if (a[i] > FBegin[i])
			return false;
	}

	if (FCount > a.Count()) return true;

	return false;
}

template<class T>
void THArray<T>::Zero()
{
	for (uint i = 0; i < FCount; i++)
		FBegin[i] = T();
}

template<class T>
void THArray<T>::ClearMem()
{
	delete[] FMemory;
	FMemory = nullptr;
	FBegin = nullptr;
	FCount = 0;
	FCapacity = 0;
}

template<class T>
void THArray<T>::SetValue(const uint Index, const T& Value)
{
	Error(Index, FCount);
	FBegin[Index] = Value;
}

template<class T>
T& THArray<T>::GetValue(const uint Index) const
{
	Error(Index, FCount);
	return FBegin[Index];
}

template<class T>
uint THArray<T>::InsertValue(const uint Index, const T& Value)
{
	Error(Index, FCount + 1);

	//if (FCount >= FCapacity) Grow();
	EnsureCapacity(FCount + 1);

	if (Index < (FCount >> 1) && // check which part (left or right) of an array is smaller and move data of that part 
		FBegin > FMemory)   // make sure that we have free space on the left 	
	{
		FBegin--;
		for (uint i = 0; i < Index; i++)
			FBegin[i] = FBegin[i + 1];
	}
	else
	{
		for (uint i = FCount; i > Index; i--)
			FBegin[i] = FBegin[i - 1];
	}

	FBegin[Index] = Value;
	FCount++;

	return Index;
}

template<class T>
void THArray<T>::DeleteValue(const uint Index)
{
	Error(Index, FCount);

	//if (Index == 0) PopFront();
	//else if (Index == FCount - 1) Pop();
	//else 
		
	if (Index < (FCount >> 1))  // check which part (left or right) of an array is smaller and move data of part 
  		 //&& FBegin > FMemory))   // make sure that we have free space on the left 	
	{
		for (uint i = Index; i > 0; i--)
			FBegin[i] = FBegin[i - 1];
		FBegin++;
	}
	else
	{
		for (uint i = Index; i < FCount - 1; i++)
			FBegin[i] = FBegin[i + 1];
	}

	FCount--;
}

template<class T>
inline T* THArray<T>::GetValuePointer(const uint Index) const
{
	Error(Index, FCount);
	return FBegin + Index;
}

template<class T>
template<class Cmp>
int THArray<T>::IndexOfFrom(const T& Value, const uint Start) const
{
	Cmp cmp;
	for (uint i = Start; i < FCount; i++)
	{
		T& v = FBegin[i];
		if (cmp.eq(v, Value))
			return static_cast<int>(i);
	}
	return NPOS;
}

template<class T>
int THArray<T>::IndexOfFrom(const T& Value, const uint Start) const
{
	for (uint i = Start; i < FCount; i++)
		if (FBegin[i] == Value)
			return static_cast<int>(i);
	return NPOS;
}

template<class T>
void THArray<T>::AddFillValues(const uint Num)
{
	EnsureCapacity(FCount + Num);
	//if ((FCount + Num) > FCapacity) GrowTo(FCount + Num);

	for (uint i = FCount; i < FCount + Num; i++)
		FBegin[i] = T();
	FCount = FCount + Num;
}

// return last item in array and delete it from array
template<class T>
T	THArray<T>::Pop()
{
	Error(0, FCount); // just check that array is not empty
	FCount--;
	return FBegin[FCount];
}

template<class T>
T	THArray<T>::PopFront()
{
	Error(0, FCount); // just check that array is not empty
	T tmp = FBegin[0];
	FBegin++;   // no need to move data, just move begin pointer
	FCount--;
	//DeleteValue(0);
	return tmp;
}

template<class T>
inline void THArray<T>::Swap(const uint Index1, const uint Index2)
{
	Error(Index1, FCount);
	Error(Index2, FCount);

	if (Index1 == Index2)
		return;

	T temp = FBegin[Index1];
	FBegin[Index1] = FBegin[Index2];
	FBegin[Index2] = temp;
}

#ifdef _USE_STREAMS_
template<class T>
void THArray<T>::SaveToStream(TStream& stre)
{
	stre << FCount;
	stre.Write(FBegin, FCount * sizeof(T));
}
#endif //_USE_STREAMS_


//////////////////////////////////////////////////////////////////////
//  THArraySorted Class Interface
//////////////////////////////////////////////////////////////////////

template <class T, class Cmp>
uint THArraySorted<T, Cmp>::AddValue(const T& Value)
{
	int index = this->InternalIndexOfFrom(Value, 0);
	uint index2 = index < 0 ? static_cast<uint>(-(index + 1)) : static_cast<uint>(index);
	this->InsertValue(index2, Value);

	return index2;
}

template <class T, class Cmp>
int THArraySorted<T, Cmp>::IndexOfFrom(const T& Value, uint Start) const
{
	int index = this->InternalIndexOfFrom(Value, Start);

	return index < 0 ? -1 : index;
}

template <class T, class Cmp>
int THArraySorted<T, Cmp>::InternalIndexOfFrom(const T& Value, const uint Start) const
{
	if (Start >= this->FCount && this->FCount != 0)
	{
		char str[100];
#ifdef WIN32 
		sprintf_s(str, 100, "Error in THArraySorted: Start index %i is out of bounds!", Start);
#else
		sprintf(str, "Error in THArraySorted: Start index %i is out of bounds!", Start);
#endif
		throw THArrayException(str);
	}

	if (this->FCount == 0) return -1;

	uint left = Start, count = this->FCount - Start;
	uint step, middle;

	while (count > 0)
	{
		step = count / 2;
		middle = left + step;
		if (FCompare.mt(Value, this->FBegin[middle]))
		{
			left = middle + 1;
			count -= step + 1;
		}
		else if (FCompare.lt(Value, this->FBegin[middle]))
			count = step;
		else
			return static_cast<int>(middle);
	}

	if (left < this->FCount && FCompare.eq(Value, this->FBegin[left])) return static_cast<int>(left);

	return -static_cast<int>(left + 1);  // return position (with negative sign) where element is going to be according to sorting
}


//////////////////////////////////////////////////////////////////////
//  THArrayAuto Class Implementation
//////////////////////////////////////////////////////////////////////

template<class T>
void THArrayAuto<T>::EnsureValue(const int Index)
{
	if (Index >= this->FCount) AddFillValues(Index - this->FCount + 1);
}

template<class T>
void THArrayAuto<T>::SetValue(const int Index, const T& Value)
{
	EnsureValue(Index);
	SetValue(Index, Value);
}

template<class T>
T& THArrayAuto<T>::GetValue(const int Index)
{
	EnsureValue(Index);
	return THArray<T>::GetValue(Index);
}

template<class T>
inline T* THArrayAuto<T>::GetValuePointer(const int Index)
{
	EnsureValue(Index);
	return THArray<T>::GetValuePointer(Index);
}


//////////////////////////////////////////////////////////////////////
//  THash Class Implementation
//////////////////////////////////////////////////////////////////////


template <class I, class V, class Cmp>
THash<I, V, Cmp>::THash(const THash<I, V, Cmp>& a)
{
	FAKeys = a.FAKeys;
	FAValues = a.FAValues;
	FACompare = a.FACompare;
}

template <class I, class V, class Cmp>
bool THash<I, V, Cmp>::operator==(const THash<I, V, Cmp>& a) const
{
	return (FAKeys == a.FAKeys) && (FAValues == a.FAValues);// && (FACompare == a.FACompare);
}

template <class I, class V, class Cmp>
bool THash<I, V, Cmp>::operator>(const THash<I, V, Cmp>& a) const
{
	return (FAKeys > a.FAKeys) && (FAValues > a.FAValues);// && (a.FACompare == b.FACompare);
}

/*
template <class I, class V>
void THash<I,V>::replace(uint i1, uint i2)
{
	V vtemp = FAValues[i1];
	I itemp = FAKeys[i1];

	FAKeys.SetValue(i1, FAKeys[i2]);
	FAValues.SetValue(i1, FAValues[i2]);
	FAKeys.SetValue(i2, itemp);
	FAValues.SetValue(i2, vtemp);
}

template <class I, class V>
void THash<I,V>::Reverse()
{
	if(FAKeys.Count() < 2)
		return;

	for(uint i = 0; i < FAKeys.Count()/2; i++)
	{
		replace(i, FAKeys.Count() - 1 - i);
	}
}
*/

template <class I, class V, class Cmp>
bool THash<I, V, Cmp>::IfExists(const I& Key) const
{
	return (FAKeys.IndexOf(Key) >= 0);
	//if (FAKeys.IndexOf(Key) != DA_NPOS)
	//	return true; 
	//else 
	//	return false;
}

template <class I, class V, class Cmp>
void THash<I, V, Cmp>::Delete(const I& Key)
{
	int n = FAKeys.IndexOf(Key);
	if (n >= 0)
	{
		FAKeys.DeleteValue((uint)n);
		FAValues.DeleteValue((uint)n);
	}
}

template <class I, class V, class Cmp>
void THash<I, V, Cmp>::SetValue(const I& Key, const V& Value)
{
	int n = FAKeys.IndexOf(Key);
	if (n >= 0)
		FAValues.SetValue(static_cast<uint>(n), Value);
	else
	{
		uint index = FAKeys.AddValue(Key);
		FAValues.InsertValue(index, Value); // insert value in the same position returned by keys
	}
}

template <class I, class V, class Cmp>
V& THash<I, V, Cmp>::GetValue(const I& Key) const
{
	int n = FAKeys.IndexOf(Key);
	if (n < 0)
		throw THArrayException("THash<I,V>::GetValue(Key) : Key not found !");

	return FAValues[(uint)n];
}

template <class I, class V, class Cmp>
V* THash<I, V, Cmp>::GetValuePointer(const I& Key) const
{
	int n = FAKeys.IndexOf(Key);
	if (n < 0)
		return nullptr;
	return FAValues.GetValuePointer((uint)n);
}

/*template <class I,class V>
void THash<I,V>::Minus(THash<I, V> in)
{
	I Key;
	for (int i=0; i<FAKeys.Count(); i++)
	{
		Key = FAKeys.GetValue(i);
		if (in.FAKeys.IndexOf(Key) != -1) FAValues.SetValue(i, FAValues.GetValue(i) - in.FAValues.GetValue(in.FAKeys.IndexOf(Key)));
	}
	for (i=0; i<in.FAKeys.Count(); i++)
	{
		Key = in.FAKeys.GetValue(i);
		if (FAKeys.IndexOf(Key) != -1) continue;
		else SetValue(Key, -in.FAValues.GetValue(i));
	}
}*/


//////////////////////////////////////////////////////////////////////
//  THash2 Class Implementation
//////////////////////////////////////////////////////////////////////

template <class I1, class I2, class V, class Cmp>
uint THash2<I1, I2, V, Cmp>::InternalGetCount()
{
	uint result = 0;

	//for each (I1& a in GetAIndexes())
	//{
	//	ValuesHash& val = hash.GetValue(a);
	//	result += val.Count();
	//}

	KeysArray& ind = GetAIndexes();
	for (uint i = 0; i < ind.Count(); i++)
	{
		I1 a = ind[i];
		ValuesHash& val = hash.GetValue(a);
		result += val.Count();
	}

	return result;
}

template <class I1, class I2, class V, class Cmp>
void THash2<I1, I2, V, Cmp>::SetValue(const I1& Key1, const ValuesHash& Value)
{
	hash.SetValue(Key1, Value);
	FCount = InternalGetCount();
}

// special method when Key2 and Value are empty or do not exist
// in this case we create Key1 empty section only
// nothing is done if Key1 section already exist in THash2
template <class I1, class I2, class V, class Cmp>
void THash2<I1, I2, V, Cmp>::SetValue(const I1& Key1)
{
	if (hash.GetValuePointer(Key1) == nullptr)
	{
		ValuesHash h;
		hash.SetValue(Key1, h);
		//	FCount++;
	}

	// do nothing if Key1 already exist in THash2
}

template <class I1, class I2, class V, class Cmp>
void THash2<I1, I2, V, Cmp>::SetValue(const I1& Key1, const I2& Key2, const V& Value)
{
	ValuesHash* InsH = hash.GetValuePointer(Key1);

	if (InsH != nullptr)
	{
		uint before = InsH->Count();
		InsH->SetValue(Key2, Value);
		uint after = InsH->Count();
		FCount += after - before;
	}
	else
	{
		ValuesHash h;
		h.SetValue(Key2, Value);
		hash.SetValue(Key1, h);
		FCount++;
	}
}

template <class I1, class I2, class V, class Cmp>
V& THash2<I1, I2, V, Cmp>::GetValue(const I1& Key1, const I2& Key2)
{
	ValuesHash* h = hash.GetValuePointer(Key1);
	if (h == nullptr)
		throw THArrayException("THash2::GetValue(Key1, Key2) : Key1 not found !");
	return h->GetValue(Key2);
}

template<class I1, class I2, class V, class Cmp>
inline V* THash2<I1, I2, V, Cmp>::GetValuePointer(const I1& Key1, const I2& Key2)
{
	auto p = hash.GetValuePointer(Key1);
	if (p == nullptr) return nullptr;
	return p->GetValuePointer(Key2);
}

template <class I1, class I2, class V, class Cmp>
void THash2<I1, I2, V, Cmp>::Delete(const I1& Key1, const I2& Key2)
{
	ValuesHash* TempH = hash.GetValuePointer(Key1);
	if (TempH != nullptr)
	{
		TempH->Delete(Key2);
		FCount--;
	}
	/*if(TempH.Count() == 0)
		hash.Delete(Key1);
	else
		hash.SetValue(Key1, TempH);*/
}

template <class I1, class I2, class V, class Cmp>
void THash2<I1, I2, V, Cmp>::Delete(const I1& Key1)
{
	ValuesHash* h = hash.GetValuePointer(Key1);
	int c = 0;
	if (h != nullptr)
		c = h->Count();

	hash.Delete(Key1);
	FCount -= c; //InternalGetCount();
}

template <class I1, class I2, class V, class Cmp>
bool THash2<I1, I2, V, Cmp>::IfExists(const I1& Key1, const I2& Key2)
{
	if (!hash.IfExists(Key1))
		return false;
	return hash.GetValuePointer(Key1)->IfExists(Key2);
}

/*
template <class I1, class I2, class V>
void THash2<I1,I2,V>::Minus(THash2<I1, I2, V>& in)
{
	I2 Key;
	for (int i=0; i<hash.Count(); i++)
	{
		Key = hash.GetKey(i);
		if (in.IfExists(Key))
			hash.GetValue(Key).Minus(in.GetValue(Key));
	}
	for (i=0; i<in.Count(); i++)
	{
		Key = in.GetKey(i);
		if (hash.IfExists(Key))
			continue;
		else
		{
			THash<I2,V> temp = in.GetValue(Key);
			for (int dd=0; dd<temp.Count(); dd++)
				temp.SetValue(temp.GetKey(dd), -temp.GetValue(temp.GetKey(dd)));
			hash.SetValue(Key, temp);
		}
	}
}
*/



#endif //DYNAMIC_ARRAYS_H