dbcompare.hpp

Go to the documentation of this file.

// Database comparison and filter methods -*- C++ -*-

// $Id: dbcompare.hpp 531 2008-04-03 10:22:50Z schilly $
// Copyright (C) 2003 Hermann Schichl
//
// 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 _DBCOMPARE_HPP_
#define _DBCOMPARE_HPP_

#include <vector>
#include <utility>
#include <search_node.h>

namespace coco {

bool eval(const vdbl::rowid& rid, const std::string& colname,
          dbc_method tp, vdbl::view* iv, const basic_alltype& cmpval);

template <typename _AT> 
void filter_from_view(std::vector<std::pair<vdbl::rowid,_AT> >& riv,
    vdbl::view* iv, const std::map<int,std::triple<std::string,
        dbc_method, basic_alltype> >& cols,
    const std::vector<std::vector<int> >& expr)
{
  std::map<int,bool> retr;
  std::map<int,bool>::iterator retr_it;
  size_t i, j, k;

  if(expr.empty()) return;

  if(!iv)
  {
    riv.clear();
    return;
  }

  for(i = 0; i < riv.size(); )
  {
    bool rmv(true);
    retr.clear();

    for(j = 0; j < expr.size(); ++j)
    {
      bool and_res(true);
      for(k = 0; k < expr[j].size(); ++k)
      {
        bool res;
        int cmpe(std::abs(expr[j][k]));
        bool nege(expr[j][k] < 0);
        std::map<int,std::triple<std::string, dbc_method, basic_alltype> >::
                const_iterator cols_it;

        retr_it = retr.find(cmpe);
        if(retr_it != retr.end())
          res = retr_it->second;
        else
        {
          cols_it = cols.find(cmpe);
          if(cols_it == cols.end())
          {
            throw api_exception(apiee_other,
                std::string("Error in filter_from_view: wrong column index ")+ 
                 convert_to_str(cmpe) + " in expression!");
          }
          else
          {
            const std::triple<std::string, dbc_method, basic_alltype>& 
                  colsrf(cols_it->second);

            res = eval(riv[i].first, colsrf.first, colsrf.second, iv,
                       colsrf.third);
            retr[cmpe] = res;
          }
        }
        res = nege ? !res : res;
        if(!res)
        {
          and_res = false;
          break;
        }
      }
      if(and_res)
      {
        rmv = false;
        break;
      }
    }

    if(rmv)
      riv.erase(riv.begin()+i);
    else
      ++i;
  }
}

template <typename _TR>
_TR dbccmps_abs(const _TR& x)
{
  return x < _TR() ? -x : x;
}

template <typename _TR>
class dbccmps_gt
{
private:
  long double abs, rel;
public:
  dbccmps_gt(double _rel = 1.0, double _abs = 0.0)
    : abs((long double)_abs), rel((long double)_rel) {}
  ~dbccmps_gt() {}

  bool operator()(const _TR& x, const _TR& y)
     { long double relx((long double)(dbccmps_abs(x)+dbccmps_abs(y)));
       return x > y+rel*relx+abs; }
};

template <typename _TR>
class dbccmps_absgt
{
private:
  long double abs, rel;
public:
  dbccmps_absgt(double _rel = 1.0, double _abs = 0.0)
    : abs((long double)_abs), rel((long double)_rel) {}
  ~dbccmps_absgt() {}

  bool operator()(const _TR& x, const _TR& y)
     { _TR absx(dbccmps_abs(x)), absy(dbccmps_abs(y));
       long double relx((long double)(absx+absy));
       return absx > absy+rel*relx+abs; }
};

template <typename _TR>
class dbccmps_lt
{
private:
  long double abs, rel;
public:
  dbccmps_lt(double _rel = 1.0, double _abs = 0.0)
    : abs((long double)_abs), rel((long double)_rel) {}
  ~dbccmps_lt() {}

  bool operator()(const _TR& x, const _TR& y)
     { long double relx((long double)(dbccmps_abs(x)+dbccmps_abs(y)));
       return x < y-rel*relx-abs; }
};

template <typename _TR>
class dbccmps_abslt
{
private:
  long double abs, rel;
public:
  dbccmps_abslt(double _rel = 1.0, double _abs = 0.0)
    : abs((long double)_abs), rel((long double)_rel) {}
  ~dbccmps_abslt() {}

  bool operator()(const _TR& x, const _TR& y)
     { _TR absx(dbccmps_abs(x)), absy(dbccmps_abs(y));
       long double relx((long double)(absx+absy));
       return absx < absy-rel*relx-abs; }
};

template <typename _TR>
class dbccmps_true
{
private:
  long double abs, rel;
public:
  dbccmps_true(double _rel = 1.0, double _abs = 0.0)
    : abs((long double)_abs), rel((long double)_rel) {}
  ~dbccmps_true() {}

  bool operator()(const _TR& x, const _TR& y)
     { long double absx((long double)dbccmps_abs(x));
       long double absy((long double)dbccmps_abs(y));
       long double zr(rel*(absx+absy)+abs);
       return absx > zr && absy <= zr; }
};

template <typename _TR>
class dbccmps_false
{
private:
  long double abs, rel;
public:
  dbccmps_false(double _rel = 1.0, double _abs = 0.0)
    : abs((long double)_abs), rel((long double)_rel) {}
  ~dbccmps_false() {}

  bool operator()(const _TR& x, const _TR& y)
     { long double absx((long double)dbccmps_abs(x));
       long double absy((long double)dbccmps_abs(y));
       long double zr(rel*(absx+absy)+abs);
       return absx <= zr && absy > zr; }
};

template <typename _TR>
struct dbccmp_true
{
  dbccmp_true() {}
  ~dbccmp_true() {}
  bool operator()(const _TR& x, const _TR& y)
     { return x != _TR() && y == _TR(); }
};

template <typename _TR>
struct dbccmp_false
{
  dbccmp_false() {}
  ~dbccmp_false() {}
  bool operator()(const _TR& x, const _TR& y)
     { return x == _TR() && y != _TR(); }
};

template <typename _TR, typename _AT>
typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator
  filter_s(typename std::vector<std::pair<vdbl::rowid,_AT> >& rid,
     typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator rid_b,
     const std::string& colname, dbc_method tp, vdbl::view* iv,
     unsigned int n, _TR, double rel, double abs)
{
  if(n == 0)
  {
    rid.clear();
    return rid.end();
  }
  if(rid.size() <= n)
    return rid.end();

  typename std::vector<_TR> cmpval;
  _TR _help;

  for(unsigned int i = rid_b-rid.begin(); i < rid.size();)
  {
    if(iv->get(rid[i].first, colname, _help))
    {
      ++i;
      cmpval.push_back(_help);
    }
    else
      rid.erase(rid.begin()+i);
  }
  
  if(rid.size() <= n)
    return rid.end();

  std::pair<typename std::vector<_TR>::iterator,
            typename std::vector<_TR>::iterator> cmpval_it;

  switch(tp)
  {
    case dbc_sort_max:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid.begin(), rid.end(),
          dbccmps_gt<_TR>(rel,abs));
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          dbccmps_gt<_TR>(rel,abs));
      break;
    case dbc_sort_absmax:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid.begin(), rid.end(),
          dbccmps_absgt<_TR>(rel,abs));
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          dbccmps_absgt<_TR>(rel,abs));
      break;
    case dbc_sort_min:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid.begin(), rid.end(),
          dbccmps_lt<_TR>(rel,abs));
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          dbccmps_lt<_TR>(rel,abs));
      break;
    case dbc_sort_absmin:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid.begin(), rid.end(),
          dbccmps_abslt<_TR>(rel,abs));
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          dbccmps_abslt<_TR>(rel,abs));
      break;
    case dbc_sort_true:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid.begin(), rid.end(),
          dbccmps_true<_TR>(rel,abs));
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          dbccmps_true<_TR>(rel,abs));
      break;
    case dbc_sort_false:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid.begin(), rid.end(),
          dbccmps_false<_TR>(rel,abs));
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1], 
          dbccmps_false<_TR>(rel,abs));
      break;
    default:
      throw api_exception(apiee_other, "Error in filter_u: tp is wrong!");
      break;
  }

  if(cmpval_it.second != cmpval.end())
  {
    n = cmpval_it.second - cmpval.begin();
    rid.erase(rid.begin()+n, rid.end());
  }
  n = cmpval_it.first - cmpval.begin();
  return rid.begin()+n;
}

template <typename _TR, typename _AT>
typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator
  filter_u(typename std::vector<std::pair<vdbl::rowid,_AT> >& rid,
     typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator rid_b,
     const std::string& colname, dbc_method tp, vdbl::view* iv,
     unsigned int n, _TR)
{
  if(n == 0)
  {
    rid.clear();
    return rid.end();
  }
  if(rid.size() <= n)
    return rid.end();

  typename std::vector<_TR> cmpval;
  _TR _help;

  for(unsigned int i = rid_b-rid.begin(); i < rid.size();)
  {
    if(iv->get(rid[i].first, colname, _help))
    {
      ++i;
      cmpval.push_back(_help);
    }
    else
      rid.erase(rid.begin()+i);
  }
  
  if(rid.size() <= n)
    return rid.end();

  std::pair<typename std::vector<_TR>::iterator,
            typename std::vector<_TR>::iterator> cmpval_it;

  switch(tp)
  {
    case dbc_sort_max:
    case dbc_sort_absmax:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid_b, rid.end(),
          std::greater<_TR>());
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          std::greater<_TR>());
      break;
    case dbc_sort_min:
    case dbc_sort_absmin:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid_b, rid.end(),
          std::less<_TR>());
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          std::less<_TR>());
      break;
    case dbc_sort_true:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid_b, rid.end(),
          dbccmp_true<_TR>());
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1],
          dbccmp_true<_TR>());
      break;
    case dbc_sort_false:
      std::pair_sort(cmpval.begin(), cmpval.end(), rid_b, rid.end(),
          dbccmp_false<_TR>());
      cmpval_it = std::equal_range(cmpval.begin(), cmpval.end(), cmpval[n-1], 
          dbccmp_false<_TR>());
      break;
    default:
      throw api_exception(apiee_other, "Error in filter_u: tp is wrong!");
      break;
  }

  if(cmpval_it.second != cmpval.end())
  {
    n = cmpval_it.second - cmpval.begin();
    rid.erase(rid_b+n, rid.end());
  }
  n = cmpval_it.first - cmpval.begin();
  return rid_b+n;
}

template <typename _AT>
typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator
  filter(typename std::vector<std::pair<vdbl::rowid,_AT> >& rid,
     typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator rid_b,
     const std::string& colname, dbc_method tp, vdbl::view* iv,
     unsigned int n, std::pair<double, double> rel_abs)
{
  typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator ret;
  const char *tyn = iv->get_coltype(colname).name();

  if(!strcmp(typeid(double).name(), tyn))
    ret = filter_s(rid, rid_b, colname, tp, iv, n, 0.0,
        rel_abs.first, rel_abs.second);
  else if(!strcmp(typeid(long int).name(), tyn))
    ret = filter_s(rid, rid_b, colname, tp, iv, n, 0L,
        rel_abs.first, rel_abs.second);
  else if(!strcmp(typeid(unsigned long int).name(), tyn))
    ret = filter_u(rid, rid_b, colname, tp, iv, n, 0UL);
  else if(!strcmp(typeid(search_node_id).name(), tyn))
    ret = filter_u(rid, rid_b, colname, tp, iv, n,
        search_node_id());
  else if(!strcmp(typeid(bool).name(), tyn))
    ret = filter_u(rid, rid_b, colname, tp, iv, n, true);
  else if(!strcmp(typeid(int).name(), tyn))
    ret = filter_s(rid, rid_b, colname, tp, iv, n, 0,
        rel_abs.first, rel_abs.second);
  else if(!strcmp(typeid(unsigned int).name(), tyn))
    ret = filter_u(rid, rid_b, colname, tp, iv, n, 0U);
  else if(!strcmp(typeid(std::string).name(), tyn))
    ret = filter_u(rid, rid_b, colname, tp, iv, n,
        std::string());
  else
    throw api_exception(apiee_other,
        std::string("Error in filter: don't know how to handle type ")+
        iv->get_coltype(colname).name() + "!");

  return ret;
}

template <typename _AT> 
void list_from_view(typename std::vector<std::pair<vdbl::rowid,_AT> >& riv,
    vdbl::view* iv, const std::map<int,std::triple<std::string,
        dbc_method, basic_alltype > >& cols, const std::vector<int>& sort,
        unsigned int n=1)
{
  if(sort.empty()) return;

  if(!iv)
    return;
  
  size_t i;
  typename std::vector<std::pair<vdbl::rowid,_AT> >::iterator riv_b(riv.begin());
  std::map<int, std::triple<std::string, dbc_method, basic_alltype> >
    ::const_iterator cols_it;

  for(i = 0; i < sort.size() && riv.size() > n; ++i)
  {
    cols_it = cols.find(sort[i]);
    if(cols_it != cols.end())
    {
      std::pair<double,double> relabs;
      if((*cols_it).second.third.contents_type() == ALLTYPE_EMPTY)
        relabs = std::make_pair(0., 0.);
      else if((*cols_it).second.third.contents_type() == ALLTYPE_DOUBLE)
        relabs = std::make_pair(0., (*cols_it).second.third.nd());
      else if((*cols_it).second.third.contents_type() == ALLTYPE_ALLOCED_D)
      {
        if((*cols_it).second.third.d().size() == 1)
          relabs = std::make_pair(0., (*cols_it).second.third.d()[0]);
        else if((*cols_it).second.third.d().size() == 2)
          relabs = std::make_pair((*cols_it).second.third.d()[1],
                                  (*cols_it).second.third.d()[0]);
        else
          throw api_exception(apiee_other,
            std::string("Error in list_from_view: vals contents vector has ")+
            "invalid length for sorting!");
      }
      else
        throw api_exception(apiee_other,
          std::string("Error in list_from_view: vals contents vector has ")+
                      "invalid type for sorting!");
      riv_b = filter(riv, riv_b, (*cols_it).second.first, (*cols_it).second.second,
                     iv, n-(riv_b-riv.begin()), relabs);
    }
  }
}

} // namespace coco

#endif /* _DBCOMPARE_HPP_ */

---