Pasted

package ch.fhnw.claudemartin.algd2;
 
import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
 
public class MSList<T extends Comparable<? super T>> extends LinkedList<T> {
  private static final long serialVersionUID = 0XB00B135L;
 
  public MSList() {
    super();
  }
 
  public void mergeSort() {
    iteratorPool.clear();
    mergeSort(0, size() - 1);
    iteratorPool.clear();
  }
 
  protected void mergeSort(int left, int right) {
    if (left < right) {
      int middle = (left + right) / 2;
      mergeSort(left, middle);
      mergeSort(middle + 1, right);
      merge(left, middle, right);
    }
  }
 
  final List<T> helper = new java.util.LinkedList<T>();
  
  private Method checkForComodification;
  final private LinkedList<ListIterator<T>> iteratorPool = new LinkedList<>();
  /**
   * Return iterator so that itr.nextIndex() == index + 1 and itr.previousIndex() == index.
   * The iterator is set to that the last returned element is at the given index (if index>=0).
   * Iterator at beginning of list: getIteratorAt(-1)
   */
  ListIterator<T> getIteratorAt(final int index) {
    return getIteratorAt(index, null);
  }
  /**
   * Return iterator so that last returned element is at the given index.
   * The returned iterator will not be the same as <i>not</i>.
   */
  ListIterator<T> getIteratorAt(final int index, ListIterator<T> not) {
    ListIterator<T> rv = null;
    if(index == -1) {// this is always fast:
      rv = (ListIterator<T>) this.iterator();
      iteratorPool.add(rv);
      return rv;
    }
    Iterator<ListIterator<T>> poolItr = iteratorPool.iterator();
    while(poolItr.hasNext()) {
      ListIterator<T> itr = poolItr.next();
      if(itr == not) continue;
      try {
        if(checkForComodification == null) {
          checkForComodification = itr.getClass().getDeclaredMethod("checkForComodification");
          checkForComodification.setAccessible(true);
        }
        checkForComodification.invoke(itr);
      } catch (Exception e) {
        poolItr.remove();
        continue;
      }
      if(rv == null) rv = itr;
      else {
        int diffItr = Math.abs(itr.nextIndex() - 1 - index);
        int diffRv = Math.abs(rv.nextIndex() - 1 - index);
        if(diffItr < diffRv)
          rv = itr;
        if(diffItr <= 3)
          break; // close enough
      }
    }
    
    if(rv == null) {
      rv = (ListIterator<T>) iterator();
      iteratorPool.add(rv);
    }
    
    while(rv.nextIndex()<=index)
      rv.next();
    if(rv.previousIndex()>index) {
      while(rv.previousIndex()>index)
        rv.previous();
      rv.previous();
      rv.next(); // last returned == get(index)
    }
    assert rv.previousIndex() == index;
    assert rv.nextIndex() == index + 1;
    return rv;
  }
  
  /**
   * @param left
   *          Index of leftmost element, first element of left part.
   * @param middle
   *          Index of last Element of left part. Right part begins at <code>middle+1</code>.
   * @param right
   *          Index of last Element of right part.
   */
  protected void merge(final int left, final int middle, final int right) {
    if (left >= right)
      return;
    assert middle == (left + right) / 2;
 
    helper.clear();
    ListIterator<T> i1 = this.getIteratorAt(left-1);
    int idx1 = left;
    T o1 = i1.hasNext() ? i1.next() : null;
    assert o1 == null || this.get(idx1) == o1;
 
    ListIterator<T> i2 = this.getIteratorAt(middle, i1);
    int idx2 = middle + 1;
    T o2 = i2.hasNext() ? i2.next() : null;
    assert o2 == null || this.get(idx2) == o2;
 
    while (true) {
      if (o1 == null && o2 == null) {
        break;
      } else if (o2 == null || o1 != null && o1.compareTo(o2) <= 0) {
        helper.add(o1);
        o1 = idx1++ < middle ? i1.next() : null;
      } else {
        helper.add(o2);
        o2 = idx2++ < right ? i2.next() : null;
      }
    }
 
    assert helper.size() == (right-left)+1;
    i1 = this.getIteratorAt(left);
 
    for (T el : helper) {
      i1.set(el);
      if (i1.hasNext())
        i1.next();
    }
  }
 
  @SuppressWarnings("unchecked")
  public MSList<T> clone() {
    return (MSList<T>) super.clone();
  };
 
  @SuppressWarnings({ "unchecked" })
  protected MSList<T>[] split() {
    int half = this.size() / 2;
    MSList<T>[] rv = new MSList[] { new MSList<T>(), new MSList<T>() };
    int index = 0;
    for (index = 0; index < half; index++)
      rv[0].add(this.get(index));
    for (index = half; index < this.size(); index++)
      rv[1].add(this.get(index));
    return rv;
  }
 
  @Override
  public String toString() {
    if (size() < 50)
      return "MSList(n=" + size() + "; " + Arrays.toString(this.toArray()) + ")";
    else
      return "MSList(n=" + size() + ")";
  }
}