springCproject/ProblemSolver.h at master · zlldnv/springCproject · 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
#ifndef RECURSIVETEMPLATE_PROBLEMSOLVER_H
#define RECURSIVETEMPLATE_PROBLEMSOLVER_H

#include <vector>
#include "Constraint.h"

template<int N, class ITEM_TYPE, class B_CONSTRAINT, class L_CONSTRAINT>
class ProblemSolver {
private:
    std::vector<ITEM_TYPE *> items;
    Constraint<ITEM_TYPE> *bConstraint;
    Constraint<ITEM_TYPE> *lConstraint;

    std::vector<ITEM_TYPE *> findSolution(std::vector<ITEM_TYPE *> currentPath, int pathSize, ITEM_TYPE *newItem) {
        std::vector<ITEM_TYPE *> path;
        path.reserve((unsigned long) N);
        if (currentPath.size() != 0) {
            for (int i = 0; i < currentPath.size(); ++i) {
                path.insert(path.begin() + i, currentPath[i]);
            }
        }

        int oi = N;
        unsigned  i = 0;
        if (pathSize == N - 1) {

            if ((bConstraint == nullptr || bConstraint->CheckConstraint(path, newItem)) && (lConstraint == nullptr || lConstraint->CheckConstraint(path, newItem))) {
                path.insert(path.begin() + pathSize, newItem);
                return path;
            }
        } else {
            if (bConstraint == nullptr || bConstraint->CheckConstraint(path, newItem)) {

                path.insert(path.begin() + pathSize, newItem);
                for (int i = 0; i < items.size(); ++i) {
                    std::vector<ITEM_TYPE *> possibleSolution = findSolution(path, pathSize + 1, items[i]);
                    if (possibleSolution.size() == 0)
                        continue;
                    return possibleSolution;
                }
            }

        }
        return std::vector<ITEM_TYPE *>();
    }

public:
    std::vector<ITEM_TYPE *> Solve(std::vector<ITEM_TYPE *> items, B_CONSTRAINT *boundaryConstraint = nullptr,
                                   L_CONSTRAINT *leafConstraint = nullptr) {
        this->items = items;
        if (Constraint<ITEM_TYPE> *bc = reinterpret_cast<Constraint<ITEM_TYPE> *>(boundaryConstraint)) {
            Constraint<ITEM_TYPE> *lc = reinterpret_cast<Constraint<ITEM_TYPE> *>(leafConstraint);
            if (lc || leafConstraint == nullptr) {

                bConstraint = bc;
                lConstraint = lc;

                for (int i = 0; i < items.size(); i++) {
                    auto path = findSolution(std::vector<ITEM_TYPE *>(), 0, items[i]);
                    if (path.size() == 0) {
                        continue;
                    }
                    return path;
                }
            }
        }
        return std::vector<ITEM_TYPE *>();
    }
};


#endif //RECURSIVETEMPLATE_PROBLEMSOLVER_H