// Hlutir af tagi SkipList<E> eru skopplistar (skip lists)
// sem innihalda safn gilda af tagi E.  Gildi af tagi E
// verða að vera samanburðarhæf hvort við annað.  Dæmi um
// lögleg E eru t.d. klasarnir Double, Integer og String.
//
// Þetta er dæmi um fjölnota (generic) klasa.  Ekki verður
// spurt um fjölnota klasa á prófi, en líklegt er að margir
// hafi samt áhuga á þessum möguleika í Java.
// 
// Höfundur: Snorri Agnarsson, snorri@hi.is
//
class SkipList<E extends Comparable<? super E>>
{

	// Hlutir af tagi SkipListNode eru hnútar í skopplista.
	private static class SkipListNode<T>
	{
		private T value;
		private SkipListNode<T>[] next;

		// Notkun: node = new SkipListNode<E>(lev,val);
		// Eftir:  node er nýr hlekkur á lev hæðum með
		//         gildi val.
		public SkipListNode( int lev, T val )
		{
			value = val;
			next = (SkipListNode<T>[])new SkipListNode[lev];
		}
	}

	static final int MAXLEVEL = 32;
	static final double PROMOTION_PROBABILITY = 0.5;
	
	private SkipListNode<E> startNode;
	private int count;
	
	// Fastayrðing gagna:
	//
	//  1) Fjöldi gilda í skopplistanum er count.
	//  2) startNode vísar á sérstakan hlekk sem notaður
	//     er sem byrjunarhnútur í öllum keðjunum.
	//     a) Gildið í þeim hlekk skiptir ekki máli og er
	//        ekki talið með í safni gilda skopplistans.
	//     b) Hæð þess hlekks er a.m.k. jöfn mestu hæð
	//        hinna hlekkjanna í skopplistanum.
	//  3) Hlekkirnir eru í vaxandi röð miðað við gildið í
	//     value.
	//
	//  Fyrir SkipListNode gildir:
	//  4) value er gildið í hnútnum.
	//  5) Hnúturinn er í hæðum 0,...,next.length()-1 í 
	//     skopplistanum, þ.e. fyrir i=0,...,next.length()-1
	//     gildir að next[i] er keðja þeirra hlekkja sem eru 
	//     fyrir aftan þennan hlekk í hæð i.  Sérhver keðja
	//     endar á hlekk með next[i]==null.
	//  6) Allir hlekkirnir eru í hæð 0, sumir einnig í hæð 1,
	//     sumir þeirra sem eru í hæð 1 eru einnig í hæð 2,
	//     o.s.frv.  Ef hlekkur er í hæð i+1 þá er hann einnig
	//     í hæð i.

	// Notkun: SkipList<E> s = new SkipList<E>();
	// Eftir:  s er nýr tómur skopplisti gilda af tagi E.
	public SkipList()
	{
		startNode = new SkipListNode<E>(1,null);
		count = 0;
	}
	
	// Notkun: n = s.getCount();
	// Eftir:  n er fjöldi gilda í s.
	public int getCount()
	{
		return count;
	}

	// Notkun: finger = s.search(val);
	// Eftir:  finger er leitarfingur fyrir gildið val, þ.e.
	//         finger er fylki af lengd lev, þar sem
	//         lev er mesta hæð í s þannig að fyrir
	//         i=0,...,lev-1 gildir að finger[i] vísar á 
	//         aftasta hlekk í keðjunni í hæð i sem hefur
	//         gildi minna en val.  Athugið að sá hlekkur
	//         gæti verið byrjunarhlekkurinn í keðjunni, en
	//         gildi hans er ekki talið með í safninu.
	private SkipListNode<E>[] search( E val )
	{
		int level = startNode.next.length;
		SkipListNode<E>[] finger = 
			(SkipListNode<E>[])new SkipListNode[level];
		level--;
		finger[level] = startNode;
		for(;;)
		{
			// * Fyrir i=level+1,... gildir að finger[i] vísar
			//   á hlekk í keðjunni í hæð i frá startNode til 
			//   og með hlekknum sem finger[i] vísar á og öll
			//   gildin í þessum framhluta, til og með þeim 
			//   sem hlekk sem finger[i] vísar á eru < s og 
			//   afgangurinn, undirkeðjan frá og með 
			//   finger[i].next[i] er öll >= s.
			//   Með öðrum orðum: Hæðirnar fyrir ofan hæð i eru
			//   afgreiddar.
			// * Undirkeðjan frá startNode.next[level] til og
			//   með hlekknum sem finger[level] vísar á er 
			//   öll < s.  Sem sagt: Við erum enn að leita að
			//   réttum stað í hæð i.
			if( finger[level].next[level] == null
			||  finger[level].next[level].value.compareTo(val) >= 0
			)
			{
				if( level==0 ) return finger;
				// Niður um eina hæð:
				level--;
				finger[level] = finger[level+1];
				continue;
			}
			// Áfram eitt skref í sömu hæð:
			finger[level] = finger[level].next[level];
		}
	}

	// Notkun: s.insert(val);
	// Fyrir:  val er gildi af tagi E.
	// Eftir:  Búið er að bæta val við s.
	public void insert( E val )
	{
		count++;
		int lev = 1;
		while( lev < MAXLEVEL )
		{
			// 1 <= lev <= MAXLEVEL
			// Líkindin á því að við séum stödd hér í byrjun
			// umferðar eftir að lykkjan hófst eru 
			//     PROMOTION_PROBABILITY^(lev-1)
			if( java.lang.Math.random() > PROMOTION_PROBABILITY )
				break;
			lev++;
		}
		// Fyrir i=1,...,MAXLEVEL gildir að líkindin á því að
		// lev sé jafnt i eða hærri eru
		//     PROMOTION_PROBABILITY^(i-1)
		SkipListNode<E> newNode = new SkipListNode<E>(lev,val);
		if( lev > startNode.next.length )
		{
			SkipListNode<E>[] newNext =
				(SkipListNode<E>[])new SkipListNode[lev];
			System.arraycopy( startNode.next, 0
			                , newNext, 0
			                , startNode.next.length
			                );
			startNode.next = newNext;
		}
		SkipListNode<E>[] finger = search(val);
		for( int i=0 ; i!=lev ; i++ )
		{
			// Búið er að setja nýja hlekkinn inn í allar
			// keðjur í hæðum 0..i-1.
			SkipListNode<E> tmp = finger[i].next[i];
			finger[i].next[i] = newNode;
			newNode.next[i] = tmp;
		}
	}

	// Notkun: s.delete(val);
	// Fyrir:  val er gildi af tagi E.
	// Eftir:  Búið er að eyða einu eintaki af val úr
	//         s ef það var til í s, annars er s óbreytt.
	public void delete( E val )
	{
		SkipListNode<E>[] finger = search(val);
		if( finger[0].next[0] == null
		||  finger[0].next[0].value.compareTo(val) != 0
		)
			return;
		count--;
		SkipListNode<E> nodeToGo = finger[0].next[0];
		for( int i=0
		   ; i!=finger.length && finger[i].next[i]==nodeToGo
		   ; i++
		   )
		{
			// Búið er að eyða hlekknum nodeToGo úr keðjunum á
			// hæðum 0..i-1.
			finger[i].next[i] = nodeToGo.next[i];
		}
	}

	// Notkun: x = s.min();
	// Fyrir:  s er ekki-tómur skopplisti.
	// Eftir:  x er minnsta gildi í s.
	public E min()
	{
		return startNode.next[0].value;
	}

	// Notkun: x = s.max();
	// Fyrir:  s er ekki-tómur skopplisti.
	// Eftir:  x er stærsta gildi í s.
	public E max()
	{
		int lev=startNode.next.length-1;
		SkipListNode<E> curr = startNode;
		for(;;)
		{
			// curr vísar á einhvern hlekk í keðjunni.
			// Afgangurinn af keðjunni, fyrir aftan
			// curr, hefur í mesta lagi hæð lev, þ.e.
			// engir vísar eru í next[lev+1,...].
			if( curr.next[lev]==null )
			{
				if( lev==0 ) return curr.value;
				lev--;
			}
			else
			{
				curr = curr.next[lev];
			}
		}
	}

	// Notkun: b = s.find(val);
	// Fyrir:  val er gildi af tagi E.
	// Eftir:  b er satt þþaa val sé til í s.
	public boolean find( E val )
	{
		SkipListNode<E>[] finger = search(val);
		if( finger[0].next[0]==null ) return false;
		return
			finger[0].next[0].value.compareTo(val)==0;
	}

	// Notkun: main(args);
	// Eftir:  Búið er að prófa skopplistaklasann og skrifa
	//         villuboð ef villa fannst.
	static public void main( String[] args )
	{
		SkipList<Double> s = new SkipList<Double>();
		for( int i=0 ; i!=1000000 ; i++ )
		{
			// s inniheldur i slembitölur
			s.insert(java.lang.Math.random());
		}
		double last = s.max();
		s.delete(last);
		while( s.getCount()!=0 )
		{
			// Búið er að fjarlægja eitt eða fleiri af stærstu
			// gildunum úr s og þau komu út úr s í réttri röð.
			// Minnsta gildið sem hefur verið fjarlægt er í
			// last, og er það því >= öll gildin sem eftir eru
			// í s.
			double next = s.max();
			if( last < next )
				throw new Error("Buggy skip list class");
			s.delete(next);
			last = next;
		}
	}
}