sorting.java

java 的源代码

package com.reddragon2046.base.utilities.data.algorithms;

import com.reddragon2046.base.utilities.data.*;
import com.reddragon2046.base.utilities.data.util.IteratorFactory;
import java.util.List;

// Referenced classes of package com.reddragon2046.base.utilities.data.algorithms:
//            IteratorPredicate, IteratorIterator, Predicates

public final class Sorting
{

    private Sorting()
    {
    }

    private static void sort(InputIterator first, InputIterator last)
    {
        sort(first, last, ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    private static void sort(InputIterator first, InputIterator last, BinaryPredicate comparator)
    {
        new Sorting(first, last, comparator);
    }

    public static void sort(List list)
    {
        sort(((InputIterator) (IteratorFactory.start(list))), ((InputIterator) (IteratorFactory.finish(list))), ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    public static void sort(List list, BinaryPredicate comparator)
    {
        sort(((InputIterator) (IteratorFactory.start(list))), ((InputIterator) (IteratorFactory.finish(list))), comparator);
    }

    private Sorting(InputIterator first, InputIterator last, BinaryPredicate comparit)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        if(!(first.getCollection() instanceof List))
        {
            throw new IllegalArgumentException("iterator containers must be a Sequence");
        } else
        {
            base = (List)first.getCollection();
            comparator = comparit;
            int start = IteratorFactory.start(base).distance(first);
            int finish = IteratorFactory.start(base).distance(last);
            quickSortLoop(start, finish);
            finalInsertionSort(start, finish);
            return;
        }
    }

    void finalInsertionSort(int first, int last)
    {
        if(last - first > 16)
        {
            int limit = first + 16;
            for(int i = first + 1; i < limit; i++)
                linearInsert(first, i);

            for(int i = limit; i < last; i++)
                unguardedLinearInsert(i, base.get(i));

        } else
        {
            for(int i = first + 1; i < last; i++)
                linearInsert(first, i);

        }
    }

    void unguardedLinearInsert(int last, Object value)
    {
        for(int next = last - 1; comparator.execute(value, base.get(next)); base.set(last--, base.get(next--)));
        base.set(last, value);
    }

    void linearInsert(int first, int last)
    {
        Object value = base.get(last);
        if(comparator.execute(value, base.get(first)))
        {
            for(int i = last; i > first; i--)
                base.set(i, base.get(i - 1));

            base.set(first, value);
        } else
        {
            unguardedLinearInsert(last, value);
        }
    }

    void quickSortLoop(int first, int last)
    {
        Object pivot = null;
        Object a = null;
        Object b = null;
        Object c = null;
        while(last - first > 16)
        {
            a = base.get(first);
            b = base.get(first + (last - first) / 2);
            c = base.get(last - 1);
            if(comparator.execute(a, b))
            {
                if(comparator.execute(b, c))
                    pivot = b;
                else
                if(comparator.execute(a, c))
                    pivot = c;
                else
                    pivot = a;
            } else
            if(comparator.execute(a, c))
                pivot = a;
            else
            if(comparator.execute(b, c))
                pivot = c;
            else
                pivot = b;
            int cut = first;
            int lastx = last;
            do
            {
                while(comparator.execute(base.get(cut), pivot))
                    cut++;
                for(lastx--; comparator.execute(pivot, base.get(lastx)); lastx--);
                if(cut >= lastx)
                    break;
                Object tmp = base.get(cut);
                base.set(cut++, base.get(lastx));
                base.set(lastx, tmp);
            } while(true);
            if(cut - first >= last - cut)
            {
                quickSortLoop(cut, last);
                last = cut;
            } else
            {
                quickSortLoop(first, cut);
                first = cut;
            }
        }
    }

    public static Range iterSort(List list)
    {
        return iterSort(((InputIterator) (IteratorFactory.start(list))), ((InputIterator) (IteratorFactory.finish(list))));
    }

    public static Range iterSort(List list, BinaryPredicate comparator)
    {
        return iterSort(((InputIterator) (IteratorFactory.start(list))), ((InputIterator) (IteratorFactory.finish(list))), comparator);
    }

    private static Range iterSort(InputIterator first, InputIterator last)
    {
        return iterSort(first, last, ((BinaryPredicate) (new Predicates.HashComparator())));
    }

    private static Range iterSort(InputIterator first, InputIterator last, BinaryPredicate comparator)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        int n = first.distance(last);
        Array array = new Array();
        array.ensureCapacity(n);
        for(ForwardIterator firstx = (ForwardIterator)first.clone(); !firstx.equals(last); firstx.advance())
            array.pushBack(firstx.clone());

        sort(array, new IteratorPredicate(comparator));
        return new Range(new IteratorIterator(array.start(), first.getContainer()), new IteratorIterator(array.finish(), first.getContainer()));
    }

    static final int stlThreshold = 16;
    List base;
    BinaryPredicate comparator;
}