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