/**
Denne klassen implementerer et binært søketre som er modifisert
til å kunne returnere den i'te største verdien i logaritmisk tid.
Det er spesielt variabelen "antall" og metoden "finnTallNummer" som 
er nye i forhold til et standard søketre.
*/
public class ModifisertNode {

/*	Bruker her flyttall som verdier for enkelhets skyld;
	hvis klassen skulle vært med i en API,
	burde interfacet Comparable vært brukt. */
	private double verdi;

/*	De to barnene til denne noden;
	alle noder i venstre deltre har mindre verdi,
	og alle noder i høyre deltre har større verdi. */
	private ModifisertNode venstre = null;
	private ModifisertNode hoyre = null;
	
/*	Antallet noder i deltreet som denne er rot for.
	Dette må den holde rede på for å kunne finne det
	i'te største tallet. Noden er løvnode når den skapes,
	og antallet blir derfor initialisert til 1. */
	private int antall = 1;
	
	// Standard konstruktor.
	public ModifisertNode(double verdi) {
		this.verdi = verdi;
	}
	
	public double hentVerdi() {
		return verdi;
	}
	
	public void leggTil(ModifisertNode nyNode) {
		// Oppdaterer størrelsen på deltreet
		++antall;
		
		if (nyNode.verdi < verdi) {
			// Noden skal legges til på venstre side
			if (venstre == null) {
				// Venstre deltre var tomt
				venstre = nyNode;
			} else {
				// Noden legges rekursivt til i venstre deltre
				venstre.leggTil(nyNode);
			}
		} else {
			// Noden skal legges til på høyre side
			if (hoyre == null) {
				// Høyre deltre var tomt
				hoyre = nyNode;
			} else {
				// Noden legges rekursivt til i høyre deltre
				hoyre.leggTil(nyNode);
			}
		}
	}
	
	public ModifisertNode finnVerdi(double tall) {
		if (tall == verdi) {
			// Tallet er funnet
			return this;
		}
		if (tall < verdi) {
			// Tallet må ligge på venstre side hvis det finnes
			if (venstre != null) {
				// Det letes rekursivt videre i venstre deltre
				return venstre.finnVerdi(tall);
			}
		}
		if (tall > verdi) {
			// Tallet må ligge på høyre side hvis det finnes
			if (hoyre != null) {
				// Det letes rekursivt videre i høyre deltre
				return hoyre.finnVerdi(tall);
			}
		}
		return null; // Tallet finnes ikke
	}
	
	// Hjelpefunksjon som gjør koden i finnTallNummer mer leselig
	private int deltrestorrelse(ModifisertNode n) {
		if (n==null)
			return 0;
		return n.antall;
	}
	
	// Returnerer noden med den i'te største verdien
	public ModifisertNode finnTallNummer(int i) {
		// Sjekker at "i" ligger innenfor lovlige grenser
		if (i<=0 || i>antall)
			return null;
			
		if (deltrestorrelse(venstre) >= i) {
			// Noden ligger i venstre deltre
			return venstre.finnTallNummer(i);
		} else if (i==deltrestorrelse(venstre)+1) {
			// Noden er funnet
			return this;
		} else {
			// Noden ligger i høyre deltre
			// Vi må trekke fra antallet noder i venstre deltre
			// og denne noden selv fra "i"
			return hoyre.finnTallNummer(i-deltrestorrelse(venstre)-1);
		}
	}

	
	// Denne main-metoden brukes kun til testing
	public static void main(String[] args) {

		// Oppretter rotnoden
		ModifisertNode mittTre = new ModifisertNode(0.723);
		System.out.println("Legg til 0.723");

		// Genererer tilfeldig input til programmet
		java.util.Random rand = new java.util.Random();
		for (int i=0; i<20; ++i) {
			// Velger tilfeldig om et nytt tall skal legges til,
			// eller om et tall skal returneres
			if (rand.nextInt(2)==0) {
				// Legger til et nytt tilfeldig tall
				double nyttTall = rand.nextDouble();
				mittTre.leggTil(new ModifisertNode(nyttTall));
				System.out.println("Legg til "+nyttTall);
			} else {
				// Ber om å få ut et tall
				int tallNr = rand.nextInt(mittTre.antall)+1;
				ModifisertNode minNode = mittTre.finnTallNummer(tallNr);
				System.out.println("Tall nummer " + tallNr + " er " + minNode.hentVerdi());
			}
		}
	}
		
}