#pragma once

namespace JTL // Jack's template library
{
	/*
	size()			����������ǰ�Ĺ�ģ
	get(r)			��ȡ��Ϊr��Ԫ��
	put(r, e)		��e�滻��Ϊr��Ԫ��
	insert(r, e)	e��Ϊ��ΪrԪ�ز��룬ԭ���Ԫ�����κ���
	remove(r)		ɾ����Ϊr��Ԫ�أ����ظ�Ԫ����ԭ��ŵĶ���
	disordered()	�ж�����Ԫ���Ƿ��Ѱ��ǽ�������
	sort()			������Ԫ�ص�λ�ã�ʹ֮���ǽ�������
	find(e)			����Ŀ��Ԫ��e
	search(e)		����Ŀ��Ԫ��e�����ز�����e��������Ԫ��		������������
	deduplicate		�޳��ظ�Ԫ��
	uniquify()		�޳��ظ�Ԫ��									������������
	traverse()		����������ͳһ��������Ԫ�أ����������ɺ�������ָ��
	*/


	typedef int Rank;
	static const int DEFAULT_CAPACITY = 3;

	//template <typename T>
	//void swap(T& a, T& b)
	//{
	//	T t = a;
	//	a = b;
	//	b = t;
	//}

	template <typename T>
	class Vector
	{
	protected:
		Rank	_size;
		int		_capacity;
		T*		_elem;

	public:
		// Constructors
		Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0)
		{
			_elem = new T[_capacity = c];
			for (_size = 0; _size < s; _elem[_size++] = v) {}
		}

		Vector(T const* A, Rank n)
		{
			copy_from(A, 0, n);
		}

		Vector(T const* A, Rank lo, Rank hi)
		{
			copy_from(A, lo, hi);
		}

		Vector(Vector<T> const& V)
		{
			copy_from(V._elem, 0, V._size);
		}

		Vector(Vector<T> const& V, Rank lo, Rank hi)
		{
			copy_from(V._elem, lo, hi);
		}

		// Destructor
		~Vector()
		{
			delete[] _elem;
		}

		// Read only 
		Rank size() const { return _size; }
		bool empty() const { return !_size; }
		int disordered() const;
		Rank find(T const& e, Rank lo, Rank hi) const;
		Rank find(T const& e) const { return find(e, 0, _size); }
		Rank search(T const& e) const { return (0 >= _size) ? -1 : search(e, 0, _size); }
		Rank search(T const& e, Rank lo, Rank hi) const;
		T& operator[] (Rank r) const;
		Vector<T>& operator = (Vector<T> const& V);
		T remove(Rank r);
		int remove(Rank lo, Rank hi);
		Rank insert(Rank r, T const& e);
		Rank insert(T const& e) { return insert(_size, e); }
		void sort(Rank lo, Rank hi);
		void sort() { sort(0, _size); }
		void unsort(Rank lo, Rank hi);
		void unsort() { unsort(0, _size); }
		int deduplicate();	// unsorted
		int uniquify();		// sorted
	protected:
		void copy_from(T const* A, Rank lo, Rank hi);
		void expand();
		void shrink();
		bool bubble(Rank lo, Rank hi);
		void bubble_sort(Rank lo, Rank hi);
		Rank bubble_fast(Rank lo, Rank hi);
		void bubble_sort_fast(Rank lo, Rank hi);
		void merge(Rank lo, Rank mi, Rank hi);
		void merge_sort(Rank lo, Rank hi);

		// Common functions
		static Rank binary_search(T* A, T const& e, Rank lo, Rank hi);
		static Rank fibnacci_search(T* A, T const& e, Rank lo, Rank hi);
		static Rank interpolation_search(T* A, T const& e, Rank lo, Rank hi);
	};
};

#include "vector_implementation.h"