A tree node representing a decision in the space of solutions. More...

#include <PIP_Tree.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::PIP_Decision_Node:

Collaboration diagram for Parma_Polyhedra_Library::PIP_Decision_Node:

Public Member Functions
virtual PIP_Tree_Node *	clone () const
	Returns a pointer to a dynamically-allocated copy of `*this`.
virtual	~PIP_Decision_Node ()
	Destructor.
virtual bool	OK () const
	Returns `true` if and only if `*this` is well formed.
virtual const PIP_Decision_Node *	as_decision () const
	Returns `this`.
virtual const PIP_Solution_Node *	as_solution () const
	Returns 0, since `this` is not a solution node.
const PIP_Tree_Node *	child_node (bool b) const
	Returns a const pointer to the `b` (true or false) branch of `*this`.
PIP_Tree_Node *	child_node (bool b)
	Returns a pointer to the `b` (true or false) branch of `*this`.
void	ascii_dump (std::ostream &s) const
	Dumps to `s` an ASCII representation of `*this`.
bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise.
virtual memory_size_type	total_memory_in_bytes () const
	Returns the total size in bytes of the memory occupied by `*this`.
virtual memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by `*this`.
Protected Member Functions
	PIP_Decision_Node (const PIP_Decision_Node &y)
	Copy constructor.
virtual void	update_tableau (const PIP_Problem &pip, dimension_type external_space_dim, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set &parameters)
	Implements pure virtual method PIP_Tree_Node::update_tableau.
virtual PIP_Tree_Node *	solve (const PIP_Problem &pip, bool check_feasible_context, const Matrix &context, const Variables_Set &params, dimension_type space_dim, int indent_level)
	Implements pure virtual method PIP_Tree_Node::solve.
virtual void	print_tree (std::ostream &s, int indent, const std::vector< bool > &pip_dim_is_param, dimension_type first_art_dim) const
	Prints on `s` the tree rooted in `*this`.
Private Member Functions
	PIP_Decision_Node (const PIP_Problem owner, PIP_Tree_Node fcp, PIP_Tree_Node *tcp)
	Builds a decision node having `fcp` and `tcp` as child.
virtual void	set_owner (const PIP_Problem *owner)
	Sets the pointer to the PIP_Problem owning object.
virtual bool	check_ownership (const PIP_Problem *owner) const
	Returns `true` if and only if all the nodes in the subtree rooted in `this` is owned by `pip`.
Private Attributes
PIP_Tree_Node *	false_child
	Pointer to the "false" child of `*this`.
PIP_Tree_Node *	true_child
	Pointer to the "true" child of `*this`.
Friends
class	PIP_Solution_Node
bool	PIP_Problem::ascii_load (std::istream &s)

Detailed Description

A tree node representing a decision in the space of solutions.

Definition at line 700 of file PIP_Tree.defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::PIP_Decision_Node::~PIP_Decision_Node ( )

virtual

Destructor.

Definition at line 1061 of file PIP_Tree.cc.

References false_child, and true_child.

                                      {
  delete false_child;
  delete true_child;
}

Parma_Polyhedra_Library::PIP_Decision_Node::PIP_Decision_Node	(	const PIP_Problem *	owner,
		PIP_Tree_Node *	fcp,
		PIP_Tree_Node *	tcp
	)

explicitprivate

Builds a decision node having fcp and tcp as child.

The decision node will encode the structure "if \c cs then \p tcp else \p fcp", where the system of constraints cs is initially empty.

Parameters:

owner	Pointer to the owning PIP_Problem object; it may be null if and only if both children are null.
fcp	Pointer to "false" child; it may be null.
tcp	Pointer to "true" child; it may be null.

Note:: If any of fcp or tcp is not null, then owner is required to be not null and equal to the owner of its non-null children; otherwise the behavior is undefined.

Definition at line 1031 of file PIP_Tree.cc.

References false_child, Parma_Polyhedra_Library::PIP_Tree_Node::set_parent(), and true_child.

  : PIP_Tree_Node(owner),
    false_child(fcp),
    true_child(tcp) {
  if (false_child != 0)
    false_child->set_parent(this);
  if (true_child != 0)
    true_child->set_parent(this);
}

Parma_Polyhedra_Library::PIP_Decision_Node::PIP_Decision_Node ( const PIP_Decision_Node & y )

protected

Copy constructor.

Definition at line 1043 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::clone(), false_child, Parma_Polyhedra_Library::PIP_Tree_Node::set_parent(), and true_child.

  : PIP_Tree_Node(y),
    false_child(0),
    true_child(0) {
  if (y.false_child != 0) {
    false_child = y.false_child->clone();
    false_child->set_parent(this);
  }
  // Protect false_child from exception safety issues via std::auto_ptr.
  std::auto_ptr<PIP_Tree_Node> wrapped_node(false_child);
  if (y.true_child != 0) {
    true_child = y.true_child->clone();
    true_child->set_parent(this);
  }
  // It is now safe to release false_child.
  wrapped_node.release();
}

Member Function Documentation

const PIP_Decision_Node * Parma_Polyhedra_Library::PIP_Decision_Node::as_decision ( ) const

virtual

Returns this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1093 of file PIP_Tree.cc.

Referenced by Parma_Polyhedra_Library::PIP_Problem::ascii_dump(), and ascii_dump().

                                     {
  return this;
}

const PIP_Solution_Node * Parma_Polyhedra_Library::PIP_Decision_Node::as_solution ( ) const

virtual

Returns 0, since this is not a solution node.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1103 of file PIP_Tree.cc.

                                     {
  return 0;
}

void Parma_Polyhedra_Library::PIP_Decision_Node::ascii_dump ( std::ostream & s ) const

Dumps to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1461 of file PIP_Tree.cc.

References as_decision(), Parma_Polyhedra_Library::PIP_Solution_Node::as_solution(), Parma_Polyhedra_Library::PIP_Solution_Node::ascii_dump(), and PPL_ASSERT.

                                                 {
  // Dump base class info.
  PIP_Tree_Node::ascii_dump(s);

  // Dump true child (if any).
  s << "\ntrue_child: ";
  if (true_child == 0) {
    // Note: this branch should normally be unreachable code, since a
    // well-formed decision node always has a true child. We keep this code
    // for debugging purposes (since we want to dump broken nodes).
    s << "BOTTOM\n";
  }
  else if (const PIP_Decision_Node* dec = true_child->as_decision()) {
    s << "DECISION\n";
    dec->ascii_dump(s);
  }
  else {
    const PIP_Solution_Node* sol = true_child->as_solution();
    PPL_ASSERT(sol != 0);
    s << "SOLUTION\n";
    sol->ascii_dump(s);
  }

  // Dump false child (if any).
  s << "\nfalse_child: ";
  if (false_child == 0)
    s << "BOTTOM\n";
  else if (const PIP_Decision_Node* dec = false_child->as_decision()) {
    // Note: this branch should normally be unreachable code.
    // Since a well-formed decision node having a false child should have
    // a single context constraint, its false child will have no context
    // constraints at all, so that no further branch is possible.
    // We keep this code for debugging purposes.
    s << "DECISION\n";
    dec->ascii_dump(s);
  }
  else {
    const PIP_Solution_Node* sol = false_child->as_solution();
    PPL_ASSERT(sol != 0);
    s << "SOLUTION\n";
    sol->ascii_dump(s);
  }
}

bool Parma_Polyhedra_Library::PIP_Decision_Node::ascii_load ( std::istream & s )

Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.

Reimplemented from Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1506 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::ascii_load(), Parma_Polyhedra_Library::PIP_Solution_Node::ascii_load(), ascii_load(), Parma_Polyhedra_Library::PIP_Solution_Node::OK(), Parma_Polyhedra_Library::PIP_Tree_Node::PIP_Decision_Node, Parma_Polyhedra_Library::PIP_Solution_Node::PIP_Solution_Node(), and PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::PIP_Problem::ascii_load(), and ascii_load().

                                           {
  std::string str;

  // Load base class info.
  if (!PIP_Tree_Node::ascii_load(s))
    return false;

  // Release the "true" subtree (if any).
  delete true_child;
  true_child = 0;

  // Load true child (if any).
  if (!(s >> str) || str != "true_child:")
    return false;
  if (!(s >> str))
    return false;
  if (str == "BOTTOM")
    // Note: normally unreachable code (see comment on ascii_dump).
    true_child = 0;
  else if (str == "DECISION") {
    PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0);
    true_child = dec;
    if (!dec->ascii_load(s))
      return false;
  }
  else if (str == "SOLUTION") {
    PIP_Solution_Node* sol = new PIP_Solution_Node(0);
    true_child = sol;
    if (!sol->ascii_load(s))
      return false;
  }
  else
    // Unknown node kind.
    return false;

  // Release the "false" subtree (if any).
  delete false_child;
  false_child = 0;

  // Load false child (if any).
  if (!(s >> str) || str != "false_child:")
    return false;
  if (!(s >> str))
    return false;
  if (str == "BOTTOM")
    false_child = 0;
  else if (str == "DECISION") {
    // Note: normally unreachable code (see comment on ascii_dump).
    PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0);
    false_child = dec;
    if (!dec->ascii_load(s))
      return false;
  }
  else if (str == "SOLUTION") {
    PIP_Solution_Node* sol = new PIP_Solution_Node(0);
    false_child = sol;
    if (!sol->ascii_load(s))
      return false;
  }
  else
    // Unknown node kind.
    return false;

  // Loaded all info.
  PPL_ASSERT(OK());
  return true;
}

bool Parma_Polyhedra_Library::PIP_Decision_Node::check_ownership ( const PIP_Problem * owner ) const

privatevirtual

Returns true if and only if all the nodes in the subtree rooted in *this is owned by *pip.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1086 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::check_ownership(), false_child, Parma_Polyhedra_Library::PIP_Tree_Node::get_owner(), and true_child.

                                                                 {
  return get_owner() == owner
    && (false_child == 0 || false_child->check_ownership(owner))
    && (true_child == 0 || true_child->check_ownership(owner));
}

const PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::child_node ( bool b ) const

inline

Returns a const pointer to the b (true or false) branch of *this.

Definition at line 96 of file PIP_Tree.inlines.hh.

                                          {
  return b ? true_child : false_child;
}

PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::child_node ( bool b )

inline

Returns a pointer to the b (true or false) branch of *this.

Definition at line 102 of file PIP_Tree.inlines.hh.

                                    {
  return b ? true_child : false_child;
}

PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::clone ( ) const

virtual

Returns a pointer to a dynamically-allocated copy of *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1778 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::PIP_Decision_Node.

                               {
  return new PIP_Decision_Node(*this);
}

memory_size_type Parma_Polyhedra_Library::PIP_Decision_Node::external_memory_in_bytes ( ) const

virtual

Returns the size in bytes of the memory managed by *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 3539 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::external_memory_in_bytes(), and PPL_ASSERT.

                                                  {
  memory_size_type n = PIP_Tree_Node::external_memory_in_bytes();
  PPL_ASSERT(true_child != 0);
  n += true_child->total_memory_in_bytes();
  if (false_child != 0)
    n += false_child->total_memory_in_bytes();
  return n;
}

bool Parma_Polyhedra_Library::PIP_Decision_Node::OK ( ) const

virtual

Returns true if and only if *this is well formed.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1276 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::constraints_, Parma_Polyhedra_Library::Implementation::num_constraints(), and Parma_Polyhedra_Library::PIP_Tree_Node::OK().

                            {
  // Perform base class well-formedness check on this node.
  if (!PIP_Tree_Node::OK())
    return false;

  // Recursively check if child nodes are well-formed.
  if (false_child != 0 && !false_child->OK())
    return false;
  if (true_child != 0 && !true_child->OK())
    return false;

  // Decision nodes should always have a true child.
  if (true_child == 0) {
#ifndef NDEBUG
    std::cerr << "PIP_Decision_Node with no 'true' child.\n";
#endif
    return false;
  }

  // Decision nodes with a false child must have exactly one constraint.
  if (false_child != 0) {
    dimension_type dist = Implementation::num_constraints(constraints_);
    if (dist != 1) {
#ifndef NDEBUG
      std::cerr << "PIP_Decision_Node with a 'false' child has "
                << dist << " parametric constraints (should be 1).\n";
#endif
      return false;
    }
  }

  // All checks passed.
  return true;
}

void Parma_Polyhedra_Library::PIP_Decision_Node::print_tree	(	std::ostream &	s,
		int	indent,
		const std::vector< bool > &	pip_dim_is_param,
		dimension_type	first_art_dim
	)		const

protectedvirtual

Prints on s the tree rooted in *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 3639 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::art_parameter_count(), Parma_Polyhedra_Library::PIP_Tree_Node::indent_and_print(), PPL_ASSERT, and Parma_Polyhedra_Library::PIP_Solution_Node::print_tree().

                                                                        {
  // First print info common to decision and solution nodes.
  PIP_Tree_Node::print_tree(s, indent, pip_dim_is_param, first_art_dim);

  // Then print info specific of decision nodes.
  dimension_type child_first_art_dim = first_art_dim + art_parameter_count();

  PPL_ASSERT(true_child != 0);
  true_child->print_tree(s, indent+1, pip_dim_is_param, child_first_art_dim);

  indent_and_print(s, indent, "else\n");

  if (false_child != 0)
    false_child->print_tree(s, indent+1, pip_dim_is_param,
                            child_first_art_dim);
  else
    indent_and_print(s, indent+1, "_|_\n");
}

void Parma_Polyhedra_Library::PIP_Decision_Node::set_owner ( const PIP_Problem * owner )

privatevirtual

Sets the pointer to the PIP_Problem owning object.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1072 of file PIP_Tree.cc.

References false_child, Parma_Polyhedra_Library::PIP_Tree_Node::owner_, Parma_Polyhedra_Library::PIP_Tree_Node::set_owner(), and true_child.

Referenced by Parma_Polyhedra_Library::PIP_Problem::ascii_load().

                                                     {
  owner_ = owner;
  if (false_child != 0)
    false_child->set_owner(owner);
  if (true_child != 0)
    true_child->set_owner(owner);
}

PIP_Tree_Node * Parma_Polyhedra_Library::PIP_Decision_Node::solve	(	const PIP_Problem &	pip,
		bool	check_feasible_context,
		const Matrix &	context,
		const Variables_Set &	params,
		dimension_type	space_dim,
		int	indent_level
	)

protectedvirtual

Implements pure virtual method PIP_Tree_Node::solve.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1334 of file PIP_Tree.cc.

                                                 {
  PPL_ASSERT(indent_level >= 0);
#ifdef NOISY_PIP_TREE_STRUCTURE
  indent_and_print(std::cerr, indent_level, "=== SOLVING DECISION NODE\n");
#else
  PPL_USED(indent_level);
#endif
  PPL_ASSERT(true_child != 0);
  Matrix context_true(context);
  Variables_Set all_params(params);
  const dimension_type num_art_params = artificial_parameters.size();
  add_artificial_parameters(context_true, all_params, space_dim,
                            num_art_params);
  merge_assign(context_true, constraints_, all_params);
  const bool has_false_child = (false_child != 0);
  const bool has_true_child = (true_child != 0);
#ifdef NOISY_PIP_TREE_STRUCTURE
  indent_and_print(std::cerr, indent_level,
                   "=== DECISION: SOLVING THEN CHILD\n");
#endif
  true_child = true_child->solve(pip, check_feasible_context,
                                 context_true, all_params, space_dim,
                                 indent_level + 1);

  if (has_false_child) {
    // Decision nodes with false child must have exactly one constraint
    PPL_ASSERT(1 == Implementation::num_constraints(constraints_));
    // NOTE: modify context_true in place, complementing its last constraint.
    Matrix& context_false = context_true;
    Row& last = context_false[context_false.num_rows() - 1];
    complement_assign(last, last, 1);
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: SOLVING ELSE CHILD\n");
#endif
    false_child = false_child->solve(pip, check_feasible_context,
                                     context_false, all_params, space_dim,
                                     indent_level + 1);
  }

  if (true_child == 0 && false_child == 0) {
    // No children: the whole subtree is unfeasible.
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: BOTH BRANCHES NOW UNFEASIBLE: _|_\n");
#endif
    delete this;
    return 0;
  }

  if (has_false_child && false_child == 0) {
    // False child has become unfeasible: merge this node's artificials with
    // the true child, while removing the local parameter constraints, which
    // are no longer discriminative.
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: ELSE BRANCH NOW UNFEASIBLE\n");
    indent_and_print(std::cerr, indent_level,
                     "==> merge then branch with parent.\n");
#endif
    PIP_Tree_Node* node = true_child;
    node->parent_merge();
    node->set_parent(parent());
    true_child = 0;
    delete this;
    PPL_ASSERT(node->OK());
    return node;
  }
  else if (has_true_child && true_child == 0) {
    // True child has become unfeasible: merge this node's artificials
    // with the false child.
#ifdef NOISY_PIP_TREE_STRUCTURE
    indent_and_print(std::cerr, indent_level,
                     "=== DECISION: THEN BRANCH NOW UNFEASIBLE\n");
    indent_and_print(std::cerr, indent_level,
                     "==> merge else branch with parent.\n");
#endif
    PIP_Tree_Node* node = false_child;
    node->parent_merge();
    node->set_parent(parent());
    false_child = 0;
    delete this;
    PPL_ASSERT(node->OK());
    return node;
  }
  else if (check_feasible_context) {
    // Test all constraints for redundancy with the context, and eliminate
    // them if not necessary.
    Constraint_System cs;
    swap(cs, constraints_);
    for (Constraint_System::const_iterator
           ci = cs.begin(), ci_end = cs.end(); ci != ci_end; ++ci) {
      Matrix ctx_copy(context);
      merge_assign(ctx_copy, Constraint_System(*ci), all_params);
      Row& last = ctx_copy[ctx_copy.num_rows()-1];
      complement_assign(last, last, 1);
      if (compatibility_check(ctx_copy)) {
        // The constraint is not redundant with the context: keep it.
        constraints_.insert(*ci);
      }
    }
    // If the constraints set has become empty, only keep the true child.
    if (constraints_.empty()) {
#ifdef NOISY_PIP_TREE_STRUCTURE
      indent_and_print(std::cerr, indent_level,
                       "=== DECISION: NO BRANCHING CONSTRAINTS LEFT\n");
      indent_and_print(std::cerr, indent_level,
                       "==> merge then branch with parent.\n");
#endif
      PIP_Tree_Node* node = true_child;
      node->parent_merge();
      node->set_parent(parent());
      true_child = 0;
      delete this;
      PPL_ASSERT(node->OK());
      return node;
    }
  }
  PPL_ASSERT(OK());
  return this;
}

memory_size_type Parma_Polyhedra_Library::PIP_Decision_Node::total_memory_in_bytes ( ) const

virtual

Returns the total size in bytes of the memory occupied by *this.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 3549 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::external_memory_in_bytes().

                                               {
  return sizeof(*this) + external_memory_in_bytes();
}

void Parma_Polyhedra_Library::PIP_Decision_Node::update_tableau	(	const PIP_Problem &	pip,
		dimension_type	external_space_dim,
		dimension_type	first_pending_constraint,
		const Constraint_Sequence &	input_cs,
		const Variables_Set &	parameters
	)

protectedvirtual

Implements pure virtual method PIP_Tree_Node::update_tableau.

Implements Parma_Polyhedra_Library::PIP_Tree_Node.

Definition at line 1312 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::OK(), and PPL_ASSERT.

                                     {

  true_child->update_tableau(pip,
                             external_space_dim,
                             first_pending_constraint,
                             input_cs,
                             parameters);
  if (false_child != 0)
    false_child->update_tableau(pip,
                                external_space_dim,
                                first_pending_constraint,
                                input_cs,
                                parameters);
  PPL_ASSERT(OK());
}