rotating.java

java 的源代码

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

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

// Referenced classes of package com.reddragon2046.base.utilities.data.algorithms:
//            Copying, Reversing, Swapping

public final class Rotating
{

    private Rotating()
    {
    }

    public static void rotate(List list, int places)
    {
        ForwardIterator start = IteratorFactory.startForward(list);
        ForwardIterator finish = IteratorFactory.finishForward(list);
        ForwardIterator endRotation = IteratorFactory.startForwardAt(list, places);
        rotate(start, endRotation, finish);
    }

    public static void rotate(List list, ForwardIterator pointOfRotation)
    {
        rotate(IteratorFactory.startForward(list), pointOfRotation, IteratorFactory.finishForward(list));
    }

    private static void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        if(first.clone().equals(middle) || middle.clone().equals(last))
            return;
        if(first instanceof RandomAccessIterator)
            rotateRandomAccess((RandomAccessIterator)first, (RandomAccessIterator)middle, (RandomAccessIterator)last);
        else
        if(first instanceof BidirectionalIterator)
            rotateBidirectional((BidirectionalIterator)first, (BidirectionalIterator)middle, (BidirectionalIterator)last);
        else
            rotateForward(first, middle, last);
    }

    private static OutputIterator rotateCopy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result)
    {
        return Copying.copy(first, middle, Copying.copy(middle, last, result));
    }

    public static OutputIterator rotateCopy(List list, int positions, OutputIterator result)
    {
        ForwardIterator start = IteratorFactory.startForward(list);
        ForwardIterator finish = IteratorFactory.finishForward(list);
        ForwardIterator endRotation = IteratorFactory.startForwardAt(list, positions);
        return rotateCopy(start, endRotation, finish, result);
    }

    public static void rotateCopy(List list, int positions, List result)
    {
        rotateCopy(list, positions, ((OutputIterator) (new InsertIterator(result))));
    }

    public static List rotateCopy(List list, int positions)
    {
        Vector result = new Vector(list.size());
        rotateCopy(list, positions, ((List) (result)));
        return result;
    }

    public static OutputIterator rotateCopy(List list, ForwardIterator pointOfRotation, OutputIterator result)
    {
        return rotateCopy(IteratorFactory.startForward(list), pointOfRotation, IteratorFactory.finishForward(list), result);
    }

    public static void rotateCopy(List list, ForwardIterator pointOfRotation, List result)
    {
        rotateCopy(list, pointOfRotation, ((OutputIterator) (new InsertIterator(result))));
    }

    public static List rotateCopy(List list, ForwardIterator pointOfRotation)
    {
        Vector result = new Vector(list.size());
        rotateCopy(list, pointOfRotation, ((List) (result)));
        return result;
    }

    static void rotateBidirectional(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
    {
        Reversing.reverse(first, middle);
        Reversing.reverse(middle, last);
        Reversing.reverse(first, last);
    }

    static void rotateForward(ForwardIterator first, ForwardIterator middle, ForwardIterator last)
    {
        ForwardIterator firstx = (ForwardIterator)first.clone();
        ForwardIterator middlex = (ForwardIterator)middle.clone();
        ForwardIterator i = (ForwardIterator)middle.clone();
        do
        {
            Swapping.iterSwap(firstx, i);
            firstx.advance();
            i.advance();
            if(firstx.equals(middlex))
            {
                if(i.equals(last))
                    return;
                middlex = (ForwardIterator)i.clone();
            } else
            if(i.equals(last))
                i = (ForwardIterator)middlex.clone();
        } while(true);
    }

    static void rotateRandomAccess(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
    {
        for(int n = gcd(first.distance(last), first.distance(middle)); n-- != 0;)
        {
            RandomAccessIterator i = (RandomAccessIterator)first.clone();
            i.advance(n);
            cycle(first, last, i, first.distance(middle));
        }

    }

    static int gcd(int m, int n)
    {
        int t;
        for(; n != 0; n = t)
        {
            t = m % n;
            m = n;
        }

        return m;
    }

    static void cycle(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator initial, int shift)
    {
        Object value = initial.get();
        RandomAccessIterator ptr1 = (RandomAccessIterator)initial.clone();
        RandomAccessIterator ptr2 = (RandomAccessIterator)ptr1.clone();
        ptr2.advance(shift);
        while(!ptr2.equals(initial))
        {
            ptr1.put(ptr2.get());
            ptr1 = (RandomAccessIterator)ptr2.clone();
            if(ptr2.distance(last) > shift)
            {
                ptr2.advance(shift);
            } else
            {
                int delta = shift - ptr2.distance(last);
                ptr2 = (RandomAccessIterator)first.clone();
                ptr2.advance(delta);
            }
        }
        ptr1.put(value);
    }
}