Thursday, March 16, 2017

SelectionSort

public class SelectionSort {
  public static void main(String[] args) {

    // Utilities
    SwissArmySorter<String> sorter = new SwissArmySorter<String>();
    Copier<String> copier = new Copier<String>();

    // Default Sequence (selected by Knuth on March 19, 1963)
    String[] seq = (args.length > 0) ? args :
      new String[] {
        "503",
        "087",
        "512",
        "061",
        "908",
        "170",
        "897",
        "275",
        "653",
        "426",
        "154",
        "509",
        "612",
        "677",
        "765",
        "703"
      };

    // Copies of the Sequence
    String[] copy1 = copier.copy(seq, new String[seq.length]);    
    String[] copy2 = copier.copy(seq, new String[seq.length]);

    // Swiss Army Arrays
    SwissArmyArray<String> seq1 = new SwissArmyArray<String>(copy1);
    SwissArmyArray<String> seq2 = new SwissArmyArray<String>(copy2);

    // Sort First Swiss Army Array
    sorter.simpleSelectionSort(seq1);
    System.out.println(seq1.getMeter().getReading());
    System.out.println(seq1.toString());

    // Sort Second Swiss Army Array
    sorter.pickySelectionSort(seq2);
    System.out.println(seq2.getMeter().getReading());
    System.out.println(seq2.toString());
  }
}

class SwissArmySorter<T extends Comparable<T>> {

  public SwissArmyArray<T> simpleSelectionSort(SwissArmyArray<T> seq) {
    // Swaps indiscriminately.
    SwissArmyIndex i = new SwissArmyIndex(seq);
    SwissArmyIndex j = new SwissArmyIndex(seq);
    for (i.set(0); !i.tooBig(); i.step()) {
      for (j.set(i.plus(1)); !j.tooBig(); j.step()) {
        if (seq.inDescendingOrder(i, j)) {
          seq.swap(i, j);
        }
      }
    }
    return seq;
  }

  public SwissArmyArray<T> pickySelectionSort(SwissArmyArray<T> seq) {
    // Swap selectively instead. (Modify the following code.)
    SwissArmyIndex i = new SwissArmyIndex(seq);
    SwissArmyIndex j = new SwissArmyIndex(seq);
    for (i.set(0); !i.tooBig(); i.step()) {
      for (j.set(i.plus(1)); !j.tooBig(); j.step()) {
        if (seq.inDescendingOrder(i, j)) {
          seq.swap(i, j);
        }
      }
    }
    return seq;
  }
}

class Converter<T> {
  public String toString(T[] seq) {
    String s = "[";
    for (int i = 0; i < seq.length; i++) {
      if (i > 0) {
        s += " ";
      }
      s += seq[i].toString();
    }
    s += "]";
    return s;
  }
}

class Copier<T> {
  public T[] copy(T[] orig, T[] copy) {
    int i;
    if (orig != null && copy != null && orig.length == copy.length) {
      i = orig.length;
      while (--i >= 0) {
        copy[i] = orig[i];
      }
    }
    return copy;
  }
}

class Meter {
  private String reading = "";
  public void tick(String s) {
    reading += s;
  }
  public String getReading() {
    return reading;
  }
}

interface IMeteredWithMaxIndex {
  Meter getMeter();
  int getMaxIndex();
}

class SwissArmyArray<T extends Comparable<T>>
implements IMeteredWithMaxIndex {

  private T[] seq;  
  private SwissArmyIndex indexReg;
  private T valueReg;
  private Converter<T> converter;
  private Meter meter;

  public SwissArmyArray(T[] array) {
    seq = array;
    converter = new Converter<T>();
    meter = new Meter();
  }
  public Meter getMeter() {
    return meter;
  }
  public void setStoredValue(T value) {
    meter.tick("W");
    valueReg = value;
  }
  public T getStoredValue() {
    meter.tick("R");
    return valueReg;
  }
  public void setStoredIndex(SwissArmyIndex i) {
    meter.tick("W");
    SwissArmyIndex copy = new SwissArmyIndex(i);
    copy.set(i.get());
    indexReg = copy; // Store copy of i, not i itself which may change.
  }
  public SwissArmyIndex getStoredIndex() {
    meter.tick("R");
    return indexReg;
  }
  public T get(int i) {
    meter.tick("R");
    return seq[i];
  }
  public void set(int i, T value) {
    meter.tick("W");
    seq[i] = value;
  }
  public int getMaxIndex() {
    meter.tick("R");
    return seq.length - 1;
  }
  public int compare(int i, int j) {
    meter.tick("C");
    return seq[i].compareTo(seq[j]);
  }
  public int compare(SwissArmyIndex i, SwissArmyIndex j) {
    return compare(i.get(), j.get());
  }
  public void swap(int i, int j) {
    System.out.print("(" + get(i) + "," + get(j) + ") -> ");
    setStoredValue(get(i));
    set(i, get(j));
    set(j, getStoredValue());
    System.out.println("(" + get(i) + "," + get(j) + ")");
  }
  public void swap(SwissArmyIndex i, SwissArmyIndex j) {
    swap(i.get(), j.get());
  }
  public boolean inDescendingOrder(int i, int j) {
    return compare(i, j) > 0;
  }
  public boolean inDescendingOrder(SwissArmyIndex i, SwissArmyIndex j) {
    return compare(i, j) > 0;
  }
  public boolean inAscendingOrder(int i, int j) {
    return compare(i, j) < 0;
  }
  public boolean inAscendingOrder(SwissArmyIndex i, SwissArmyIndex j) {
    return compare(i, j) < 0;
  }
  public String toString() {
    return converter.toString(seq);
  }
}

class SwissArmyIndex
implements IMeteredWithMaxIndex {

  int i;
  int maxIndex;
  Meter meter;
  
  public SwissArmyIndex(IMeteredWithMaxIndex obj) {
    meter = obj.getMeter();
    setMaxIndex(obj.getMaxIndex());
  }
  public Meter getMeter() {
    return meter;
  }
  public void setMaxIndex(int max) {
    meter.tick("w");
    maxIndex = max;
  }
  public int getMaxIndex() {
    meter.tick("r");
    return maxIndex;
  }
  public boolean tooBig() {
    meter.tick("c");
    return i > maxIndex;
  }
  public int get() {
    meter.tick("r");
    return i;
  }
  public void set(int value) {
    meter.tick("w");
    i = value;
  }
  public void step() {
    meter.tick("w");
    i = this.plus(1);
  }
  public int plus(int n) {
    meter.tick("ra");
    return i + n;
  }
}