main page modules namespaces classes files
Gecode home

search for 

dom.icc

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:03:26 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3512 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  See the file "LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */

#include "gecode/iter.hh"

#include "gecode/support/static-stack.hh"
#include "gecode/support/block-allocator.hh"

namespace Gecode { namespace Int { namespace Regular {


  /*
   * Classes for the layered graph
   *
   */

  class State {
  public:
    unsigned int i_deg;
    unsigned int o_deg;
  };

  class Edge;
  typedef Support::BlockAllocator<Edge> EdgeAllocator;

  class Edge : public Support::BlockClient<Edge> {
  public:
    int    val;
    State* i_state;
    State* o_state;
    Edge*  next;
  };

  const int MOD_NONE  = 0; 
  const int MOD_IDEG  = 1; 
  const int MOD_ODEG  = 2; 


  class Layer {
  public:
    Edge*        edges;
    unsigned int size;
    int          modified;
  };

  template <class View>
  class Dom<View>::LayeredGraph {
  private:
    EdgeAllocator ea;
    size_t        state_size;
    State*        state_mem;
    Layer         _layer;    // One addional layer (makes layers[-1] okay)
    Layer         layers[2]; // Dynamically adjusted (also allow layers[...+1])
  public:
    LayeredGraph(ViewArray<View> x, const DFA& d);
    ~LayeredGraph(void);

    ExecStatus prune_initial(Space* home, ViewArray<View> x);
    ExecStatus prune(Space* home, ViewArray<View> x);

    size_t size(void) const;
    static void* operator new(size_t,int);
    static void  operator delete(void*);
    static void  operator delete(void*,int);
  };



  class EdgeRanges {
  private:
    const Edge* e1; const Edge* e2;
  public:
    EdgeRanges(void);
    EdgeRanges(const Edge*);
    void init(const Edge*);
    bool operator()(void) const;
    void operator++(void);
    int min(void) const;
    int max(void) const;
    unsigned int width(void) const;
  };

  forceinline
  EdgeRanges::EdgeRanges(void) {}
  forceinline
  EdgeRanges::EdgeRanges(const Edge* e)
    : e1(e), e2(e) {
    assert(e1);
    // e2 always points to the end of  the interval
    while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
      e2 = e2->next;
  }
  forceinline void
  EdgeRanges::init(const Edge* e) {
    e1=e; e2=e;
    assert(e1);
    // e2 always points to the end of  the interval
    while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
      e2 = e2->next;
  }

  forceinline bool
  EdgeRanges::operator()(void) const {
    return e1 != NULL;
  }

  forceinline void
  EdgeRanges::operator++(void) {
    e1 = e2->next;
    if (e1 != NULL) {
      e2 = e1;
      while ((e2->next != NULL) && (e2->next->val <= e2->val+1))
        e2 = e2->next;
    }
  }

  forceinline int
  EdgeRanges::min(void) const {
    return e1->val;
  }
  forceinline int
  EdgeRanges::max(void) const {
    return e2->val;
  }
  forceinline unsigned int
  EdgeRanges::width(void) const {
    return max()-min()+1;
  }



  /*
   * The layered graph
   *
   */

  template <class View>
  forceinline
  Dom<View>::LayeredGraph::LayeredGraph(ViewArray<View> x, const DFA& dfa) {
    int n = x.size();
    unsigned int n_states = dfa.n_states();

    // Allocate memory
    state_size = sizeof(State)*(n+1)*n_states;
    state_mem  = reinterpret_cast<State*>(Memory::malloc(state_size));


    // Initialize states (indegree and outdegree)
    for (int i = (n+1)*n_states; i--; ) {
      state_mem[i].i_deg = 0;
      state_mem[i].o_deg = 0;
    }

    // Mark initial state as being reachable
    state_mem[0].i_deg = 1;

    // Mark final states as reachable as well
    for (int s = dfa.final_fst(); s < dfa.final_lst(); s++)
      state_mem[n*n_states + s].o_deg = 1;

    // First pass: add transitions
    for (int i = 0; i < n; i++) {
      Edge** p = &layers[i].edges;
      // Enter links leaving reachable states (indegree != 0)
      DFA::Transitions  t_a(dfa);
      ViewRanges<View>    rx(x[i]);
      while (rx() && t_a()) {
        const DFA::Transition* t = t_a.transition();
        // Compute pointers to states
        State* i_state = state_mem + (i  )*n_states + t->i_state;
        State* o_state = state_mem + (i+1)*n_states + t->o_state;
        if (t->symbol > rx.max()) {
          ++rx;
        } else if ((t->symbol >= rx.min()) && (i_state->i_deg > 0)) {
          // Add new transition as state is reachable
          i_state->o_deg++; o_state->i_deg++;
          Edge* e = new (ea) Edge;
          e->i_state = i_state;
          e->val     = t->symbol;
          e->o_state = o_state;
          *p = e;
          p = &e->next;
          ++t_a;
        } else {
          ++t_a;
        }
      }
      // Write endmarker for edges
      *p = NULL;
    }
  }

  template <class View>
  forceinline ExecStatus
  Dom<View>::LayeredGraph::prune_initial(Space* home, ViewArray<View> x) {
    // Second pass: prune all transitions that do not lead to final state
    for (int i = x.size(); i--; ) {
      Edge** p = &layers[i].edges;
      Edge*  e = *p;
      while (e != NULL) {
        if (e->o_state->o_deg != 0) {
          // This state is still reachable, keep edge
          p = &e->next;
        } else {
          // Unreachable state, prune edge
          *p = e->next;
          e->i_state->o_deg--; e->o_state->i_deg--;
        }
        e = e->next;
      }
      *p = NULL;
    }

    // Tell back variable domains
    ExecStatus es = ES_FIX;
    for (int i=x.size(); i--; ) {
      if (layers[i].edges == NULL)
        return ES_FAILED;
      if (x[i].modified())
        es = ES_NOFIX;
      EdgeRanges er(layers[i].edges);
      if (x[i].modified()) {
        GECODE_ME_CHECK(x[i].inter(home,er));
      } else {
        x[i].narrow(home,er);
      }
      // Initialize size and modification data
      layers[i].modified = MOD_NONE;
      layers[i].size     = x[i].size();
    }
    for (int i=x.size(); i--; )
      if (!x[i].assigned())
        return es;
    return ES_SUBSUMED;
  }

  template <class View>
  forceinline ExecStatus
  Dom<View>::LayeredGraph::prune(Space* home, ViewArray<View> x) {
    int n = x.size();
    // Prune edges for which no value support exists
    for (int i = 0; i < n; i++)
      if (layers[i].size != x[i].size()) {
        layers[i].size = x[i].size();
        Edge** p = &layers[i].edges;
        Edge*  e = *p;
        ViewRanges<View> rx(x[i]);
        while (rx() && (e != NULL)) {
          if (e->val > rx.max()) {
            ++rx;
          } else if ((e->val < rx.min()) || (e->i_state->i_deg == 0)) {
            // Adapt states
            if ((--e->i_state->o_deg) == 0)
              layers[i-1].modified |= MOD_ODEG;
            if ((--e->o_state->i_deg) == 0)
              layers[i+1].modified |= MOD_IDEG;
            // Remove this edge
            *p = e->next; e = e->next;
          } else {
            // Keep edge
            p = &e->next; e = e->next;
          }
        }
        *p = NULL;
        // Remove all remaining edges
        while (e != NULL) {
          // Adapt states
          if (--e->i_state->o_deg == 0)
            layers[i-1].modified |= MOD_ODEG;
          if (--e->o_state->i_deg == 0)
            layers[i+1].modified |= MOD_IDEG;
          e = e->next;
        }
        // Write endmarker for edges
      }  else if (layers[i].modified & MOD_IDEG) {
        assert(layers[i].size == x[i].size());
        Edge** p = &layers[i].edges;
        Edge*  e = *p;
        while (e != NULL) {
          if (e->i_state->i_deg == 0) {
            // Adapt states
            if (--e->i_state->o_deg == 0)
              layers[i-1].modified |= MOD_ODEG;
            if (--e->o_state->i_deg == 0)
              layers[i+1].modified |= MOD_IDEG;
            // Remove this edge
            *p = e->next;
          } else {
            // Keep edge
            p = &e->next;
          }
          e = e->next;
        }
        // Write endmarker for edges
        *p = NULL;
      }

    for (int i=n; i--; )
      if (layers[i].modified & MOD_ODEG) {
        Edge** p = &layers[i].edges;
        Edge*  e = *p;
        while (e != NULL) {
          if (e->o_state->o_deg != 0) {
            // This state is still reachable, keep edge
            p = &e->next;
          } else {
            // Unreachable state, prune edge
            if (--e->i_state->o_deg == 0)
              layers[i-1].modified |= MOD_ODEG;
            --e->o_state->i_deg;
            *p = e->next;
          }
          e = e->next;
        }
        *p = NULL;
      }
    // Tell back variable domains
    ExecStatus es = ES_FIX;
    for (int i=n; i--; )
      if (layers[i].modified) {
        layers[i].modified = MOD_NONE;
        if (layers[i].edges == NULL)
          return ES_FAILED;
        if (x[i].modified())
          es = ES_NOFIX;
        EdgeRanges er(layers[i].edges);
        if (x[i].modified()) {
          GECODE_ME_CHECK(x[i].inter(home,er));
        } else {
          x[i].narrow(home,er);
        }
        layers[i].size = x[i].size();
      }
    for (int i=x.size(); i--; )
      if (!x[i].assigned())
        return es;
    return ES_SUBSUMED;
  }

  template <class View>
  forceinline
  Dom<View>::LayeredGraph::~LayeredGraph(void) {
    Memory::free(state_mem);
  }

  template <class View>
  forceinline size_t
  Dom<View>::LayeredGraph::size(void) const {
    return state_size + ea.size();
  }

  template <class View>
  forceinline void
  Dom<View>::LayeredGraph::operator delete(void* p) {
    Memory::free(p);
  }

  template <class View>
  forceinline void
  Dom<View>::LayeredGraph::operator delete(void* p, int) {
    Memory::free(p);
  }

  template <class View>
  forceinline void*
  Dom<View>::LayeredGraph::operator new(size_t s, int n) {
    // n ist the number of variables
    return Memory::malloc(sizeof(LayeredGraph) + n*sizeof(Layer));
  }

  template <class View>
  ExecStatus
  Dom<View>::propagate(Space* home) {
    if (lg == NULL) {
      lg = new (this->x.size()) LayeredGraph(this->x,dfa);
      return lg->prune_initial(home,this->x);
    } else {
      return lg->prune(home,this->x);
    }
  }

  template <class View>
  forceinline
  Dom<View>::Dom(Space* home, ViewArray<View>& x, DFA& d)
    : NaryPropagator<View,PC_INT_DOM>(home,x,true),
      dfa(d), lg(NULL) {
  }

  template <class View>
  ExecStatus
  Dom<View>::post(Space* home, ViewArray<View>& x, DFA& d) {
    (void) new (home) Dom<View>(home,x,d);
    return ES_OK;
  }

  template <class View>
  forceinline
  Dom<View>::Dom(Space* home, bool share, Dom<View>& p)
    : NaryPropagator<View,PC_INT_DOM>(home,share,p), lg(NULL) {
    dfa.update(share,p.dfa);
  }

  template <class View>
  size_t
  Dom<View>::dispose(Space* home) {
    dfa.~DFA();
    delete lg;
    (void) NaryPropagator<View,PC_INT_DOM>::dispose(home);
    return sizeof(*this);
  }

  template <class View>
  void
  Dom<View>::flush(void) {
    delete lg; lg = NULL;
  }

  template <class View>
  size_t
  Dom<View>::size(void) const {
    return (lg != NULL) ? lg->size() : 0;
  }

  template <class View>
  PropCost
  Dom<View>::cost(void) const {
    return cost_hi(this->x.size(), PC_LINEAR_HI);
  }

  template <class View>
  Actor*
  Dom<View>::copy(Space* home, bool share) {
    return new (home) Dom<View>(home,share,*this);
  }

}}}

// STATISTICS: int-prop