roslov_1lab

#include <iostream>
#include <ostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <random>

using namespace std;

template <typename TElement> class Sequence {
public:
	virtual void Append(TElement item) = 0;
	virtual void Prepend(TElement item) = 0;
	virtual void InsertAt(int index, TElement item) = 0;
	virtual int getLength() = 0;
	virtual int getIsEmpty() = 0;
	virtual TElement Get(int index) = 0;
	virtual TElement GetFirst() = 0;
	virtual TElement GetLast() = 0;
	virtual void Remove(TElement item) = 0;
	virtual void Swap(int i, int j) = 0;
	virtual void Show() = 0;

};

template <typename TElement> struct Node //узел
{
	TElement value;
	Node<TElement>* next;
	Node<TElement>* prev;//Указатели на адреса следующего и предыдущего элементов списка
};

template <typename TElement> class ListSequence : public Sequence<TElement> {
private:
	int Length;
	Node<TElement>* head;
	Node<TElement>* tail;
public:

	ListSequence()
	{
		head = nullptr;
		tail = nullptr;
		Length = 0;
	}

	virtual void Append(TElement item) override
	{
		struct Node<TElement>* temp;
		temp = new Node<TElement>;
		temp->value = item;
		if (head == nullptr) { //если список пустой
			head = temp;
			tail = temp;
			head->prev = nullptr;
			tail->next = nullptr;
			Length = 1;
		}
		else { //список не пустой
			temp->prev = tail;
			tail->next = temp;
			tail = temp;
			tail->next = nullptr;
			Length += 1;
		}
	}

	virtual void Prepend(TElement item)override
	{
		struct Node<TElement>* temp;
		struct Node<TElement>* p = head;
		temp = new Node<TElement>;
		temp->prev = nullptr;
		temp->value = item;
		if (head == nullptr) { //если список пустой
			head = temp;
			tail = temp;
			temp->next = nullptr;
			Length = 1;
		}
		else { //список не пустой
			p->prev = temp;
			temp->next = head;
			head = temp;
			Length += 1;

		}
	}

	virtual void InsertAt(int index, TElement item) override
	{
		index = index + 1;
		if (index == 1) return Prepend(item);
		if (index == Length + 1) return Append(item);
		if (index < 1 || index > Length + 1)
			cout << "This index out of length" << endl;
		else {
			struct Node<TElement>* temp1;
			struct Node<TElement>* p3;
			temp1 = new Node<TElement>;
			int i;
			p3 = head;
			for (i = 1; i < index; i++) {
				p3 = p3->next;
			}
			temp1->value = item;
			temp1->prev = p3->prev;
			temp1->next = p3;
			p3 = p3->prev;
			p3->next = temp1;
			p3 = temp1->next;
			p3->prev = temp1;
			Length++;
		}
	}

	virtual int getLength() override
	{
		return Length;
	}

	virtual int getIsEmpty() override
	{
		if (Length == 0) {
			cout << "Sequence is empty" << endl;
			return 1;
		}
		else {
			cout << "Sequence isn't empty" << endl;
			return -1;
		}
	}

	virtual TElement Get(int index) override
	{
		if ((Length <= index) || (index < 0)) {
			cout << "Element with index " << index << " didn't find" << endl;
			return -1;
		}
		else {
			int i;
			Node<TElement>* temp;
			temp = head;
			for (i = 0; i < index; i++) {
				temp = temp->next;
			}
			return temp->value;
		}
	}

	virtual TElement GetFirst() override
	{
		return Get(0);
	}

	virtual TElement GetLast() override
	{
		return Get(Length - 1);
	}

	virtual void Remove(TElement item) override //по значению
	{
		int i;
		Node<TElement>* p = head;
		Node<TElement>* p2 = head;
		if (head->value == item) {
			RemoveFirst();
			Length -= 1;
		}
		else {
			for (i = 1; i < Length; i++) {
				if (!p->next) {
					break;
				}
				if ((p->next->value == item) && (p->next->next != nullptr)) {
					Length -= 1;
					p->next = p->next->next;
					p = p->next;
					p->prev = p2;
					break;
				}
				if ((p->next->value == item) && (p->next->next == nullptr)) {
					RemoveLast();
					break;
				}
				p = p->next;
				p2 = p2->next;
			}
		}
	}

	void RemoveIndex(TElement index)
	{
		int i;
		Node<TElement>* p = head;
		Node<TElement>* p2 = head;
		if (index >= Length || index < 0) {
			cout << "Out of lenght" << endl;
		}
		else
		{
			if (index == 0) RemoveFirst();
			else {
				if (index == Length - 1) RemoveLast();
				else
				{
					for (i = 0; i < index - 1; i++)
					{
						p = p->next;
						p2 = p2->next;
					}
					p2 = p2->next->next;
					p->next = p2;
					p2->prev = p;
				}
			}
			Length -= 1;
		}
	}

	void RemoveFirst()
	{
		if (head == tail) {
			head = nullptr;
			tail = nullptr;
		}
		else {
			Node<TElement>* q = head;
			head = q->next;
			q->next->prev = head;
		}
	}
	void RemoveLast()
	{
		Node<TElement>* l = tail;
		tail = l->prev;
		l->prev->next = tail;
		tail->next = nullptr;
	}

	ListSequence GetSubsequence(int startIndex, int endIndex)
	{
		ListSequence B;
		Node<TElement>* p = head;
		if ((startIndex < 0) || (endIndex < 0) || (endIndex < startIndex) || (endIndex >= Length)) {
			cout << "Error with index" << endl;
		}
		else {
			for (int i = 0; i < startIndex; i++) {
				p = p->next;
			}
			for (int j = startIndex; j <= endIndex; j++) {
				B.Append(p->value);
				p = p->next;
			}
		}
		return B;
	}

	virtual void Swap(int i, int j) override
	{
		int a, b;
		a = Get(i);
		b = Get(j);
		RemoveIndex(i);
		RemoveIndex(j - 1);
		InsertAt(i, b);
		InsertAt(j, a);
	}

	virtual void Show() override
	{
		Node<TElement>* temp = head;
		while (temp != nullptr) {
			cout << temp->value << " ";
			temp = temp->next;
		}
		cout << endl;
	}

	~ListSequence() {}
};

template <typename TElement> class ArraySequence
	: public Sequence<TElement>
{
private:
	TElement* point; // указатель на массив
	int Length; // размер массива

public:
	ArraySequence()
	{
		Length = 0; // по умолчанию размер массива = 10 элементов
		point = new TElement[Length]; // выделить место в памяти для массива
	}

	virtual void Append(TElement item) override
	{
		int i;
		TElement* tmp;
		tmp = new TElement[Length]; // выделяем память
		for (i = 0; i < Length; i++) {
			tmp[i] = point[i];
		}
		Length = Length + 1; // увеличиваем размер массива на 1
		point = new TElement[Length];
		for (i = 0; i < Length - 1; i++) {
			point[i] = tmp[i];
		}
		point[Length - 1] = item;
		delete[] tmp;
	}

	virtual void Prepend(TElement item) override
	{
		int i;
		TElement* tmp;
		tmp = new TElement[Length]; // выделяем память
		for (i = 0; i < Length; i++) {
			tmp[i] = point[i];
		}
		Length = Length + 1; // увеличиваем размер массива на 1
		point = new TElement[Length];
		point[0] = item;
		for (i = 1; i < Length; i++) {
			point[i] = tmp[i - 1];
		}
		delete[] tmp;
	}

	virtual void InsertAt(int index, TElement item) override
	{
		if ((Length + 1 <= index) || (index < 0)) {
			cout << "This index out of length" << endl;
		}
		else {
			int i;
			TElement* tmp;
			tmp = new TElement[Length]; // выделяем память
			for (i = 0; i < Length; i++) {
				tmp[i] = point[i];
			}
			Length = Length + 1; // увеличиваем размер массива на 1
			delete[] point;
			point = new TElement[Length];
			for (i = 0; i < index && i < Length; i++)
				point[i] = tmp[i];
			point[index] = item;
			for (i = index + 1; i < Length; i++)
				point[i] = tmp[i - 1];
			delete[] tmp;
		}
	}

	virtual int getLength() override
	{
		return Length;
	}

	virtual int getIsEmpty() override
	{
		if (Length == 0) {
			cout << "Sequence is empty" << endl;
			return 1;
		}
		else {
			cout << "Sequence isn't empty" << endl;
			return -1;
		}
	}

	virtual TElement Get(int index) override
	{
		if ((Length <= index) || (index < 0)) {
			cout << "Element with index " << index << " didn't find" << endl;
			return -1;
		}
		else {
			return point[index];
		}
	}

	virtual TElement GetFirst() override
	{
		if (Length != 0) {
			return point[0];
		}
		else {
			cout << "Sequance is empty" << endl;
			return -1;
		}
	}

	virtual TElement GetLast() override
	{
		if (Length != 0) {
			return point[Length - 1];
		}
		else {
			cout << "Sequance is empty" << endl;
			return -1;
		}
	}

	virtual void Remove(TElement item) override
	{
		int i = 0, index, key = 0;
		while (i < Length) {
			if (point[i] == item) {
				index = i;
				i = Length;
				key = 1;
			}
			i++;
		}
		if (key) { //удаляем
			TElement* tmp;
			tmp = new TElement[Length];
			for (i = 0; i < Length; i++) {
				tmp[i] = point[i];
			}
			Length = Length - 1;
			point = new TElement[Length];
			for (i = 0; i < index && i < Length; i++) {
				point[i] = tmp[i];
			}
			for (i = index; i < Length; i++) {
				point[i] = tmp[i + 1];
			}
		}
	}

	void RemoveIndex(TElement index)
	{
		int i;
		TElement* tmp;
		tmp = new TElement[Length];
		for (i = 0; i < Length; i++) {
			tmp[i] = point[i];
		}
		Length = Length - 1;
		delete[] point;
		point = new TElement[Length];
		for (i = 0; i < index && i < Length; i++) {
			point[i] = tmp[i];
		}
		for (i = index; i < Length; i++) {
			point[i] = tmp[i + 1];
		}
		delete[] tmp;
	}

	ArraySequence GetSubsequence(int startIndex, int endIndex)
	{
		ArraySequence B;
		if ((startIndex < 0) || (endIndex < 0) || (endIndex < startIndex) || (endIndex >= Length)) {
			cout << "Error with index" << endl;
		}
		else {
			for (int i = startIndex; i <= endIndex; i++) {
				B.Append(point[i]);
			}
		}
		return B;
	}

	virtual void Swap(int i, int j) override
	{
		int a, b;
		a = Get(i);
		b = Get(j);
		RemoveIndex(i);
		RemoveIndex(j - 1);
		InsertAt(i, b);
		InsertAt(j, a);
	}

	virtual void Show() override
	{
		int i;
		for (i = 0; i < Length; i++) {
			cout << point[i] << " ";
		}
		cout << endl;
	}

	~ArraySequence() {}
};

template <typename TElement> class Sorter {
public:
	virtual void Sort(Sequence<TElement>&) = 0;

};

template <typename TElement, typename Cmp>
class InsertionSort
	: public Sorter<TElement>
{
private:
	Cmp m_compare;

public:
	InsertionSort() = delete;
	InsertionSort(Cmp cmp) : m_compare(cmp)
	{}; //конструктор
	InsertionSort(const InsertionSort&) = default;
	InsertionSort& operator=(const InsertionSort&) = default; //оператор копирования
	void Sort(Sequence<TElement>& seq) override
	{
		int i, j;
		for (i = 1; i < seq.getLength(); i++) //первый элемент не трогаем
		{
			for (j = i; j > 0 && m_compare(seq.Get(j - 1), seq.Get(j)) == 1; j--) //ищем место для вставки
			{
				seq.Swap(j - 1, j);
			}
		}
	};
};

template <typename TElement, typename Cmp>
class HeapSort
	: public Sorter<TElement>
{
private:
	Cmp m_compare;

	void MaxHeapify(Sequence<TElement>& seq, int n, int i)
	{
		int l, r, largest = i;
		l = 2 * i + 1; //левый
		r = 2 * i + 2; //правый

		// Если левый дочерний элемент больше корня
		if ((l < n) && (m_compare(seq.Get(l), seq.Get(largest)) == 1))
		{
			largest = l;
		}

		// Если правый дочерний элемент больше, чем самый большой элемент на данный момент
		if ((r < n) && (m_compare(seq.Get(r), seq.Get(largest)) == 1))
		{
			largest = r;
		}

		// Если самый большой элемент не корень
		if (largest != i)
		{
			seq.Swap(i, largest);
			MaxHeapify(seq, n, largest);
		}
	}


public:
	HeapSort() = delete;
	HeapSort(Cmp cmp) : m_compare(cmp)
	{}; //конструктор
	HeapSort(const HeapSort&) = default;
	HeapSort& operator=(const HeapSort&) = default; //оператор копирования
	void Sort(Sequence<TElement>& seq) override
	{
		int n = seq.getLength();

		int i;

		for (i = n / 2 - 1; i >= 0; i--)
		{
			MaxHeapify(seq, n, i);
		}

		for (i = n - 1; i > 0; i--)
		{
			seq.Swap(0, i);
			MaxHeapify(seq, i, 0);
		}
	}
};


int randomazer(int min, int max)
{
	static random_device rd;
	static mt19937 generator(rd());
	static uniform_int_distribution<> distribution(min, max);

	return distribution(generator);
}

void test1(ArraySequence<int> A, ArraySequence<int> A2)
{
	A.getIsEmpty();
	A.getLength();
	cout << endl;
	A.Append(23);
	A.getLength();
	A.GetFirst();
	A.GetLast();
	A.Get(0);
	A.Get(-1);
	A.Get(1);
	cout << endl;
	A.Append(43);
	A.Show();
	A.getLength();
	A.GetFirst();
	A.GetLast();
	A.Get(0);
	A.Get(1);
	A.Get(-1);
	A.Get(2);
	cout << endl;
	A.Prepend(53);
	A.getLength();
	A.GetFirst();
	A.GetLast();
	A.Get(0);
	A.Get(1);
	A.Get(-1);
	A.Get(3);
	cout << endl;
	A2 = A.GetSubsequence(1, 1);
	A2.getLength();
	A2.GetFirst();
	A2.GetLast();
	cout << endl;
}

void test2(ListSequence<int> A, ListSequence<int> A2)
{
	A.getIsEmpty();
	A.getLength();
	cout << endl;
	A.Append(23);
	A.getLength();
	A.GetFirst();
	A.GetLast();
	A.Get(0);
	A.Get(-1);
	A.Get(1);
	cout << endl;
	A.Append(43);
	A.Show();
	A.getLength();
	A.GetFirst();
	A.GetLast();
	A.Get(0);
	A.Get(1);
	A.Get(-1);
	A.Get(2);
	cout << endl;
	A.Prepend(53);
	A.getLength();
	A.GetFirst();
	A.GetLast();
	A.Get(0);
	A.Get(1);
	A.Get(-1);
	A.Get(3);
	cout << endl;
	A2 = A.GetSubsequence(1, 1);
	A2.getLength();
	A2.GetFirst();
	A2.GetLast();
	cout << endl;
}

void lab0()
{
	int i = 1;
	while (i) {
		cout << "Which Sequence do you want?" << endl;
		cout << "1 - Array Sequance" << endl;
		cout << "2 - List Sequance" << endl;
		cout << "0 - EXIT" << endl;
		int n;
		cin >> n;
		cout << endl;
		ArraySequence<int> A1;
		ArraySequence<int> A2;
		ListSequence<int> B1;
		ListSequence<int> B2;
		switch (n) {
		case 1:
			test1(A1, A2);
			break;
		case 2:
			test2(B1, B2);
			break;
		case 0:
			i = 0;
			break;
		default:
			break;
		}
	}
}

int main()
{
	unsigned int start_time;
	unsigned int end_time = clock(); // конечное время
	unsigned int search_time;
	auto cmp = [](int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); };
	InsertionSort<int, decltype(cmp)> InsSorter(cmp); //InsSorter - обьект сортировки
	HeapSort<int, decltype(cmp)> HeapSorter(cmp);
	//shSorter.Sort(seq2);
	ArraySequence<int> ArSeqInser;
	ListSequence<int> ListSeqInser;
	ArraySequence<int> ArSeqHeap;
	ListSequence<int> ListSeqHeap;

	int LenghtOfSequance = 20;

	int k; //Заполнение списка рандомными числами

	for (int y = 0; y < LenghtOfSequance; y++) {
		k = randomazer(-10, 10);
		ArSeqHeap.Append(k);
		ListSeqHeap.Append(k);
		ArSeqInser.Append(k);
		ListSeqInser.Append(k);
	}

	int i = 1, j;
	while (i)
	{
		cout << "Which sort do you want?" << endl;
		cout << "1 - Intersection sort" << endl;
		cout << "2 - Heapsort" << endl;
		cout << "0 - EXIT" << endl;
		int n;
		cin >> n;
		cout << endl;
		switch (n)
		{
		case 1: //Intersection
			j = 1;
			while (j)
			{
				cout << "you choose INTERSECTION SORT" << endl;
				cout << "Which sequance do you want?" << endl;
				cout << "1 - List" << endl;
				cout << "2 - Array" << endl;
				cout << "0 - BACK" << endl;
				cin >> n;
				cout << endl;
				switch (n)
				{
				case 1:
					cout << "Before: ";
					ListSeqInser.Show();
					start_time = clock();
					InsSorter.Sort(ListSeqInser);
					end_time = clock();
					cout << "After: ";
					ListSeqInser.Show();
					cout << "Time: " << end_time - start_time << endl;
					break;
				case 2:
					cout << "Before: ";
					ArSeqInser.Show();
					start_time = clock();
					InsSorter.Sort(ArSeqInser);
					end_time = clock();
					cout << "After: ";
					ArSeqInser.Show();
					cout << "Time: " << end_time - start_time << endl;
					break;
				case 0:
					j = 0;
					break;
				default:
					break;
				}

			}
			break;
		case 2: //Heap sort
			j = 1;
			while (j)
			{
				cout << "you choose HEAP SORT" << endl;
				cout << "Which sequance do you want?" << endl;
				cout << "1 - List" << endl;
				cout << "2 - Array" << endl;
				cout << "0 - BACK" << endl;
				cin >> n;
				cout << endl;
				switch (n)
				{
				case 1:
					cout << "Before: ";
					ListSeqHeap.Show();
					start_time = clock();
					HeapSorter.Sort(ListSeqHeap);
					end_time = clock();
					cout << "After: ";
					ListSeqHeap.Show();
					cout << "Time: " << end_time - start_time << endl;
					break;
				case 2:
					cout << "Before: ";
					ArSeqHeap.Show();
					start_time = clock();
					HeapSorter.Sort(ArSeqHeap);
					end_time = clock();
					cout << "After: ";
					ArSeqHeap.Show();
					cout << "Time: " << end_time - start_time << endl;
					break;
				case 0:
					j = 0;
					break;
				default:
					break;
				}

			}
			break;
		case 0:
			i = 0;
			break;
		default:
			break;
		}
	}

	return 0;
}