33 int const NODE_ROW_BITS = 20;
34 int const NODE_ATTR_BITS = 1;
35 int const NODE_COL_BITS = 64 - NODE_ROW_BITS - NODE_ATTR_BITS;
37 int const NODE_ROW_OFFSET = NODE_COL_BITS + NODE_ATTR_BITS;
38 int const NODE_ATTR_OFFSET = NODE_COL_BITS;
40 uint64_t
const NODE_ROW_MAX = (uint64_t(1) << NODE_ROW_BITS) - 1;
41 uint64_t
const NODE_COL_MAX = (uint64_t(1) << NODE_COL_BITS) - 1;
43 uint64_t
const NODE_ROW_MASK = NODE_ROW_MAX << NODE_ROW_OFFSET;
44 uint64_t
const NODE_ATTR_MASK = uint64_t(1) << NODE_ATTR_OFFSET;
53 NodeId(uint64_t code) :
57 NodeId(uint64_t row, uint64_t col) :
58 code_((row << NODE_ROW_OFFSET) | col) {
61 NodeId(uint64_t row, uint64_t col,
bool attr) :
62 code_((row << NODE_ROW_OFFSET) | col) {
67 return code_ >> NODE_ROW_OFFSET;
71 return code_ & NODE_COL_MAX;
74 void setAttr(
bool val) {
76 code_ |= NODE_ATTR_MASK;
79 code_ &= ~NODE_ATTR_MASK;
83 bool getAttr()
const {
84 return (code_ & NODE_ATTR_MASK) != 0;
87 NodeId withoutAttr()
const {
88 return code_ & ~NODE_ATTR_MASK;
91 bool hasEmpty()
const {
92 return code_ == 1 || getAttr();
95 uint64_t code()
const {
96 return code_ & ~NODE_ATTR_MASK;
100 return code() * 314159257;
103 bool operator==(NodeId
const& o)
const {
104 return code() == o.code();
107 bool operator!=(NodeId
const& o)
const {
108 return !(*
this == o);
111 bool operator<(NodeId
const& o)
const {
112 return code() < o.code();
115 bool operator>=(NodeId
const& o)
const {
119 bool operator>(NodeId
const& o)
const {
123 bool operator<=(NodeId
const& o)
const {
127 friend std::ostream& operator<<(std::ostream& os, NodeId
const& o) {
128 os << o.row() <<
":" << o.col();
129 if (o.code_ & NODE_ATTR_MASK) os <<
"+";
134 struct NodeBranchId {
142 NodeBranchId(
int row,
size_t col,
int val) :
143 col(col), row(row), val(val) {
149 NodeId branch[ARITY];
154 Node(NodeId f0, NodeId f1) {
156 for (
int i = 1; i < ARITY; ++i) {
161 Node(NodeId
const* f) {
162 for (
int i = 0; i < ARITY; ++i) {
167 size_t hash()
const {
168 size_t h = branch[0].code();
169 for (
int i = 1; i < ARITY; ++i) {
170 h = h * 314159257 + branch[i].code() * 271828171;
175 bool operator==(Node
const& o)
const {
176 for (
int i = 0; i < ARITY; ++i) {
177 if (branch[i] != o.branch[i])
return false;
182 bool operator!=(Node
const& o)
const {
183 return !operator==(o);
186 friend std::ostream& operator<<(std::ostream& os, Node
const& o) {
187 os <<
"(" << o.branch[0];
188 for (
int i = 1; i < ARITY; ++i) {
189 os <<
"," << o.branch[i];
196 struct InitializedNode: Node<ARITY> {
201 InitializedNode(NodeId f0, NodeId f1) :
202 Node<ARITY>(f0, f1) {
205 InitializedNode(Node<ARITY>
const& o) :
206 Node<ARITY>(o.branch) {