home | career | drupal | java | mac | mysql | perl | scala | uml | unix

Groovy example source code file (fannkuch.java)

This example Groovy source code file (fannkuch.java) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Java - Groovy tags/keywords

atomicinteger, atomicinteger, interruptedexception, interruptedexception, n, n, runnable, thread, thread

The Groovy fannkuch.java source code

/*
* The Computer Language Benchmarks Game
* http://shootout.alioth.debian.org/
*
* Based on contribution of Eckehard Berns
* Based on code by Heiner Marxen
* and the ATS version by Hongwei Xi
* convert to Java by The Anh Tran
*/

import java.util.concurrent.atomic.AtomicInteger;

public final class fannkuch implements Runnable
{
    private final int n;
    private final int[] flip_max_arr;
    private final AtomicInteger remain_task = new AtomicInteger(0);
    
    public static void main(String[] args)
    {
        int x = (args.length > 0) ? Integer.parseInt(args[0]) : 7;
        fannkuch f = new fannkuch(x);
        System.out.format("Pfannkuchen(%d) = %d\n", x, f.fank_game());
    }
    
    public fannkuch(int N)
    {
        n = N;
        // hold flip_count result for each swap index
        flip_max_arr = new int[n];
    }
    
    private final int fank_game()
    {
        Thread[] th = new Thread[Runtime.getRuntime().availableProcessors()];
        for (int i = 0; i < th.length; i++)
        {
            th[i] = new Thread(this);
            th[i].start();
        }
        
        print_30_permut();
        
        for (Thread t : th)
        {
            try {
                t.join();
            }
            catch (InterruptedException ie)
            {   }
        }
        
        int mx = 0;
        for (int i : flip_max_arr)
            if (mx < i)
                mx = i;
        return mx;
    }
    
    // In order to divide tasks 'equally' for many threads, permut generation
    // strategy is different than that of original single thread.
    // this function will 'correctly' print first 30 permutations
    private final void print_30_permut()
    {
        // declare and initialize
        final int[] permutation = new int[n];
        for ( int i = 0; i < n; i++ )
        {
            permutation[i] = i;
            System.out.print((1 + i));
        }
        System.out.println();
        
        final int[] perm_remain = new int[n];
        for ( int i = 1; i <= n; i++ )
            perm_remain[i -1] = i;
        
        int numPermutationsPrinted = 1;
        for ( int pos_right = 2; pos_right <= n; pos_right++ )
        {
            int pos_left = pos_right -1;
            do
            {
                // rotate down perm[0..prev] by one
                next_perm(permutation, pos_left);
                
                if (--perm_remain[pos_left] > 0)
                {
                    if (numPermutationsPrinted++ < 30)
                    {
                        for (int i = 0; i < n; ++i)
                            System.out.print((1 + permutation[i]));
                        System.out.println();
                    }
                    else
                        return;
                    
                    for ( ; pos_left != 1; --pos_left)
                        perm_remain[pos_left -1] = pos_left;
                }
                else
                    ++pos_left;
            } while (pos_left < pos_right);
        }
    }
    
    public void run()
    {
        final int[] permutation = new int[n];
        final int[] perm_remain = new int[n];
        final int[] perm_flip = new int[n];

        int pos_right;
        while ((pos_right = remain_task.getAndIncrement()) < (n - 1))
        {
            int flip_max = 0;

            for (int i = 0; i < n - 1; i++)
                permutation[i] = i;

            permutation[pos_right] = (n - 1);
            permutation[n - 1] = (pos_right);

            for (int i = 1; i <= n; i++)
                perm_remain[i - 1] = i;

            int pos_left = n - 2;
            while (pos_left < n - 1)
            {
                // rotate down perm[0..r] by one
                next_perm(permutation, pos_left);

                if (--perm_remain[pos_left] > 0)
                {
                    for (; pos_left != 1; --pos_left)
                        perm_remain[pos_left - 1] = pos_left;

                    if ((permutation[0] != 0) && (permutation[n - 1] != (n - 1)))
                    {
                        System.arraycopy(permutation, 0, perm_flip, 0, n);
                        int flipcount = count_flip(perm_flip);
                        if (flip_max < flipcount)
                            flip_max = flipcount;
                    }
                }
                else
                    pos_left++;
            }

            // update max_flip foreach flipping position
            flip_max_arr[pos_right] = flip_max;
        }
    }


    // Take a permut array, continuously flipping until first element is '1'
    // Return flipping times
    private static final int count_flip(final int[] perm_flip)
    {
        // cache first element, avoid swapping perm[0] and perm[k]
        int v0 = perm_flip[0];
        int tmp;

        int flip_count = 0;
        do
        {
            for (int i = 1, j = v0 - 1; i < j; ++i, --j)
            {
                tmp = perm_flip[i];
                perm_flip[i] = perm_flip[j];
                perm_flip[j] = tmp;
            }

            tmp = perm_flip[v0];
            perm_flip[v0] = v0;
            v0 = tmp;

            flip_count++;
        } while (v0 != 0); // first element == '1' ?

        return flip_count;
    }

    // Return next permut, by rotating elements [0 - position] one 'step'
    // next_perm('1234', 2) -> '2314'
    private static final void next_perm(final int[] permutation, int position)
    {
        int perm0 = permutation[0];

        for (int i = 0; i < position; ++i)
            permutation[i] = permutation[i + 1];
        permutation[position] = perm0;
    }
}

Other Groovy examples (source code examples)

Here is a short list of links related to this Groovy fannkuch.java source code file:

new blog posts

 

Copyright 1998-2014 Alvin Alexander, alvinalexander.com
All Rights Reserved.