Advertisement
DulcetAirman

JUnit-Tests for Merge-Sort for LinkedList

Sep 27th, 2012
234
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.fhnw.claudemartin.algd2;
  2.  
  3. import static org.junit.Assert.assertEquals;
  4. import static org.junit.Assert.assertSame;
  5. import static org.junit.Assert.assertTrue;
  6.  
  7. import java.util.Collections;
  8. import java.util.LinkedList;
  9. import java.util.List;
  10. import java.util.ListIterator;
  11. import java.util.Random;
  12.  
  13. import org.junit.Test;
  14.  
  15. public class MSListTest extends MSList<Integer> {
  16.   private static final long serialVersionUID = 1L;
  17.  
  18.   @Test
  19.   public void testMSList() throws Exception {
  20.     Random rnd = new Random(123L);
  21.     MSList<Integer> list = new MSList<>();
  22.     for (int i = 0; i <= 100; i++)
  23.       list.add((int) (rnd.nextInt(101)));
  24.     MSList<Integer> clone = list.clone();
  25.     assertEquals(list, clone);
  26.     list.mergeSort();
  27.     Collections.sort(clone);
  28.     assertEquals(clone, list);
  29.   }
  30.  
  31.   @Test
  32.   public void testGetIteratorAt() {
  33.     MSList<Integer> list = new MSList<Integer>();
  34.     ListIterator<Integer> itr = list.getIteratorAt(-1);
  35.     assertEquals(0, itr.nextIndex());
  36.     assertEquals(-1, itr.previousIndex());
  37.  
  38.     for (int i = 10; i > 0; i--)
  39.       list.add(i);
  40.  
  41.     itr = list.getIteratorAt(5);
  42.     assertSame(itr, list.getIteratorAt(5));
  43.     assertEquals(6, itr.nextIndex());
  44.     assertEquals(5, itr.previousIndex());
  45.   }
  46.  
  47.   @Test
  48.   public void testMergeSortIntInt() {
  49.     MSList<Integer> list = new MSList<Integer>();
  50.     for (int i = 10; i > 0; i--)
  51.       list.add(i);
  52.  
  53.     MSList<Integer> clone = list.clone();
  54.  
  55.     int last = list.size() - 1;
  56.     list.mergeSort(1, last - 1);
  57.     assertEquals(list.get(0), clone.get(0));
  58.     assertEquals(list.get(1), clone.get(last - 1));
  59.     assertEquals(list.get(2), clone.get(last - 2));
  60.     // usw...
  61.     assertEquals(list.get(last), clone.get(last));
  62.   }
  63.  
  64.   @Test
  65.   public void testMerge() {
  66.     { // Ganze Liste mergen:
  67.       MSList<Integer> list = new MSList<Integer>();
  68.       for (int i = 0; i < 20; i++) {
  69.         list.add(i);
  70.         final int lastIdx = list.size() - 1;
  71.         list.merge(0, lastIdx / 2, lastIdx);
  72.         assertTrue(list.toString(), isSorted(list));
  73.       }
  74.       list.addAll(list.clone());
  75.       final int lastIdx = list.size() - 1;
  76.       list.merge(0, (lastIdx - 1) / 2, lastIdx);
  77.       assertTrue(list.toString(), isSorted(list));
  78.  
  79.     }
  80.  
  81.     {// Teilweise mergen:
  82.       MSList<Integer> list = new MSList<Integer>();
  83.       for (int i = 0; i < 20; i++)
  84.         list.add(i);
  85.       // list ist bereits sortiert. Merge darf nichts ändern.
  86.       for (int i = 0; i < list.size() / 2; i++) {
  87.         MSList<Integer> clone = list.clone();
  88.         final int left = i;
  89.         final int right = list.size() - 1;
  90.         list.merge(left, (left + right) / 2, right);
  91.         assertEquals(clone, list);
  92.       }
  93.     }
  94.   }
  95.  
  96.   @Test
  97.   public void testSplit() {
  98.     MSList<Integer> list0 = new MSList<Integer>();
  99.     for (int i = 0; i < 20; i++)
  100.       list0.add(i);
  101.     MSList<Integer> list1 = list0.clone();
  102.     for (int i = 100; i < 20; i++)
  103.       list0.add(i);
  104.  
  105.     MSList<Integer> union = list0.clone();
  106.     union.addAll(list1);
  107.  
  108.     MSList<Integer>[] split = union.split();
  109.     assertEquals(list0, split[0]);
  110.     assertEquals(list1, split[1]);
  111.  
  112.     // Anzahl variierend:
  113.     list0.clear();
  114.     for (int i = 0; i < 20; i++) {
  115.       split = list0.split();
  116.       list1.clear();
  117.       list1.addAll(split[0]);
  118.       list1.addAll(split[1]);
  119.       assertEquals(list0, list1);
  120.       list0.add(i);
  121.     }
  122.   }
  123.  
  124.   @Test
  125.   public void testPerformance() {
  126.     LinkedList<Double> readings = new LinkedList<>();
  127.     for (int n = 5000; n <= 80000; n*=2) {
  128.       MSList<Integer> list = new MSList<Integer>();
  129.       for (int i = 0; i < n; i++)
  130.         list.add(i % 17);
  131.       MSList<Integer> clone = list.clone();
  132.      
  133.       long start = System.currentTimeMillis();
  134.       list.mergeSort();
  135.       long timeMS = System.currentTimeMillis() - start;
  136.       System.out.println("MSList: " + timeMS);
  137.      
  138.       start = System.currentTimeMillis();
  139.       Collections.sort(clone);
  140.       long timeJava = System.currentTimeMillis() - start;
  141.       System.out.println("Java: " + timeJava);
  142.       if (timeJava > 0 && timeJava < timeMS) {
  143.         double reading = (timeMS / timeJava);
  144.         System.out.println("MSList is " + reading + " times slower than Java with n="+n);
  145.         readings.add(reading);
  146.       }
  147.     }
  148.     double avg = 0d;
  149.     for (Double r : readings)
  150.       avg += r;
  151.     avg /= readings.size();
  152.     System.out.println("Average: "+avg);
  153.   }
  154.  
  155.   public static <T extends Comparable<T>> boolean isSorted(List<T> list) {
  156.     T previous = null;
  157.     for (T t : list) {
  158.       if (previous != null && t.compareTo(previous) < 0)
  159.         return false;
  160.       previous = t;
  161.     }
  162.     return true;
  163.   }
  164. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement