#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_SKIP_LIST
#define CA_UWATERLOO_ALUMNI_DWHARDER_SKIP_LIST

#include <cassert>
#include <ostream>

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2009 by Douglas Wilhelm Harder.  All rights reserved.
// Skip lists were first described by William Pugh in 1990.

namespace Data_structures {
	/****************************************************
	 * ************************************************ *
	 * *                  Skip Lists                  * *
	 * ************************************************ *
	 ****************************************************/

	template <typename K, typename Type>
	class Skip_list {
		public:
			Skip_list();
			~Skip_list();
			bool empty() const;
			int size() const;
			int count( K const & ) const;
			Type operator[]( K const & ) const;
			int total_search() const;
			double average_search() const;
			bool validate() const;

			Type &operator[]( K const & );
			int clear();

			class iterator;
			class pair;

			iterator begin();
			iterator end();
			iterator find( K const & );

		private:
			class node;

			int list_size;
			int height;
			node **head;
			node *tail;
			int index;
			int prev_modulus, modulus, next_modulus;

			static int const modulus_table[32];

			void search_head( K const &, int &, node* & ) const;
			bool search_list( K const &, int, node* & ) const;
			void increment_number();
			void decrement_number();
			int new_height();
			void resize_head( int );

		template <typename J, typename S>
		friend std::ostream &operator<<( std::ostream &, const Skip_list<J, S> & );

		friend class iterator;
	};

	template <typename K, typename Type>
	int const Skip_list<K, Type>::modulus_table[32] = {
		1, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
		65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607,
		16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823,
		2147483647
	};

	/****************************************************
	 * ************************************************ *
	 * *                Skip List Node                * *
	 * ************************************************ *
	 ****************************************************/

	template <typename K, typename Type>
	class Skip_list<K, Type>::node {
		public:
			K key;
			Type value;
			int levels;
			node **next;
			node *previous;

			node( K const &, int, node * = 0 );
			~node();

		template <typename J, typename S>
		friend std::ostream &operator<<( std::ostream &, const Skip_list<J, S> & );
	};

	/****************************************************
	 * ************************************************ *
	 * *                   Iterator                   * *
	 * ************************************************ *
	 ****************************************************/

	template <typename K, typename Type>
	class Skip_list<K, Type>::iterator {
		private:
			node *current_node;
			iterator( node * );

		public:
			iterator();

			iterator &operator++();
			iterator operator++( int );
			iterator &operator--();
			iterator operator--( int );
			pair operator*();
			bool operator==( iterator const &rhs ) const;
			bool operator!=( iterator const &rhs ) const;

		friend class Skip_list;
	};

	/****************************************************
	 * ************************************************ *
	 * *                     Pair                     * *
	 * ************************************************ *
	 ****************************************************/

	template <typename K, typename Type>
	class Skip_list<K, Type>::pair {
		public:
			K const first;
			Type &second;

			pair():
			first ( K() ),
			second( Type() ) {
				// Empty constructor
			}

			pair( K const &f, Type &s ):
			first (f),
			second(s) {
				// Empty constructor
			}

			pair( pair const & p):
			first ( p.first ),
			second( p.second ) {
				// Empty copy constructor
			}
	};

	/****************************************************
	 * ************************************************ *
	 * *            Skip List Definitions             * *
	 * ************************************************ *
	 ****************************************************/

	/***************************************************
	 *      Constructors, Destructors, operator =      *
	 ***************************************************/

	/*
	 * Constructor
	 *    Skip_list<K, Type> :: Skip_list()
	 *
	 * This creates a skip list with:
	 *    A list size of 0:  empty or storing no objects
	 *    A height of 1:  each node has at most one next pointer
	 *    An array (initially of capacity 1 storing the value 0) of head pointers to nodes
	 *    A tail pointer (initially 0)
	 *    An index pointer into the modulus table
	 *    The previous, current, and next moduli:  1, 1, and 3
	 */

	template <typename K, typename Type>
	Skip_list<K, Type>::Skip_list():
		list_size( 0 ),
		height( 1 ),
		head( new node *[height] ),
		tail( 0 ),
		index( 2 ),
		prev_modulus( 1 ),
		modulus( 1 ),
		next_modulus( 3 )
	{
		head[0] = 0;
	}

	/*
	 * Destructor
	 *    Skip_list<K, Type> :: ~Skip_list()
	 *
	 * Walk through the skip list and delete
	 * all of the nodes. O(n)
	 */

	template <typename K, typename Type>
	Skip_list<K, Type>::~Skip_list() {
		node *ptr = head[0];

		while ( ptr != 0 ) {
			node *tmp = ptr;
			ptr = ptr->next[0];
			delete tmp;
		}

		delete [] head;
	}

	template <typename K, typename Type>
	Skip_list<K, Type>::node::node( K const &k, int lvl, node *p ):
	key( k ),
	value(),
	levels( lvl ),
	next( new node *[levels] ),
	previous( p ) {
		for ( int i = 0; i < levels; ++i ) {
			next[i] = 0;
		}
	}

	template <typename K, typename Type>
	Skip_list<K, Type>::node::~node() {
		delete [] next;
	}

	/***************************************************
	 *                Public Accessors                 *
	 ***************************************************/

	/*
	 * Empty
	 *    bool Skip_list<K, Type> :: empty() const
	 *
	 * Returns true if the skip list is empty; otherwise return false.  O(1)
	 */

	template <typename K, typename Type>
	bool Skip_list<K, Type>::empty() const {
		return list_size == 0;
	}

	/*
	 * Size
	 *    int Skip_list<K, Type> :: size() const
	 *
	 * Return the number of nodes within the skip list.  O(1)
	 */

	template <typename K, typename Type>
	int Skip_list<K, Type>::size() const {
		return list_size;
	}

	/*********************************************************************
	 * int count( K const &k ) const
	 *
	 *  Count the number of occurrences of the key 'k' in the skip list.
	 *   - This function returns 0 or 1.
	 *********************************************************************/

	template <typename K, typename Type>
	int Skip_list<K, Type>::count( K const &k ) const {
		if ( empty() ) {
			return 0;
		}

		// Find the first level, starting from the highest
		// array pointer, which references a key which is
		// greater than or equal to the searched-for key.

		int lvl;
		node *ptr = 0;

		search_head( k, lvl, ptr );

		// If ptr is not assigned, the first key is greater
		// than the searched-for key.

		if ( ptr == 0 ) {
			return 0;
		}

		return search_list( k, lvl, ptr ) ? 1 : 0;
	}

	template <typename K, typename Type>
	Type Skip_list<K, Type>::operator[] ( K const &k ) const {
		// If the skip list is empty, return the default instance of Type

		if ( empty() ) {
			return Type();
		}

		// Get the highest head[i] such that head[i]->key <= key

		int lvl;
		node *ptr = 0;

		search_head( k, lvl, ptr );

		if ( ptr == 0 ) {
			return Type();
		}

		return search_list( k, lvl, ptr ) ? ptr->value : Type();
	}

	/*
	 * Total Number of Nodes to Find an Entry
	 *  - For each object in the skip list, determine
	 *    the number of steps required to 'find' the
	 *    object.
	 */

	template <typename K, typename Type>
	int Skip_list<K, Type>::total_search() const {
		if ( empty() ) {
			return 0;
		}

		int total = 0;

		for ( node *ptr = head[0]; ptr != 0; ptr = ptr->next[0] ) {
			int lvl;
			node *search = 0;

			for ( lvl = height - 1; lvl >= 0; --lvl ) {
				++total;

				if ( ptr->key >= head[lvl]->key ) {
					search = head[lvl];
					break;
				}
			}

			assert( search != 0 );

			for ( int i = lvl; i >= 0; --i ) {
				while ( true ) {
					if ( search->next[i] == 0  ) {
						break;
					}

					++total;

					if ( search->next[i]->key > ptr->key ) {
						break;
					}

					search = search->next[i];
				}

				++total;

				if ( search->key == ptr->key ) {
					break;
				}
			}
		}

		return total;
	}

	template <typename K, typename Type>
	double Skip_list<K, Type>::average_search() const {
		if ( empty() ) {
			return 0;
		}

		return static_cast<double>( total_search() )/static_cast<double>( list_size );
	}

	/*
	 * Validate the structure of the skip list
	 */

	template <typename K, typename Type>
	bool Skip_list<K, Type>::validate() const {
		int node_count[height];

		for ( int i = 0; i < height; ++i ) {
			node_count[i] = 0;
		}

		// Count how many nodes there are at each height

		for ( node *ptr = head[0]; ptr != 0; ptr = ptr->next[0] ) {
			for ( int i = 0; i < ptr->levels; ++i ) {
				++node_count[i];
			}
		}

		for ( int h = 0; h < height; ++h ) {
			int forward_count = 0;

			for ( node *ptr = head[h]; ptr != 0; ptr = ptr->next[h] ) {
				++forward_count;

				if ( ptr->next[h] != 0 ) {
					if ( ptr->key > ptr->next[h]->key ) {
						std::cout << "Error, at height " << h << ", the key " << ptr->key << " > " << ptr->next[h]->key << " but the first appears first in the level" << std::endl;
						return false;
					}
				}
			}

			if ( forward_count != node_count[h] ) {
				std::cout << "Error, expecting " << list_size << " nodes at height " << h << ", but got " << node_count[h] << std::endl;
				return false;
			}
		}

		if ( node_count[0] != list_size ) {
			std::cout << "Error, expecting size " << list_size << " nodes starting from the front, but got " << node_count[0] << std::endl;
			return false;
		}

		// Count how many nodes there are moving in reverse

		int reverse_count = 0;

		for ( node *ptr = tail; ptr != 0; ptr = ptr->previous ) {
			++reverse_count;
		}

		if ( reverse_count != list_size ) {
			std::cout << "Error, expecting " << list_size << " nodes starting from the back, but got " << reverse_count << std::endl;
			return false;
		}

		// Try to find each node within the skip list

		for ( node *ptr = head[0]; ptr != 0; ptr = ptr->next[0] ) {
			for ( int h = 0; h < ptr->levels; ++h ) {
				node *tmp = head[h];

				while ( tmp != 0 && tmp != ptr ) {
					tmp = tmp->next[h];
				}

				if ( tmp != ptr ) {
					std::cout << "Error, expecting to find the node with key " << ptr->key << " at level " << h << " but did not" << std::endl;
					return false;
				}
			}
		}

		return true;
	}

	/***************************************************
	 *                 Public Mutators                 *
	 ***************************************************/

	template <typename K, typename Type>
	Type& Skip_list<K, Type>::operator[] ( K const &k ) {
		// CASE 1:  THE SKIP LIST IS EMPTY
		// If the skip list is empty,
		//    insert a new node and return the stored default value

		if ( empty() ) {
			increment_number();
			head[0] = new node( k, 1, 0 );
			tail = head[0];

			return head[0]->value;
		}

		// CASE 2:  THE NEW ENTRY IS AT THE FRONT
		//   All head pointers less than or equal to the new node's height
		//   must be updated.

		if ( k < head[0]->key ) {
			increment_number();

			int h = new_height();
			node *tmp = new node( k, h, 0 );
			head[0]->previous = tmp;

			for ( int i = 0; i < h; ++i ) {
				tmp->next[i] = head[i];
				head[i] = tmp;
			}

			return head[0]->value;
		}

		// CASE 3:  THE GENERAL CASE

		// Get the highest head[i] such that head[i]->key <= key

		int lvl;
		node *ptr = 0;

		search_head( k, lvl, ptr );

		assert( ptr != 0 );

		// In the array previous, previous[i] will store a pointer to that
		// entry in the skip list which preceeds the key 'k'.
		//  - From our previous search, previous[lvl] = ptr.

		node *previous_nodes[lvl + 1];

		for ( int i = lvl; i >= 0; --i ) {
			while ( true ) {
				// Until we are either at the end of level 'i' or
				// we find a key greater than 'k', keep stepping forward
				// at this level.

				if ( ptr->next[i] == 0 || ptr->next[i]->key > k ) {
					break;
				}

				ptr = ptr->next[i];
			}

			// If we find the entry with key 'k',
			//      we need only return the value;
			// Otherwise,
			//      store a pointer to 'ptr'.

			if ( ptr->key == k ) {
				// CASE 3a:  THE KEY WAS FOUND
				return ptr->value;
			} else {
				previous_nodes[i] = ptr;
			}
		}

		increment_number();

		if ( ptr->next[0] == 0 ) {
			// CASE 3b:  THE KEY IS AFTER THE LAST NODE IN THE SKIP LIST

			// The entire 'next' array of the new node will be all 0's

			int h = new_height();
			node *tmp = new node( k, h, ptr );

			// The last entry at each level 'i' preceding the
			// new node must have their 'next' pointer at that
			// level updated to this object.

			for ( int i = 0; i < h && i <= lvl; ++i ) {
				previous_nodes[i]->next[i] = tmp;
			}

			// If there are no entries at a level 'i' before
			// the new node, the 'head' array must be updated.

			for ( int i = lvl + 1; i < h; ++i ) {
				head[i] = tmp;
			}

			tail = tmp;

			return tmp->value;
		} else {
			// CASE 3c:  THE KEY IS BETWEEN THE FIRST AND LAST NODES

			int h = new_height();
			node *tmp = new node( k, h, ptr );

			// The last entry at each level 'i' preceding the
			// new node must have their 'next' pointer at that
			// level updated to that object.

			for ( int i = 0; i < h && i <= lvl; ++i ) {
				tmp->next[i] = previous_nodes[i]->next[i];
				previous_nodes[i]->next[i] = tmp;
			}

			tmp->next[0]->previous = tmp;

			// Any level for which the new node is before
			// any other node must see the 'head' updated.

			for ( int i = lvl + 1; i < h; ++i ) {
				tmp->next[i] = head[i];
				head[i] = tmp;
			}

			return tmp->value;
		}
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator Skip_list<K, Type>::begin() {
		return iterator( head[0] );
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator Skip_list<K, Type>::end() {
		return iterator( 0 );
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator Skip_list<K, Type>::find( K const &k ) {
		// If the skip list is empty, return the iterator end()

		if ( empty() ) {
			return end();
		}

		// Get the highest head[i] such that head[i]->key <= key

		int lvl;
		node *ptr = 0;

		search_head( k, lvl, ptr );

		if ( ptr == 0 ) {
			return end();
		}

		return search_list( k, lvl, ptr ) ? iterator( ptr ) : end();
	}

	/*********************************************************************
	 * void clear()
	 *
	 *  Empty the skip list
	 *********************************************************************/

	template <typename K, typename Type>
	int Skip_list<K, Type>::clear() {
		node *ptr = head[0];

		while ( ptr != 0 ) {
			node *tmp = ptr;
			ptr = ptr->next[0];
			delete tmp;
		}

		list_size = 0;
		height = 1;
		head[0] = 0;
		tail = 0;

		index = 2;
		prev_modulus = 1;
		modulus = 1;
		next_modulus = 3;
	}

	/***************************************************
	 *            Private Member Functions             *
	 ***************************************************/

	/*
	 * Search Head Array
	 *  void Skip_list<K, Type> :: search_head( K const &, int &, node *& )
	 *
	 * Search from the top of the head array until a pointer
	 * is found which points to a node containg a key less than
	 * the searched-for key.
	 * 
	 * For example, in this situation, if k denotes the relative location
	 * of the key the function would assign
	 *
	 *    lvl = 2 and ptr = &x
	 *   3---------------->|->
	 *   2------>|-------->|->
	 *   1->|--->|--->|--->|->
	 *   0-******x*********
	 *             ^
	 *             k
	 */

	template <typename K, typename Type>
	void Skip_list<K, Type>::search_head( K const &k, int &lvl, node* &ptr ) const {
		for ( int i = height - 1; i >= 0; --i ) {
			if ( k >= head[i]->key ) {
				lvl = i;
				ptr = head[i];
				return;
			}
		}
	}

	/*
	 * Search List
	 *  bool Skip_list<K, Type> :: search_list( K const &, int, node *& )
	 *
	 * Starting with the level and node found by search_head, begin
	 * looking forward for a node storing a value >= k by following
	 * the largest jumps possible and only stepping down the head
	 * pointer when a node storing a key greater than the searched-for key
	 * is found.
	 */

	template <typename K, typename Type>
	bool Skip_list<K, Type>::search_list( K const &k, int lvl, node* &ptr ) const {
		for ( int i = lvl; i >= 0; --i ) {
			while ( true ) {
				if ( ptr->next[i] == 0 || ptr->next[i]->key > k ) {
					break;
				}

				ptr = ptr->next[i];
			}

			if ( ptr->key == k ) {
				return true;
			}
		}

		return false;
	}

	template <typename K, typename Type>
	void Skip_list<K, Type>::increment_number() {
		++list_size;

		if ( list_size == next_modulus ) {
			++index;

			prev_modulus = modulus;
			modulus = next_modulus;
			next_modulus = modulus_table[index];
		}
	}

	template <typename K, typename Type>
	void Skip_list<K, Type>::decrement_number() {
		--list_size;
	}

	template <typename K, typename Type>
	int Skip_list<K, Type>::new_height() {
		// int r = (rand() % ((list_size + 1)/2)) + 1;
		// int r = (rand() % list_size) + 1;

		int r = (rand() % modulus) + 1;

		for ( int mask = 1, h = 1; true; mask <<= 1, ++h ) {
			if ( mask & r ) {
				if ( height < h ) {
					resize_head( h );
				}

				return h;
			}
		}

		assert( false );
	}

	/*********************************************************************
	 * void resize_head()
	 *
	 *  If the height increases:
	 *   - Allocate memory for a new head array,
	 *   - Copy the old head pointers over,
	 *   - Delete the old array and update with the new, and
	 *   - Update the height
	 *********************************************************************/

	template <typename K, typename Type>
	void Skip_list<K, Type>::resize_head( int new_height ) {
		node **new_head = new node *[new_height];

		for ( int k = 0; k < height; ++k ) {
			new_head[k] = head[k];
		}

		for ( int k = height; k < new_height; ++k ) {
			new_head[k] = 0;
		}

		delete [] head;
		head = new_head;
		height = new_height;
	}

	/****************************************************
	 * ************************************************ *
	 * *            Iterator Definitions              * *
	 * ************************************************ *
	 ****************************************************/

	template <typename K, typename Type>
	Skip_list<K, Type>::iterator::iterator( node *n ):
	current_node( n ) {
		// Empty constructor
	}

	template <typename K, typename Type>
	Skip_list<K, Type>::iterator::iterator():
	current_node( 0 ) {
		// Empty constructor
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator &Skip_list<K, Type>::iterator::operator++() {
		if ( current_node != 0 ) {
			current_node = current_node->next[0];
		}

		return *this;
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator Skip_list<K, Type>::iterator::operator++( int ) {
		iterator copy = *this;

		++(*this);

		return copy;
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator &Skip_list<K, Type>::iterator::operator--() {
		if ( current_node != 0 ) {
			current_node = current_node->previous;
		}

		return *this;
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::iterator Skip_list<K, Type>::iterator::operator--( int ) {
		iterator copy = *this;

		--(*this);

		return copy;
	}

	template <typename K, typename Type>
	typename Skip_list<K, Type>::pair Skip_list<K, Type>::iterator::operator*() {
		return pair( current_node->key, current_node->value );
	}

	template <typename K, typename Type>
	bool Skip_list<K, Type>::iterator::operator==( iterator const &rhs ) const {
		return ( current_node == rhs.current_node );
	}

	template <typename K, typename Type>
	bool Skip_list<K, Type>::iterator::operator!=( iterator const &rhs ) const {
		return ( current_node != rhs.current_node );
	}

	/****************************************************
	 * ************************************************ *
	 * *                   Friends                    * *
	 * ************************************************ *
	 ****************************************************/


	/*********************************************************************
	 * out << skip;
	 *
	 *  Print the skip list in the following format:
	 *
	 *   Size:     50
	 *   Height:   4
	 *   Total:    534
	 *   Average:  10.68
	 *   3------->|--------|-----------|----------------------> 0
	 *   2-|--|---|------|-|-----|-----|------|---|--||-------> 0
	 *   1-||||-|-|------|-|-||--|--||-|||---||--||--||||||---> 0
	 *   0-**************************************************-> 0
	 *
	 *********************************************************************/

	template <typename K, typename Type>
	std::ostream &operator<<( std::ostream &out, const Skip_list<K, Type> &list ) {
		out << "Size:     " << list.list_size << std::endl;
		out << "Height:   " << list.height << std::endl;
		out << "Total:    " << list.total_search() << std::endl;
		out << "Average:  " << list.average_search() << std::endl;

		for ( int i = list.height - 1; i >= 1; --i ) {
			out << i << "-";

			for ( typename Skip_list<K, Type>::node *ptr = list.head[0]; ptr != 0; ptr = ptr->next[0] ) {
				if ( ptr->levels > i ) {
					out << "|";
				} else {
					out << "-";
				}
			}

			out << "-> 0" << std::endl;
		}

		out << "0-";

		for ( typename Skip_list<K, Type>::node *ptr = list.head[0]; ptr != 0; ptr = ptr->next[0] ) {
			out << "*";
		}

		out << "-> 0";

		if ( !list.empty() ) {
			out << std::endl << list.head[0]->key;

			for ( typename Skip_list<K, Type>::node *ptr = list.head[0]->next[0]; ptr != 0; ptr = ptr->next[0] ) {
				out << ", " << ptr->key;
			}
		}

		return out;
	}
}

#endif