#include <stdlib.h>
#include <iostream.h>

#define DEBUG_STATE_MANAGER
#define DEBUG_QUEUE
//#define BRUTE_FORCE

#define MAX_PRIORITY 1000

#define EXAMPLE3
#define SUBEXAMPLE6

#include "zadani.cpp"

/* trida pro uchovani jednoho stavu stavoveho prostoru */
class State {
    private:
        State *prev;                // ukazatel na predchozi stav
        State *next;                // dalsi stav stav. prostoru
        unsigned bucket[BUCKETS];   // obsah kybliku v tomto stavu

        // je i platny index kyble?
        static int check(int i) {
            return (i>=0 && i<BUCKETS);
        }

    public:
        // bezparametricky konstruktor
        State() {
            prev = next = NULL;
            for(int i=0; i<BUCKETS; i++) bucket[i] = 0;
        }

        // konstruktor pro naplneni defaultnimi hodnotami
        State(unsigned bucket_start[]) {
            prev = next = NULL;
            for(int i=0; i<BUCKETS; i++) bucket[i] = bucket_start[i];
        }

        // konstruktor - kybliky se zdedi z predchoziho stavu
        State(State *tprev) {
            for(int i=0; i<BUCKETS; i++) bucket[i] = tprev->bucket[i];
            prev = tprev;
            next = NULL;
        }

        // vrat obodovani stavu, 0 je nejlepsi (spravne) reseni
        int getScore() {
            int score = 0;

            #ifndef BRUTE_FORCE
            for(int i=0; i<BUCKETS; i++) {
//                score += abs(bucket[i] - bucket_final[i]);
                if(bucket[i] != bucket_final[i]) {
//                    if(bucket[i] == 0) score += 5;
//                    if(bucket[i] == bucket_size[i]) score += 5;
                    score += 1;
                }
            }
            #endif

            if(score > MAX_PRIORITY) score = MAX_PRIORITY;
            return score;
        }

        // je to vysledek?
        int isResult(unsigned bucket_final[]) {
            for(int i=0; i<BUCKETS; i++) if(bucket[i] != bucket_final[i]) return 0;
            return 1;
        }

        // jsou stavy stejne?
        int compare(State *s) {
            for(int i=0; i<BUCKETS; i++) if(bucket[i] != s->bucket[i]) return 0;
            return 1;
        }

        // prelij vodu z from do to
        int pour(int from, int to) {
            if(!check(from) || !check(to)) return 0;
            int pour_from = bucket[from];
            int pour_to = bucket_size[to] - bucket[to];
            if(pour_from > pour_to) {
                bucket[to] += pour_to;
                bucket[from] -= pour_to;
            } else {
                bucket[to] += pour_from;
                bucket[from] -= pour_from;
            }
            return 1;
        }

        // vyprazdni kyblik
        int empty(int i) {
            if(!check(i)) return 0;
            bucket[i] = 0;
            return 1;
        }

        // napln kyblik
        int fill(int i) {
            if(!check(i)) return 0;
            bucket[i] = bucket_size[i];
            return 1;
        }

        // je kyblik plny?
        int isFull(int i) {
            if(!check(i)) return 0;
            return bucket[i] == bucket_size[i];
        }

        // je kyblik prazdny?
        int isEmpty(int i) {
            if(!check(i)) return 0;
            return bucket[i] == 0;
        }

        // vrat obsah kybliku
        int getBucket(int i) {
            if(check(i)) return bucket[i]; else return -1;
        }

        // vrat dalsi stav prostoru
        State *getNext() {
            return next;
        }

        // vrat predchazejici stav na ceste prostorem
        State *getPrev() {
            return prev;
        }

        // napoj dalsi stav v prostoru
        State *add(State *tnext) {
            return next = tnext;
        }

        // vypis stavu pro debug
        void echo() {
            cout << "(";
            for(int i=0; i<BUCKETS; i++) {
                if(i) cout << ", ";
                cout << bucket[i];
            }
            cout << ")";
        }
};

/* trida pro reprezentaci stavoveho prostoru */
class StateManager {
    private:
        State *first;
        int size;

    public:
        // konstruktor
        StateManager() {
            first = NULL;
            size = 0;
        }

        // destruktor
        ~StateManager() {
            State *temp = first;
            while(temp != NULL) {
                first = temp->getNext();
                delete temp;
                temp = first;
            }
        }

        // existuje tento stav jiy v prostoru?
        int exists(State *s) {
            State *temp = first;
            while(temp != NULL) {
                if(temp->compare(s)) return 1;
                temp = temp->getNext();
            }
            return 0;
        }

        // pridej dalsi stav, pokud v prostoru jeste neni
        int add(State *s) {
            #ifdef DEBUG_STATE_MANAGER
            cout << "StateManager: add:  ";
            s->echo();
            #endif
            if(exists(s)) {
                #ifdef DEBUG_STATE_MANAGER
                cout << " - jiz existuje" << endl;
                #endif
                return 0;
            }
            s->add(first);
            first = s;
            size++;
            #ifdef DEBUG_STATE_MANAGER
            cout << " - pridan" << endl;
            #endif
            return 1;
        }
};

/* trida pro jednu bunku prioritni fronty */
class QueueCell {
    private:
        int priority;
        State *s;
        QueueCell *next;

    public:
        // konstruktor...
        QueueCell(int tpriority, State *ts) {
            s = ts;
            next = NULL;
            if(tpriority > MAX_PRIORITY) tpriority = MAX_PRIORITY;
            priority = tpriority;
        }

        // pripoj dalsi bunku
        QueueCell *add(QueueCell *tnext) {
            return next = tnext;
        }

        // zjisti prioritu
        int getPriority() {
            return priority;
        }

        // vrat odkaz na stav
        State *getState() {
            return s;
        }

        // vrat dalsi bunku
        QueueCell *getNext() {
            return next;
        }
};

/* trida pro prioritni frontu */
class Queue {
    private:
        int size;
        QueueCell *first, *last;
        int pushs;

    public:
        // konstruktor
        Queue() {
            first = last = new QueueCell(-1, NULL);
            size = 0;
            pushs = 0;
        }

        // je prazdna?
        int empty() {
            return size==0;
        }

        // velikost
        int getSize() {
            return size;
        }

        // vloz prvek
        void push(int priority, State *s) {
            QueueCell *qc = new QueueCell(priority, s);
            last = last->add(qc);
            size++;
            pushs++;

            #ifdef DEBUG_QUEUE
            cout << "Queue:        push: ";
            s->echo();
            cout << " - priorita " << priority;
            cout << ", ve fronte " << getSize() << endl;
            #endif
        }

        // vyber prvek s nejnizsi prioritou
        State *pop() {
            QueueCell *temp = first->getNext(), *found = NULL;
            QueueCell *prev = first, *prefound = NULL;
            State *result;
            int min = MAX_PRIORITY;
            int priority;

            #ifdef DEBUG_QUEUE
            cout << "Queue:        pop:  ";
            #endif

            // prohledavej
            while(temp != NULL) {
                priority = temp->getPriority();
                if(priority < min) {
                    min = priority;
                    found = temp;
                    prefound = prev;
                }
                prev = temp;
                temp = temp->getNext();
            }
            if(found == NULL) return NULL;

            // vyrad z fronty a vrat vysledek
            size--;
            result = found->getState();
            prefound->add(found->getNext());
            if(last == found) last = prefound;
            delete found;

            #ifdef DEBUG_QUEUE
            found->getState()->echo();
            cout << " - priorita " << min;
            cout << ", ve fronte " << getSize() << endl;
            #endif

            return result;
        }

        // kolikrat bylo celkove pusnuto
        int getPushs() {
            return pushs;
        }
};

int main() {
    StateManager *sm = new StateManager();
    State *s = new State(bucket_start);
    State *t;
    Queue *q = new Queue();
    int i, j, d;

    q->push(s->getScore(), s);
    while(!q->empty()) {
        // vezmi celo fronty
        s = q->pop();
        if(s->isResult(bucket_final)) break;

        // zkousej plnit kyble
        for(i=0; i<BUCKETS; i++) if(!s->isFull(i)) {
            t = new State(s);
            t->fill(i);
            if(sm->add(t)) q->push(t->getScore(), t);
        }

        // zkousej vylivat kyble
        for(i=0; i<BUCKETS; i++) if(!s->isEmpty(i)) {
            t = new State(s);
            t->empty(i);
            if(sm->add(t)) q->push(t->getScore(), t);
        }

        // zkousej prelevat kyble
        for(i=0; i<(BUCKETS-1); i++) {
            for(j=i+1; j<BUCKETS; j++) {
                if(!s->isEmpty(i) && !s->isFull(j)) {
                    t = new State(s);
                    t->pour(i, j);
                    if(sm->add(t)) q->push(t->getScore(), t);
                }
            }
        }

    }

    // vyhodnoceni
    if(s->isResult(bucket_final)) {
        cout << endl << "Nalezeno reseni!" << endl;
        d = 0;
        while(s != NULL) {
            d++;
            s = s->getPrev();
        }
        cout << "Delka cesty: " << d << endl;
    } else {
        cout << endl << "Reseni neexistuje!" << endl;
    }
    cout << "Prozkoumanych stavu " << q->getPushs() << endl;

    system("PAUSE");
    return 0;
}