Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
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>
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:
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
QString getLabel(T *n) const
Get label of node n.
Definition: node.hpp:144
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
T * operator[](int i) const
Return node for index i.
Definition: node.hpp:89
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition: node.hpp:132
NodeAllocatorBase< VisualNode > NodeAllocator
Definition: node.hh:143
Base class for nodes of the search tree.
Definition: node.hh:106
Node allocator.
Definition: node.hh:48
NodeAllocatorBase(bool bab)
Constructor.
Definition: node.hpp:50
Computation spaces.
Definition: core.hpp:1701
T * best(int i) const
Return index of best node before i.
Definition: node.hpp:97
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
void clearLabel(T *n)
Remove label of node n.
Definition: node.hpp:138
bool hasLabel(T *n) const
Return whether node n has a label.
Definition: node.hpp:126
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
void setBest(int i, int b)
Set index of best node before i to b.
Definition: node.hpp:106
~NodeAllocatorBase(void)
Destructor.
Definition: node.hpp:59
bool showLabels(void) const
Return branching label flag.
Definition: node.hpp:120
bool bab(void) const
Return branch-and-bound flag.
Definition: node.hpp:114
Node class that supports visual layout
Definition: visualnode.hh:125
Gecode toplevel namespace