#ifndef SKIPLIST_H
#define SKIPLIST_H

//#define DEBUG

#ifdef DEBUG
#include <conio.h>
#endif

#ifndef RCITLIST_H
#include <rcitlist.h>
#endif

#ifndef DARRAY_H
#include <darray.h>
#endif


#ifndef __STDLIB_H
#include <stdlib.h>
#endif

// This implementation of a skip list uses the type Tower as a descendent of
// *Link* the node class found in *rcitlist.h*. Tower will create new virtual
// functions *insert*, *getNext*, and *removeNext* that will take into account
// the multiple links found in a skip list node. SkipIterator will also
// be implemented to replace ListIterator in the call to List::insert.

const TowerHeight = 4;
// Article on skip lists recommends the following randomLevel function
// to get a good distribution of values at different levels.
// The simple random function seems to do just as well.
/*const double PickLevel = 0.75;//also try 0.5

int randomLevel()
{
	int newLevel=0;
	while ((PickLevel > random(100)/100.0)&& (newLevel < TowerHeight-1))
		newLevel++;
	return newLevel;
}               */
// **** randomLevel not needed

//***** class Tower

template <class Type>
class Tower :public Link<Type>
{
public:
	Tower(int h);
	Tower(Type val,Link<Type> *next, Tower nextOnes,int h = 0);
	// If all pointers point to list nodes, let list distructor get rid of
	// the pointers.
	Link<Type>* insert(Type val,Tower nextOnes,int h);
	Link<Type>* getNextOne(int level);//returns pointer to next node at level
//	virtual Link<Type>* removeNext();// removes next node and adjusts next to next->next
	int getHeight(){return height;}
	Link<Type>* & operator [](int i) {return tower[i];}
protected:
	Array<Link<Type>*> tower;
	int height;
};

//***** class SkipList

template <class Type> class SkipIterator;


template <class Type>
class SkipList :public List<Type>
{
public:
	SkipList(int h = TowerHeight);
	~SkipList();
	virtual ListIterator<Type>* genIterator();// generates an iterator for a type of list
	virtual void 	add(const Type &value);	// add to head of List
	void printLevels();
protected:

	int tallest; //tallest tower currently in list
	int height; // tallest possible tower
	Tower<Type> firstPointers;
	List<Type>::_size;
	List<Type>::ptrToFirstItem;
	friend SkipIterator<Type>;
};

//***** class SkipIterator


template <class Type>
class SkipIterator :public OrderedIterator<Type>
{
public:
	SkipIterator (SkipList<Type>&);
	~SkipIterator();
	virtual int	init(); //sets up the local tower and calls ListIterator::init()
	virtual int	locate(const Type&);// locate the first occurrence of an item
	virtual void 	addBefore(const Type &newValue); // add before current location
	virtual void removeCurrent();// removes the item current from the list
protected:

	virtual void moveToNext(); //advances one through list
	// height, tallest, firstPointers, _size and firstItem
	// are needed to have access to
	// their counterparts in the list.
	int &height;
	int &tallest;
	int &_size;
	Tower<Type> &firstPointers;
	List<Type>::RCPtr *firstItem;

	int currentLevel; // current level in traversal
	Tower<Type> history;//list of previous pointers for backfill.
	Tower<Type> nextOnes;// list of next items
};

//*********** Code for classes **************

//**********  Tower functions **************

template <class Type>
Tower<Type>::Tower(int h=TowerHeight):tower(h,0)
{
	height = h;
	for(int i = 0;i<h;i++)
		tower[i] = NULL;
}

template <class Type>
Tower<Type>::Tower(Type val,Link<Type> *next,Tower<Type> nextOnes,int h = 0)
	:tower(h,0),Link<Type>(val,next)
{
	height = h;
	for(int i = 0;i<h;i++)
		tower[i] = nextOnes[i];//[] operator defined as tower[i]
}



template <class Type>
Link<Type>* Tower<Type>::insert(Type val,Tower<Type> nextOnes,int h)
{
	ptrToNextLink =new Tower<Type>(val,ptrToNextLink,nextOnes,h);
	assert(ptrToNextLink != NULL);
	return ptrToNextLink;
}

template <class Type>
Link<Type>* Tower<Type>::getNextOne(int level)
{
	if ((level >= 0)&& (level < height))
		return tower[level];
	else if(level == -1)
		return getNext();
#ifdef DEBUG
	else
	{
		cout<<"The node containning "<<value()<<" does not have Level "
			<<level<<" height "<<height<<" \n";
		assert(level <height);
		return NULL;
	}
#endif
}

//********** SkipList code ******************

template <class Type>
SkipList<Type>::SkipList(int h = TowerHeight)
	:List<Type>(),firstPointers(h)
{
	randomize();
	height = h;
	tallest = 0;
}

template <class Type>
SkipList<Type>::~SkipList()
{
}

template <class Type>
ListIterator<Type>* SkipList<Type>::genIterator()
{
	ListIterator<Type>* returnVal = new SkipIterator<Type>(*this);
	return returnVal;
}

template <class Type>
void 	SkipList<Type>::add(const Type &value)	// add to head of List
{
	int level = random(height);//randomLevel(); // zero level is always possible

	if (level > tallest)
		tallest = level;
	#ifdef DEBUG
		cerr<<"In add adding "<<value<<" at level "<<level-1<<endl;
	#endif
	Tower<Type> *temp = new Tower<Type>(value,(Tower<Type>*)ptrToFirstItem->data,firstPointers,level);
	assert(temp != NULL);
	ptrToFirstItem->data = temp;
	_size++;
	// connect this new node up to the level of its tower
	for (int i = 0; i< level;i++)
		firstPointers[i] = temp;
}

template <class Type>
void SkipList<Type>::printLevels()
{
	for(int i = tallest-1;i>=0;i--)
	{
			cout<<"*********\nlevel "<<i<<endl;
		Link<Type> *now = firstPointers[i];
		while (now)
		{
			cout<<now->value()<<' ';
			now = ((Tower<Type>*)now)->getNextOne(i);
		}
		cout<<endl;
	}
	#ifdef DEBUG
	getch();
	#endif
}


//********** SkipIterator code

template <class Type>
SkipIterator<Type>::SkipIterator(SkipList<Type> &l)
	:OrderedIterator<Type>(l),height(l.height),tallest(l.tallest),
	_size(l._size),history(height),nextOnes(height),
	firstPointers(l.firstPointers),firstItem(l.ptrToFirstItem)
{
	init();
}

template <class Type>
SkipIterator<Type>::~SkipIterator()
{

}

template <class Type>
int SkipIterator<Type>::init()
{
	ListIterator<Type>::init();

	currentLevel = tallest-1;//Start at the shallowest list (the top)
	if (currentLevel >=0)
		current = firstPointers[currentLevel]; //look as far as possible into list
	return current != NULL;
 // otherwise current is data->ptrToFirstItem set in ListIterator::init()
}

template <class Type>
void SkipIterator<Type>::moveToNext()
{
		previous = current;
		current = ((Tower<Type>*)current)->getNextOne(currentLevel);
}


template <class Type>
int SkipIterator<Type>::locate(const Type &val)
{

	init();	//start at the beginning
	#ifdef DEBUG
		cout<<"Seaching for "<<val<<" starting at level "<<currentLevel<<endl;
	#endif
	while (currentLevel >=-1)//search at each level -1 is link level
	{
		#ifdef DEBUG
		if(current)
			cout<<"current item "<<current->value()<<" ";
		else
			cout<<"current is NULL ";
		#endif
		while (current && current->value() < val)
		{
			moveToNext();
			#ifdef DEBUG
			if (current)
				cout<<" Moving to next item of "<<current->value()<<' ';
			else
				cout<<" Next item NULL "<<endl;
			#endif
		}
		if (currentLevel>=0) // save place for backfilling if insert or delete
		{
			history[currentLevel] = previous;
			nextOnes[currentLevel] = current;
		}
		if (--currentLevel >=-1) // go to next level and find next item
		{
		  if (previous)
			current = ((Tower<Type>*)previous)->getNextOne(currentLevel);
		  else if(currentLevel >= 0)
			current = firstPointers[currentLevel];
		  else
			current = firstItem->data;
		}
	  #ifdef DEBUG
	  cout<<endl;
	  #endif
	}

	if(current && (current->value() == val))
		return 1;
	else
		return 0;
}

template <class Type>
void 	SkipIterator<Type>::addBefore(const Type &newValue) // add before current location
{
	if(previous)// insert in the middle of the list
	{
		int newLevel = random(height);//randomLevel();//
		#ifdef DEBUG
		cout<<"In addBefore adding "<<newValue<<" at level "<<newLevel-1<<endl;
		#endif
      // new node found in previous after the next line
		previous =
			((Tower<Type>*)previous)->insert(newValue,nextOnes,newLevel);
		// if new node is taller than all previous nodes it must be connected
		// to the beginning of the list.

		if (newLevel > tallest)
		{
			for(int i = tallest;i<newLevel;i++)
				firstPointers[i]=previous;
			tallest = newLevel;
		}
		// set all the the things in front of newLink to point to newLink
		// at the correct level(s). history is only active from 0 to currentLevel
		for (int i = 0;i<newLevel;i++)
			if(history[i]) //if there is a prior node set next pointer
				(*((Tower<Type>*)history[i]))[i]=previous;//set the next pointer for previous towers
		_size++;
	}
	else  //insert at the beginning of the list
		theList.add(newValue);
	_pos++;
}                     

template <class Type>
void SkipIterator<Type>::removeCurrent()
{
	#ifdef DEBUG
	cout<<"\n********In removeCurrent with current value "<<current->value()<<endl;
	#endif
	if(previous==NULL && current && (((Tower<Type>*)current)->getHeight()>0))
	{
		// adjust the first pointers because the first thing in list
		// has been removed.
		#ifdef DEBUG
		cout<<"Must have previous == NULL. Next values are\n";
		for(int j =0;j<((Tower<Type>*)current)->getHeight();j++)
		{
			cout<<"level "<<j<<' ';
			if(((Tower<Type>*)current)->getNextOne(j))
				cout<<' '<<((Tower<Type>*)current)->getNextOne(j)->value()<<endl;
			else
				cout<<' '<<"NULL"<<endl;
		}
		getch();
		#endif
		for(int i = tallest-1;i>=0;i--)
			if (firstPointers[i] == current)
			{
				firstPointers[i] = ((Tower<Type>*)current)->getNextOne(i);
				if(firstPointers[i] ==NULL) //tallest is now shorter
					tallest--;
			}
	}
	else if (current && (((Tower<Type>*)current)->getHeight()>0))//used only with current not NULL
	{
	//must reconnect history to make sure that list is maintained
		#ifdef DEBUG
		cout<<"Next values in removeCurrent\n";
		for(int j =0;j<((Tower<Type>*)current)->getHeight();j++)
		{
			cout<<"level "<<j<<' ';
			if(((Tower<Type>*)current)->getNextOne(j))
				cout<<' '<<((Tower<Type>*)current)->getNextOne(j)->value()<<endl;
			else
				cout<<' '<<"NULL"<<endl;
		}
		getch();
		#endif
		for (int i = 0;i<((Tower<Type>*)current)->getHeight();i++)
			if(history[i]) //if there is a prior node set next pointer
				(*((Tower<Type>*)history[i]))[i]=
					((Tower<Type>*)current)->getNextOne(i);//set the next pointer for previous towers
			else//nothing before current here so readjust
			{
				firstPointers[i] =((Tower<Type>*)current)->getNextOne(i);
				if(firstPointers[i] ==NULL) //tallest is now shorter
					tallest--;
			}
	}
	
	ListIterator<Type>::removeCurrent();//takes care of the list connections
}
#endif