Pasted

package ch.fhnw.claudemartin.algd2;
 
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertSame;
import static org.junit.Assert.assertTrue;
 
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
 
import org.junit.Test;
 
public class MSListTest extends MSList<Integer> {
  private static final long serialVersionUID = 1L;
 
  @Test
  public void testMSList() throws Exception {
    Random rnd = new Random(123L);
    MSList<Integer> list = new MSList<>();
    for (int i = 0; i <= 100; i++)
      list.add((int) (rnd.nextInt(101)));
    MSList<Integer> clone = list.clone();
    assertEquals(list, clone);
    list.mergeSort();
    Collections.sort(clone);
    assertEquals(clone, list);
  }
 
  @Test
  public void testGetIteratorAt() {
    MSList<Integer> list = new MSList<Integer>();
    ListIterator<Integer> itr = list.getIteratorAt(-1);
    assertEquals(0, itr.nextIndex());
    assertEquals(-1, itr.previousIndex());
 
    for (int i = 10; i > 0; i--)
      list.add(i);
 
    itr = list.getIteratorAt(5);
    assertSame(itr, list.getIteratorAt(5));
    assertEquals(6, itr.nextIndex());
    assertEquals(5, itr.previousIndex());
  }
 
  @Test
  public void testMergeSortIntInt() {
    MSList<Integer> list = new MSList<Integer>();
    for (int i = 10; i > 0; i--)
      list.add(i);
 
    MSList<Integer> clone = list.clone();
 
    int last = list.size() - 1;
    list.mergeSort(1, last - 1);
    assertEquals(list.get(0), clone.get(0));
    assertEquals(list.get(1), clone.get(last - 1));
    assertEquals(list.get(2), clone.get(last - 2));
    // usw...
    assertEquals(list.get(last), clone.get(last));
  }
 
  @Test
  public void testMerge() {
    { // Ganze Liste mergen:
      MSList<Integer> list = new MSList<Integer>();
      for (int i = 0; i < 20; i++) {
        list.add(i);
        final int lastIdx = list.size() - 1;
        list.merge(0, lastIdx / 2, lastIdx);
        assertTrue(list.toString(), isSorted(list));
      }
      list.addAll(list.clone());
      final int lastIdx = list.size() - 1;
      list.merge(0, (lastIdx - 1) / 2, lastIdx);
      assertTrue(list.toString(), isSorted(list));
 
    }
 
    {// Teilweise mergen:
      MSList<Integer> list = new MSList<Integer>();
      for (int i = 0; i < 20; i++)
        list.add(i);
      // list ist bereits sortiert. Merge darf nichts ändern.
      for (int i = 0; i < list.size() / 2; i++) {
        MSList<Integer> clone = list.clone();
        final int left = i;
        final int right = list.size() - 1;
        list.merge(left, (left + right) / 2, right);
        assertEquals(clone, list);
      }
    }
  }
 
  @Test
  public void testSplit() {
    MSList<Integer> list0 = new MSList<Integer>();
    for (int i = 0; i < 20; i++)
      list0.add(i);
    MSList<Integer> list1 = list0.clone();
    for (int i = 100; i < 20; i++)
      list0.add(i);
 
    MSList<Integer> union = list0.clone();
    union.addAll(list1);
 
    MSList<Integer>[] split = union.split();
    assertEquals(list0, split[0]);
    assertEquals(list1, split[1]);
 
    // Anzahl variierend:
    list0.clear();
    for (int i = 0; i < 20; i++) {
      split = list0.split();
      list1.clear();
      list1.addAll(split[0]);
      list1.addAll(split[1]);
      assertEquals(list0, list1);
      list0.add(i);
    }
  }
 
  @Test
  public void testPerformance() {
    LinkedList<Double> readings = new LinkedList<>();
    for (int n = 5000; n <= 80000; n*=2) {
      MSList<Integer> list = new MSList<Integer>();
      for (int i = 0; i < n; i++)
        list.add(i % 17);
      MSList<Integer> clone = list.clone();
      
      long start = System.currentTimeMillis();
      list.mergeSort();
      long timeMS = System.currentTimeMillis() - start;
      System.out.println("MSList: " + timeMS);
      
      start = System.currentTimeMillis();
      Collections.sort(clone);
      long timeJava = System.currentTimeMillis() - start;
      System.out.println("Java: " + timeJava);
      if (timeJava > 0 && timeJava < timeMS) {
        double reading = (timeMS / timeJava);
        System.out.println("MSList is " + reading + " times slower than Java with n="+n);
        readings.add(reading);
      }
    }
    double avg = 0d;
    for (Double r : readings) 
      avg += r;
    avg /= readings.size();
    System.out.println("Average: "+avg);
  }
 
  public static <T extends Comparable<T>> boolean isSorted(List<T> list) {
    T previous = null;
    for (T t : list) {
      if (previous != null && t.compareTo(previous) < 0)
        return false;
      previous = t;
    }
    return true;
  }
}