search_node.hpp

Go to the documentation of this file.

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

// $Id: search_node.hpp 929 2009-11-12 17:19:12Z mihaly $
// 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_HPP_
#define _SEARCH_NODE_HPP_

#include <wnodectx.h>

namespace coco {

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

inline search_node::search_node(const search_node_id& _i, const vdbl::userid& _dui,
                                gptr<search_node>* _gm, gptr<vdbl::database>& _db,
                                search_node_relation __snr)
    : __global_model(_gm?new ptr<search_node>(**_gm):NULL),
      __dbase(new ptr<vdbl::database>(*_db)),
      _dbuser(_dui), _snr(__snr), _id(_i), _keep(), _rid(VDBL_MAXROWID)
  {}

inline search_node::search_node(const search_node& __sn)
    : __global_model(
        __sn.__global_model?new ptr<search_node>(**__sn.__global_model):NULL),
      __dbase(__sn.__dbase?new ptr<vdbl::database>(**__sn.__dbase):NULL),
      _dbuser(__sn._dbuser), _snr(__sn._snr), _id(__sn._id), _keep(__sn._keep),
      _rid(__sn._rid)
  {}

inline search_node::search_node(const search_node_id& _i, const vdbl::userid& _dui,
                                gptr<vdbl::database>& _db,
                                search_node_relation __snr)
    : __global_model(NULL), __dbase(new ptr<vdbl::database>(*_db)),
      _dbuser(_dui), _snr(__snr), _id(_i), _keep(), _rid(VDBL_MAXROWID)
  {}

inline search_node::~search_node()
{
  if(__dbase)
  {
    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());
    }
    delete __dbase;
  }
  if(__global_model) delete __global_model;
}

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

inline work_node::work_node(const work_node& __w)
        : _Base(__w),
          deltas(__w.deltas),
          parents_in_graph(__w.parents_in_graph),
          undeltas(__w.undeltas),
          dtable(__w.dtable),
          dtable_id(__w.dtable_id),
          gitable(__w.gitable),
          gitable_id(__w.gitable_id),
          wnc(new work_node_context(this)),
          __vdb(new vdbl::viewdbase(
                *this->database()->get_local_copy(),
                this->get_dbuserid(), *wnc,
                std::vector<std::pair<vdbl::tableid,vdbl::rowid> >(
                   this->get_annotations().begin(),
                   this->get_annotations().end()))),
          __vdbf(__w.__vdbf),
          node_ranges(__w.node_ranges),
          node_order(__w.node_order),
          infeasible(__w.infeasible),
          log_vol(__w.log_vol),
          gain_factor(__w.gain_factor),
          globalinfo(__w.globalinfo),
          _tnum(__w._tnum),
          proposed_splits(__w.proposed_splits),
          split_delta_ids(__w.split_delta_ids),
          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)
{
  set_deltanew_it(__w);
}

inline work_node::~work_node() { delete __vdb; delete wnc; }

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);
}

} // namespace coco

#include <api_delta.h>
#include <api_cert.h>

namespace coco {

inline search_node& search_node::operator=(const search_node& __w)
{
  if(this != &__w)
  {
    if(__global_model) delete __global_model;
    if(__w.__global_model)
      __global_model = new ptr<search_node>(**__w.__global_model);
    else
      __global_model = NULL;
    if(__dbase) delete __dbase;
    if(__w.__dbase)
      __dbase = new ptr<vdbl::database>(**__w.__dbase);
    else
      __dbase = NULL;
    _dbuser = __w._dbuser;
    _snr = __w._snr;
    _id = __w._id;
    _rid = __w._rid;
    _keep = __w._keep;
  }
  return *this;
}

inline delta_node& delta_node::operator=(const delta_node& __w)
{
  if(this != &__w)
  {
    ((_DBase*)this)->_DBase::operator=(*(_DBase*)&__w);
    di = __w.di;
  }
  return *this;
}

inline full_node& full_node::operator=(const full_node& __w)
{
  if(this != &__w)
  {
    if(_m) delete _m;
    ((_FBase*)this)->_FBase::operator=(*(_FBase*)&__w);
    if(__w._m)
      _m = new ptr<model>(**__w._m);
    else
      _m = NULL;
    _ann = __w._ann;
  }
  return *this;
}

inline work_node& work_node::operator=(const full_node& __f)
{
  if(this != &__f)
  {
    ((_Base*)this)->_Base::operator=(*(_Base*)&__f);
    deltas.clear();
    undeltas.clear();
    node_ranges.clear();
    node_order.clear();
    infeasible = false;
    gain_factor = 1.;
    _tnum = 0;
    proposed_splits.clear();
    n_bds = 0;
    n_lin = 0;
    n_quad = 0;
    n_poly = 0;
    n_other = 0;
    if(__vdb) delete __vdb;
    if(wnc) delete wnc;
    wnc = new work_node_context(this);
    __vdb = new vdbl::viewdbase(*this->database()->get_local_copy(),
          this->get_dbuserid(), *wnc,
          std::vector<std::pair<vdbl::tableid,vdbl::rowid> >(
             this->get_annotations().begin(),
             this->get_annotations().end()));
    init_all();
    set_rowid(__f.get_rowid());
  }
  return *this;
}

inline work_node& work_node::operator=(const work_node& __w)
{
  if(this != &__w)
  {
    ((_Base*)this)->_Base::operator=(*(_Base*)&__w);
    deltas = __w.deltas;
    parents_in_graph = __w.parents_in_graph;
    undeltas = __w.undeltas;
    dtable = __w.dtable;
    dtable_id = __w.dtable_id;
    gitable = __w.gitable;
    gitable_id = __w.gitable_id;
    node_ranges = __w.node_ranges;
    node_order = __w.node_order;
    infeasible = __w.infeasible;
    log_vol = __w.log_vol;
    gain_factor = __w.gain_factor;
    globalinfo = __w.globalinfo;
    _tnum = __w._tnum;
    proposed_splits = __w.proposed_splits;
    split_delta_ids = __w.split_delta_ids;
    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;
    set_deltanew_it(__w);
    if(__vdb) delete __vdb;
    if(wnc) delete wnc;
    wnc = new work_node_context(this);
    __vdb = new vdbl::viewdbase(*this->database()->get_local_copy(),
          this->get_dbuserid(), *wnc,
          std::vector<std::pair<vdbl::tableid,vdbl::rowid> >(
             this->get_annotations().begin(),
             this->get_annotations().end()));
    __vdbf = __w.__vdbf;
  }
  return *this;
}


inline work_node operator+(const work_node& _w, const delta_id& _i)
{
  work_node _tmp(_w);
  const delta& _d(const_cast<const work_node *>(&_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(const_cast<const work_node&>(_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 _TA> 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 _TA> 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;
}


work_node operator-(const work_node& _w, const delta_id& _d);

work_node& operator-=(work_node& _w, const delta_id& _d);


template <template <class _Tp, class _TA> 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 _TA> 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 api_exception(apiee_internal,
        "delta_node::get_delta: 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 api_exception(apiee_internal,
        "delta_node::get_delta: 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 api_exception(apiee_internal,
        "work_node::get_delta: Database inconsistency: unkown delta");
  const vdbl::col &_c(_r.get_col(dtable->get_col_id("delta"), error));
  if(error)
    throw api_exception(apiee_internal,
        "work_node::get_delta: 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 api_exception(apiee_internal,
        "work_node::get_delta: Database inconsistency: unkown delta");
  const vdbl::col &_c(_r->get_col(dtable->get_col_id("delta"), error));
  if(error)
    throw api_exception(apiee_internal,
        "work_node::get_delta: 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 certificate work_node::get_certificate(const delta_id& _id)
{
  bool error;
  const vdbl::row &_r(dtable->get_row(_id, error));
  if(error)
    throw api_exception(apiee_internal,
        "work_node::get_certificate: Database inconsistency: unkown delta");
  vdbl::colid _cci(dtable->get_col_id("certificate"));
  const vdbl::col &_c(_r.get_col(_cci, error));
  certificate _C;
  if(error)
  {
    const vdbl::col &_d(dtable->get_def(_cci, error));
    if(error)
      throw api_exception(apiee_internal,
          "work_node::get_certificate: Database inconsistency: delta table malformed!");
    else
      _d.get(_C);
  }
  else
  _c.get(_C);
  return _C;
}

inline const certificate& work_node::get_certificate(const delta_id& _id) const
{
  bool error;
  const vdbl::row *_r(dtable->get_row_ptr(_id));
  if(_r == NULL)
    throw api_exception(apiee_internal,
        "work_node::get_certificate: Database inconsistency: unkown delta");
  vdbl::colid _cci(dtable->get_col_id("certificate"));
  const vdbl::col &_c(_r->get_col(_cci, error));
  const vdbl::typed_col<certificate> *_cp;
  if(error)
  {
    const vdbl::col &_d(dtable->get_def(_cci, error));
    if(error)
      throw api_exception(apiee_internal,
        "work_node::get_certificate: Database inconsistency: delta table malformed!");
    else
      _cp = (const vdbl::typed_col<certificate>*)_d.get_ptr_to_val();
  }
  else
    _cp = (const vdbl::typed_col<certificate>*)_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(-COCO_INF,COCO_INF));                
}

inline unsigned int work_node::n(unsigned int __type) const
{
  unsigned int h=0;
  std::vector<expression_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;
}

inline void work_node::set_deltanew_it(const work_node& __w)
{
// Mihaly, 12.01.2004. Setting deltanew_it.
// we may have a lot more old deltas than new ones => start from the end
  deltanew_it = deltas.end();
  if ( ! deltas.empty() ) {   // otherwise nothing more to do
    std::list<delta_id>::const_iterator dit = __w.deltas.end();
    while ( (dit != __w.deltanew_it) && (dit != __w.deltas.begin()) )
    {
      dit--;
      deltanew_it--;
    }
    if ( (dit != __w.deltanew_it) && (dit == __w.deltas.begin()) )
    {
      throw api_exception(apiee_internal,
      "work_node::set_deltanew_it: Unable to find a properly set deltanew_it!");
    }
  }
// end Mihaly
}

template <class _TW, class _TV, class _VR, class _TP, class _TR, class _TI>
inline 
typename work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::_Self&
  work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::set(
                                const _Iterator& _c)
{
  for(__c_cur = _c; __c_cur != (*__cs).end(); ++__c_cur)
  {
    if((*__c_cur)->is(__tp))
      break;
  }
  return *this;
}

template <class _TW, class _TV, class _VR, class _TP, class _TR, class _TI>
inline 
typename work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::_Self&
  work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::operator++()
{
  if(__c_cur != (*__cs).end())
    ++__c_cur;
  for(; __c_cur != (*__cs).end(); ++__c_cur)
  {
    if((*__c_cur)->is(__tp))
      break;
  }
  return *this;
}

template <class _TW, class _TV, class _VR, class _TP, class _TR, class _TI>
inline 
typename work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::_Self
  work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::operator++(int)
{
  _Self __tmp = *this;
  ++__tmp;
  return __tmp;
}
  
template <class _TW, class _TV, class _VR, class _TP, class _TR, class _TI>
inline 
typename work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::_Self&
  work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::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;
}
  
template <class _TW, class _TV, class _VR, class _TP, class _TR, class _TI>
inline 
typename work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::_Self
  work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::operator--(int)
{
  _Self __tmp = *this;
  --__tmp;
  return __tmp;
}
  
template <class _TW, class _TV, class _VR, class _TP, class _TR, class _TI>
inline 
typename work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::_Self&
  work_node::constraint_iterator_base<_TW,_TV,_VR,_TP,_TR,_TI>::operator=(
                        const _Self& _c)
{
  if (this != & _c) {
    __cs    = _c.__cs;
    __c_cur = _c.__c_cur;
    __tp    = _c.__tp;
  }
  return *this;
}

} // namespace coco
#endif // _SEARCH_NODE_HPP_

---