permuting.java

java 的源代码

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

import com.reddragon2046.base.utilities.data.*;

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

public final class Permuting
{

    private Permuting()
    {
    }

    public static boolean nextPermutation(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator)
    {
        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 false;
        i.advance();
        if(i.equals(last))
            return false;
        i = (BidirectionalIterator)last.clone();
        i.retreat();
        do
        {
            BidirectionalIterator ii = (BidirectionalIterator)i.clone();
            i.retreat();
            if(comparator.execute(i.get(), ii.get()))
            {
                BidirectionalIterator j = (BidirectionalIterator)last.clone();
                j.retreat();
                for(; !comparator.execute(i.get(), j.get()); j.retreat());
                Swapping.iterSwap(i, j);
                Reversing.reverse(ii, last);
                return true;
            }
        } while(!i.equals(first));
        Reversing.reverse(first, last);
        return false;
    }

    public static boolean nextPermutation(Container container, BinaryPredicate comparator)
    {
        return nextPermutation((BidirectionalIterator)container.start(), (BidirectionalIterator)container.finish(), comparator);
    }

    public static boolean prevPermutation(BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator)
    {
        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 false;
        i.advance();
        if(i.equals(last))
            return false;
        i = (BidirectionalIterator)last.clone();
        i.retreat();
        do
        {
            BidirectionalIterator ii = (BidirectionalIterator)i.clone();
            i.retreat();
            if(comparator.execute(ii.get(), i.get()))
            {
                BidirectionalIterator j = (BidirectionalIterator)last.clone();
                j.retreat();
                for(; !comparator.execute(j.get(), i.get()); j.retreat());
                Swapping.iterSwap(i, j);
                Reversing.reverse(ii, last);
                return true;
            }
        } while(!i.equals(first));
        Reversing.reverse(first, last);
        return false;
    }

    public static boolean prevPermutation(Container container, BinaryPredicate comparator)
    {
        return prevPermutation((BidirectionalIterator)container.start(), (BidirectionalIterator)container.finish(), comparator);
    }
}