main page
modules
namespaces
classes
files
Gecode home
Generated on Sun Aug 9 2020 05:34:08 for Gecode by
doxygen
1.8.18
gecode
gist
node.hh
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Guido Tack <tack@gecode.org>
5
*
6
* Copyright:
7
* Guido Tack, 2006
8
*
9
* This file is part of Gecode, the generic constraint
10
* development environment:
11
* http://www.gecode.org
12
*
13
* Permission is hereby granted, free of charge, to any person obtaining
14
* a copy of this software and associated documentation files (the
15
* "Software"), to deal in the Software without restriction, including
16
* without limitation the rights to use, copy, modify, merge, publish,
17
* distribute, sublicense, and/or sell copies of the Software, and to
18
* permit persons to whom the Software is furnished to do so, subject to
19
* the following conditions:
20
*
21
* The above copyright notice and this permission notice shall be
22
* included in all copies or substantial portions of the Software.
23
*
24
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31
*
32
*/
33
34
#ifndef GECODE_GIST_NODE_HH
35
#define GECODE_GIST_NODE_HH
36
37
#include <
gecode/kernel.hh
>
38
39
#include <QHash>
40
#include <QString>
41
42
namespace
Gecode
{
namespace
Gist {
43
44
class
VisualNode;
45
47
template
<
class
T>
48
class
NodeAllocatorBase
{
49
private
:
51
static
const
int
NodeBlockSize = 1<<14;
53
class
Block {
54
public
:
56
T
b
[NodeBlockSize];
58
int
best
[NodeBlockSize];
59
};
61
Block** b;
63
int
n;
65
int
cur_b;
67
int
cur_t;
69
void
allocate(
void
);
71
bool
_bab;
73
QHash<T*,QString> labels;
74
public
:
76
NodeAllocatorBase
(
bool
bab
);
78
~NodeAllocatorBase
(
void
);
80
int
allocate(
int
p
);
82
int
allocate(
Space
* root);
84
T*
operator []
(
int
i
)
const
;
86
T*
best
(
int
i
)
const
;
88
void
setBest
(
int
i
,
int
b
);
90
bool
bab
(
void
)
const
;
92
bool
showLabels
(
void
)
const
;
94
void
showLabels
(
bool
b);
96
bool
hasLabel
(T* n)
const
;
98
void
setLabel
(T* n,
const
QString&
l
);
100
void
clearLabel
(T* n);
102
QString
getLabel
(T* n)
const
;
103
};
104
106
class
Node
{
107
private
:
109
enum
{
110
UNDET,
//< Number of children not determined
111
LEAF,
//< Leaf node
112
TWO_CHILDREN,
//< Node with at most two children
113
MORE_CHILDREN
//< Node with more than two children
114
};
115
117
void
* childrenOrFirstChild;
118
122
int
noOfChildren;
123
125
int
parent;
126
128
unsigned
int
getTag(
void
)
const
;
130
void
setTag(
unsigned
int
tag);
132
void
* getPtr(
void
)
const
;
134
int
getFirstChild(
void
)
const
;
135
136
protected
:
138
bool
isUndetermined
(
void
)
const
;
139
141
int
getChild
(
int
n
)
const
;
142
public
:
143
typedef
NodeAllocatorBase<VisualNode>
NodeAllocator
;
144
146
Node
(
int
p
,
bool
failed =
false
);
147
149
int
getParent
(
void
)
const
;
151
VisualNode
*
getParent
(
const
NodeAllocator
& na)
const
;
153
VisualNode
*
getChild
(
const
NodeAllocator
& na,
int
n
)
const
;
154
156
int
getIndex
(
const
NodeAllocator
& na)
const
;
157
159
bool
isRoot
(
void
)
const
;
160
162
void
setNumberOfChildren
(
unsigned
int
n
,
NodeAllocator
& na);
163
165
unsigned
int
getNumberOfChildren
(
void
)
const
;
166
167
};
168
169
}}
170
171
#endif
172
173
// STATISTICS: gist-any
kernel.hh
Gecode::Gist::NodeAllocatorBase::operator[]
T * operator[](int i) const
Return node for index i.
Definition:
node.hpp:89
Gecode::Gist::NodeAllocatorBase::getLabel
QString getLabel(T *n) const
Get label of node n.
Definition:
node.hpp:144
Gecode::Gist::VisualNode
Node class that supports visual layout
Definition:
visualnode.hh:125
Gecode::Gist::NodeAllocatorBase::NodeAllocatorBase
NodeAllocatorBase(bool bab)
Constructor.
Definition:
node.hpp:50
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Gist::Node::getIndex
int getIndex(const NodeAllocator &na) const
Return index of this node.
Definition:
node.hpp:227
Gecode::Gist::Node::setNumberOfChildren
void setNumberOfChildren(unsigned int n, NodeAllocator &na)
Set the number of children to n and initialize children.
Definition:
node.cpp:42
Gecode::Gist::Node::isRoot
bool isRoot(void) const
Check if this node is the root of a tree.
Definition:
node.hpp:211
Gecode::Gist::NodeAllocatorBase::hasLabel
bool hasLabel(T *n) const
Return whether node n has a label.
Definition:
node.hpp:126
Gecode::Gist::Node
Base class for nodes of the search tree.
Definition:
node.hh:106
Gecode
Gecode toplevel namespace
Gecode::Gist::NodeAllocatorBase::best
T * best(int i) const
Return index of best node before i.
Definition:
node.hpp:97
Gecode::Gist::NodeAllocatorBase::~NodeAllocatorBase
~NodeAllocatorBase(void)
Destructor.
Definition:
node.hpp:59
Gecode::Gist::NodeAllocatorBase::clearLabel
void clearLabel(T *n)
Remove label of node n.
Definition:
node.hpp:138
Gecode::Gist::NodeAllocatorBase
Node allocator.
Definition:
node.hh:48
Gecode::Gist::Node::Node
Node(int p, bool failed=false)
Construct node with parent p.
Definition:
node.hpp:175
Gecode::Gist::Node::NodeAllocator
NodeAllocatorBase< VisualNode > NodeAllocator
Definition:
node.hh:143
b
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Gecode::Gist::Node::getChild
int getChild(int n) const
Return index of child no n.
Definition:
node.hpp:195
Gecode::Gist::Node::getParent
int getParent(void) const
Return the parent.
Definition:
node.hpp:182
Gecode::Gist::NodeAllocatorBase::setBest
void setBest(int i, int b)
Set index of best node before i to b.
Definition:
node.hpp:106
Gecode::Gist::NodeAllocatorBase::bab
bool bab(void) const
Return branch-and-bound flag.
Definition:
node.hpp:114
Gecode::Gist::Node::getNumberOfChildren
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition:
node.hpp:214
Gecode::Gist::Node::isUndetermined
bool isUndetermined(void) const
Return whether this node is undetermined.
Definition:
node.hpp:192
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Gist::NodeAllocatorBase::showLabels
bool showLabels(void) const
Return branching label flag.
Definition:
node.hpp:120
Gecode::Gist::NodeAllocatorBase::showLabels
void showLabels(bool b)
Set branching label flag.
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::Gist::NodeAllocatorBase::setLabel
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition:
node.hpp:132