15puzzle/database.cpp at master · AndrewVDo/15puzzle · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include"fifteenPuzzle.h"
#include <fstream>
#include <sstream>

using namespace std;

Database::Database(Problem* problem){
    this->problem = problem;
}

std::unique_ptr<uint8_t[]> Database::encodeState(const uint8_t state[16], int quadrant){
    unique_ptr<uint8_t[]> encodedState( new uint8_t[16] );
    memcpy(encodedState.get(), state, 16 * sizeof(uint8_t));
    switch(quadrant){
        case 0:
            for(int i=0; i<16; i++){
                if(encodedState[i] != 1 && encodedState[i] != 2 && encodedState[i] != 3 && encodedState[i] != 5 && encodedState[i] != 6 && encodedState[i] != 0)
                    encodedState[i] = '*';
            };
            break;
        case 1:
            for(int i=0; i<16; i++){
                if(encodedState[i] != 4 && encodedState[i] != 7 && encodedState[i] != 8 && encodedState[i] != 11 && encodedState[i] != 12 &&encodedState[i] != 0)
                    encodedState[i] = '*';
            };
            break;
        case 2:
            for(int i=0; i<16; i++){
                if(encodedState[i] != 9 && encodedState[i] != 10 && encodedState[i] != 13 && encodedState[i] != 14 && encodedState[i] != 15 &&encodedState[i] != 0)
                    encodedState[i] = '*';
            };
            break;
    }
    return encodedState;
}

int Database::addRow(size_t key, int value){
    auto found = this->table.find(key);
    if(found == this->table.end()){
        this->table[key] = value;
        return 1; //new
    }
    if(this->table[key] > value){
        this->table[key] = value;
        return 0; //replace
    }
    return -1; //none
}

int Database::checkRow(const uint8_t state[16], int quadrant){
    auto encodedState = this->encodeState(state, quadrant);
    auto key = this->problem->getHash(encodedState.get());
    return this->table[key];
}

int Database::expand(Node* node, std::queue<std::unique_ptr<Node>>* frontier){
    auto result = this->addRow(this->problem->getHash(node->state), node->depth);
    if(result < 0) return 0;

    auto actions = problem->actions(node->state);
    switch (node->action){
        case 0:
            actions[2] = false;
            break;
        case 1:
            actions[3] = false;
            break;
        case 2:
            actions[0] = false;
            break;
        case 3:
            actions[1] = false;
            break;
    }
    for(int i=0; i<4; i++){
        if(actions[i]){
            frontier->push(unique_ptr<Node>(node->child_node(this->problem, i)));
        }
    }
    return result;
}

void Database::breadthFirstSearch(){
    queue<unique_ptr<Node>> frontier;
    frontier.push(unique_ptr<Node>(new Node(this->encodeState(this->problem->goalState, 0).get())));
    frontier.push(unique_ptr<Node>(new Node(this->encodeState(this->problem->goalState, 1).get())));
    frontier.push(unique_ptr<Node>(new Node(this->encodeState(this->problem->goalState, 2).get())));

    int databaseSize = 0;
    while(!frontier.empty()){
        databaseSize += this->expand(frontier.front().get(), &frontier);
        frontier.pop();
    }
}

void Database::saveDB(char filename[128]){
    ofstream myfile;
    myfile.open(filename);
    for(auto element : this->table){
        myfile << element.first << ',' << element.second << '\n';
    }
    myfile.close();
}

void Database::loadDB(char filename[128]){
    size_t linesRead = 0;
    ifstream file(filename);
    if (file.is_open()) {
        string line;
        string key;
        string value;
        while (getline(file, line)) {
            getline(file, line);
            istringstream iss(line);

            getline(iss, key, ',');
            getline(iss, value, ',');

            this->table[this->problem->hash_fn(key)] = stoi(value);
            linesRead++;
        }
        file.close();
    }
}