Algo3

//ALGO2 IS1 213B LAB03
//MACIEJ DOMINIAK
//dm44308@zut.edu.pl
#include <iostream>
#include <ctime>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
class Node
{
	public:
	int key,height;
	double d_variable;
	char ch_variable;
	Node** forward;
	//node constructor
	Node(int key, int level)
	{
		this->key = key;
		this->height = level;
		this->d_variable = rand();
		this->ch_variable = 'T';
		forward = new Node * [level];
		for (int i = 0; i < level; i++)
		{
			forward[i] = NULL;
		}
	}
};
class Skiplist
{
	public:
	Node* HEADER;
	int MAX_LEVEL;
	float PROB;
	int size;

	//constructor	DONE
	Skiplist(int MAX_LEVEL,float PROB)
	{
		this->MAX_LEVEL = MAX_LEVEL;
		this->PROB = PROB;
		size = 0;
		HEADER = new Node(-1,MAX_LEVEL);
	}

	//generates random level including probability MAYBE??
	int randomLevel()
	{
		int level = 1;
		int r = rand() % 100;
		while ((r < PROB * 100) && (level < MAX_LEVEL))
		{
			level++;
			r = rand() % 100;
		}
		return level;
	}

	//inserts one element to the list MAYBE??
	void insertElement(int key)
	{
		Node* current = HEADER;
		Node** update = new Node * [MAX_LEVEL];
		for (int i = 0; i < MAX_LEVEL; i++)
		{
			update[i] = NULL;
		}
		for (int i = MAX_LEVEL - 1; i >= 0; i--)
		{
			while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
			{
				current = current->forward[i];
			}
			update[i] = current;

		}
		current = current->forward[0];
		if (current == NULL || current->key != key)
		{
			int r_level = randomLevel();
			Node* new_node = new Node(key, r_level);
			for (int i = 0; i < new_node->height; i++)
			{
				new_node->forward[i] = update[i]->forward[i];
				update[i]->forward[i] = new_node;
			}
			size++;
			return;
		}
		if (current->key = key)
		{
			current->ch_variable = 'D';
		}
	}

	//shows all elements  THATS JUST FOR ME
	void showAll()
	{
		Node* current = HEADER->forward[0];
		if (current == NULL)return;
		while (current != NULL)
		{
			cout << endl << "Key value:" << current->key<<' '<<current<<endl;
			current = current->forward[0];
		}
	}

	//inserts many elements to the list  DONE
	void insertManyElements(int amount)
	{
		int j = 0;
		while (j < amount)
		{
			Node* current = HEADER;
			int key = (4 * rand()) % 999901 + 99;
			Node** update = new Node * [MAX_LEVEL];
			for (int i = 0; i < MAX_LEVEL; i++)
			{
				update[i] = NULL;
			}
			for (int i = MAX_LEVEL - 1; i >= 0; i--)
			{
				while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
				{
					current = current->forward[i];
				}
				update[i] = current;

			}
			current = current->forward[0];
			if (current == NULL || current->key != key)
			{
				int r_level = randomLevel();
				Node* new_node = new Node(key, r_level);
				for (int i = 0; i < new_node->height; i++)
				{
					new_node->forward[i] = update[i]->forward[i];
					update[i]->forward[i] = new_node;
				}
				size++;
				j++;
				continue;
			}
			if (current->key = key)
			{
				current->ch_variable = 'D';
			}
		}
	}

	//finds element in a list  DONE
	Node* findElement(int key)
	{
		Node* current = HEADER;
		for (int i = MAX_LEVEL-1; i >= 0; i--)
		{
			while (current->forward[i] && current->forward[i]->key < key)
				current = current->forward[i];
		}
		current = current->forward[0];
		if (current==NULL)
			return NULL;
		if(current->key==key)
		{
			return current;
		}
		else
		{
			return NULL;
		}
	}

	//returns an array of how many nodes there are in particular levels	DONE
	void howManyNodes()
	{
		int *tab=new int[MAX_LEVEL];
		int sum=0;
		for (int i = 0; i < MAX_LEVEL; i++)
		{
			tab[i] = 0;
		}
		for (int i = MAX_LEVEL - 1; i >= 0; i--)
		{
			Node* jump = HEADER->forward[i];
			while (jump != NULL)
			{
				tab[i]++;
				jump = jump->forward[i];
			}
			sum += tab[i];

		}
		for (int i = 0; i < MAX_LEVEL; i++)
		{
			cout << endl << "Level " << i << " has:" << tab[i] << " nodes";
		}
		cout << endl << "Sum of all nodes equals:" << sum;
	}

	//shows X first elements DONE
	void showFirstElements(int amount)
	{
		if (amount > size)return;
		Node* current = HEADER->forward[0];
		cout <<endl<< "These are first " << amount << " elements:";
		for (int i = 0; i < amount; i++)
		{
			cout << current->key << ' ';
			current = current->forward[0];
		}
	}

	//shows Y last elements DONE
	void showLastElements(int amount)
	{
		if (amount > size)return;
		int skip = size - amount;
		Node* current = HEADER->forward[0];
		cout << endl << "These are last " << amount << " elements:";
		for (int i = 0; i < size; i++)
		{
			if (i >= skip)cout << current->key<<' ';
			current = current->forward[0];
		}
	}

	//deletes an element from a list
	void deleteElement(int key)
	{
		Node* current = HEADER;
		Node** update = new Node * [MAX_LEVEL];
		for (int i = 0; i < MAX_LEVEL; i++)
		{
			update[i] = NULL;
		}
		for (int i = MAX_LEVEL - 1; i >= 0; i--)
		{
			while ((current->forward[i] != NULL) && (current->forward[i]->key < key))
			{
				current = current->forward[i];
			}
			update[i] = current;

		}
		current = current->forward[0];
		if (current == NULL)
		{
			return;
		}
		if (current->key == key)
		{
			for (int i = 0; i < current->height; i++)
			{
				update[i]->forward[i] = current->forward[i];
			}
			delete current;
			size--;
		}
		else
		{
			return;
		}
	}

	//deletes entire list
	void deleteList()
	{
		Node* current = HEADER->forward[0];
		for (int i = MAX_LEVEL - 1; i >= 0; i--)
			HEADER->forward[i] = NULL;
		while (current->forward[0] != NULL)
		{
			Node* previous;
			previous = current;
			current = current->forward[0];
			delete previous;
		}
	}

};
int main()
{
	srand(unsigned(time(NULL)));

	Skiplist my_list(5, 0.5);


	return 0;
}