/*	
*
*	File:	RsVector.h
*	Author:	tomasb
*	Version 1.0
*	Desc:   Dynamic list
*		
*/

#pragma once


template <class T> class RsVector
{

	void GrowOne()
	{
		if (!m_size) m_size = 4;
		m_size += m_size;

		T* n = new T[m_size];
		for (RtUlong i = 0; i<m_count;i++) {
			n[i] = m_list[i];
		};
		delete [] m_list;
		m_list = n;
	};

	void GrowSpecified(RtUlong s)
	{

		m_size = m_size + s;

		T* n = new T[m_size];
		for (RtUlong i = 0; i<m_count;i++) {
			n[i] = m_list[i];
		};
		delete [] m_list;
		m_list = n;
	};

public:
	T		*m_list;
	RtUlong	m_size;
	RtUlong	m_count;

	RsVector()
	{
		m_size = 0;
		m_count = 0;
		m_list = NULL;
	};

	~RsVector()
	{
		delete [] m_list;
	};

	inline void clear()
	{
		delete [] m_list;
		m_count = 0;
		m_size = 0;
		m_list = NULL;
	};

	inline void release()
	{
		for (RtUlong i = 0; i<m_count;i++) {
			delete m_list[i];
		};
		delete [] m_list;
		m_count = 0;
		m_size = 0;
		m_list = NULL;
	};

	inline void push_back(T v)
	{
		if (m_size == m_count) GrowOne();
		m_list[m_count] = v;
		m_count++;
	};

	inline void pop_back()
	{
		m_count--;
	};

	inline T& pop_get_last() 
	{
		m_count--;
		return m_list[m_count];
	};

	inline void add(const RsVector<T> &v)
	{
		if (m_count + v.m_count > m_size) GrowSpecified(v.m_count);

		for (RtUlong i = 0; i<v.m_count;i++) {
			m_list[m_count++] = v.m_list[i];
		};
	};

	inline void add(const T* v,RtUlong count)
	{
		if (m_count + count > m_size) GrowSpecified(count);

		for (RtUlong i = 0; i<count;i++) {
			m_list[m_count++] = v[i];
		};
	};

	inline void copy(const RsVector<T> &v)
	{
		RtUlong i = v.size();
		AllocateExactSize(i);
		RtUlong j;
		for (j = 0; j<i;j++) {
			m_list[j] = v[j];
		};
		m_count = i;	
	};

	inline void detach()
	{
		m_count = 0;
		m_size = 0;
		m_list = NULL;
	}

	inline void detach(RsVector<T> &v)
	{
		v.clear();
		v.m_list = m_list;  m_list = NULL;
		v.m_size = m_size;  m_size = 0;
		v.m_count = m_count;m_count = 0;
	};

	inline RsVector<T>& operator = (const RsVector<T> &v)
	{
		clear();
		add(v);
		return *this;
	};


	inline T& get_new()
	{
		if (m_size == m_count) GrowOne();
		m_count++;
		return m_list[m_count-1];
	};

	template <class Q> inline void remove(const Q &v)
	{
		for (RtUlong i = 0; i<m_count;i++) {
			if (m_list[i] == v) {
				m_count--;
				m_list[i] = m_list[m_count];
				return;
			};
		};
	};


	template <class Q> inline void remove_shift(const Q &v)
	{
		for (RtUlong i = 0; i<m_count;i++) {
			if (m_list[i] == v) {
				remove_at_shift(i);
				return;
			};
		};
	};

	inline bool contains(const T &v) const
	{
		for (RtUlong i = 0; i<m_count;i++) {
			if (m_list[i] == v) {
				return true;
			};
		};
		return false;
	};

	inline void remove_at(RtUlong i)
	{
		_ASSERT(i < m_count);
		m_count--;
		m_list[i] = m_list[m_count];
	};

	inline void remove_at_shift(RtUlong i)
	{
		_ASSERT(i < m_count);
		m_count--;
		for (;i < m_count;i++) {
			m_list[i] = m_list[i+1];
		};
	};

	inline void insert_after(RtUlong i, T v)
	{
		_ASSERT(i < m_count);
		if (m_size == m_count) GrowOne();

		RtUlong j = m_count;
		i++;
		while (j > i) {
			j--;
			m_list[j+1] = m_list[j];
		};
		m_list[i] = v;
		m_count++;
	};

	inline void insert_before(RtUlong i, T v)
	{
		_ASSERT(i < m_count);
		if (m_size == m_count) GrowOne();

		RtUlong j = m_count;

		while (j > i) {
			j--;
			m_list[j+1] = m_list[j];
		};
		m_list[i] = v;
		m_count++;
	};

	void allocate(RtUlong c)
	{
		m_size = c;

		if (m_count > c) m_count = c;

		if (m_size > 0) {
			T* n = new T[m_size];
			for (RtUlong i = 0; i<m_count;i++) {
				n[i] = m_list[i];
			};
			delete [] m_list;
			m_list = n;
		}
		else {
			delete [] m_list;
			m_list = NULL;
		}
	};

	void optimize_size()
	{
		allocate(m_count);
	};

	inline void preallocate(RtUlong c)	
	{
		_ASSERT(!m_count);	//use allocate for resizing nonempty vector
		m_count = 0;
		if (m_size < c) {
			delete [] m_list;
			m_size = c;
			m_list = new T[m_size];
		};
	};

	inline void AllocateExactSize(RtUlong c)
	{
		m_count = 0;
		if (m_size != c) {
			delete [] m_list;
			m_size = c;
			m_list = new T[m_size];
		};
	};

	inline void AllocateArray(RtUlong c)
	{
		if (m_size < c) allocate(c);
		m_count = c;
	};

	inline RtUlong GetSize() const {return m_size;};

	inline void reset()
	{
		m_count =0;
	};

	inline void set_size(RtUlong c)
	{
		m_count = c;
	};

	inline RtUlong size() const
	{
		return m_count;
	};

	inline T& operator [] (RtUlong index) const 
	{
		_ASSERT(index < m_count);
		return m_list[index];
	};


	void InsertDescending(T v)
	{
		if (m_size == m_count) 
			GrowOne();
		
		//insert sort
		RtUlong c = m_count;
		while (c) {
			if (v > m_list[c-1]) {
				m_list[c] = m_list[c-1];
				c--;
			}
			else break;
		}
		m_list[c] = v;
		m_count++;
	}

	void InsertAscending(T v)
	{
		if (m_size == m_count) 
			GrowOne();

		//insert sort
		RtUlong c = m_count;.
		while (c) {
			if (v < m_list[c-1]) {
				m_list[c] = m_list[c-1];
				c--;
			}
			else break;
		}
		m_list[c] = v;
		m_count++;
	}

	void HeapifyAscending(RtUlong i,RtUlong m_count)
	{
		RtUlong largest = i;								
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<m_count && m_list[largest] < m_list[q]) largest = q;
			q = 2*i+2;													
			if (q<m_count && m_list[largest] < m_list[q]) largest = q;
			if (largest == i) return;									
			T p = m_list[largest];									
			m_list[largest] = m_list[i];	
			m_list[i] = p;															
			i = largest;																
		} while (true);																	
	};

	void SortAscending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) HeapifyAscending(i-1,m_count);
		for (i = m_count-1;i>0;i--) {
			T p = m_list[0];
			m_list[0] = m_list[i];
			m_list[i] = p;
			HeapifyAscending(0,i);
		};
	};					

	void SortAscending(RtUlong start, RtUlong stop)
	{
		RtUlong size = stop - start;
		if (size <= 1) return;
		RtUlong old_cnt = m_count;

		m_list += start;
		m_count = size;

		SortAscending();

		m_count = old_cnt;
		m_list -= start;

	};	

	void MergeAscending(const RsVector<T> &dst)
	{
		allocate(m_count+ dst.m_count);

		RtUlong dwPtr1 = m_count;
		RtUlong dwPtr2 = dst.m_count;
		RtUlong dwDst = dwPtr1 + dwPtr2;

		while (dwPtr1 && dwPtr2) {
			if (m_list[dwPtr1-1] < dst.m_list[dwPtr2-1]) {
				dwPtr2--;
				dwDst--;
				m_list[dwDst] = dst.m_list[dwPtr2];
			}
			else {
				dwPtr1--;
				dwDst--;
				m_list[dwDst] = m_list[dwPtr1];
			};
		}

		if (dwPtr1) {
			//do nothing as items are on its place
		}
		else if (dwPtr2) {
			//copy remaining dst items
			for (dwDst = 0; dwDst < dwPtr2;dwDst++) {
				m_list[dwDst] = dst.m_list[dwDst];
			};
		}

	}

	void ListHeapifyAscending(RtUlong i,RtUlong count)
	{
		RtUlong largest = i;								
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<count && *m_list[largest] < *m_list[q]) largest = q;
			q = 2*i+2;													
			if (q<count && *m_list[largest] < *m_list[q]) largest = q;
			if (largest == i) return;									
			T p = m_list[largest];									
			m_list[largest] = m_list[i];	
			m_list[i] = p;															
			i = largest;																
		} while (true);																	
	};

	void ListSortAscending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) ListHeapifyAscending(i-1,m_count);
		for (i = m_count-1;i>0;i--) {
			T p = m_list[0];
			m_list[0] = m_list[i];
			m_list[i] = p;
			ListHeapifyAscending(0,i);
		};
	};																					

	void HeapifyDescending(RtUlong i,RtUlong count)
	{
		RtUlong smallest = i;
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<count && m_list[smallest] > m_list[q]) smallest = q;
			q = 2*i+2;													
			if (q<count && m_list[smallest] > m_list[q]) smallest = q;
			if (smallest == i) return;
			T p = m_list[smallest];	
			m_list[smallest] = m_list[i];
			m_list[i] = p;
			i = smallest;																
		} while (true);																	
	};

	void SortDescending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) HeapifyDescending(i-1,m_count);
		for (i = m_count-1;i>0;i--) {
			T p = m_list[0];
			m_list[0] = m_list[i];
			m_list[i] = p;
			HeapifyDescending(0,i);
		};
	};																					

	void SortDescending(RtUlong start, RtUlong stop)
	{
		RtUlong size = stop - start;
		if (size <= 1) return;
		RtUlong old_cnt = m_count;

		m_list += start;
		m_count = size;

		SortDescending();

		m_count = old_cnt;
		m_list -= start;
	};				

	void ListHeapifyDescending(RtUlong i,RtUlong m_count)
	{
		RtUlong smallest = i;
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<m_count && *m_list[smallest] > *m_list[q]) smallest = q;
			q = 2*i+2;													
			if (q<m_count && *m_list[smallest] > *m_list[q]) smallest = q;
			if (smallest == i) return;
			T p = m_list[smallest];	
			m_list[smallest] = m_list[i];
			m_list[i] = p;
			i = smallest;																
		} while (true);																	
	};

	void ListSortDescending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) ListHeapifyDescending(i-1,m_count);
		for (i = m_count-1;i>0;i--) {
			T p = m_list[0];
			m_list[0] = m_list[i];
			m_list[i] = p;
			ListHeapifyDescending(0,i);
		};
	};																					

	void ListCreateQueueAscending(RtUlong i,RtUlong m_count)
	{
		RtUlong smallest = i;
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<m_count && *m_list[q] < *m_list[smallest]) smallest = q;
			q = 2*i+2;													
			if (q<m_count && *m_list[q] < *m_list[smallest]) smallest = q;
			if (smallest == i) return;
			T p = m_list[smallest];	
			m_list[smallest] = m_list[i];
			m_list[i] = p;
			i = smallest;																
		} while (true);																	
	};

	void ListCreateQueueAscending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) ListCreateQueueAscending(i-1,m_count);
		
	};		

	void ListUpdateQueueAscending(RtUlong idx, RtUlong count)
	{
		T pItem = m_list[idx];
		RtUlong top, p1,p2, nxt;
		top = (count-1) / 2;
		while (idx < top) {
			p1 = 2*idx+1;
			p2 = p1+1;

			if (p1 < count && *m_list[p1] < *pItem) {
				if (p2 < count && *m_list[p2] < *m_list[p1]) {
					nxt = p2;
				}
				else nxt = p1;
			}
			else if (p2 < count && *m_list[p2] < *pItem) {
				nxt = p2;
			}
			else break;
			m_list[idx] = m_list[nxt];
			idx = nxt;
		};
		m_list[idx] = pItem;	
	};

	void CreateQueueAscending(RtUlong i,RtUlong m_count)
	{
		RtUlong smallest = i;
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<m_count && m_list[q] < m_list[smallest]) smallest = q;
			q = 2*i+2;													
			if (q<m_count && m_list[q] < m_list[smallest]) smallest = q;
			if (smallest == i) return;
			T p = m_list[smallest];	
			m_list[smallest] = m_list[i];
			m_list[i] = p;
			i = smallest;																
		} while (true);																	
	};

	void CreateQueueAscending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) CreateQueueAscending(i-1,m_count);
	};		

	void CreateQueueDescending(RtUlong i,RtUlong m_count)
	{
		RtUlong smallest = i;
		RtUlong q;										
		do {											
			q = 2*i+1;									
			if (q<m_count && m_list[q] > m_list[smallest]) smallest = q;
			q = 2*i+2;													
			if (q<m_count && m_list[q] > m_list[smallest]) smallest = q;
			if (smallest == i) return;
			T p = m_list[smallest];	
			m_list[smallest] = m_list[i];
			m_list[i] = p;
			i = smallest;																
		} while (true);																	
	};

	void CreateQueueDescending()
	{
		if (!m_count) return;
		RtUlong cnt = m_count / 2;
		RtUlong i;
		for (i = cnt;i>0;i--) CreateQueueDescending(i-1,m_count);

	};		

	void UpdateQueueAscending(RtUlong idx, RtUlong count)
	{
		T pItem = m_list[idx];
		RtUlong top, p1,p2, nxt;
		top = (count-1) / 2;
		while (idx < top) {
			p1 = 2*idx+1;
			p2 = p1+1;

			if (p1 < count && m_list[p1] < pItem) {
				if (p2 < count && m_list[p2] < m_list[p1]) {
					nxt = p2;
				}
				else nxt = p1;
			}
			else if (p2 < count && m_list[p2] < pItem) {
				nxt = p2;
			}
			else break;
			m_list[idx] = m_list[nxt];
			idx = nxt;
		};
		m_list[idx] = pItem;	
	};

	void UpdateQueueDescending(RtUlong idx, RtUlong count)
	{
		T pItem = m_list[idx];
		RtUlong top, p1,p2, nxt;
		top = (count-1) / 2;
		while (idx < top) {
			p1 = 2*idx+1;
			p2 = p1+1;

			if (p1 < count && m_list[p1] > pItem) {
				if (p2 < count && m_list[p2] > m_list[p1]) {
					nxt = p2;
				}
				else nxt = p1;
			}
			else if (p2 < count && m_list[p2] > pItem) {
				nxt = p2;
			}
			else break;
			m_list[idx] = m_list[nxt];
			idx = nxt;
		};
		m_list[idx] = pItem;	
	};

	void UpdateQueueBottomAscending(RtUlong idx)
	{
		if (!idx)
			return;

		T pe = m_list[idx];
		RtUlong parent;
		//traverse heap to parent
		while (idx > 0) {
			parent = (idx-1) / 2;
			if (m_list[parent] < pe) 
				break;
			m_list[idx] = m_list[parent];
			idx = parent;
		};
		m_list[idx] = pe;			
	}

	void UpdateQueueBottomDescending(RtUlong idx)
	{
		if (!idx)
			return;

		T pe = m_list[idx];
		RtUlong parent;
		//traverse heap to parent
		while (idx > 0) {
			parent = (idx-1) / 2;
			if (m_list[parent] > pe) 
				break;
			m_list[idx] = m_list[parent];
			idx = parent;
		};
		m_list[idx] = pe;			
	}

	void Save(IStream *pStream)
	{
		pStream->Write(&m_count, sizeof(m_count), NULL);
		pStream->Write(m_list,sizeof(T) * m_count,NULL);
	};

	void Read(IStream *pStream)
	{
		RtUlong c;
		pStream->Read(&c, sizeof(c), NULL);
		AllocateArray(c);
		pStream->Read(m_list,sizeof(T) * c,NULL);
	};

	void copy_to(T *out)
	{
		memcpy(out,m_list,sizeof(T)*m_count);
	};
};

