import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SkipList implements LinkedList {

  // die oberste Ebene in der Skip-Liste
  SortedList topLayer;
  Random coin = new Random(1);
  
  public SkipList() {
    this.topLayer = new SortedList();
  }

  /** 
   * Liefert den Knoten der nullten Ebene mit dem gesuchten Wert v (wobei Integer.MIN_VALUE < v < Integer.MAX_VALUE). 
   * Falls ein solcher nicht existiert, wird der Knoten der nullten Ebene mit dem zu v nächstkleineren Wert zurückgegeben.
   */
  @Override
  public ListNode search(int v) {
    // TODO Sucht den Knoten auf der *nullten* Ebene.
    //      Dafür muss jeweils auf der aktuellen Ebene der Knoten mit dem Wert v bzw. zu v nächstkleinerem Wert
    //      gesucht werden und dann eine Ebene nach unten gegangen werden.
    return null;
  }
  
  /** 
   * Falls noch kein Knoten mit dem Wert v in der Skip-Liste enthalten ist, wird ein solcher eingefügt 
   * und der Knoten mit dem Wert v auf der untersten Ebene zurückgeben; andernfalls wird der bereits in der untersten 
   * Ebene der Skip-Liste existierende Knoten mit Wert v zurückgegeben. 
   * Für den Eingabewert v gilt: Integer.MIN_VALUE < v < Integer.MAX_VALUE.
   * (Beim Einfügen muss zuerst der Knoten auf der untersten Ebene gefunden werden, neben dem er eingefügt werden soll. 
   * Anschließend wird jeweils mittels Münzwurf entscheiden, ob der Knoten auch in die oberen Ebenen übernommen wird.)
   */
  @Override
  public ListNode insert(int v) {    
    // TODO a) Stelle suchen, an der eingefügt werden soll.
    //      b) Einfügen.
    //      c) Nun mittels Münzwurf entscheiden, ob Knoten auf nächsthöherer Ebene eingefügt wird.
    //      d) Evtl. muss die neue Ebene erstellt werden (createNewLayer()) 
    //         oder der Knoten kann direkt eingefügt werden.
    //      e) Wiederhole c) bis d) bis Münzwurf negativ ausfällt.
    return null;
  }

  /**
   * Erstellt eine neue, leere Ebene oben auf der Skip-Liste.
   */
  public ListNode createNewLayer() {
    SortedList newTopLayer = new SortedList();
    newTopLayer.first.down = topLayer.first;
    newTopLayer.last.down = topLayer.last;
    topLayer.first.up = newTopLayer.first;
    topLayer.last.up = newTopLayer.last;    
    this.topLayer = newTopLayer;
    return this.topLayer.first;
  }
  
  /**
   * Wirft eine Münze.
   * @return
   */
  public boolean flipACoin() {
    return coin.nextDouble() >= 0.5;
  }

  /**
   * Gibt den Inhalt der sortierten Liste aus.
   */  
  public void print() {
    System.out.print("Ebene: "); 
    topLayer.print();
    ListNode current = topLayer.first;
    while (current.down != null) {
      current = current.down;
      System.out.print("Ebene: "); 
      current.print();
    }
    System.out.println("");
  }
  
  /**
   * Hilfsmethode zum Überprüfen der Referenzen
   */
  public boolean checkReferences() {
    boolean correct = topLayer.checkReferences();
    ListNode current = topLayer.first;
    while (current.down != null) {
      current = current.down;
      correct &= current.checkReferences();
      ListNode currentLayer = current;
      
      // ist es die unterste Ebene?
      boolean bottomLevel = current.down == null;
      
      while (currentLayer.next != null) {
        currentLayer = currentLayer.next;
        correct &= bottomLevel || currentLayer.down != null;
        correct &= currentLayer.down == null || currentLayer.down.value == currentLayer.value;
        correct &= currentLayer.up == null || currentLayer.up.value == currentLayer.value;        
      }
    }
    return correct;
  }
      
  public static void main(String[] argv) {
    SkipList s = new SkipList();
    
    List<Integer> numbers = new ArrayList<>();
    for (int i = 20; i >= 1; i--) {
      numbers.add(i);
    }
    for (int i = 1; i < 5; i++) {
      Collections.shuffle(numbers, new Random(1));
    }
        
    System.out.println("Einfügen");
    for (int i : numbers) {
      s.insert(i);      
      s.print();
      checkAndPrint("Verlinkung ok? ", s.checkReferences());      
      checkAndPrint("Knoten vorhanden? ", s.search(i) != null && s.search(i).value == i);
    }
    
    System.out.println("Die Ausgabe sollte so aussehen:");
    
    System.out.println("Ebene: First <-->------->------->------->------->------->------->------->------->------->------->------->------->------->------->-------> 16 <-->------->------->------->-------> Last");
    System.out.println("Ebene: First <-->------->------->------->------->------->------->------->------->------->------->------->------->------->------->-------> 16 <-->------->------->------->-------> Last");
    System.out.println("Ebene: First <-->------->------->------->------->------->  6 <-->------->  8 <-->  9 <-->------->-------> 12 <-->------->------->-------> 16 <-->-------> 18 <-->------->-------> Last");
    System.out.println("Ebene: First <-->------->------->------->------->  5 <-->  6 <-->------->  8 <-->  9 <-->------->-------> 12 <--> 13 <-->-------> 15 <--> 16 <--> 17 <--> 18 <-->------->-------> Last");
    System.out.println("Ebene: First <-->  1 <-->  2 <-->  3 <-->  4 <-->  5 <-->  6 <-->  7 <-->  8 <-->  9 <--> 10 <--> 11 <--> 12 <--> 13 <--> 14 <--> 15 <--> 16 <--> 17 <--> 18 <--> 19 <--> 20 <--> Last");
            
    System.out.println("\nSuche");
    for (int i : numbers) {
      ListNode node = s.search(i);
      System.out.println("Knoten " + i + " gefunden? " + ((node != null && node.value == i) ? "Ja" : "Nein"));
      assert(node != null && node.value == i);
    }
  }
  
  public static void checkAndPrint(String message, boolean correct) {
    if (!correct) {
      System.out.println(message + "NEIN");
    } 
    assert(correct);
  }
}