Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement