Advertisement
DulcetAirman

Merge-Sort for LinkedList

Sep 27th, 2012
150
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.fhnw.claudemartin.algd2;
  2.  
  3. import java.lang.reflect.Method;
  4. import java.util.Arrays;
  5. import java.util.Iterator;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.ListIterator;
  9.  
  10. public class MSList<T extends Comparable<? super T>> extends LinkedList<T> {
  11.   private static final long serialVersionUID = 0XB00B135L;
  12.  
  13.   public MSList() {
  14.     super();
  15.   }
  16.  
  17.   public void mergeSort() {
  18.     iteratorPool.clear();
  19.     mergeSort(0, size() - 1);
  20.     iteratorPool.clear();
  21.   }
  22.  
  23.   protected void mergeSort(int left, int right) {
  24.     if (left < right) {
  25.       int middle = (left + right) / 2;
  26.       mergeSort(left, middle);
  27.       mergeSort(middle + 1, right);
  28.       merge(left, middle, right);
  29.     }
  30.   }
  31.  
  32.   final List<T> helper = new java.util.LinkedList<T>();
  33.  
  34.   private Method checkForComodification;
  35.   final private LinkedList<ListIterator<T>> iteratorPool = new LinkedList<>();
  36.   /**
  37.    * Return iterator so that itr.nextIndex() == index + 1 and itr.previousIndex() == index.
  38.    * The iterator is set to that the last returned element is at the given index (if index>=0).
  39.    * Iterator at beginning of list: getIteratorAt(-1)
  40.    */
  41.   ListIterator<T> getIteratorAt(final int index) {
  42.     return getIteratorAt(index, null);
  43.   }
  44.   /**
  45.    * Return iterator so that last returned element is at the given index.
  46.    * The returned iterator will not be the same as <i>not</i>.
  47.    */
  48.   ListIterator<T> getIteratorAt(final int index, ListIterator<T> not) {
  49.     ListIterator<T> rv = null;
  50.     if(index == -1) {// this is always fast:
  51.       rv = (ListIterator<T>) this.iterator();
  52.       iteratorPool.add(rv);
  53.       return rv;
  54.     }
  55.     Iterator<ListIterator<T>> poolItr = iteratorPool.iterator();
  56.     while(poolItr.hasNext()) {
  57.       ListIterator<T> itr = poolItr.next();
  58.       if(itr == not) continue;
  59.       try {
  60.         if(checkForComodification == null) {
  61.           checkForComodification = itr.getClass().getDeclaredMethod("checkForComodification");
  62.           checkForComodification.setAccessible(true);
  63.         }
  64.         checkForComodification.invoke(itr);
  65.       } catch (Exception e) {
  66.         poolItr.remove();
  67.         continue;
  68.       }
  69.       if(rv == null) rv = itr;
  70.       else {
  71.         int diffItr = Math.abs(itr.nextIndex() - 1 - index);
  72.         int diffRv = Math.abs(rv.nextIndex() - 1 - index);
  73.         if(diffItr < diffRv)
  74.           rv = itr;
  75.         if(diffItr <= 3)
  76.           break; // close enough
  77.       }
  78.     }
  79.    
  80.     if(rv == null) {
  81.       rv = (ListIterator<T>) iterator();
  82.       iteratorPool.add(rv);
  83.     }
  84.    
  85.     while(rv.nextIndex()<=index)
  86.       rv.next();
  87.     if(rv.previousIndex()>index) {
  88.       while(rv.previousIndex()>index)
  89.         rv.previous();
  90.       rv.previous();
  91.       rv.next(); // last returned == get(index)
  92.     }
  93.     assert rv.previousIndex() == index;
  94.     assert rv.nextIndex() == index + 1;
  95.     return rv;
  96.   }
  97.  
  98.   /**
  99.    * @param left
  100.    *          Index of leftmost element, first element of left part.
  101.    * @param middle
  102.    *          Index of last Element of left part. Right part begins at <code>middle+1</code>.
  103.    * @param right
  104.    *          Index of last Element of right part.
  105.    */
  106.   protected void merge(final int left, final int middle, final int right) {
  107.     if (left >= right)
  108.       return;
  109.     assert middle == (left + right) / 2;
  110.  
  111.     helper.clear();
  112.     ListIterator<T> i1 = this.getIteratorAt(left-1);
  113.     int idx1 = left;
  114.     T o1 = i1.hasNext() ? i1.next() : null;
  115.     assert o1 == null || this.get(idx1) == o1;
  116.  
  117.     ListIterator<T> i2 = this.getIteratorAt(middle, i1);
  118.     int idx2 = middle + 1;
  119.     T o2 = i2.hasNext() ? i2.next() : null;
  120.     assert o2 == null || this.get(idx2) == o2;
  121.  
  122.     while (true) {
  123.       if (o1 == null && o2 == null) {
  124.         break;
  125.       } else if (o2 == null || o1 != null && o1.compareTo(o2) <= 0) {
  126.         helper.add(o1);
  127.         o1 = idx1++ < middle ? i1.next() : null;
  128.       } else {
  129.         helper.add(o2);
  130.         o2 = idx2++ < right ? i2.next() : null;
  131.       }
  132.     }
  133.  
  134.     assert helper.size() == (right-left)+1;
  135.     i1 = this.getIteratorAt(left);
  136.  
  137.     for (T el : helper) {
  138.       i1.set(el);
  139.       if (i1.hasNext())
  140.         i1.next();
  141.     }
  142.   }
  143.  
  144.   @SuppressWarnings("unchecked")
  145.   public MSList<T> clone() {
  146.     return (MSList<T>) super.clone();
  147.   };
  148.  
  149.   @SuppressWarnings({ "unchecked" })
  150.   protected MSList<T>[] split() {
  151.     int half = this.size() / 2;
  152.     MSList<T>[] rv = new MSList[] { new MSList<T>(), new MSList<T>() };
  153.     int index = 0;
  154.     for (index = 0; index < half; index++)
  155.       rv[0].add(this.get(index));
  156.     for (index = half; index < this.size(); index++)
  157.       rv[1].add(this.get(index));
  158.     return rv;
  159.   }
  160.  
  161.   @Override
  162.   public String toString() {
  163.     if (size() < 50)
  164.       return "MSList(n=" + size() + "; " + Arrays.toString(this.toArray()) + ")";
  165.     else
  166.       return "MSList(n=" + size() + ")";
  167.   }
  168. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement