path: root / Year 2 / Structures and data algorithms / Project / exa / SkipList.hpp

#ifndef SKIPLIST
#define SKIPLIST

#include <istream>
#include <ostream>
#include <deque>
#include <exception>

template <class T>
class SkipList {
	struct Node {
		Node* next;
		Node* skip;
		T value;

		Node(const T& value, Node* next = nullptr, Node* skip = nullptr) : next(next), skip(skip), value(value) {}
	};

	Node* head;
	Node* tail;
	unsigned listSize;

	void copyFrom(const SkipList&);
	void free();

	Node* findNode(const T&);
	bool recShortSublist(Node*, std::deque<T>&, std::deque<T>&);

public:
	std::deque<T> shortestSublistIncluding(std::deque<T>&);

	void push(const T& elem);
	bool addSkip(const T&, const T&);
	T pop();
	T& front();
	T& back();

	unsigned size();
	bool empty();

	std::istream& operator>>(std::istream& istr);
	std::ostream& print(std::ostream& ostr);

	class Iterator {
		Node* current;
		Iterator(Node* start) : current(start) {}

	public:
		Iterator& operator++() {
			if (current != nullptr)
				current = current->next;
			return *this;
		}

		Iterator& operator++(int) {
			Iterator toRet = *this;
			++(*this);
			return toRet;
		}

		T& operator*() {
			return current->value;
		}

		bool operator==(const Iterator& other) const {
			return current == other.current;
		}

		bool operator!=(const Iterator& other) const {
			return !(*this == other);
		}

		friend class SkipList;
	};
	Iterator begin();
	Iterator end();

	SkipList();
	SkipList(const SkipList&);
	SkipList& operator=(const SkipList&);
	~SkipList();

	SkipList(SkipList&&);
	SkipList& operator=(SkipList&&);
};

/*
 * Exercise functionality
 */

template <class T>
bool SkipList<T>::recShortSublist(Node* current, std::deque<T>& search, std::deque<T>& out) {
	if (current == nullptr) return false;

	out.push_back(current->value);

	if (current->value == search.front()) {
		search.pop_front();
		if (search.empty()) return true;
	}

	if (!recShortSublist(current->skip, search, out) && !recShortSublist(current->next, search, out)) {
		out.pop_back();
		return false;
	}
	return true;
}

template <class T>
std::deque<T> SkipList<T>::shortestSublistIncluding(std::deque<T>& locs) {
	// Sort locs
	for (Node* i = head; i != nullptr; i = i->next) {
		for (auto j = locs.begin(), end = locs.end(); j != end; ++j) {
			if (*j == i->value) {
				locs.erase(j);
				locs.push_back(i->value);
				break;
			}
		}
	}

	std::deque<T> out;
	recShortSublist(head, locs, out);
	return out;
}

/*
 * SkipList functionality
 */

/* Private functions */

template <class T>
typename SkipList<T>::Node* SkipList<T>::findNode(const T& value) {
	Node* start = head;
	while (start != nullptr) {
		if (start->value == value) return start;
		start = start->next;
	}
	return nullptr;
}

/* Public functions */

template <class T>
void SkipList<T>::push(const T& elem) {
	if (empty()) {
		head = tail = new Node(elem);
	}
	else {
		tail->next = new Node(elem);
		tail = tail->next;
	}
	listSize++;
}

template <class T>
bool SkipList<T>::addSkip(const T& start, const T& end) {
	Node* from = findNode(start);
	if (from == nullptr) return false;
	Node* to = findNode(end);
	if (to == nullptr) return false;

	from->skip = to;
	return true;
}

template <class T>
T SkipList<T>::pop() {
	if (empty())
		throw std::logic_error("Pop called on empty SkipList!");

	T val = head->value;
	Node* oldHead = head;
	head = head->next;
	delete oldHead;
	listSize--;
	return val;
}

template <class T>
T& SkipList<T>::front() {
	if (empty())
		throw std::logic_error("Front called on empty SkipList!");

	return head->value;
}

template <class T>
T& SkipList<T>::back() {
	if (empty())
		throw std::logic_error("Back called on empty SkipList!");

	return tail->value;
}

template <class T>
unsigned SkipList<T>::size() {
	return listSize;
}

template <class T>
bool SkipList<T>::empty() {
	return listSize == 0;
}

template <class T>
std::istream& SkipList<T>::operator>>(std::istream& istr) {
	return istr; // TODO
}

template <class T>
std::ostream& SkipList<T>::print(std::ostream& ostr) {
	for (Node* i = head; i != nullptr; i = i->next) {
		ostr << i->value << ", ";
		if (i->skip != nullptr)
			ostr << i->skip->value;
		ostr << "; ";
	}
	return ostr;
}

/*
 * Iterators
 */

template <class T>
typename SkipList<T>::Iterator SkipList<T>::begin() {
	return Iterator(head);
}

template <class T>
typename SkipList<T>::Iterator SkipList<T>::end() {
	return Iterator(nullptr);
}

/* 
 * Rule of 6
 */

template <class T>
void SkipList<T>::copyFrom(const SkipList& other) {
	Node* newHead = new Node(other.head->value);
	Node*& newTail = newHead->next;

	T** skips = new T*[other.size()];
	skips[0] = newHead->skip;

	for (Node* i = other.head->next, si = 1; i != nullptr; i = i->next, si++) {
		newTail = new Node(i->value);
		skips[si] = i->skip->value;
		if (i->next != nullptr)
			newTail = newTail->next;
	}

	head = newHead;
	tail = newTail;
	listSize = other.listSize();

	for (unsigned i = 0; i < other.size(); i++) {
		newHead->skip = findNode(*skips[i]);
	}
	delete[] skips;
}

template <class T>
void SkipList<T>::free() {
	Node* n;
	while (head != nullptr) {
		n = head->next;
		delete head;
		head = n;
	}
}

template <class T>
SkipList<T>::SkipList() : head(nullptr), tail(nullptr), listSize(0) {}

template <class T>
SkipList<T>::SkipList(const SkipList& other) {
	copyFrom(other);
}

template <class T>
SkipList<T>& SkipList<T>::operator=(const SkipList& other) {
	if (this != &other) {
		free();
		copyFrom(other);
	}
	return *this;
}

template <class T>
SkipList<T>::~SkipList() {
	free();
}

template <class T>
SkipList<T>::SkipList(SkipList&& other) {
	head = other.head;
	tail = other.tail;
	listSize = other.listSize;

	other.head = other.tail = nullptr;
}

template <class T>
SkipList<T>& SkipList<T>::operator=(SkipList&& other) {
	if (this != &other) {
		free();

		head = other.head;
		tail = other.tail;
		listSize = other.listSize;

		other.head = other.tail = nullptr;
	}
	return *this;
}

#endif