view-val-graph.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, 2002
 *     Guido Tack, 2004
 *
 *  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_VIEW_VAL_GRAPH_HH__
#define __GECODE_INT_VIEW_VAL_GRAPH_HH__

#include <gecode/int.hh>

namespace Gecode { namespace Int { namespace ViewValGraph {

  template<class T>
  class CombPtrFlag {
  private:
    ptrdiff_t cpf;
  public:
    CombPtrFlag(T* p1, T* p2);
    void init(T* p1, T* p2);
    T* ptr(T* p) const;
    int is_set(void) const;
    void set(void);
    void unset(void);
  };

  class BiLink {
  private:
    BiLink* _prev;
    BiLink* _next;
  public:
    BiLink(void);
    BiLink* prev(void) const;
    BiLink* next(void) const;
    void prev(BiLink* l);
    void next(BiLink* l);
    void add(BiLink* l);
    void unlink(void);
    void mark(void);
    bool marked(void) const;
    bool empty(void) const;
  };


  template<class View> class Edge;

  template<class View>
  class Node : public BiLink {
  public:
    Edge<View>* iter;
    unsigned int low, min, comp;
    Node(void);
    Edge<View>* edge_fst(void) const;
    Edge<View>* edge_lst(void) const;

    static void* operator new(size_t, Space&);
    static void  operator delete(void*, size_t);
    static void  operator delete(void*,Space&);
  };

  template<class View>
  class ValNode : public Node<View> {
  protected:
    const int      _val;
    Edge<View>*    _matching;
    ValNode<View>* _next_val;
  public:
    ValNode(int v);
    ValNode(int v, ValNode<View>* n);
    int val(void) const;
    void matching(Edge<View>* m);
    Edge<View>* matching(void) const;
    ValNode<View>** next_val_ref(void);
    ValNode<View>* next_val(void) const;
    void next_val(ValNode<View>* v);
  };

  template<class View>
  class ViewNode : public Node<View> {
  protected:
    unsigned int _size;
    View        _view;
    Edge<View>* _val_edges;
  public:
    ViewNode(void);
    ViewNode(View x);
    Edge<View>*  val_edges(void) const;
    Edge<View>** val_edges_ref(void);
    bool fake(void) const;
    View view(void) const;
    void update(void);
    bool changed(void) const;
    bool matched(void) const;
  };

  template<class View>
  class Edge : public BiLink {
  protected:
    Edge<View>* _next_edge;
    CombPtrFlag<Node<View> > sd;
  public:
    Edge(ValNode<View>* v, ViewNode<View>* x);
    Edge(ValNode<View>* v, ViewNode<View>* x, Edge<View>* n);
    Node<View>* dst(Node<View>* s) const;

    ViewNode<View>* view(ValNode<View>* v) const;
    ValNode<View>* val(ViewNode<View>* x) const;

    bool used(Node<View>* v) const;
    void use(void);
    void free(void);

    void revert(Node<View>* d);

    Edge<View>*  next_edge(void) const;
    Edge<View>** next_edge_ref(void);
    Edge<View>* next(void) const;

    static void* operator new(size_t, Space&);
    static void  operator delete(void*, size_t);
    static void  operator delete(void*,Space&);
  };

  template<class View>
  class IterPruneVal {
  protected:
    ViewNode<View>* x;
    Edge<View>* e;
  public:


    IterPruneVal(ViewNode<View>* x);



    bool operator ()(void) const;
    void operator ++(void);



    int val(void) const;
  };

}}}

#include <gecode/int/view-val-graph/comb-ptr-flag.hpp>
#include <gecode/int/view-val-graph/bi-link.hpp>
#include <gecode/int/view-val-graph/edge.hpp>
#include <gecode/int/view-val-graph/node.hpp>
#include <gecode/int/view-val-graph/iter-prune-val.hpp>

namespace Gecode { namespace Int { namespace ViewValGraph {

  template<class View>
  class Graph {
  protected:
    ViewNode<View>** view;
    ValNode<View>* val;
    int n_view;
    int n_val;
    unsigned int count;
    typedef Support::StaticStack<ViewNode<View>*,Region> ViewNodeStack;
    void init(Space& home, ViewNode<View>* x);
    bool match(ViewNodeStack& m, ViewNode<View>* x);
    void scc(void);
  public:
    Graph(void);
    operator bool(void) const;
    void purge(void);
  };

}}}

#include <gecode/int/view-val-graph/graph.hpp>

#endif

// STATISTICS: int-prop