cumulative.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2009
 *     Guido Tack, 2010
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#ifndef __GECODE_INT_CUMULATIVE_HH__
#define __GECODE_INT_CUMULATIVE_HH__

#include <gecode/int/task.hh>
#include <gecode/int/unary.hh>

namespace Gecode { namespace Int { namespace Cumulative {

  void mul_check(long long int x, long long int y);

  void mul_check(long long int x, long long int y, long long int z);

}}}

#include <gecode/int/cumulative/limits.hpp>

namespace Gecode { namespace Int { namespace Cumulative {

  class ManFixPTask : public Unary::ManFixPTask {
  protected:
    int _c;
  public:


    ManFixPTask(void);
    ManFixPTask(IntVar s, int p, int c);
    void init(IntVar s, int p, int c);
    void init(const ManFixPTask& t);



    int c(void) const;
    long long int e(void) const;



    void update(Space& home, ManFixPTask& t);

  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);

  class ManFixPSETask : public Unary::ManFixPSETask {
  protected:
    int _c;
  public:


    ManFixPSETask(void);
    ManFixPSETask(TaskType t, IntVar s, int p, int c);
    void init(TaskType t, IntVar s, int p, int c);
    void init(const ManFixPSETask& t);



    int c(void) const;
    long long int e(void) const;



    void update(Space& home, ManFixPSETask& t);

  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);

  class ManFlexTask : public Unary::ManFlexTask {
  protected:
    int _c;
  public:


    ManFlexTask(void);
    ManFlexTask(IntVar s, IntVar p, IntVar e, int c);
    void init(IntVar s, IntVar p, IntVar e, int c);
    void init(const ManFlexTask& t);



    int c(void) const;
    long long int e(void) const;



    void update(Space& home, ManFlexTask& t);

  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);


  class OptFixPTask : public ManToOptTask<ManFixPTask> {
  protected:
    using ManToOptTask<ManFixPTask>::_m;
  public:


    OptFixPTask(void);
    OptFixPTask(IntVar s, int p, int c, BoolVar m);
    void init(IntVar s, int p, int c, BoolVar m);

    operator Unary::OptFixPTask (void);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);

  class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
  protected:
    using ManToOptTask<ManFixPSETask>::_m;
  public:


    OptFixPSETask(void);
    OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m);
    void init(TaskType t, IntVar s, int p, int c, BoolVar m);

    operator Unary::OptFixPSETask (void);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);

  class OptFlexTask : public ManToOptTask<ManFlexTask> {
  protected:
    using ManToOptTask<ManFlexTask>::_m;
  public:


    OptFlexTask(void);
    OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
    void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m);

    operator Unary::OptFlexTask (void);
  };

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);

}}}

#include <gecode/int/cumulative/task.hpp>

namespace Gecode { namespace Int { namespace Cumulative {

  typedef ManFixPTask ManFixPTaskFwd;

  typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd;

  typedef ManFixPSETask ManFixPSETaskFwd;

  typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd;

  typedef OptFixPTask OptFixPTaskFwd;

  typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd;

  typedef OptFixPSETask OptFixPSETaskFwd;

  typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd;

  typedef ManFlexTask ManFlexTaskFwd;

  typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd;

  typedef OptFlexTask OptFlexTaskFwd;

  typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd;


  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);

  template<class Char, class Traits>
  std::basic_ostream<Char,Traits>&
  operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);

}}}

#include <gecode/int/cumulative/task-view.hpp>

namespace Gecode { namespace Int {

  template<>
  class TaskViewTraits<Cumulative::ManFixPTaskFwd> {
  public:
    typedef Cumulative::ManFixPTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::ManFixPTaskBwd> {
  public:
    typedef Cumulative::ManFixPTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::ManFixPSETaskFwd> {
  public:
    typedef Cumulative::ManFixPSETask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::ManFixPSETaskBwd> {
  public:
    typedef Cumulative::ManFixPSETask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::OptFixPTaskFwd> {
  public:
    typedef Cumulative::OptFixPTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::OptFixPTaskBwd> {
  public:
    typedef Cumulative::OptFixPTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::OptFixPSETaskFwd> {
  public:
    typedef Cumulative::OptFixPSETask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::OptFixPSETaskBwd> {
  public:
    typedef Cumulative::OptFixPSETask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::ManFlexTaskFwd> {
  public:
    typedef Cumulative::ManFlexTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::ManFlexTaskBwd> {
  public:
    typedef Cumulative::ManFlexTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::OptFlexTaskFwd> {
  public:
    typedef Cumulative::OptFlexTask Task;
  };

  template<>
  class TaskViewTraits<Cumulative::OptFlexTaskBwd> {
  public:
    typedef Cumulative::OptFlexTask Task;
  };


  template<>
  class TaskTraits<Cumulative::ManFixPTask> {
  public:
    typedef Cumulative::ManFixPTaskFwd TaskViewFwd;
    typedef Cumulative::ManFixPTaskBwd TaskViewBwd;
    typedef Unary::ManFixPTask UnaryTask;
  };

  template<>
  class TaskTraits<Cumulative::ManFixPSETask> {
  public:
    typedef Cumulative::ManFixPSETaskFwd TaskViewFwd;
    typedef Cumulative::ManFixPSETaskBwd TaskViewBwd;
    typedef Unary::ManFixPSETask UnaryTask;
  };

  template<>
  class TaskTraits<Cumulative::OptFixPTask> {
  public:
    typedef Cumulative::OptFixPTaskFwd TaskViewFwd;
    typedef Cumulative::OptFixPTaskBwd TaskViewBwd;
    typedef Cumulative::ManFixPTask ManTask;
    typedef Unary::OptFixPTask UnaryTask;
  };

  template<>
  class TaskTraits<Cumulative::OptFixPSETask> {
  public:
    typedef Cumulative::OptFixPSETaskFwd TaskViewFwd;
    typedef Cumulative::OptFixPSETaskBwd TaskViewBwd;
    typedef Cumulative::ManFixPSETask ManTask;
    typedef Unary::OptFixPSETask UnaryTask;
  };

  template<>
  class TaskTraits<Cumulative::ManFlexTask> {
  public:
    typedef Cumulative::ManFlexTaskFwd TaskViewFwd;
    typedef Cumulative::ManFlexTaskBwd TaskViewBwd;
    typedef Unary::ManFlexTask UnaryTask;
  };

  template<>
  class TaskTraits<Cumulative::OptFlexTask> {
  public:
    typedef Cumulative::OptFlexTaskFwd TaskViewFwd;
    typedef Cumulative::OptFlexTaskBwd TaskViewBwd;
    typedef Cumulative::ManFlexTask ManTask;
    typedef Unary::OptFlexTask UnaryTask;
  };

}}

namespace Gecode { namespace Int { namespace Cumulative {

  class OmegaNode {
  public:
    long long int e;
    long long int env;
    void init(const OmegaNode& l, const OmegaNode& r);
    void update(const OmegaNode& l, const OmegaNode& r);
  };

  template<class TaskView>
  class OmegaTree : public TaskTree<TaskView,OmegaNode> {
  protected:
    using TaskTree<TaskView,OmegaNode>::tasks;
    using TaskTree<TaskView,OmegaNode>::leaf;
    using TaskTree<TaskView,OmegaNode>::root;
    using TaskTree<TaskView,OmegaNode>::init;
    using TaskTree<TaskView,OmegaNode>::update;
    int c;
  public:
    OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
    void insert(int i);
    void remove(int i);
    long long int env(void) const;
  };

  class ExtOmegaNode : public OmegaNode {
  public:
    long long int cenv;
    void init(const ExtOmegaNode& l, const ExtOmegaNode& r);
    void update(const ExtOmegaNode& l, const ExtOmegaNode& r);
  };

  template<class TaskView>
  class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> {
  protected:
    using TaskTree<TaskView,ExtOmegaNode>::tasks;
    using TaskTree<TaskView,ExtOmegaNode>::leaf;
    using TaskTree<TaskView,ExtOmegaNode>::root;
    using TaskTree<TaskView,ExtOmegaNode>::init;
    using TaskTree<TaskView,ExtOmegaNode>::update;
    using TaskTree<TaskView,ExtOmegaNode>::node;
    using TaskTree<TaskView,ExtOmegaNode>::n_leaf;
    using TaskTree<TaskView,ExtOmegaNode>::n_left;
    using TaskTree<TaskView,ExtOmegaNode>::left;
    using TaskTree<TaskView,ExtOmegaNode>::n_right;
    using TaskTree<TaskView,ExtOmegaNode>::right;
    using TaskTree<TaskView,ExtOmegaNode>::n_root;
    using TaskTree<TaskView,ExtOmegaNode>::n_parent;
    using TaskTree<TaskView,ExtOmegaNode>::n_nodes;
    using TaskTree<TaskView,ExtOmegaNode>::_leaf;
    int c, ci;
  public:
    template<class Node>
    ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t);
    void init(int ci);
    long long int env(int i);
  };


  class OmegaLambdaNode : public OmegaNode {
  public:
    static const int undef = -1;
    long long int le;
    long long int lenv;
    int resLe;
    int resLenv;
    void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
    void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
  };

  template<class TaskView>
  class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
  protected:
    using TaskTree<TaskView,OmegaLambdaNode>::tasks;
    using TaskTree<TaskView,OmegaLambdaNode>::leaf;
    using TaskTree<TaskView,OmegaLambdaNode>::root;
    using TaskTree<TaskView,OmegaLambdaNode>::init;
    using TaskTree<TaskView,OmegaLambdaNode>::update;
    int c;
  public:
    OmegaLambdaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
    void shift(int i);
    void lremove(int i);
    bool lempty(void) const;
    int responsible(void) const;
    long long int env(void) const;
    long long int lenv(void) const;
  };

}}}

#include <gecode/int/cumulative/tree.hpp>

namespace Gecode { namespace Int { namespace Cumulative {

  template<class Task>
  ExecStatus
  subsumed(Space& home, Propagator& p, int c, TaskArray<Task>& t);

  template<class ManTask>
  ExecStatus overload(Space& home, int c, TaskArray<ManTask>& t);

  template<class Task, class Cap>
  ExecStatus timetabling(Space& home, Propagator& p, Cap c,
                         TaskArray<Task>& t);

  template<class Task>
  ExecStatus edgefinding(Space& home, int c, TaskArray<Task>& t);

  template<class ManTask, class Cap, class PL>
  class ManProp : public TaskProp<ManTask,PL> {
  protected:
    using TaskProp<ManTask,PL>::t;
    Cap c;
    ManProp(Home home, Cap c, TaskArray<ManTask>& t);
    ManProp(Space& home, ManProp& p);
  public:
    virtual Actor* copy(Space& home);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Home home, Cap c, TaskArray<ManTask>& t);
    virtual size_t dispose(Space& home);
  };

  template<class OptTask, class Cap, class PL>
  class OptProp : public TaskProp<OptTask,PL> {
  protected:
    using TaskProp<OptTask,PL>::t;
    Cap c;
    OptProp(Home home, Cap c, TaskArray<OptTask>& t);
    OptProp(Space& home, OptProp& p);
  public:
    virtual Actor* copy(Space& home);
    virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
    static ExecStatus post(Home home, Cap c, TaskArray<OptTask>& t);
    virtual size_t dispose(Space& home);
  };

  template<class ManTask, class Cap>
  ExecStatus
  cmanpost(Home home, Cap c, TaskArray<ManTask>& t, IntPropLevel ipl);

  template<class OptTask, class Cap>
  ExecStatus
  coptpost(Home home, Cap c, TaskArray<OptTask>& t, IntPropLevel ipl);

}}}

#include <gecode/int/cumulative/time-tabling.hpp>
#include <gecode/int/cumulative/subsumption.hpp>
#include <gecode/int/cumulative/overload.hpp>
#include <gecode/int/cumulative/edge-finding.hpp>
#include <gecode/int/cumulative/man-prop.hpp>
#include <gecode/int/cumulative/opt-prop.hpp>
#include <gecode/int/cumulative/post.hpp>

#endif

// STATISTICS: int-prop