scheduleCombinationBasic_tpl.h

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2005 by Pierre-Henri WUILLEMIN et Christophe GONZALES   *
 *   {prenom.nom}_at_lip6.fr                                               *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#ifndef DOXYGEN_SHOULD_SKIP_THIS

#  include <agrum/agrum.h>
#  include <limits>

#  include <agrum/graphicalModels/inference/scheduleCombinationBasic.h>

namespace gum {

  template < typename GUM_SCALAR >
  ScheduleCombinationBasic< GUM_SCALAR >::ScheduleCombinationBasic(
     MultiDimImplementation< GUM_SCALAR >* (*combine)(
        const MultiDimImplementation< GUM_SCALAR >&,
        const MultiDimImplementation< GUM_SCALAR >&)) :
      ScheduleCombination< GUM_SCALAR >(),
      _combine(combine) {
    GUM_CONSTRUCTOR(ScheduleCombinationBasic);
  }

  template < typename GUM_SCALAR >
  ScheduleCombinationBasic< GUM_SCALAR >::ScheduleCombinationBasic(
     const ScheduleCombinationBasic< GUM_SCALAR >& from) :
      ScheduleCombination< GUM_SCALAR >(from),
      _combine(from._combine) {
    GUM_CONS_CPY(ScheduleCombinationBasic);
  }

  template < typename GUM_SCALAR >
  ScheduleCombinationBasic< GUM_SCALAR >::~ScheduleCombinationBasic() {
    GUM_DESTRUCTOR(ScheduleCombinationBasic);
  }

  template < typename GUM_SCALAR >
  ScheduleCombinationBasic< GUM_SCALAR >*
     ScheduleCombinationBasic< GUM_SCALAR >::newFactory() const {
    return new ScheduleCombinationBasic< GUM_SCALAR >(*this);
  }

  template < typename GUM_SCALAR >
  void ScheduleCombinationBasic< GUM_SCALAR >::setCombineFunction(
     MultiDimImplementation< GUM_SCALAR >* (*combine)(
        const MultiDimImplementation< GUM_SCALAR >&,
        const MultiDimImplementation< GUM_SCALAR >&)) {
    _combine = combine;
  }

  template < typename GUM_SCALAR >
  MultiDimImplementation< GUM_SCALAR >* (
     *ScheduleCombinationBasic< GUM_SCALAR >::combineFunction())(
     const MultiDimImplementation< GUM_SCALAR >&,
     const MultiDimImplementation< GUM_SCALAR >&) {
    return _combine;
  }

  template < typename GUM_SCALAR >
  Size ScheduleCombinationBasic< GUM_SCALAR >::_combinedSize(
     const Sequence< const DiscreteVariable* >& seq1,
     const Sequence< const DiscreteVariable* >& seq2) const {
    if (seq1.empty() && seq2.empty()) return 0;

    Size size = 1;

    for (const auto var : seq1)
      size *= var->domainSize();

    for (const auto var : seq2)
      if (!seq1.exists(var)) size *= var->domainSize();

    return size;
  }

  // adds operations to an already created schedule
  template < typename GUM_SCALAR >
  ScheduleMultiDim< GUM_SCALAR > ScheduleCombinationBasic< GUM_SCALAR >::combine(
     const Set< const ScheduleMultiDim< GUM_SCALAR >* >& set,
     Schedule< GUM_SCALAR >&                             schedule) {
    // check if the set passed in argument is empty. If so, raise an exception
    if (set.size() < 2) {
      GUM_ERROR(InvalidArgumentsNumber,
                "the set passed to a ScheduleCombinationBasic"
                " should at least contain two elements");
    }

    // create a vector with all the tables to combine
    std::vector< const ScheduleMultiDim< GUM_SCALAR >* > tables(set.size());

    {
      Idx i = 0;

      for (const auto sched : set) {
        tables[i] = sched;
        i += 1;
      }
    }

    // create a vector indicating wether the elements in tables are freshly
    // created ScheduleMultiDim<GUM_SCALAR>* due to the combination of some
    // ScheduleMultiDims or if they were added by the user into the
    // combination container
    std::vector< bool > is_t_new(tables.size(), false);

    // for each pair of tables (i,j), compute the size of the table that would
    // result from the addition of tables i and j and store the result into a
    // priorityQueue
    std::pair< Idx, Idx > pair;

    PriorityQueue< std::pair< Idx, Idx >, Size > queue;

    for (Idx i = 0; i < tables.size(); ++i) {
      pair.first = i;
      const Sequence< const DiscreteVariable* >& seq1 =
         tables[i]->variablesSequence();

      for (Idx j = i + 1; j < tables.size(); ++j) {
        pair.second = j;
        queue.insert(pair, _combinedSize(seq1, tables[j]->variablesSequence()));
      }
    }

    // now parse the priority queue: the top element (i,j) gives the combination
    // to perform. When the result R has been computed, substitute i by R,
    // remove
    // table j and recompute all the priorities of all the pairs (R,k) still
    // available.
    // Timer timer;
    for (Idx k = 1; k < tables.size(); ++k) {
      // get the combination to perform and do it
      pair = queue.pop();
      Idx ti = pair.first;
      Idx tj = pair.second;

      // create the combination that will be performed later on and put it into
      // the schedule
      ScheduleCombine< GUM_SCALAR > comb(*(tables[ti]), *(tables[tj]), _combine);
      NodeId                        comb_id = schedule.insert(comb);

      // substitute tables[pair.first] by the result and delete the temporary
      // multidim tables

      if (tables[ti] && is_t_new[ti]) {
        ScheduleDeleteMultiDim< GUM_SCALAR > del(*(tables[ti]));
        NodeId                               del_id = schedule.insert(del);
        const NodeSet& set_i = schedule.operationsInvolving(*(tables[ti]));
        schedule.forceAfter(del_id, set_i);
      }

      if (tables[tj] && is_t_new[tj]) {
        ScheduleDeleteMultiDim< GUM_SCALAR > del(*(tables[tj]));
        NodeId                               del_id = schedule.insert(del);
        const NodeSet& set_j = schedule.operationsInvolving(*(tables[tj]));
        schedule.forceAfter(del_id, set_j);
      }

      tables[ti] = &(static_cast< const ScheduleCombine< GUM_SCALAR >& >

                     (schedule.operation(comb_id))
                        .result());
      is_t_new[ti] = true;
      tables[tj] = 0;

      // remove all the pairs involving tj in the priority queue

      for (Idx ind = 0; ind < tj; ++ind) {
        if (tables[ind]) {
          pair.first = ind;
          queue.erase(pair);
        }
      }

      pair.first = tj;

      for (Idx ind = tj + 1; ind < tables.size(); ++ind) {
        if (tables[ind]) {
          pair.second = ind;
          queue.erase(pair);
        }
      }

      // update the "combinated" size of all the pairs involving "result"
      {
        const Sequence< const DiscreteVariable* >& seq1 =
           tables[ti]->variablesSequence();
        pair.second = ti;
        Size newsize;

        for (Idx ind = 0; ind < ti; ++ind) {
          if (tables[ind]) {
            pair.first = ind;
            newsize = _combinedSize(seq1, tables[ind]->variablesSequence());
            queue.setPriority(pair, newsize);
          }
        }

        pair.first = ti;

        for (Idx ind = ti + 1; ind < tables.size(); ++ind) {
          if (tables[ind]) {
            pair.second = ind;
            newsize = _combinedSize(seq1, tables[ind]->variablesSequence());
            queue.setPriority(pair, newsize);
          }
        }
      }
    }

    // here, there remains only one nonzero pointer in tables:
    // the result of our combination
    Idx k = 0;

    while (!tables[k])
      ++k;

    return *(tables[k]);
  }

  // adds operations to an already created schedule
  template < typename GUM_SCALAR >
  INLINE ScheduleMultiDim< GUM_SCALAR >
         ScheduleCombinationBasic< GUM_SCALAR >::combine(
        const Set< const MultiDimImplementation< GUM_SCALAR >* >& set,
        Schedule< GUM_SCALAR >&                                   schedule) {
    return ScheduleCombination< GUM_SCALAR >::combine(set, schedule);
  }

  // adds operations to an already created schedule
  template < typename GUM_SCALAR >
  template < template < typename > class TABLE >
  INLINE ScheduleMultiDim< GUM_SCALAR >
         ScheduleCombinationBasic< GUM_SCALAR >::combine(
        const Set< const TABLE< GUM_SCALAR >* >& set,
        Schedule< GUM_SCALAR >&                  schedule) {
    return ScheduleCombination< GUM_SCALAR >::combine(set, schedule);
  }

  template < typename GUM_SCALAR >
  float ScheduleCombinationBasic< GUM_SCALAR >::nbOperations(
     const Set< const ScheduleMultiDim< GUM_SCALAR >* >& set,
     const Schedule< GUM_SCALAR >&                       schedule) {
    // check if the set passed in argument is empty.
    if (set.size() < 2) return 0.0f;

    float result = 0.0f;

    // create a vector with all the tables to combine
    std::vector< const Sequence< const DiscreteVariable* >* > tables(set.size());

    {
      Idx i = 0;

      for (const auto sched : set) {
        tables[i] = &(sched->variablesSequence());
        i += 1;
      }
    }

    // create a vector indicating wether the elements in tables are freshly
    // created Sequence<const DiscreteVariable *>* due to the combination of
    // some
    // ScheduleMultiDims or if they were added by the user into the combination
    // container
    std::vector< bool > is_t_new(tables.size(), false);

    // for each pair of tables (i,j), compute the size of the table that would
    // result from the addition of tables i and j and store the result into a
    // priorityQueue
    std::pair< Idx, Idx >                        pair;
    PriorityQueue< std::pair< Idx, Idx >, Size > queue;

    for (Idx i = 0; i < tables.size(); ++i) {
      pair.first = i;

      for (Idx j = i + 1; j < tables.size(); ++j) {
        pair.second = j;
        queue.insert(pair, _combinedSize(*(tables[i]), *(tables[j])));
      }
    }

    // now parse the priority queue: the top element (i,j) gives the combination
    // to perform. When the result R has been computed, substitute i by R,
    // remove
    // table j and recompute all the priorities of all the pairs (R,k) still
    // available.
    for (Idx k = 1; k < tables.size(); ++k) {
      // get the combination to perform and do it
      pair = queue.pop();
      Idx ti = pair.first;
      Idx tj = pair.second;

      // compute the result
      Sequence< const DiscreteVariable* >* new_seq =
         new Sequence< const DiscreteVariable* >;
      const Sequence< const DiscreteVariable* >& seq1 = *(tables[ti]);
      const Sequence< const DiscreteVariable* >& seq2 = *(tables[tj]);

      Size new_size = 1;

      for (const auto var : seq1) {
        new_size *= var->domainSize();
        new_seq->insert(var);
      }

      for (const auto var : seq2)
        if (!seq1.exists(var)) {
          new_size *= var->domainSize();
          new_seq->insert(var);
        }

      result += new_size;

      // substitute tables[pair.first] by the result

      if (tables[ti] && is_t_new[ti]) delete tables[ti];

      if (tables[tj] && is_t_new[tj]) delete tables[tj];

      tables[ti] = new_seq;

      is_t_new[ti] = true;

      tables[tj] = 0;

      // remove all the pairs involving tj in the priority queue
      for (Idx ind = 0; ind < tj; ++ind) {
        if (tables[ind]) {
          pair.first = ind;
          queue.erase(pair);
        }
      }

      pair.first = tj;

      for (Idx ind = tj + 1; ind < tables.size(); ++ind) {
        if (tables[ind]) {
          pair.second = ind;
          queue.erase(pair);
        }
      }

      // update the "combined" size of all the pairs involving "new_seq"
      {
        pair.second = ti;
        Size newsize;

        for (Idx ind = 0; ind < ti; ++ind) {
          if (tables[ind]) {
            pair.first = ind;
            newsize = _combinedSize(*new_seq, *(tables[ind]));
            queue.setPriority(pair, newsize);
          }
        }

        pair.first = ti;

        for (Idx ind = ti + 1; ind < tables.size(); ++ind) {
          if (tables[ind]) {
            pair.second = ind;
            newsize = _combinedSize(*new_seq, *(tables[ind]));
            queue.setPriority(pair, newsize);
          }
        }
      }
    }

    // here, there remains only one nonzero pointer in tables:
    // the result of our combination
    Idx k = 0;

    while (!tables[k])
      ++k;

    delete tables[k];

    return result;
  }

  template < typename GUM_SCALAR >
  INLINE float ScheduleCombinationBasic< GUM_SCALAR >::nbOperations(
     const Set< const MultiDimImplementation< GUM_SCALAR >* >& set,
     const Schedule< GUM_SCALAR >&                             schedule) {
    return ScheduleCombination< GUM_SCALAR >::nbOperations(set, schedule);
  }

  template < typename GUM_SCALAR >
  template < template < typename > class TABLE >
  INLINE float ScheduleCombinationBasic< GUM_SCALAR >::nbOperations(
     const Set< const TABLE< GUM_SCALAR >* >& set,
     const Schedule< GUM_SCALAR >&            schedule) {
    return ScheduleCombination< GUM_SCALAR >::nbOperations(set, schedule);
  }

  template < typename GUM_SCALAR >
  std::pair< long, long > ScheduleCombinationBasic< GUM_SCALAR >::memoryUsage(
     const Set< const ScheduleMultiDim< GUM_SCALAR >* >& set,
     const Schedule< GUM_SCALAR >&                       schedule) {
    // check if the set passed in argument is empty.
    if (set.size() < 2) return std::pair< long, long >(0, 0);

    long max_memory = 0;
    long current_memory = 0;

    // create a vector with all the tables to combine
    std::vector< const Sequence< const DiscreteVariable* >* > tables(set.size());
    std::vector< Size > table_size(set.size());

    {
      Idx i = 0;

      for (const auto tab : set) {
        tables[i] = &(tab->variablesSequence());
        Size size = 0;

        for (const auto var : tab->variablesSequence())
          size *= var->domainSize();

        table_size[i] = size;
        i += 1;
      }
    }

    // create a vector indicating wether the elements in tables are freshly
    // created Sequence<const DiscreteVariable *>* due to the combination of
    // some
    // ScheduleMultiDims or if they were added by the user into the combination
    // container
    std::vector< bool > is_t_new(tables.size(), false);

    // for each pair of tables (i,j), compute the size of the table that would
    // result from the addition of tables i and j and store the result into a
    // priorityQueue
    std::pair< Idx, Idx > pair;

    PriorityQueue< std::pair< Idx, Idx >, Size > queue;

    for (Idx i = 0; i < tables.size(); ++i) {
      pair.first = i;

      for (Idx j = i + 1; j < tables.size(); ++j) {
        pair.second = j;
        queue.insert(pair, _combinedSize(*(tables[i]), *(tables[j])));
      }
    }

    // now parse the priority queue: the top element (i,j) gives the combination
    // to perform. When the result R has been computed, substitute i by R,
    // remove
    // table j and recompute all the priorities of all the pairs (R,k) still
    // available.
    for (Idx k = 1; k < tables.size(); ++k) {
      // get the combination to perform and do it
      pair = queue.pop();
      Idx ti = pair.first;
      Idx tj = pair.second;

      // compute the result
      Sequence< const DiscreteVariable* >* new_seq =
         new Sequence< const DiscreteVariable* >;
      const Sequence< const DiscreteVariable* >& seq1 = *(tables[ti]);
      const Sequence< const DiscreteVariable* >& seq2 = *(tables[tj]);

      long new_size = 1;

      for (const auto var : seq1) {
        if (std::numeric_limits< long >::max() / (long)var->domainSize()
            < new_size)
          GUM_ERROR(OutOfBounds, "memory usage out of long int range");

        new_size *= long(var->domainSize());
        new_seq->insert(var);
      }

      for (const auto var : seq2) {
        if (!seq1.exists(var)) {
          if (std::numeric_limits< long >::max() / (long)var->domainSize()
              < new_size)
            GUM_ERROR(OutOfBounds, "memory usage out of long int range");

          new_size *= long(var->domainSize());
          new_seq->insert(var);
        }
      }

      if (std::numeric_limits< long >::max() - current_memory < new_size) {
        GUM_ERROR(OutOfBounds, "memory usage out of long int range");
      }

      current_memory += new_size;

      if (current_memory > max_memory) { max_memory = current_memory; }

      // substitute tables[pair.first] by the result
      if (tables[ti] && is_t_new[ti]) {
        delete tables[ti];
        current_memory -= long(table_size[ti]);
      }

      if (tables[tj] && is_t_new[tj]) {
        delete tables[tj];
        current_memory -= long(table_size[tj]);
      }

      tables[ti] = new_seq;

      table_size[ti] = new_size;
      is_t_new[ti] = true;
      tables[tj] = 0;

      // remove all the pairs involving tj in the priority queue

      for (Idx ind = 0; ind < tj; ++ind) {
        if (tables[ind]) {
          pair.first = ind;
          queue.erase(pair);
        }
      }

      pair.first = tj;

      for (Idx ind = tj + 1; ind < tables.size(); ++ind) {
        if (tables[ind]) {
          pair.second = ind;
          queue.erase(pair);
        }
      }

      // update the "combined" size of all the pairs involving "new_seq"
      {
        pair.second = ti;
        Size newsize;

        for (Idx ind = 0; ind < ti; ++ind) {
          if (tables[ind]) {
            pair.first = ind;
            newsize = _combinedSize(*new_seq, *(tables[ind]));
            queue.setPriority(pair, newsize);
          }
        }

        pair.first = ti;

        for (Idx ind = ti + 1; ind < tables.size(); ++ind) {
          if (tables[ind]) {
            pair.second = ind;
            newsize = _combinedSize(*new_seq, *(tables[ind]));
            queue.setPriority(pair, newsize);
          }
        }
      }
    }

    // here, there remains only one nonzero pointer in tables:
    // the result of our combination
    Idx k = 0;

    while (!tables[k])
      ++k;

    delete tables[k];

    return std::pair< long, long >(max_memory, current_memory);
  }

  template < typename GUM_SCALAR >
  INLINE std::pair< long, long >
         ScheduleCombinationBasic< GUM_SCALAR >::memoryUsage(
        const Set< const MultiDimImplementation< GUM_SCALAR >* >& set,
        const Schedule< GUM_SCALAR >&                             schedule) {
    return ScheduleCombination< GUM_SCALAR >::memoryUsage(set, schedule);
  }

  template < typename GUM_SCALAR >
  template < template < typename > class TABLE >
  INLINE std::pair< long, long >
         ScheduleCombinationBasic< GUM_SCALAR >::memoryUsage(
        const Set< const TABLE< GUM_SCALAR >* >& set,
        const Schedule< GUM_SCALAR >&            schedule) {
    return ScheduleCombination< GUM_SCALAR >::memoryUsage(set, schedule);
  }

} /* namespace gum */

#endif /* DOXYGEN_SHOULD_SKIP_THIS */