extensional.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2007
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2008-07-11 09:28:48 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
 *     $Revision: 7285 $
 *
 *  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_EXTENSIONAL_HH__
#define __GECODE_INT_EXTENSIONAL_HH__

#include "gecode/int.hh"

#include "gecode/int/rel.hh"

namespace Gecode { namespace Int { namespace Extensional {

  class Layer;
  class State;

  template <class View>
  class LayeredGraph : public Propagator {
  protected:
    class Index : public Advisor {
    public:
      int i;
      Index(Space* home, Propagator* p, Council<Index>& c, int i);
      Index(Space* home, bool share, Index& a);
      void dispose(Space* home, Council<Index>& c);
    };
    class IndexRange {
    private:
      int _fst; 
      int _lst; 
    public:
      IndexRange(void);
      void reset(void);
      void add(int i);
      int fst(void) const;
      int lst(void) const;
    };
    Council<Index> c;
    ViewArray<View> x;
    DFA dfa;
    int start;
    Layer* layers;
    State* states;
    IndexRange i_ch;
    IndexRange o_ch;
    
    bool constructed(void) const;
    void eliminate(void);
    ExecStatus construct(Space* home);
    ExecStatus prune(Space* home);

    LayeredGraph(Space* home, bool share, LayeredGraph<View>& p);
  public:
    LayeredGraph(Space* home, ViewArray<View>& x, DFA& d);
    virtual Actor* copy(Space* home, bool share);
    virtual PropCost cost(ModEventDelta med) const;
    virtual ExecStatus advise(Space* home, Advisor* a, const Delta* d);
    virtual ExecStatus propagate(Space* home, ModEventDelta med);
    virtual Reflection::ActorSpec spec(const Space* home,
                                        Reflection::VarMap& m) const;
    static void post(Space* home, Reflection::VarMap& vars,
                     const Reflection::ActorSpec& spec);
    static Gecode::Support::Symbol ati(void);
    virtual size_t dispose(Space* home);
    static ExecStatus post(Space* home, ViewArray<View>& x, DFA& d);
  };

}}}

#include "gecode/int/extensional/layered-graph.icc"


#include "gecode/int/extensional/bitset.icc"

namespace Gecode { namespace Int { namespace Extensional {

  typedef TupleSet::Tuple Tuple;
  typedef BitSet* Domain;

  template <class View, bool subscribe = true>
  class Base : public Propagator {
  protected:
    ViewArray<View> x; 
    TupleSet tupleSet; 
    Tuple** last_data; 

    TupleSet::TupleSetI* ts(void);

    Base(Space* home, bool share, Base<View,subscribe>& p);
    Base(Space* home, ViewArray<View>& x, const TupleSet& t);

    void  init_last(Space* home, Tuple** source);
    Tuple last(int var, int val);
    Tuple last_next(int var, int val);
    void  init_dom(Space* home, Domain dom);
    bool  valid(Tuple t, Domain dom);
    Tuple find_support(Domain dom, int var, int val);

  public:
    virtual PropCost cost(ModEventDelta med) const;

    // Dispose propagator
    virtual size_t dispose(Space* home);
  };
}}}

#include "gecode/int/extensional/base.icc"


namespace Gecode { namespace Int { namespace Extensional {

  template <class View>
  class Basic : public Base<View> {
  protected:
    using Base<View>::x;
    using Base<View>::tupleSet;
    using Base<View>::ts;
    using Base<View>::last;
    using Base<View>::last_next;
    using Base<View>::init_last;
    using Base<View>::init_dom;
    using Base<View>::find_support;

    Basic(Space* home, bool share, Basic<View>& p);
    Basic(Space* home, ViewArray<View>& x, const TupleSet& t);

  public:
    virtual ExecStatus propagate(Space* home, ModEventDelta med);
    virtual PropCost cost(ModEventDelta med) const;
    virtual Actor* copy(Space* home, bool share);
    static ExecStatus post(Space* home, ViewArray<View>& x, const TupleSet& t);

    virtual Reflection::ActorSpec spec(const Space* home,
                                        Reflection::VarMap& m) const;
    static void post(Space* home, Reflection::VarMap& vars,
                     const Reflection::ActorSpec& spec);
    static Gecode::Support::Symbol ati(void);
  };
}}}

#include "gecode/int/extensional/basic.icc"


namespace Gecode { namespace Int { namespace Extensional {
  template <class View>
  class Incremental : public Base<View, false> {
  protected:
    using Base<View, false>::x;
    using Base<View, false>::tupleSet;
    using Base<View, false>::ts;
    using Base<View, false>::last;
    using Base<View, false>::last_next;
    using Base<View, false>::init_last;
    using Base<View, false>::init_dom;
    class SupportEntry : public FreeList {
    public:
      Tuple t;
      SupportEntry* next;
      


      SupportEntry(void);
      SupportEntry(Tuple t0, SupportEntry* n0 = NULL);
      


      void dispose(Space* home, SupportEntry* l);
      void dispose(Space* home);
      
      static void* operator new(size_t s, Space* home);
      static void  operator delete(void*);
      static void  operator delete(void*, Space*);
    };
    enum WorkType {
      WT_FIND_SUPPORT,
      WT_REMOVE_VALUE
    };
    class Work {
    public:
      WorkType work;
      int var;
      int val;
      Work(WorkType w0, int var0, int val0)
        : work(w0), var(var0), val(val0) {}
    };



    typedef ::Gecode::Support::DynamicStack<Work> WorkStack;
    SupportEntry** support_data;
    WorkStack work;
    int unassigned;

    Incremental(Space* home, bool share, Incremental<View>& p);
    Incremental(Space* home, ViewArray<View>& x, const TupleSet& t);

    void   find_support(Space* home, Domain dom, int var, int val);
    void   init_support(Space* home);
    void    add_support(Space* home, Tuple l);
    void remove_support(Space* home, Tuple l, int var, int val);
    SupportEntry* support(int var, int val);
  public:
    virtual ExecStatus propagate(Space* home, ModEventDelta med);
    virtual PropCost cost(ModEventDelta med) const;
    virtual Actor* copy(Space* home, bool share);
    static ExecStatus post(Space* home, ViewArray<View>& x, const TupleSet& t);
    // Dispose propagator
    size_t dispose(Space* home);


    virtual Reflection::ActorSpec spec(const Space* home,
                                        Reflection::VarMap& m) const;
    static void post(Space* home, Reflection::VarMap& vars,
                     const Reflection::ActorSpec& spec);
    static Gecode::Support::Symbol ati(void);


    //
    // Advisor proper
    //
  private:
    class SupportAdvisor : public ViewAdvisor<View> {
    public:
      using ViewAdvisor<View>::x;
      unsigned int pos;
      SupportAdvisor(Space* home, Propagator* p, Council<SupportAdvisor>& c,
                     View v, unsigned int position) 
        : ViewAdvisor<View>(home,p,c,v), pos(position) {}
      SupportAdvisor(Space* home, bool share, SupportAdvisor& a) 
        : ViewAdvisor<View>(home, share, a), pos(a.pos) {
      }
      void dispose(Space* home, Council<SupportAdvisor>& c) {
            ViewAdvisor<View>::dispose(home,c);
      }
    };
    Council<SupportAdvisor> ac;
  public:
    virtual ExecStatus advise(Space* home, Advisor* a, const Delta* d);
  };
  
}}}

#include "gecode/int/extensional/incremental.icc"


#endif

// STATISTICS: int-prop