LinkedList.h

#pragma once
#include "BusInfo.cpp"
/// <summary>
/// Øàáëîí îäíîñâÿçíîãî ñïèñêà
/// </summary>
/// <typeparam name="T">Ëþáîé êëàññ</typeparam>
template<class T>
class LinkedList
{
private:
	/// <summary>
	/// Âíóòðåííèé êëàññ LinkedList, ñëóæèò îá¸ðòêîé íàä T äëÿ ñîäåðæàíèÿ id è ññûëêè íà ñëåäóþùèé ýëåìåíò
	/// </summary>
	class Node
	{
	public:
		int id;
		T* value;
		Node* next;
		/// <summary>
		/// Êîíñòðóêòîð, ñîçäàþùèé îá¸ðòêó íàä Ò
		/// </summary>
		Node(int id, T* instance) {
			this->id = id;
			this->value = instance;
			this->next = nullptr;
		}	
		///Äåñòðóêòîð, êîòîðûé âûäà¸ò îøèáêó, åñëè ïðè óäàëåíèè íå îáíóëèòü ññûëêó íà ñëåäóþùèé ýëåìåíò
		~Node() {
			if (next != nullptr)
			{
				throw new std::exception("Óíè÷òîæåíèå âåòâè");
			}
		};
	};
public:
	LinkedList()
	{
		initialize();
	}
	/// <summary>
	/// Äîáàâëÿåò íîâóþ íîäó, ñîäåðæàùóþ instance. Êàæäûé ðàç óâåëè÷èâàåò ñ÷¸ò÷èê, ÷òîáû id íå ïîâòîðÿëîñü
	/// </summary>
	/// <param name="instance">Ýêçåìïëÿð êëàññà Ò, êîòîðûé áóäåò äîáàâëåí â ñïèñîê</param>
	/// <returns>Âîçâðàùàåò id íîâîé íîäû èëè -1 ïðè îøèáêå âñòàâêè</returns>
	int add(T* instance)
	{
		if (insert(counter, instance))
		{
			return counter++;
		}
		else
		{
			return -1;
		}
	}
	/// <summary>
	/// Äîáàâëåíèå instance ïî óêàçàííîìó id 
	/// </summary>
	/// <param name="id">èäåíòèôèêàòîð, ïî êîòîðîìó íóæíî äîáàâèòü íîäó</param>
	/// <param name="instance">ýêçåìïëÿð êëàññà Ò, êîòîðûé áóäåò äîáàâëåí â ñïèñîê</param>
	/// <returns>Âîçâðàùàåò true, åñëè ïîëó÷èëîñü âñòàâèòü è false, åñëè óæå ñóùåñòâóåò íîäà ñ òàêèì æå id</returns>
	bool insert(int id, T* instance)
	{
		bool res = insert_node(new Node(id, instance));
		return res;
	}
	/// <summary>
	/// Âûïîëíÿåò ïîèñê íîäû, ñëåäóþùàÿ çà êîòîðîé èìååò èäåíòèôèêàòîð ðàâíûé âõîäíîìó ïàðàìåòðó id.
	/// Ïðîèçâîäèò óäàëåíèå ñëåäóùåé çà íàéäåííîé íîäîé è ïðèñîåäèíåíèå ñìëåäóþùåé çà óäàë¸ííîé íîäû ê íàéäåííîé.
	/// </summary>
	/// <param name="id">èäåíòèôèêàòîð, ïî êîòîðîìó íóæíî óäàëèòü íîäó</param>
	/// <returns>Âîçâðàùàåò true, åñëè ïîëó÷èëîñü óäàëèòü è false, åñëè íå ñóùåñòâóåò íîäà ñ òàêèì æå id</returns>
	bool remove(int id)
	{
		Node* temp_node = start;
		if (temp_node == nullptr)
		{
			return false;
		}
		if (temp_node->id == id)
		{
			start = temp_node->next;
			temp_node->next = nullptr;
			delete temp_node;
			return true;
		}
		while (temp_node != nullptr &&
			   temp_node->next != nullptr &&
			   temp_node->next->id != id)
		{
			temp_node = temp_node->next;
		}
		if (temp_node == nullptr || temp_node->next == nullptr)
		{
			return false;
		}
		else
		{
			Node* temp_node_next = temp_node->next->next;
			temp_node->next->next = nullptr;
			delete temp_node->next;
			temp_node->next = temp_node_next;
			return true;
		}
	}
	/// <summary>
	/// Èùåò íîäó ñ óêàçàííûì id
	/// </summary>
	/// <param name="new_node">Âîçâðàùàåò íàéäåííóþ íîäó èëè nullptr, åñëè íàéòè íå óäàëîñü</param>
	/// <returns></returns>
	T* find(int id)
	{
		Node* temp_node = find_node(id);
		return temp_node == nullptr ? nullptr : temp_node->value;
	}
	/// <summary>
	/// Âîçâðàùàåò ñòàðòîâóþ íîäó, îíà ìîæåò áûòü nullptr
	/// </summary>
	T* find_first()
	{
		return start == nullptr ? nullptr : start->value;
	}
	/// <summary>
	/// Èùåò íîäó ñ óêàçàííûì id. Âîçâðàùàåò ñëåäóþùó çà íåé íîäó, îíà ìîæåò áûòü nullptr
	/// </summary>
	T* find_next(int id)
	{
		Node* temp_node = find_node(id);
		return (temp_node == nullptr || temp_node->next == nullptr) ? nullptr : temp_node->next->value;
	}
private:
	Node* start;
	int counter;
	/// <summary>
	/// Ìåòîä, çàïóöñêàåìûé â êîíñòðóêòîðå
	/// <para/>Óñòàíàâëèâàåò ñ÷¸ò÷èê â 0 è îáíóëÿåò óêàçàòåëü íà ñòàðòîâóþ íîäó
	/// </summary>
	void initialize()
	{
		this->counter = 0;
		start = nullptr;
	}
	/// <summary>
	/// Ïåðåáîð íîä, ïîêà íå ñîâïàä¸ò id	
	/// </summary>
	/// <returns>Âîçâðàùàåò íîäó ñ íóæíûì id èëè nullptr</returns>
	Node* find_node(int id)
	{
		Node* temp_node = start;
		while (temp_node != nullptr && temp_node->id != id)
		{
			temp_node = temp_node->next;
		}
		return temp_node;
	}
	/// <summary>
	/// Âñòàâêà íîâîé íîäû.
	/// Çàíèìàåò ìåñòî ïî âîçðàñòàíèþ id (ñîðòèðîâêà ïðè âñòàâêå)
	/// </summary>
	/// <returns>Âîçâðàùàåò true, åñëè ïîëó÷èëîñü âñòàâèòü è false, åñëè óæå ñóùåñòâóåò íîäà ñ òàêèì æå id</returns>
	bool insert_node(Node* new_node)
	{
		if (start == nullptr)
		{
			start = new_node;
			return true;
		}
		Node* temp_node = start;
		if (temp_node->id > new_node->id)
		{
			new_node->next = temp_node;
			start = new_node;
			return true;
		}
		while (temp_node->id < new_node->id && temp_node->next != nullptr)
		{
			temp_node = temp_node->next;
		}
		if (temp_node->id == new_node->id)
		{
			return false;
		}
		if (temp_node->next != nullptr)
		{
			new_node->next = temp_node->next;
		}
		temp_node->next = new_node;
		return true;
	}
};