---

search_node.h

Go to the documentation of this file.

// Search Node implementation -*- C++ -*-

// Copyright (C) 2001-2003 Hermann Schichl, Evgueni Petrov, Brice Pajot
//
// This file is part of the COCONUT API.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#ifndef _SEARCH_NODE_H
#define _SEARCH_NODE_H

// FIXED by IRIN as of 08/11/2002
// + re-ordered and/or completed some initialization lists
// + made some methods of search_node, full_node etc. "const"
// + suppressed some empty declarations
// + made the destructors of search_node & Co. "virtual" 
//

#include <iostream>
#include <interval.h>
#include <coconut_config.h>
#include <model.h>
#include <annotation.h>
#include <map>
#include <set>
#include <list>
#include <string>
#include <gptr.h>
#include <stdint.h>
#include <database>
#include <db_alltype>

using namespace vgtl;

#include <api_deltabase.h>

typedef enum {
  snr_root,             // this is the root node of a search graph
  snr_reduction,        // this is a reduction of the parent node
  snr_relaxation,       // this is a relaxation of the parent node
  snr_split,            // this is one of a number of splits of the parent
  snr_glue,             // this is a glueing of a number of parent nodes
  snr_worknode,         // this is a **standalone** work-node
  snr_virtual,          // this is a virtual node of the search graph
} search_node_relation;

typedef uint32_t search_node_id;

#if 0
class id_data
{
  search_node_id _maxid;
  //delta_id _maxDid;
  vdbl::userid _dbuser;

public:
  id_data(const vdbl::userid& _dbu = vdbl::userid())
                        : _maxid(0), //_maxDid(0),
                          _dbuser(_dbu) {}

  search_node_id get_search_node_id() { return _maxid++; }
  //delta_id get_delta_id() { return _maxDid++; }
  vdbl::userid get_dbuserid() const { return _dbuser; }
};
#endif

class search_node
{
protected:
  gptr<search_node>* __global_model;
  gptr<vdbl::database>* __dbase;
  vdbl::userid _dbuser;
  search_node_relation _snr;
  search_node_id _id;
  std::vector<annotation> _keep;

protected:
  search_node_id node_id() const { return _id; }
  search_node_relation parent_relation() const { return _snr; }

public:
  virtual bool is_delta() const { return false; } // const added by evgueni 16/09/2002

  search_node(const search_node_id& _i, const vdbl::userid& _dui,
              gptr<search_node>& _gm, gptr<vdbl::database>& _db,
              search_node_relation __snr = snr_reduction)
    : 
    __global_model(&_gm), __dbase(&_db), _dbuser(_dui),
    _snr(__snr), _id(_i), _keep() {}

  search_node(const search_node_id& _i, const vdbl::userid& _dui,
              gptr<search_node>* _gm, gptr<vdbl::database>& _db,
              search_node_relation __snr = snr_reduction)
    : __global_model(_gm), __dbase(&_db), _dbuser(_dui),
      _snr(__snr), _id(_i), _keep() {}

  search_node(const search_node& __sn) : __global_model(__sn.__global_model),
        __dbase(__sn.__dbase), _dbuser(__sn._dbuser),
        _snr(__sn._snr), _id(__sn._id), _keep(__sn._keep) {}

  search_node(const search_node_id& _i, const vdbl::userid& _dui,
              gptr<vdbl::database>& _db, search_node_relation __snr = snr_root)
        : __global_model(NULL), __dbase(&_db), _dbuser(_dui),
          _snr(__snr), _id(_i), _keep()
    {
      if(__dbase == NULL)
      {
        vdbl::database *__db = new vdbl::database;
        __dbase = new ptr<vdbl::database>(__db);
      }
    }

  virtual ~search_node() // Brice (25/10/02) : added virtual destructor
    {
      vdbl::database *_db = (*__dbase).get_local_copy();
      for(std::vector<annotation>::iterator __x = _keep.begin();
          __x != _keep.end(); ++__x)
      {
        vdbl::table* _dbt = (vdbl::table*)_db->get_table(__x->get_table(),
                                                         _dbuser);
        _dbt->remove(__x->get_entry());
      }
    }

  vdbl::userid get_dbuserid() const { return _dbuser; }

  gptr<search_node>* global_model() const { return __global_model; }

  gptr<vdbl::database>* database() const { return __dbase; }

  search_node_id get_id() const { return _id; }

  void keep(const annotation& _an) { _keep.push_back(_an); }
  
  void keep(const std::vector<annotation>& _anv)
        { _keep.insert(_keep.end(), _anv.begin(), _anv.end()); }

  void unkeep(const annotation& _an)
  {
    for(std::vector<annotation>::iterator __x = _keep.begin();
        __x != _keep.end(); ++__x)
      if(_an == *__x)
      {
        _keep.erase(__x);
        break;
      }
  } 
  
  void unkeep(const std::vector<annotation>& _anv)
  {
    for(std::vector<annotation>::const_iterator __x = _anv.begin();
        __x != _anv.end(); ++__x)
      unkeep(*__x);
  }

  friend class search_graph;
};

class delta_node : public search_node
{
private:
  std::vector<delta_id> di;

public:
  // constructors,...
  delta_node(const search_node_id& _i, const vdbl::userid& _dui,
             std::vector<delta_id>& __d, gptr<search_node>& _gm,
             gptr<vdbl::database>& _db,
             search_node_relation _snr = snr_reduction)
        : search_node(_i, _dui, _gm, _db, _snr), di(__d)
    {}
  
  virtual ~delta_node() {} // Brice (25/10/02) : added virtual destructor

  bool is_delta() const { return true; } // const added by evgueni 15/09/2002

  unsigned int n_deltas() const { return di.size(); } // const added by evgueni 15/09/2002

  delta_id get_delta_id(unsigned int i) const
  {
    return di[i];
  }
  
  delta get_delta(unsigned int i);

  const delta& get_delta(unsigned int i) const;
};

class full_node : public search_node
{
protected:
  gptr<model>*          _m;

public:
  std::vector<annotation> _ann;

protected:
  full_node(const search_node_id& _i, const vdbl::userid& _dui,
            gptr<model>& __mod, gptr<search_node>* _gm,
            gptr<vdbl::database>& _db,
            search_node_relation _snr = snr_reduction)
        : search_node(_i, _dui, _gm, _db, _snr), _ann()
  {
    _m = &__mod;
  }

  full_node(const search_node_id& _i, const vdbl::userid& _dui,
            gptr<model>& __mod, gptr<search_node>* _gm,
            gptr<vdbl::database>& _db, const std::vector<annotation>& _a,
            search_node_relation _snr = snr_reduction)
                 : search_node(_i, _dui, _gm, _db, _snr), _ann(_a)
  {
    _m = &__mod;
  }

public:
  // constructors,...
  full_node(const search_node_id& _i, const vdbl::userid& _dui,
            gptr<model>& __mod, gptr<search_node>& _gm,
            gptr<vdbl::database>& _db,
            search_node_relation _snr = snr_reduction) :
    search_node(_i, _dui, _gm, _db, _snr), _ann()
  {
    _m = &__mod;
  }

  full_node(const search_node_id& _i, const vdbl::userid& _dui,
            gptr<model>& __mod, gptr<search_node>& _gm,
            gptr<vdbl::database>& _db, const std::vector<annotation>& _a,
            search_node_relation _snr = snr_reduction) :
    search_node(_i, _dui, _gm, _db, _snr), _ann(_a)
  {
    _m = &__mod;
  }

  virtual ~full_node() {} // Brice (25/10/02) : added virtual destructor
  
  bool is_delta() const { return false; } // const added by evgueni 15/09/2002

  const annotation& get_annotation(unsigned int i) const
  {
    return _ann[i];
  }

  const std::vector<annotation>& get_annotations() const
  {
    return _ann;
  }

  const model* get_model() const { return (*_m).get_local_copy(); } 

  const vdbl::database* get_database() const
        { return (*database()).get_local_copy(); } 

  model* get_model_ptr() const
    {
      return (*_m).get_local_copy();
    } // const by evgueni 15/09/2002

  vdbl::database* get_database_ptr() const
    {
      return (*database()).get_local_copy();
    }

  friend class delta_base;
  friend class dag_delta;
  friend class dag_undelta;
};

class work_node : public full_node
{
private:
  typedef full_node _Base;

public:
  template <class _W, class _V, class _VR, class _P, class _R, class _I>
  class constraint_iterator_base;

  typedef constraint_iterator_base<model::walker,const std::vector<model::walker>*,
             const std::vector<model::walker>&,const model::walker*,
             const model::walker&,
             std::vector<model::walker>::const_iterator> constraint_const_iterator;
  typedef constraint_iterator_base<model::walker,std::vector<model::walker>*,
             std::vector<model::walker>&,model::walker*,model::walker&,
             std::vector<model::walker>::iterator> constraint_iterator;

public:  
  std::list<delta_id> deltas;
  std::map<delta_id,undelta> undeltas;
  vdbl::standard_table *dtable;
  vdbl::tableid dtable_id;
  // to add a list of references to delta_id or a map to delta_id's

  // additional data needed in the solution process 
public:
  std::vector<interval> node_ranges;
  bool infeasible;

  double log_vol;
  double gain_factor;

public:
  typedef uint32_t transaction_number;

private:
  transaction_number _tnum;

public:
  transaction_number get_transaction_number() { return ++_tnum; }

public:
  std::map<transaction_number,std::list<std::vector<delta> > > proposed_splits;

private:
  unsigned int n_bds;
  unsigned int n_lin;
  unsigned int n_quad;
  unsigned int n_poly;
  unsigned int n_other;

public:
  void init_cnumbers();
  void reset_node_ranges(); // reset all unused node ranges to [-I,I]
  void make_node_ranges(bool keep_old_ranges);
  double compute_log_volume(const std::vector<interval>& _r) const;

public:
  work_node(const work_node& __w) : 
    _Base(__w),
    deltas(__w.deltas),
    undeltas(__w.undeltas),
    dtable(__w.dtable),
    dtable_id(__w.dtable_id),
    node_ranges(__w.node_ranges),
    infeasible(__w.infeasible),
    log_vol(__w.log_vol),
    gain_factor(__w.gain_factor),
    _tnum(__w._tnum),
    proposed_splits(__w.proposed_splits),
    n_bds(__w.n_bds), 
    n_lin(__w.n_lin),
    n_quad(__w.n_quad), 
    n_poly(__w.n_poly),
    n_other(__w.n_other)
  {}

  work_node(const search_node_id& _i, const vdbl::userid& _dui,
            gptr<model>& __m, gptr<vdbl::database>& __d,
            const std::vector<annotation>& __an,
            const std::list<delta_id>& __de, gptr<search_node>* _gm,
            search_node_relation snr = snr_worknode);

  virtual ~work_node() {}

  const model* get_model() const { return (*_m).get_local_copy(); } 
  model* get_model() { return (*_m).get_local_copy(); } 

public:
  // usage e.g.: get(ex_bounds|ex_linear|ex_quadratic) for a
  //             full quadratic model
  // equivalent: get(ex_anyquad)
  model get(unsigned int __type);
  // NOT YET IMPLEMENTED
  //  {} Brice (25/10/02) : Suppressed empty declaration

  // usage e.g.:
  //     constraint_iterator b = get_begin(ex_linear);
  //     while(b != get_end(ex_linear))
  //     {
  //         do_something(*b);
  //         ++b;
  //     }
  // to iterate through some constraints
  constraint_const_iterator get_begin(unsigned int __type) const;
  constraint_const_iterator get_end(unsigned int __type) const;

  constraint_iterator get_begin(unsigned int __type);
  constraint_iterator get_end(unsigned int __type);

  delta get_delta(const delta_id& _id);

  const delta& get_delta(const delta_id& _id) const;

  double log_volume() const { return log_vol; }
  double gain() const { return gain_factor; }
  double reset_gain() {double ret = gain_factor; gain_factor = 1.; return ret;}

  // usage:   n(ex_linear|ex_equality)  returns the number of linear
  //                                    equality constraints
  unsigned int n(unsigned int __type) const;

public:
  friend work_node operator+(const work_node& _w, const delta_id& _d);
  friend work_node operator-(const work_node& _w, const delta_id& _d);
  friend work_node& operator+=(work_node& _w, const delta_id& _d);
  friend work_node& operator-=(work_node& _w, const delta_id& _d);

  template <template <class _Tp, class _A> class _Ctr, class _Al>
  friend work_node operator+(const work_node& _w, const _Ctr<delta_id,_Al>& _d);

  template <template <class _Tp, class _A> class _Ctr, class _Al>
  friend work_node operator-(const work_node& _w, const _Ctr<delta_id,_Al>& _d);

  template <template <class _Tp, class _A> class _Ctr, class _Al>
  friend work_node& operator+=(work_node& _w, const _Ctr<delta_id,_Al>& _d);

  template <template <class _Tp, class _A> class _Ctr, class _Al>
  friend work_node& operator-=(work_node& _w, const _Ctr<delta_id,_Al>& _d);

  friend class delta;
  friend class undelta;
  friend class work_node_comp_hook;
};

template <class _W, class _V, class _VR, class _P, class _R, class _I>
class work_node::constraint_iterator_base
{
private:
  typedef constraint_iterator_base<_W,_V,_VR,_P,_R,_I> _Self;

private:
  _V __cs;
  _I __c_cur;
  unsigned int __tp;

private:
  typedef _V _Vector;
  typedef _I _Iterator;
  typedef _VR _Reference;

public:
  typedef std::bidirectional_iterator_tag iterator_category;
  
  typedef _W value_type;
  typedef _R reference;
  typedef _P pointer;

  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  
public:
  constraint_iterator_base() : __cs(NULL), __c_cur() {}
  constraint_iterator_base(_Reference cs, unsigned int tp)
                                        : __cs(&cs), __tp(tp) {}
  constraint_iterator_base(const _Self& __c)
                : __cs(__c.__cs), __c_cur(__c.__c_cur), __tp(__c.__tp) {}

  ~constraint_iterator_base() {}

  reference operator*() const { return *__c_cur; }
  pointer operator->() const { return &(operator*()); }

  bool operator==(const _Self& _c)
    { return __cs == _c.__cs && __c_cur == _c.__c_cur; }
  
  bool operator!=(const _Self& _c)
    { return __cs != _c.__cs || __c_cur != _c.__c_cur; }

  _Self& set(const _Iterator& _c)
    {
      for(__c_cur = _c; __c_cur != (*__cs).end(); ++__c_cur)
      {
        if((*__c_cur)->is(__tp))
          break;
      }
      return *this;
    }

  _Self& operator++()
    {
      if(__c_cur != (*__cs).end())
        ++__c_cur;
      for(; __c_cur != (*__cs).end(); ++__c_cur)
      {
        if((*__c_cur)->is(__tp))
          break;
      }
      return *this;
    }

  _Self operator++(int)
    {
      _Self __tmp = *this;
      ++__tmp;
      return __tmp;
    }
  
  _Self& operator--()
    {
      if(__c_cur == (*__cs).begin())
        __c_cur = (*__cs).end();
      else if(__c_cur != (*__cs).end())
        --__c_cur;
      for(; __c_cur != (*__cs).begin(); --__c_cur)
      {
        if((*__c_cur)->is(__tp))
          break;
      }
      if(__c_cur == (*__cs).begin() && !(*__c_cur)->is(__tp))
        __c_cur = (*__cs).end();
      return *this;
    }
  
  _Self operator--(int)
    {
      _Self __tmp = *this;
      --__tmp;
      return __tmp;
    }
  
  _Self& operator=(const _Self& _c)
    {
      __cs = _c.__cs;
      __c_cur = _c.__c_cur;
      __tp = _c.__tp;
      return *this;
    }
};

inline work_node::constraint_const_iterator
  work_node::get_begin(unsigned int __type) const
{
  constraint_const_iterator __tmp((*_m)->constraints, __type);
  __tmp.set((*_m)->constraints.begin());
  return(__tmp);
}

inline work_node::constraint_const_iterator
  work_node::get_end(unsigned int __type) const
{
  constraint_const_iterator __tmp((*_m)->constraints, __type);
  __tmp.set((*_m)->constraints.end());
  return(__tmp);
}

inline work_node::constraint_iterator work_node::get_begin(unsigned int __type)
{
  constraint_iterator __tmp((*_m)->constraints, __type);
  __tmp.set((*_m)->constraints.begin());
  return(__tmp);
}

inline work_node::constraint_iterator work_node::get_end(unsigned int __type)
{
  constraint_iterator __tmp((*_m)->constraints, __type);
  __tmp.set((*_m)->constraints.end());
  return(__tmp);
}

#include <api_delta.h>

inline work_node operator+(const work_node& _w, const delta_id& _i)
{
  work_node _tmp(_w);
  const delta& _d(_tmp.get_delta(_i));
  if(!_d.apply3(_tmp, _w, _i))
    std::cerr << "Warning: Could not apply delta <" <<
      _i << "> to work node <" << _tmp.get_id() << ">!" << std::endl;
  return _tmp;
}

inline work_node& operator+=(work_node& _w, const delta_id& _i)
{
  const delta& _d(_w.get_delta(_i));
  if(!_d.apply(_w, _i))
    std::cerr << "Warning: Could not apply delta <" <<
      _i << "> to work node <" << _w.get_id() << ">!" << std::endl;
  return _w;
}

template <template <class _Tp, class _A> class _Ctr, class _Al>
inline work_node operator+(const work_node& _w, const _Ctr<delta_id, _Al>& _d)
{
  work_node _tmp(_w);
  typename _Ctr<delta_id, _Al>::const_iterator __b, __e;

  __e = _d.end();
  for(__b = _d.begin(); __b != __e; ++__b)
    _tmp += *__b;
  return _tmp;
}

template <template <class _Tp, class _A> class _Ctr, class _Al>
inline work_node operator-(const work_node& _w, const _Ctr<delta_id, _Al>& _d)
{
  work_node _tmp(_w);
  typedef typename _Ctr<delta_id, _Al>::const_iterator _Ccit;
  typedef typename std::reverse_iterator<_Ccit> _rCcit;
  _rCcit __b, __e;

  __e = _d.rend();
  for(__b = _d.rbegin(); __b != __e; ++__b)
    _tmp -= *__b;
  return _tmp;
}

template <template <class _Tp, class _A> class _Ctr, class _Al>
inline work_node& operator+=(work_node& _w, const _Ctr<delta_id, _Al>& _d)
{
  typename _Ctr<delta_id, _Al>::const_iterator __b, __e;

  __e = _d.end();
  for(__b = _d.begin(); __b != __e; ++__b)
    _w += *__b;
  return _w;
}

template <template <class _Tp, class _A> class _Ctr, class _Al>
inline work_node& operator-=(work_node& _w, const _Ctr<delta_id, _Al>& _d)
{
  typedef typename _Ctr<delta_id, _Al>::const_iterator _Ccit;
  typedef typename std::reverse_iterator<_Ccit> _rCcit;
  _rCcit __b, __e;

  __e = _d.rend();
  for(__b = _d.rbegin(); __b != __e; ++__b)
    _w -= *__b;
  return _w;
}

inline delta delta_node::get_delta(unsigned int i)
{
  vdbl::standard_table* dt =
      (vdbl::standard_table*)(*database())->get_table("deltas", get_dbuserid());
  vdbl::alltype<delta> *_at;
  vdbl::context _ctxdummy;
  bool ret = dt->retrieve(get_delta_id(i), dt->get_col_id("delta"), &_ctxdummy,
                          (vdbl::alltype_base*)_at);
  if(ret == false)
    throw "Database inconsistency: unkown delta";
  return _at->content();
}

inline const delta& delta_node::get_delta(unsigned int i) const
{
  vdbl::standard_table* dt =
              (vdbl::standard_table*)(*database())->
                                        get_table("deltas", get_dbuserid());
  vdbl::alltype<delta> *_at;
  vdbl::context _ctxdummy;
  bool ret = dt->retrieve(get_delta_id(i), dt->get_col_id("delta"), &_ctxdummy,
                          (vdbl::alltype_base*)_at);
  if(ret == false)
    throw "Database inconsistency: unkown delta";
  return _at->content();
}

inline delta work_node::get_delta(const delta_id& _id)
{
  bool error;
  const vdbl::row &_r(dtable->get_row(_id, error));
  if(error)
    throw "Database inconsistency: delta not found!";
  const vdbl::col &_c(_r.get_col(dtable->get_col_id("delta"), error));
  if(error)
    throw "Database inconsistency: delta table malformed!";
  delta _d;
  _c.get(_d);
  return _d;
}

inline const delta& work_node::get_delta(const delta_id& _id) const
{
  bool error;
  const vdbl::row *_r(dtable->get_row_ptr(_id));
  if(_r == NULL)
    throw "Database inconsistency: delta not found!";
  const vdbl::col &_c(_r->get_col(dtable->get_col_id("delta"), error));
  if(error)
    throw "Database inconsistency: delta table malformed!";
  const vdbl::typed_col<delta> *_cp =
                         (const vdbl::typed_col<delta>*)_c.get_ptr_to_val();
  return _cp->get_val();
}

inline void work_node::reset_node_ranges()
// reset all unused node ranges to [-I,I]
{
  unsigned int n = (**_m).number_of_nodes();

  for(unsigned int i = 0; i < n; ++i)
    if((**_m).node(i) == (**_m).ground())
      node_ranges.push_back(interval(-INFINITY,INFINITY));                
}

inline unsigned int work_node::n(unsigned int __type) const
{
  unsigned int h=0;
  std::vector<model::walker>::const_iterator __b, __e;

  if(!(__type & ~ex_any)) // no other bits are set
  {
    if(__type & ex_bound)
      h += n_bds;
    if(__type & ex_linear)
      h += n_lin;
    if(__type & ex_quadratic)
      h += n_quad;
    if(__type & ex_polynomial)
      h += n_poly;
    if(__type & ex_other)
      h += n_other;
  }   
  else // no cache, so count
  {
    __e = (**_m).constraints.end();
    for(__b = (**_m).constraints.begin(); __b != __e; ++__b)
      if((*__b)->is(__type))
        h++;
  }
  return h;
}

#endif // _SEARCH_NODE_H

---