Examples of cc.redberry.core.utils.BitArray

cc.redberry.core.utils.BitArray
This class represents an "array of booleans" with many fast and useful methods. Consumes ~ 8 times less memory than array of booleans for big sizes. Has slightly different semantics than java's built in {@link java.util.BitSet} andalso provides addititonal functionality like {@link #loadValueFrom(BitArray,int,int,int)} and {@link #copyOfRange(int,int)}.

     */
    public static BigInteger orderOfPermutation(short[] permutation) {
        //we shall decompose this permutation into product of cycles and calculate l.c.m. of their sizes


        //to mark viewed points
        BitArray used = new BitArray(permutation.length);
        //lcm
        BigInteger lcm = BigInteger.ONE, temp;


        int start, pointer, currentSize, counter = 0;
        //while not all points are seen
        //loop over cycles
        while (counter < permutation.length) {
            //get first point that was not already traversed
            start = pointer = used.nextZeroBit(0);
            currentSize = 0;
            //processing current cycle
            //loop over current cycle
            do {
                assert !used.get(pointer);
                used.set(pointer);
                pointer = permutation[pointer];
                ++currentSize;
            } while (pointer != start);
            counter += currentSize;
            temp = BigInteger.valueOf(currentSize);

View Full Code Here

     */
    public static BigInteger orderOfPermutation(byte[] permutation) {
        //we shall decompose this permutation into product of cycles and calculate l.c.m. of their sizes


        //to mark viewed points
        BitArray used = new BitArray(permutation.length);
        //lcm
        BigInteger lcm = BigInteger.ONE, temp;


        int start, pointer, currentSize, counter = 0;
        //while not all points are seen
        //loop over cycles
        while (counter < permutation.length) {
            //get first point that was not already traversed
            start = pointer = used.nextZeroBit(0);
            currentSize = 0;
            //processing current cycle
            //loop over current cycle
            do {
                assert !used.get(pointer);
                used.set(pointer);
                pointer = permutation[pointer];
                ++currentSize;
            } while (pointer != start);
            counter += currentSize;
            temp = BigInteger.valueOf(currentSize);

View Full Code Here

     */
    public static boolean orderOfPermutationIsOdd(final int[] permutation) {
        //decompose this permutation into product of cycles and calculate parity of l.c.m. of their sizes


        //to mark viewed points
        BitArray used = new BitArray(permutation.length);
        int start, pointer, currentSize, counter = 0;
        //while not all points are seen
        //loop over cycles
        while (counter < permutation.length) {
            //get first point that was not already traversed
            start = pointer = used.nextZeroBit(0);
            currentSize = 0;
            //processing current cycle
            //loop over current cycle
            do {
                assert !used.get(pointer);
                used.set(pointer);
                pointer = permutation[pointer];
                ++currentSize;
            } while (pointer != start);
            if (currentSize % 2 == 0)
                return false;

View Full Code Here

     */
    public static boolean orderOfPermutationIsOdd(final short[] permutation) {
        //decompose this permutation into product of cycles and calculate parity of l.c.m. of their sizes


        //to mark viewed points
        BitArray used = new BitArray(permutation.length);
        int start, pointer, currentSize, counter = 0;
        //while not all points are seen
        //loop over cycles
        while (counter < permutation.length) {
            //get first point that was not already traversed
            start = pointer = used.nextZeroBit(0);
            currentSize = 0;
            //processing current cycle
            //loop over current cycle
            do {
                assert !used.get(pointer);
                used.set(pointer);
                pointer = permutation[pointer];
                ++currentSize;
            } while (pointer != start);
            if (currentSize % 2 == 0)
                return false;

View Full Code Here

     */
    public static boolean orderOfPermutationIsOdd(final byte[] permutation) {
        //decompose this permutation into product of cycles and calculate parity of l.c.m. of their sizes


        //to mark viewed points
        BitArray used = new BitArray(permutation.length);
        int start, pointer, currentSize, counter = 0;
        //while not all points are seen
        //loop over cycles
        while (counter < permutation.length) {
            //get first point that was not already traversed
            start = pointer = used.nextZeroBit(0);
            currentSize = 0;
            //processing current cycle
            //loop over current cycle
            do {
                assert !used.get(pointer);
                used.set(pointer);
                pointer = permutation[pointer];
                ++currentSize;
            } while (pointer != start);
            if (currentSize % 2 == 0)
                return false;

View Full Code Here

        IntArrayList orbitList = new IntArrayList();
        orbitList.add(point);
        if (generators.isEmpty())
            return orbitList;//throw new IllegalArgumentException("Empty generators.");
        //seen points
        BitArray seen = new BitArray(degree);
        seen.set(point);
        int imageOfPoint;
        //main loop over all points in orbit
        for (int orbitIndex = 0; orbitIndex < orbitList.size(); ++orbitIndex) {
            //loop over all generators of a group
            for (Permutation generator : generators) {
                //image of point under permutation
                imageOfPoint = generator.newIndexOf(orbitList.get(orbitIndex));
                //testing whether current permutation maps orbit point into orbit or not
                if (!seen.get(imageOfPoint)) {
                    //adding new point to orbit
                    orbitList.add(imageOfPoint);
                    //filling Schreier vector
                    seen.set(imageOfPoint);
                }
            }
        }
        return orbitList;
    }

View Full Code Here

     * @param permutation permutation written in one-line notation
     * @return permutation written in disjoint cycles notation
     */
    public static int[][] convertOneLineToCycles(final int[] permutation) {
        ArrayList<int[]> cycles = new ArrayList<>();
        BitArray seen = new BitArray(permutation.length);
        int counter = 0;
        while (counter < permutation.length) {
            int start = seen.nextZeroBit(0);
            if (permutation[start] == start) {
                ++counter;
                seen.set(start);
                continue;
            }
            IntArrayList cycle = new IntArrayList();
            while (!seen.get(start)) {
                seen.set(start);
                ++counter;
                cycle.add(start);
                start = permutation[start];
            }
            cycles.add(cycle.toArray());

View Full Code Here

     * @param permutation permutation written in one-line notation
     * @return permutation written in disjoint cycles notation
     */
    public static int[][] convertOneLineToCycles(final short[] permutation) {
        ArrayList<int[]> cycles = new ArrayList<>();
        BitArray seen = new BitArray(permutation.length);
        int counter = 0;
        while (counter < permutation.length) {
            int start = seen.nextZeroBit(0);
            if (permutation[start] == start) {
                ++counter;
                seen.set(start);
                continue;
            }
            IntArrayList cycle = new IntArrayList();
            while (!seen.get(start)) {
                seen.set(start);
                ++counter;
                cycle.add(start);
                start = permutation[start];
            }
            cycles.add(cycle.toArray());

View Full Code Here

     * @param permutation permutation written in one-line notation
     * @return permutation written in disjoint cycles notation
     */
    public static int[][] convertOneLineToCycles(final byte[] permutation) {
        ArrayList<int[]> cycles = new ArrayList<>();
        BitArray seen = new BitArray(permutation.length);
        int counter = 0;
        while (counter < permutation.length) {
            int start = seen.nextZeroBit(0);
            if (permutation[start] == start) {
                ++counter;
                seen.set(start);
                continue;
            }
            IntArrayList cycle = new IntArrayList();
            while (!seen.get(start)) {
                seen.set(start);
                ++counter;
                cycle.add(start);
                start = permutation[start];
            }
            cycles.add(cycle.toArray());

View Full Code Here

     * @param permutation permutation written in one-line notation
     * @return an array of cycles lengths
     */
    public static int[] lengthsOfCycles(final int[] permutation) {
        IntArrayList sizes = new IntArrayList();
        BitArray seen = new BitArray(permutation.length);
        int counter = 0;
        while (counter < permutation.length) {
            int start = seen.nextZeroBit(0);
            if (permutation[start] == start) {
                ++counter;
                seen.set(start);
                continue;
            }
            int size = 0;
            while (!seen.get(start)) {
                seen.set(start);
                ++counter;
                ++size;
                start = permutation[start];
            }
            sizes.add(size);

View Full Code Here

0 1 2 3 4 5 6

TOP

Related Classes of cc.redberry.core.utils.BitArray

cc.redberry.core.combinatorics.IntDistinctTuplesPort

cc.redberry.core.graph.PrimitiveSubgraphPartition

cc.redberry.core.groups.permutations.AlgorithmsBase

cc.redberry.core.groups.permutations.Combinatorics

cc.redberry.core.groups.permutations.PermutationOneLineAbstract

cc.redberry.core.groups.permutations.Permutations

cc.redberry.core.indices.StructureOfIndices

cc.redberry.core.parser.preprocessor.GeneralIndicesInsertion

cc.redberry.core.parser.preprocessor.GeneralIndicesInsertion$SimpleTransformer

cc.redberry.core.transformations.substitutions.SubstitutionIterator$SumFC

All source code are property of their respective owners. Java is a trademark of Sun Microsystems, Inc and owned by ORACLE Inc. Contact coftware#gmail.com.