---

search_graph.cc

Go to the documentation of this file.

// Search Graph 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.

// 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 <search_graph.h>

using namespace vgtl;
using namespace std;

#include "sum_deltas.h"

search_focus& search_graph::new_focus(const search_inspector& where)
{
  search_inspector where_copy = where;
  walker focus_to_add((node_type *) where_copy.node());

  if(find(focus.begin(), focus.end(), focus_to_add) != focus.end())
    throw search_graph_exception
      ("in search_graph :: new_focus : the inspected node is already focused");
  focus.push_front(focus_to_add);
  return focus.front();
}

void search_graph::destroy_focus(const search_focus& where)
{
  list<walker>::iterator i = find(focus.begin(), focus.end(), where);
  if(i == focus.end())
    throw search_graph_exception
        ("in search_graph :: destroy_focus (...) : the focus does not exist");
  focus.erase(i);
}

search_focus& search_graph::set_focus(search_focus& focus_to_replace,
                                      const search_inspector& where)
{
  list<walker>::iterator i =
      find(focus.begin(), focus.end(), focus_to_replace);
  if(i == focus.end())
    throw search_graph_exception
        ("in search_graph :: set_focus (...) : the focus does not exist");
  search_inspector where_copy = where;

  *i = walker((node_type *) where_copy.node());
  return *i;
}

search_inspector& search_graph::new_inspector(const search_inspector &
                                                        inspector_to_add)
{
  list<const_walker>::iterator i =
      find(inspector.begin(), inspector.end(), inspector_to_add);
  if(i != inspector.end())
    return *i;
  inspector.push_front(inspector_to_add);
  return inspector.front();
}

void search_graph::destroy_inspector(const search_inspector &
                                                inspector_to_destroy)
{
  list<const_walker>::iterator i =
      find(inspector.begin(), inspector.end(), inspector_to_destroy);
  if(i == inspector.end())
    throw search_graph_exception
      ("in search_graph :: destroy_inspector (...) : the inspector does not exist");
  inspector.erase(i);
}

work_node search_graph::extract(const search_inspector & where)
{
  list<const_walker>::iterator i =
      find(inspector.begin(), inspector.end(), where);
  if(i == inspector.end())
    throw search_graph_exception
        ("in search_graph :: extract (...) : the inspector does not exist");
  work_node *result = recursive_walk_up_if(where, sum_deltas(ptr_ground));
  work_node where_as_work_node(*result);
  where_as_work_node._snr = (*where)->parent_relation();
  delete result;

  return where_as_work_node;
}

work_node search_graph::extract(const search_focus & where)
{
  list<walker>::iterator i =
      find(focus.begin(), focus.end(), where);
  if(i == focus.end())
    throw search_graph_exception
        ("in search_graph :: extract (...) : the focus does not exist");
  work_node *result = recursive_walk_up_if(where, sum_deltas(ptr_ground));
  work_node where_as_work_node(*result);
  where_as_work_node._snr = (*where)->parent_relation();
  delete result;

  return where_as_work_node;
}

search_inspector& search_graph::insert(const search_focus &where,
                                       const search_node &what)
{
  search_focus protected_where(where);
  walker new_where =
      split(protected_where, protected_where.child_begin(), sky(),
            sky().parent_begin(), (search_node*) &what);

  const_walker new_where_as_const_walker((node_type*) new_where.node());

  inspector.push_front(new_where_as_const_walker);
  return inspector.front();
}

search_inspector& search_graph::replace(search_focus& where,
                                        const search_node &what)
{
  list<walker>::iterator i = find(focus.begin(), focus.end(), where);
  if(i == focus.end())
    throw search_graph_exception
        ("in search_graph :: replace (...) : the focus does not exist");
  *where = (search_node*) &what;
  inspector.push_front(const_walker((node_type*) where.node()));
  return inspector.front();
}

void search_graph::_internal_remove(search_focus& where)
{
  if((*where)->is_delta())
  {                             // removing a delta_node : 
    delta_node& where_as_delta = *(delta_node*) *where;   // cast to delta_node
    if(!where.is_leaf())
    {
      for(walker::children_iterator c = where.child_begin();
          c != where.child_end(); ++c)
        if((*(where >> c))->is_delta())
        {
          // cast to delta_node *
          delta_node*& c_as_delta = (delta_node*) *(where >> c);

          vector<delta_id> delta_where_plus_delta_c;
          for(unsigned int i = 0; i < where_as_delta.n_deltas(); ++i)
          {
            db_deltas_to_remove.push_front(where_as_delta.get_delta_id(i));
            delta_where_plus_delta_c.push_back(db_deltas_to_remove.front());
          }
          for(unsigned int i = 0; i < c_as_delta->n_deltas(); ++i)
          {
            db_deltas_to_remove.push_front(c_as_delta->get_delta_id(i));
            delta_where_plus_delta_c.push_back(db_deltas_to_remove.front());
          }
          gptr<vdbl::database>* _xdb = c_as_delta->database();
          delete c_as_delta;
          for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
              i != search_nodes_to_deallocate.end(); ++i)
            if(c_as_delta == *i)
            {
              search_nodes_to_deallocate.erase(i);
              break;
            }

          c_as_delta = new delta_node(get_node_id(), __dbuser,
                                      delta_where_plus_delta_c, ptr_ground,
                                      *_xdb);
          search_nodes_to_deallocate.push_front(c_as_delta);
        }
    }
  }
  else
  {                             // removing a full_node :
    full_node& where_as_full = *(full_node*) *where; // cast to full_node
    if(!where.is_leaf())
    {
      for(walker::children_iterator c = where.child_begin();
          c != where.child_end(); ++c)
        if((*(where >> c))->is_delta())
        {
          delta_node *&c_as_delta = (delta_node*) *(where >> c);  // cast to delta_node *
          work_node full_where_plus_delta_c(full_node_to_work_node
                                            (where_as_full, ptr_ground));
          for(unsigned int i = 0; i < c_as_delta->n_deltas(); ++i)
            full_where_plus_delta_c += c_as_delta->get_delta_id(i);
          delete *(where >> c);
          for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
              i != search_nodes_to_deallocate.end(); ++i)
            if(*(where >> c) == *i)
            {
              search_nodes_to_deallocate.erase(i);
              break;
            }

          *(where >> c) = new work_node(full_where_plus_delta_c);
          search_nodes_to_deallocate.push_front(*(where >> c));
        }
    }
  }
  // now take care for promoting the erase information properly
  // especially the information in _snr is important
  if((*where)->parent_relation() == snr_split)
  {
    if(where.n_parents() > 1)
      throw search_graph_exception
        ("in search_graph :: remove (...) : a split has more than one parent");
    else
    {
      walker::parents_iterator p = where.parent_begin();
      walker parent_of_where = where << p;
      unsigned int num_of_splits(0);
      walker first_split;
      for(walker::children_iterator c = parent_of_where.child_begin();
          c != parent_of_where.child_end(); ++c)
      {
        walker child_of_parent_of_where = parent_of_where >> c;
        if(child_of_parent_of_where != where &&
          (*child_of_parent_of_where)->parent_relation() == snr_split)
        {
          if(num_of_splits == 0)
            first_split = child_of_parent_of_where;
          num_of_splits++;
        }
      }
      if(num_of_splits == 1)  // a single split is a reduction
        (*first_split)->_snr = snr_reduction;
    }
  }

  delete *where;
  for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
      i != search_nodes_to_deallocate.end(); ++i)
    if(*where == *i)
    {
      search_nodes_to_deallocate.erase(i);
      break;
    }

  erase(where);
  return;
}

void search_graph::remove(search_focus& where)
{
  list<walker>::iterator flw = find(focus.begin(), focus.end(), where);
  if(flw == focus.end())
    throw search_graph_exception
        ("in search_graph :: remove (...) : the focus does not exist");
  if(where.n_parents() >= 2 && (*where)->parent_relation() != snr_glue)
    throw search_graph_exception
        ("in search_graph :: remove (...) : search_node has several ancestors");
  _internal_remove(where);
}

search_focus& search_graph::promote(search_focus& where)
{
  list<walker>::iterator i = find(focus.begin(), focus.end(), where);
  if(i == focus.end())
    throw search_graph_exception
        ("in search_graph :: promote (...) : the focus does not exist");
  if(where.n_parents() >= 2)
    throw search_graph_exception
        ("in search_graph :: promote (...) : search_node has several ancestors");
  walker p = where << where.parent_begin();

  if((*where)->is_delta())
  {                             // promoting a delta_node :
    delta_node *where_as_delta = (delta_node*) *where;  // cast to delta_node *

    if((*p)->is_delta())
    {
      delta_node* p_as_delta = (delta_node*) *p;

      vector<delta_id> delta_where_plus_delta_p;
      for(unsigned int i = 0; i < where_as_delta->n_deltas(); ++i)
      {
        db_deltas_to_remove.push_front(where_as_delta->get_delta_id(i));
        delta_where_plus_delta_p.push_back(db_deltas_to_remove.front());
      }
      for(unsigned int i = 0; i < p_as_delta->n_deltas(); ++i)
      {
        db_deltas_to_remove.push_front(p_as_delta->get_delta_id(i));
        delta_where_plus_delta_p.push_back(db_deltas_to_remove.front());
      }
      gptr<vdbl::database>* _xdb = p_as_delta->database();
      delete *p;
      for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
          i != search_nodes_to_deallocate.end(); ++i)
        if(*p == *i)
        {
          search_nodes_to_deallocate.erase(i);
          break;
        }

      *p = new delta_node(get_node_id(), __dbuser, delta_where_plus_delta_p,
                          ptr_ground, *_xdb);
    }
    else
    {
      full_node *p_as_full = (full_node*) *p;            // cast to full_node
      work_node full_p_plus_delta_where(full_node_to_work_node
                                                (*p_as_full, ptr_ground));

      for(unsigned int i = 0; i < where_as_delta->n_deltas(); ++i)
        full_p_plus_delta_where += where_as_delta->get_delta_id(i);
      delete *p;
      for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
          i != search_nodes_to_deallocate.end(); ++i)
        if(*p == *i)
        {
          search_nodes_to_deallocate.erase(i);
          break;
        }

      *p = new work_node(full_p_plus_delta_where);
    }
    search_nodes_to_deallocate.push_front(*p);
  }
  else
  {                             // promoting a full_node :
    delete *p;
    for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
        i != search_nodes_to_deallocate.end(); ++i)
      if(*p == *i)
      {
        search_nodes_to_deallocate.erase(i);
        break;
      }

    *p = *where;
  }
  *i = p;
  delete *where;
  for(list<search_node*>::iterator i=search_nodes_to_deallocate.begin();
      i != search_nodes_to_deallocate.end(); ++i)
    if(*where == *i)
    {
      search_nodes_to_deallocate.erase(i);
      break;
    }

  erase(where);
  return *i;
}

void search_graph::remove_upwards(search_focus& where, bool relaxation_kills)
{
  list<walker>::iterator flw = find(focus.begin(), focus.end(), where);
  if(flw == focus.end())
    throw search_graph_exception
        ("in search_graph :: remove_upwards (...) : the focus does not exist");
  if(where.n_parents() >= 2 && (*where)->parent_relation() != snr_glue)
    throw search_graph_exception
        ("in search_graph :: remove_upwards (...) : search_node has several ancestors");

  list<walker> to_be_erased;
  to_be_erased.push_front(*flw);

  for(flw = to_be_erased.begin(); flw != to_be_erased.end(); ++flw)
  {
    switch((**flw)->parent_relation())
    {
      case snr_root:
        // this cleans the whole search graph, so no need to do anything
        break;
      case snr_split:
        // removing splits does not traverse upwards
        break;
      case snr_relaxation:
        if(!relaxation_kills)
          break;
        // no break intentionally
      case snr_reduction:
      case snr_glue:
        // all parents have to vanish, as well
        for(walker::parents_iterator p = (*flw).parent_begin();
            p != (*flw).parent_end(); ++p)
          to_be_erased.push_back((*flw) << p);
        break;
      case snr_worknode:
      case snr_virtual:
        throw search_graph_exception
          ("in search_graph :: remove_upwards (...) : search_node is unremovable!");
        break;
      default:
        throw search_graph_exception
          ("in search_graph :: remove_upwards (...) : search_node has unknown parent relation!");
        break;
    }
    _internal_remove(*flw);
  }
}

---