import java.util.Collections;

public class Inventar {
  private Gegenstand[] gegenstaende;
  
  public Inventar() {
    this.gegenstaende = new Gegenstand[10];
    gegenstaende[0] = new Gegenstand ("Bogen", 25);
    gegenstaende[1] = new Gegenstand ("Gürtel", 17);
    gegenstaende[2] = new Gegenstand ("Helm", 32);
    gegenstaende[3] = new Gegenstand ("Pfeile", 56);
    gegenstaende[4] = new Gegenstand ("Ring", 25);
    gegenstaende[5] = new Gegenstand ("Schild", 19);
    gegenstaende[6] = new Gegenstand ("Schwert", 8);
    gegenstaende[7] = new Gegenstand ("Rüstung", 66);
    gegenstaende[8] = new Gegenstand ("Stiefel", 29);
    gegenstaende[9] = new Gegenstand ("Kette", 6);
    gegenstaende[9] = new Gegenstand ("Kette2", 20);
    gegenstaende[9] = new Gegenstand ("Kette3", 29);
    //Gegenstand[] gegenstaendeSorted = selectionSort2(gegenstaende);

    //System.out.println("My insertionSort");
    //Gegenstand[] gegenstaendeSorted = insertionSort(gegenstaende);
    //for(int i = 0; i < gegenstaendeSorted.length; i++) {
    //  System.out.println(gegenstaendeSorted[i].getAusdauer());
    //}

    //System.out.println("Mr C insertionSort");
    //Gegenstand[] gegenstaendeSortedC = insertionSort(gegenstaende);
    //for(int i = 0; i < gegenstaendeSortedC.length; i++) {
    //  System.out.println(gegenstaendeSortedC[i].getAusdauer());
    //}

    //Test bubble sort
    System.out.println("Bubble sort");
    Gegenstand[] sortedArray = bubbleSort(gegenstaende);
    for(int i = 0; i < sortedArray.length; i++) {
      System.out.println("Index " + i + " Ausdauer: " + sortedArray[i].getAusdauer());
    }
    
    
    // Test binary search:
    //int position = binarySearch(gegenstaende, gegenstaende[2].getName());
    //System.out.println("Found " + gegenstaende[position].getName() + " at position: " + position + " with 'ausdauer': " + gegenstaende[position].getAusdauer());
  }

  public Gegenstand[] insertionSort(Gegenstand[] gegenstaende) {
    int i = 1;
    while(i < gegenstaende.length) {
      int j = i;

      while(j > 0 && gegenstaende[j-1].getAusdauer() > gegenstaende[j].getAusdauer()) {
        Gegenstand temp = gegenstaende[j-1];
        gegenstaende[j - 1] = gegenstaende[j];
        gegenstaende[j] = temp;

        j--;
      }
      i++;
      showItems(gegenstaende);
    }
    return gegenstaende;
  }

  public void showItems(Gegenstand[] gegenstaende) {
    System.out.print("[ ");
    for(int i = 0; i < gegenstaende.length; i++) {
      System.out.print(gegenstaende[i].getAusdauer() + ", ");
    }
    System.out.println("");
  }

  public Gegenstand[] insertionSortC(Gegenstand[] array) {
    for (int i = 1; i < array.length-1; i++) {
      Gegenstand key = array[i];
      int j = i - 1;

      while(j >= 0 && array[j].getAusdauer() > key.getAusdauer()) {
        array[j + 1] = array[j];
        j--;
      }
      array[j+1] = key;
      showItems(array);
    }
    return array;
  }

  public Gegenstand[] selectionSort2(Gegenstand[] gegenstaende) {
    for (int i = 0; i < gegenstaende.length - 2; i++) {
        int indexDesKleinsten = i;
        for (int j = i + 1; j < gegenstaende.length - 1; j++) {
            if (gegenstaende[j].getName().compareTo(gegenstaende[indexDesKleinsten].getName()) < 0) {
                indexDesKleinsten = j;
            }
        }
        if (indexDesKleinsten != i) {
            Gegenstand helper = gegenstaende[i];
            gegenstaende[i] = gegenstaende[indexDesKleinsten];
            gegenstaende[indexDesKleinsten] = helper;
        }
    }
    return gegenstaende;
  }

  public int binarySearch(Gegenstand[] gegenstaende, String searchedName) {
    int low = 0;
    int high = gegenstaende.length-1;

    while(low <= high) {
      int pivot = (low + high) / 2;

      int compareToResult = gegenstaende[pivot].getName().compareTo(searchedName);
      if(compareToResult == 0) {
        return pivot;
      } else if (compareToResult < 0) {
        low = pivot + 1;
      } else if (compareToResult > 0) {
        high = pivot -1;
      }
    }
    return -1;
  }

  public Gegenstand[] bubbleSort(Gegenstand[] gegenstaende) {
    int n = gegenstaende.length;
    for(int i = 0; i <= n-2; i++) {
      for(int j = 0; j <= n-2-i; j++) {
        if (gegenstaende[j].getAusdauer() > gegenstaende[j+1].getAusdauer()) {
          Gegenstand temp = gegenstaende[j];
          gegenstaende[j] = gegenstaende[j+1];
          gegenstaende[j+1] = temp;
        }
      }
    }
    return gegenstaende;
  }

  public void lineareSuche(String name) {
    // to do
  }

  public Gegenstand[] getGegenstaende() {
    return gegenstaende;
  }

  public void maxAusdauer() {
    // to do
  }
}