import java.util.ArrayList;
import java.util.Scanner;

/**
 * Solves Problem 19.c of Homework 1. Adapted from the homework and the listing
 * for Problem 19.b (cnet-create-trisort), which Problem 19.c refers to:
 * <p>
 * Creates a merge-exchange sorting network (as discussed in
 * class) of a given size. The program reads a single integer n on standard
 * input, ignoring all whitespace. The output is the canonical linear
 * representation of the merge-exchange sort network for n inputs.
 *
 * @author Ed Ropple
 */

public class CnetCreateMexsortMain {

    /**
     * Takes in a single integer from stdin and puts it through the
     * merge-exchange network sort network. The sort network was translated from
     * Laurentiu Cristofor's Java implementation, passed out and discussed in
     * class (Cristofor's implementation originally referred to the Knuth text,
     * but ours is not a direct reference to the Knuth book).
     *
     * @param args      The command line arguments for the program. Are ignored
     *                  by this program.
     */
    public static void main(String[] args) {

        System.out.println("Enter below a single non-negative integer.");
        System.out.println("Whitespace is ignored, but your number is not");
        System.out.println("checked and will generate an exception.");
        System.out.println("Note that this number is the number of ");
        System.out.println("comparators; i.e. inputting 6 will create a");
        System.out.println("trisort from 0 to 5; for a trisort of comparators");
        System.out.println("0 to 9, input 10. (This value is incidentially");
        System.out.println("the same as the number of elements being sorted,");
        System.out.println("as the requirements state.)");
        System.out.println();

        Scanner s = new Scanner(System.in);
        String foo = "";

        // read from stdin, emerge once given non-whitespace input (thank you,
        // trim function, I love you so)
        while (true)
        {
            System.out.print("> ");
            foo = s.nextLine().trim();

            if (foo.length() < 1)
                continue;
            else
                break;
        }

        int mexsortSize = Integer.parseInt(foo);


        ArrayList<ComparatorPair> swapPairs = new ArrayList<ComparatorPair>();

        // function is a translation from the Laurentiu Cristofor merge-exchange
        // java program provided in class. Link:
        //
        // http://www.cs.umb.edu/~laur/Java/Sorters/MergeExchangeSort.java
        //
        // Mr. Cristofor's code is very un-Java-like, but with the way it has
        // been implemented I am somewhat leery about altering it too much, and
        // so I've erred on the side of caution and chosen to leave it mostly
        // as-is. I'm personally not too fond of the O(n) pow2() function, but
        // I don't want to run the risk of the Java Math.pow() function, which
        // uses double-precision floats, potentially causing problems with the
        // existing code. I suppose it could be worse. It could be recursive...

        if (mexsortSize > 1)
        {
            int t, p, q, r, d;
            t = (int)(Math.log(mexsortSize) / Math.log(2));
            
            if (pow2(t) < mexsortSize)
            {
                t++;
            }

            p = pow2(t - 1);

            while (true)
            {
                q = pow2(t - 1);
                r = 0;
                d = p;

                while (true)
                {
                    for (int i = 0; i < mexsortSize - d; i++)
                    {
                        if ((i & p) == r)
                        {
                            swapPairs.add(new ComparatorPair(i, i + d));
                        }
                    }

                    if (q != p)
                    {
                        d = q - p;
                        q = q / 2;
                        r = p;
                    }
                    else
                        break;
                }
                
                p = p / 2;

                if (p == 0) break;
            }
        }

        System.out.println();
        System.out.println(Functions.makeCanonicalLinearOutput(swapPairs));
    }


    /**
     * Returns the exponent (2 ^ exponent).
     *
     * @param exponent exponent of 2 to return (2 ^ exponent)
     * @return the value (2 ^ exponent)
     */
    private static int pow2(int exponent) {
          int value = 1;
          for (int i = 1; i <= exponent; i++){
              value *= 2;
          }
          return value;
      }
}