Untitled

#include "main.h"

int MAXSIZE = 0;

class JJK_RESTAURANT_OPERATIONS;
class RESTAURANT_Gojo;
class RESTAURANT_Sukuna;
class HuffTree_AVL;

class RESTAURANT_Gojo
{
	class Tree_BST;

private:
	vector<Tree_BST> areaTable;

public:
	RESTAURANT_Gojo() : areaTable(MAXSIZE + 1) {}
	void insertAreaTable(int result)
	{
		int ID = result % MAXSIZE + 1;
		areaTable[ID].insert(result);
	}

	void remove_KOKUSEN()
	{
		for (int i = 1; i < MAXSIZE + 1; i++)
			areaTable[i].remove();
	}

	void print_LIMITLESS(int number)
	{
		if (number <= 0 || number > MAXSIZE)
			return; //! quá kí tự
		areaTable[number].print();
	}

private:
	class Tree_BST
	{
		class Node;

	private:
		Node *root;
		queue<int> queueTime;

	public:
		Tree_BST() : root(nullptr) {}
		~Tree_BST()
		{
			while (!queueTime.empty())
			{
				int temp = queueTime.front();
				queueTime.pop();
				root = remove_recursive(root, temp);
			}
		}
		int size()
		{
			return queueTime.size();
		}
		Node *insert_recursive(Node *node, int result)
		{
			if (!node)
				return new Node(result);
			if (result < node->result)
			{
				node->left = insert_recursive(node->left, result);
			}
			else
			{
				node->right = insert_recursive(node->right, result);
			}
			return node;
		}
		void insert(int result)
		{
			root = insert_recursive(root, result);
			queueTime.push(result);
		}

		Node *remove_recursive(Node *node, int result)
		{
			if (!node)
				return nullptr;
			if (result < node->result)
			{
				node->left = remove_recursive(node->left, result);
			}
			else if (result > node->result)
			{
				node->right = remove_recursive(node->right, result);
			}
			if (node->result == result)
			{
				Node *nodeDel = node;
				if (!node->left && !node->right)
				{
					node = nullptr;
				}
				else if (!node->left)
				{
					node = node->right;
				}
				else if (!node->right)
				{
					node = node->left;
				}
				else
				{
					Node *tmp = node->right;
					while (tmp->left != nullptr)
					{
						tmp = tmp->left;
					}
					swap(tmp->result, node->result);
					node->right = remove_recursive(node->right, result);
					return node;
				}
				delete nodeDel;
			}
			return node;
		}
		int CountNode(Node *node)
		{
			return node == NULL ? 0 : 1 + CountNode(node->left) + CountNode(node->right);
		}
		unsigned long long DFS(Node *node, const vector<vector<long long>> &dp)
		{
			if (node == NULL)
				return 1;
			int nleft = CountNode(node->left);
			int nRight = CountNode(node->right);
			return (unsigned long long)(dp[nleft + nRight][nleft] % MAXSIZE * (DFS(node->left, dp) % MAXSIZE * DFS(node->right, dp) % MAXSIZE) % MAXSIZE) % MAXSIZE;
		}
		void PascalTriangle(int n, vector<vector<long long>> &dp)
		{
			for (int i = 0; i <= n; i++)
			{
				dp[i] = vector<long long>(i + 1, 1); // initially all 1
				for (int j = 1; j < i; j++)
				{
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]);
				}
			}
		}
		void remove()
		{
			if (this->size() == 0)
				return; //! trường hợp rỗng bỏ qua
			vector<vector<long long>> dp(queueTime.size() + 1);
			PascalTriangle(queueTime.size(), dp);
			unsigned long long number = DFS(root, dp);
			while (number != 0 && !queueTime.empty())
			{
				int temp = queueTime.front();		 //! tìm khách hàng đầu tiên được lưu trong sổ và lấy được vị trí nó rồi
				queueTime.pop();					 //! xóa nó khỏi sổ
				root = remove_recursive(root, temp); //! tới chỗ nó cho nó cút khỏi nhà hàng
				number--;
			}
		}

		//^ test case thôi nộp bài thì xóa đi nha --------------------------------------------------------------------
		string test_print_recursive(Node* node)
		{
			if(node == nullptr) return "NULL"; //! trường hợp dừng print
			if(node->left == nullptr && node->right == nullptr) return to_string(node->result); //! tr
			return to_string(node->result)+"("+test_print_recursive(node->left) +","+test_print_recursive(node->right)+")";
		}
		void test_print(){
			//! trường hợp rỗng bỏ qua
			if(this->size() == 0){
				solution << "Tree: EMPTY\n";
				return;
			}
			solution << "Tree: " << test_print_recursive(root);
			solution << "\n";
		}
		//^ ----------------------------------------------------------------------------------------------------------

		void print_recursive(Node *node)
		{
			if (node != NULL)
			{
				solution << node->result << "\n";
				print_recursive(node->left);
				print_recursive(node->right);
			}
		}
		void print()
		{
			//^ test case thôi nộp bài thì xóa đi nha --------------------------------------------------------------------
			test_print();
			//^ ----------------------------------------------------------------------------------------------------------
			// print_recursive(root);
		}

	private:
		class Node
		{
		private:
			int result;
			Node *left;
			Node *right;
			friend class Tree_BST;

		public:
			Node(int result) : result(result), left(NULL), right(NULL) {}
		};
	};
};

class RESTAURANT_Sukuna
{
	class Node;

private:
	vector<Node *> areaTable;
	list<Node *> LRU;

private:
	Node *whoFirst(Node *a, Node *b)
	{
		for (Node *it : LRU)
		{
			if (it == a)
				return b;
			if (it == b)
				return a;
		}
		return nullptr;
	}
	void ReHeap_down(int index)
	{
		int leftChild = 2 * index + 1;
		int rightChild = 2 * index + 2;
		int smallest = index;

		if (leftChild < areaTable.size())
		{
			if (areaTable[leftChild]->size() < areaTable[smallest]->size())
			{
				smallest = leftChild;
			}
			else if (areaTable[leftChild]->size() == areaTable[smallest]->size())
			{
				if (whoFirst(areaTable[leftChild], areaTable[smallest]) == areaTable[leftChild])
				{
					smallest = leftChild;
				}
			}
		}
		if (rightChild < areaTable.size())
		{
			if (areaTable[rightChild]->size() < areaTable[smallest]->size())
			{
				smallest = rightChild;
			}
			else if (areaTable[rightChild]->size() == areaTable[smallest]->size())
			{
				if (whoFirst(areaTable[rightChild], areaTable[smallest]) == areaTable[rightChild])
				{
					smallest = rightChild;
				}
			}
		}
		if (smallest != index)
		{
			swap(areaTable[index], areaTable[smallest]);
			ReHeap_down(smallest);
		}
	}

	void ReHeap_up(int index)
	{
		while (index > 0)
		{
			int parent = (index - 1) / 2;
			if (areaTable[index]->size() < areaTable[parent]->size() || (areaTable[index]->size() == areaTable[parent]->size() && whoFirst(areaTable[index], areaTable[parent]) == areaTable[index]))
			{

				swap(areaTable[index], areaTable[parent]);
				index = parent;
			}
			else
				break;
		}
	}

	void moveTop(Node *node)
	{
		list<Node *>::iterator it = std::find(LRU.begin(), LRU.end(), node);
		if (it != LRU.end())
		{
			LRU.erase(it);
		}
		LRU.push_front(node);
	}

	void removeNode(Node *node)
	{
		list<Node *>::iterator it = find(LRU.begin(), LRU.end(), node);
		LRU.erase(it);
	}

public:
	RESTAURANT_Sukuna() {}
	~RESTAURANT_Sukuna()
	{
		for (int i = 0; i < areaTable.size(); i++)
			delete areaTable[i];
	}
	void insertAreaTable(int result)
	{
		int ID = result % MAXSIZE + 1;
		int index = -1;
		for (int i = 0; i < areaTable.size(); i++)
		{
			if (ID == areaTable[i]->ID)
				index = i;
		}
		if (index == -1)
		{
			areaTable.push_back(new Node(ID));
			index = areaTable.size() - 1;
			areaTable[index]->insert(result);
			this->moveTop(areaTable[index]);
			this->ReHeap_up(index);
		}
		else
		{
			areaTable[index]->insert(result);
			this->moveTop(areaTable[index]);
			this->ReHeap_down(index);
		}
	}

	void remove_KEITEIKEN(int number)
	{
		if (areaTable.size() <= 0)
			return;
		vector<Node *> areaTableNew(areaTable.begin(), areaTable.end());
		queue<Node *> listDelete; //! danh sách các khu cấn xóa
		for (int i = 0; areaTable.size() && i < number; i++)
		{
			Node *nodeDelete = areaTable[0];
			swap(areaTable[0], areaTable[areaTable.size() - 1]);
			areaTable.pop_back();
			this->ReHeap_down(0);
			listDelete.push(nodeDelete);
		}
		areaTable = areaTableNew;
		while (listDelete.size())
		{
			Node *nodeDelete = listDelete.front();
			listDelete.pop();

			solution << "remove customers in the area ID = " << nodeDelete->ID << "(len=" << nodeDelete->head.size() << ")"
					 << ": ";
			nodeDelete->remove(number);
			solution << "\n";

			int index = 0;
			while (areaTable[index] != nodeDelete)
				index++;

			if (nodeDelete->size() == 0)
			{
				swap(areaTable[index], areaTable[areaTable.size() - 1]);
				this->removeNode(areaTable[areaTable.size() - 1]);
				delete areaTable[areaTable.size() - 1];

				areaTable.pop_back();
			}
			this->ReHeap_down(index);
		}
	}

	void print_pre_order(int index, int number)
	{
		if (index >= this->areaTable.size())
			return;

		this->areaTable[index]->print(number);
		print_pre_order(index * 2 + 1, number);
		print_pre_order(index * 2 + 2, number);
	}
	void print_LIMITLESS(int number)
	{
		if (number <= 0)
			return;

		// solution << "Heap : ";
		// for(auto it : this->areaTable)
		// {
		// 	int order = 0;
		// 	for (auto ix : LRU) {
		// 		if (ix == it) break;
		// 		++order;
		// 	}
		// 	solution << it->ID << "(len="<< it->size() <<",index=" << order <<")" << " ";
		// }
		// solution << "\n";

		solution << "Heap : ";
		for (auto it : this->areaTable)
			solution << it->ID << " ";
		solution << "\n";

		solution << "list LRU : ";
		for (auto it : LRU)
			solution << it->ID << " ";
		solution << "\n";

		print_pre_order(0, number);
	}
	//^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
private:
	class Node
	{
	private:
		int ID;			//! ID của bàn đó
		list<int> head; //! lưu danh sách các result của khách hàng
		friend class RESTAURANT_Sukuna;

	public:
		Node(int ID) : ID(ID) {}
		int size() const { return head.size(); }
		void insert(int result) { head.push_front(result); }
		void remove(int number)
		{

			while (number-- && head.size() > 0)
			{
				solution << head.back() << " ";
				head.pop_back();
			}
			//^ gợi ý dùng hàm của linklist có sẵn
			//* thêm solution << head.back() << " "; để in ra
			// if(head.size()>0) solution << head.back() << " ";
		}
		void print(int number)
		{
			solution << "customers in the area ID = " << ID << "(len=" << head.size() << ")"
					 << ": ";
			for (list<int>::iterator it = head.begin(); number > 0 && it != head.end(); ++it, --number)
			{
				solution << *it << " ";
			}
			solution << "\n";
		}
	};
};