-
Notifications
You must be signed in to change notification settings - Fork 0
/
Cage.h
127 lines (105 loc) · 4.33 KB
/
Cage.h
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
125
126
127
#pragma once
#include "PossibleValues.h"
#include <bitset>
#include <iostream>
#include <map>
#include <optional>
#include <set>
#include <stdint.h>
#include <vector>
template <uint32_t N> class Cell;
template <uint32_t N> class Cage;
template <uint32_t N> class Cage {
public:
Cage() : Cage({}, 0) {}
Cage(std::set<Cell<N> *> cells, const uint32_t sum);
Cage(std::set<Cage<N> *> cages);
inline std::set<Cell<N> *> getCells() const { return cells_; }
inline uint32_t getNumCells() const { return cells_.size(); }
inline uint32_t getSum() const { return sum_; }
/**
* Check whether this cage is a subset of the other cage; returns true if the
* two cages are equal.
*/
bool isSubsetOf(const Cage<N> *other) const;
bool isSupersetOf(const Cage<N> *other) const;
Cage<N> operator-(const Cage<N> &other) const;
template <uint32_t N_>
friend std::ostream &operator<<(std::ostream &os, const Cage<N_> &cage);
protected:
std::set<Cell<N> *> cells_; /*!< Cells which are members of this cage. */
uint32_t sum_; /*!< Total sum of the cage. */
};
template <uint32_t N> class LogicalCage : public Cage<N> {
public:
LogicalCage() : LogicalCage({}, 0) {}
LogicalCage(std::set<Cell<N> *> cells, const uint32_t sum);
LogicalCage(std::set<Cage<N> *> cages);
LogicalCage(const Cage<N> &cage);
void init();
void uninit();
void registerNewOverlappingCage(LogicalCage<N> *cage);
void registerNewSupersetCage(LogicalCage<N> *cage);
void unregisterCage(LogicalCage<N> *cage);
inline bool getUniqueness() const { return uniqueness_; }
Cage<N> getMaximumSubset(const std::set<LogicalCage<N> *> &group) const;
Cage<N> getMinimumSuperset(const std::set<LogicalCage<N> *> &group) const;
inline bool isSuperset() const { return subsetCages_.size() > 0; }
inline bool overlapsWith(const LogicalCage<N> *cage) const {
return overlappingCages_.find(const_cast<LogicalCage<N> *>(cage)) !=
overlappingCages_.end();
}
void needsEvaluation() { needsEvaluation_.set(); }
/**
* Check whether a particular cell value will satisfy the constraints of this
* cage. Since it is difficult to efficiently enforce uniqueness, if this cage
* has a uniqueness constraint, it is only entirely enforced if this cage has
* 3 or fewer cells.
*/
bool testCellValues(const Cell<N> *cell, const uint32_t value);
bool testCellValues(const uint32_t sumUsedValues,
PossibleValues<N> &usedValues,
const uint32_t numberUsedCells,
std::bitset<N * N> &usedCells,
std::vector<const Cell<N> *> &remaining) const;
template <uint32_t N_>
friend std::ostream &operator<<(std::ostream &os,
const LogicalCage<N_> &cage);
static bool orderByComplexity(const LogicalCage<N> *left,
const LogicalCage<N> *right);
private:
void updateUniqueness();
bool uniqueness_; /*!< If true, then the values of cells in this cage are
required to be unique. */
std::set<LogicalCage<N> *> overlappingCages_; /*!< Cache of cages which share
at least one cell with this cage. */
std::set<LogicalCage<N> *>
subsetCages_; /*!< Cache of cages which are a subset of this cage. */
std::set<LogicalCage<N> *>
supersetCages_; /*!< Cache of cages which are a superset of this cage. */
std::vector<const Cell<N> *>
sortedCells_; /*!< Cache of cells sorted by how many possible values there
are. */
std::bitset<N> needsEvaluation_; /*!< Keep track of whether cells have changed
since the last cage evaluation. */
};
template <uint32_t N>
std::ostream &operator<<(std::ostream &os, const Cage<N> &cage) {
os << "Cage(sum: " << cage.getSum() << ", cells: {";
for (const Cell<N> *cell : cage.getCells()) {
os << *cell << ", ";
}
os << "})";
return os;
}
template <uint32_t N>
std::ostream &operator<<(std::ostream &os, const LogicalCage<N> &cage) {
os << "LogicalCage(sum: " << cage.getSum() << ", cells: {";
for (const Cell<N> *cell : cage.getCells()) {
os << *cell << ", ";
}
os << "}, uniqueness: " << cage.getUniqueness() << ", "
<< cage.overlappingCages_.size() << " overlapping, "
<< cage.subsetCages_.size() << " subset}";
return os;
}