shuffling.java

来自「java 的源代码」· Java 代码 · 共 85 行

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;
import java.util.Random;

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

public final class Shuffling
{

    private Shuffling()
    {
    }

    private static void randomShuffle(ForwardIterator first, ForwardIterator last, Random rand)
    {
        if(!first.isCompatibleWith(last))
            throw new IllegalArgumentException("iterators not compatible");
        if(!(first.getContainer() instanceof Sequence))
            throw new IllegalArgumentException("iterator containers must be a Sequence");
        BidirectionalIterator i = (BidirectionalIterator)first.clone();
        if(i.equals(last))
            return;
        i.advance();
        for(int n = 2; !i.equals(last); n++)
        {
            BidirectionalIterator j = (BidirectionalIterator)first.clone();
            j.advance(Math.abs(rand.nextInt()) % n);
            Swapping.iterSwap(i, j);
            i.advance();
        }

    }

    private static void randomShuffle(ForwardIterator first, ForwardIterator last)
    {
        randomShuffle(first, last, randgen);
    }

    public static void randomShuffle(List list, Random rand)
    {
        randomShuffle(((ForwardIterator) (IteratorFactory.start(list))), ((ForwardIterator) (IteratorFactory.finish(list))), rand);
    }

    public static void randomShuffle(List list)
    {
        randomShuffle(list, randgen);
    }

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

    public static Range iterShuffle(List list, Random rand)
    {
        return iterShuffle(((ForwardIterator) (IteratorFactory.start(list))), ((ForwardIterator) (IteratorFactory.finish(list))), rand);
    }

    private static Range iterShuffle(ForwardIterator first, ForwardIterator last)
    {
        return iterShuffle(first, last, randgen);
    }

    private static Range iterShuffle(ForwardIterator first, ForwardIterator last, Random rand)
    {
        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());

        randomShuffle(array, rand);
        return new Range(new IteratorIterator(array.start(), first.getContainer()), new IteratorIterator(array.finish(), first.getContainer()));
    }

    static Random randgen = new Random();

}