projectors.hh

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Guido Tack <tack@gecode.org>
 *
 *  Contributing authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Guido Tack, 2006
 *     Christian Schulte, 2007
 *
 *  Last modified:
 *     $Date: 2008-08-07 16:04:08 +0200 (Thu, 07 Aug 2008) $ by $Author: tack $
 *     $Revision: 7536 $
 *
 *  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_GENERATOR_PROJECOTRS_HH
#define __GECODE_GENERATOR_PROJECTORS_HH

#include "gecode/set.hh"

namespace Gecode {


  class SetExprCode {
  private:
    SharedArray<int> c;
  public:
    enum Instruction {
      COMPLEMENT, 
      INTER,      
      UNION,      
      GLB,        
      LUB,        
      EMPTY,      
      UNIVERSE,   
      LAST        
    };

    class Stream {
    private:
      Support::DynamicArray<int> is;
      int n;
    public:
      Stream(void);
      void add(int i);
      int size(void) const;
      int operator[](int i) const;
    };
 


    SetExprCode(void);
    SetExprCode(const Stream& s);
    SetExprCode(const SetExprCode& sc);

    void update(Space* home, bool share, SetExprCode& sc);
    
    int size(void) const;

    int operator[](int i) const;

  };
  
  class SetExpr {
  public:
    typedef int var_idx;

    enum RelType {
      REL_INTER, 
      REL_UNION  
    };
    
  private:
    class Node;

    Node* ax; 
    int sign; 
  public:

    SetExpr(void);
    GECODE_SET_EXPORT SetExpr(const SetExpr& s);
    GECODE_SET_EXPORT SetExpr(var_idx v);
    GECODE_SET_EXPORT SetExpr(const SetExpr& s, int sign);
    GECODE_SET_EXPORT SetExpr(const SetExpr& s, int ssign,
                              RelType r,
                              const SetExpr& t, int tsign);
    GECODE_SET_EXPORT const SetExpr& operator=(const SetExpr& e);
    GECODE_SET_EXPORT int arity(void) const;
    GECODE_SET_EXPORT SetExprCode encode(void) const;
    GECODE_SET_EXPORT ~SetExpr(void);
  };

}



Gecode::SetExpr operator-(const Gecode::SetExpr& s);
Gecode::SetExpr operator||(const Gecode::SetExpr& s,
                           const Gecode::SetExpr& t);
Gecode::SetExpr operator&&(const Gecode::SetExpr& s,
                           const Gecode::SetExpr& t);
Gecode::SetExpr operator-(const Gecode::SetExpr& s,
                          const Gecode::SetExpr& t);


namespace Gecode {

  class Projector {
  private:
    SetExpr::var_idx i; 
    SetExprCode glb; 
    SetExprCode lub; 
    int _arity; 
  public:
    Projector(void);
    Projector(SetExpr::var_idx x, const SetExpr& sglb, const SetExpr& slub);

    GECODE_SET_EXPORT void scope(Support::DynamicArray<int>& scope) const;

    GECODE_SET_EXPORT int arity(void) const;
              
    template <bool negated>
    ExecStatus propagate(Space* home, ViewArray<Set::SetView>& x);

    GECODE_SET_EXPORT ExecStatus check(Space* home,
                                       ViewArray<Set::SetView>& x);

    unsigned int glbSize(ViewArray<Set::SetView>& x);
    
    unsigned int lubSize(ViewArray<Set::SetView>& x);

    const SetExprCode& getGlb(void) const;

    const SetExprCode& getLub(void) const;

    SetExpr::var_idx getIdx(void) const;

  };
  
  class ProjectorSet {
  private:
    SharedArray<Projector> _ps; 
    int _count; 
    int _arity; 
    
  public:
    
    ProjectorSet(void);
    
    ProjectorSet(int n);

    void update(Space* home, bool share, ProjectorSet& p);

    GECODE_SET_EXPORT void add(const Projector& p);

    int arity(void) const;

    GECODE_SET_EXPORT void scope(Support::DynamicArray<int>& scope,
                                 unsigned int size) const;
    
    template <bool negated>
    ExecStatus propagate(Space* home, ViewArray<Set::SetView>& x);

    GECODE_SET_EXPORT ExecStatus check(Space* home,
                                       ViewArray<Set::SetView>& x);

    int size(void) const;

    const Projector& operator[](int i) const;

  };



  class Formula {
  public:
    enum Operator { AND, OR, IMPL, EQUIV };
  private:
    class Node;
    Node* ax; 
    int sign; 
  public:
    GECODE_SET_EXPORT Formula(const Formula& f);
    GECODE_SET_EXPORT const Formula& operator=(const Formula& f);
    GECODE_SET_EXPORT ~Formula(void);
    GECODE_SET_EXPORT Formula(int var);
    GECODE_SET_EXPORT Formula(bool b);
    GECODE_SET_EXPORT Formula(const Formula& f, int sign);
    GECODE_SET_EXPORT Formula(const Formula& f, int fs,
                              Operator o,
                              const Formula& g, int gs);
    GECODE_SET_EXPORT ProjectorSet projectors(void);
    
  };

}



Gecode::Formula operator&(const Gecode::Formula& f, const Gecode::Formula& g);
Gecode::Formula operator|(const Gecode::Formula& f, const Gecode::Formula& g);
Gecode::Formula operator-(const Gecode::Formula& f);
Gecode::Formula operator>>(const Gecode::Formula& f,
                           const Gecode::Formula& g);
Gecode::Formula operator==(const Gecode::Formula& f,
                           const Gecode::Formula& g);


namespace Gecode {
  


  GECODE_SET_EXPORT void
  projector(Space* home, const SetVarArgs& xa,
            ProjectorSet& ps, bool negated=false);

  GECODE_SET_EXPORT void
  projector(Space* home, const SetVar& xa, const SetVar& ya,
            ProjectorSet& ps, bool negated=false);

  GECODE_SET_EXPORT void
  projector(Space* home, const SetVar& xa, const SetVar& ya,
            const BoolVar& bv,
            ProjectorSet& ps);

  GECODE_SET_EXPORT void
  projector(Space* home,
            const SetVar& xa, const SetVar& ya, const SetVar& za,
            ProjectorSet& ps, bool negated=false);

  GECODE_SET_EXPORT void
  projector(Space* home,
            const SetVar& xa, const SetVar& ya, const SetVar& za,
            const BoolVar& bv,
            ProjectorSet& ps);
  
  GECODE_SET_EXPORT void
  projector(Space* home, const SetVar& xa, const SetVar& ya,
            const IntVar& i,
            Projector& p);

  GECODE_SET_EXPORT void
  projector(Space* home, const SetVar& xa, const SetVar& ya,
            const SetVar& za, const IntVar& i,
            Projector& p);



}

GECODE_SET_EXPORT std::ostream&
operator<<(std::ostream&, const Gecode::SetExprCode& sec);

GECODE_SET_EXPORT std::ostream&
operator<<(std::ostream&, const Gecode::Projector& p);

GECODE_SET_EXPORT std::ostream&
operator<<(std::ostream&, const Gecode::ProjectorSet& ps);

#include "gecode/set/projectors/set-expr.icc"
#include "gecode/set/projectors/projector.icc"
#include "gecode/set/projectors/projector-set.icc"
#include "gecode/set/projectors/formula.icc"

#endif

// STATISTICS: set-prop