/*
 * A breadth-first search of the Tower of Hanoi problem.
 */

#include "Array.h"
#include "BitArray.h"
#include "HashTable.h"
#include "ReadBuffer.h"
#include "WriteBuffer.h"
#include "types.h"
#include "roomy.h"
#include "params.h"
#include "knudirs.h"
#include "RoomyBitArray.h"
#include "RoomyBitsArray.h"

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <sys/stat.h>

#define N_PEGS 4
#define N_RINGS 15
#define N_STATES 1073741824

#define TRACING

/******************************************************************************
 *                    Representing Locations of Rings 
 *****************************************************************************/

typedef uint8 Peg;
typedef uint8 Ring;
typedef Peg State[N_RINGS]; // list the peg each ring is on

void getHomeState(State out) {
    Ring i; for(i=0; i<N_RINGS; i++) out[i] = 0;
}

void printState(State s) {
    Ring i;
    printf("[");
    for(i=0; i<N_RINGS-1; i++)
        printf("%i ", s[i]);
    printf("%i]", s[N_RINGS-1]);
}

void copyState(State to, State from) {
    memcpy(to, from, N_RINGS * sizeof(Peg));
}

/******************************************************************************
 *            Mapping States to Integers (mixed radix encoding)
 *****************************************************************************/

uint64 rank(State s) {
    uint64 r = 0;
    uint64 m = 1;
    Ring i;
    for(i=0; i<N_RINGS; i++) {
        r += s[i] * m;
        m *= N_PEGS;
    }
    return r;
}

void unrank(uint64 r, State out) {
    int i;
    uint64 m = 1;
    for(i=0; i<N_RINGS-1; i++) m *= N_PEGS;
    for(i=N_RINGS-1; i>=0; i--) {
        out[i] = r/m;
        r -= out[i] * m;
        m /= N_PEGS;
    }
}

/******************************************************************************
 *                    Generation of Neighboring States 
 *****************************************************************************/

// Return a list containing the top (smallest) ring for each peg. If there
// are no rings on a peg, N_RINGS will be returned for that peg.
void topRings(State s, Ring tops[]) {
    int i;
    for(i=0; i<N_PEGS; i++) tops[i] = N_RINGS;
    for(i=N_RINGS-1; i>=0; i--) tops[s[i]] = i;
}

// Generate all states that can be reached in one move from the given state
// (represented as integers). Return the number of neighbors generated.
int genAll(uint64 r, uint64 nbrs[]) {
    State s;
    unrank(r, s);
    Ring tops[N_PEGS];
    topRings(s, tops);
    int numGen = 0;
    Peg i;
    for(i=0; i<N_PEGS; i++) {
        Peg j;
        for(j=0; j<N_PEGS; j++) {
            if(tops[i] < tops[j]) {
                State new;
                copyState(new, s);
                new[tops[i]] = j;
                nbrs[numGen] = rank(new);
                numGen++;
            }
        }
    }
    return numGen;
}

/******************************************************************************
 *                        Roomy Implementation
 *                Using three RoomyBitArray data structures
 *****************************************************************************/

RoomyBitArray* dupe;
RoomyBitArray* cur;
RoomyBitArray* next;

// to be mapped over the RoomyBitArray representing the current level
typedef struct {
    uint8 cur;
} GenValue;
void generate(uint64 r, void* rawInput) {
    GenValue* input = (GenValue*)rawInput;
    if(input->cur) {
        uint64 nbrs[N_PEGS * N_PEGS];
        int numGen = genAll(r, nbrs);
        int i;
        for(i=0; i<numGen; i++) {
            RoomyBitArray_set(next, nbrs[i]);
        }
    }
}

// to be mapped (with modification) over the duplicate and next levels,
// removing dupes from next level and merging next level into dupes.
typedef struct {
    uint8 dupe;
    uint8 next;
} MergeValue;
void mergeDupes(uint64 r, void* rawInput, void* rawOutput) {
    MergeValue* input = (MergeValue*)rawInput;
    MergeValue* output = (MergeValue*)rawOutput;
    // if state could be at next level...
    if(input->next) {

        // if it's a dupe, remove it from next level
        if(input->dupe) {
            output->dupe = 1;
            output->next = 0;
        
        // else, leave it at next level and mark as a future dupe
        } else {
            output->dupe = 1;
            output->next = 1;
        }
    
    // if it's not at the next level, leave it as is
    } else {
        output->dupe = input->dupe;
        output->next = input->next;
    }
}

// Top level function for method using three 1-bit arrays
void threeBitBFS() {
    #ifdef TRACING
    Roomy_log("BEGINING %i-RING %i-PEG BFS\n", N_RINGS, N_PEGS);
    #endif

    // Initialize bit arrays for duplicates, current level, and next level
    dupe = RoomyBitArray_make("dupes", N_STATES);
    cur = RoomyBitArray_make("lev0", N_STATES);
    next = RoomyBitArray_make("lev1", N_STATES);

    #ifdef TRACING
    Roomy_log("Initial RoomyBitArrays constructed\n");
    #endif

    // set home state
    State home;
    getHomeState(home);
    uint64 homePos = rank(home);
    RoomyBitArray_set(dupe, homePos);
    RoomyBitArray_set(cur, homePos);
    Roomy_sync();

    // generate levels
    int curLevel = 0;
    uint64 numThisLevel = 1;

    #ifdef TRACING
    Roomy_log("Level %i done: %lli elements\n", curLevel, numThisLevel);
    #endif

    while(numThisLevel) {
        // generate next level from current
        RoomyBitArray** rbaList = malloc(1 * sizeof(RoomyBitArray*));
        rbaList[0] = cur;
        RoomyBitArray_map(rbaList, 1, generate);
        RoomyBitArray_sync(next);
        free(rbaList);

        // detect duplicates
        rbaList = malloc(2 * sizeof(RoomyBitArray*));
        rbaList[0] = dupe;
        rbaList[1] = next;
        RoomyBitArray_mapAndModify(rbaList, 2, mergeDupes);

        // create new next level, delete current level, rotate pointers
        curLevel++;
        RoomyBitArray_destroy(cur);
        cur = next;
        char levName[1024];
        sprintf(levName, "lev%i", curLevel+1);
        next = RoomyBitArray_make(levName, N_STATES);

        // get the number of new states at current level
        numThisLevel = RoomyBitArray_numSet(cur);

        #ifdef TRACING
        Roomy_log("Level %i done: %lli elements\n", curLevel, numThisLevel);
        #endif
    }

    RoomyBitArray_destroy(dupe);
    RoomyBitArray_destroy(cur);
    RoomyBitArray_destroy(next);

   #ifdef TRACING
   Roomy_log("PANCAKE BFS DONE\n");
   #endif
}

/******************************************************************************
 *                                  Tests
 *****************************************************************************/

void testStates() {
    uint64 i;
    for(i=0; i<N_STATES; i++) {
        State s;
        unrank(i, s);
        printf("s1=");
        printState(s);
        uint64 r = rank(s);
        printf(" i=%lli, s2=", i);
        printState(s);
        printf(" r=%lli\n", r);

        if(i>500) break;
    }
}

/******************************************************************************
 *                                  Main 
 *****************************************************************************/

int main(int argc, char **argv) {
    //testStates();
    
    Roomy_init(&argc, &argv);
    threeBitBFS();
    Roomy_finalize();
    
    return 0;
}