/*
 *  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"

namespace Gecode { namespace Int { namespace Element {

  /**
   * \brief Links for index-value map
   *
   * Data structure linking pairs of index and value (index,value)
   * where pairs are linked in order of both index and
   * value (to allow for easy removal while keeping both index and
   * value sorted).
   *
   */
  class IdxValLink  {
  public:
    IdxValLink* idx_next;
    IdxValLink* val_next;
    int idx, val;

    void mark(void);
    bool marked(void) const;
  };

  forceinline void
  IdxValLink::mark(void) {
    idx = -1;
  }
  forceinline bool
  IdxValLink::marked(void) const {
    return idx<0;
  }



  /**
   * \brief Value iterator for indices in index-value map
   *
   * The iterator also removes marked index-value pairs.
   *
   */
  class IterIdx {
  private:
    IdxValLink* l;
  public:
    IterIdx(void);
    IterIdx(IdxValLink&);
    void init(IdxValLink&);
    bool operator()(void) const;
    void operator++(void);
    int  val(void) const;
  };

  forceinline
  IterIdx::IterIdx(void) {}
  forceinline
  IterIdx::IterIdx(IdxValLink& ivl) {
    IdxValLink* p=&ivl;
    l = p->idx_next;
    while ((l != NULL) && l->marked())
      l=l->idx_next;
    p->idx_next=l;
  }
  forceinline void
  IterIdx::init(IdxValLink& ivl) {
    IdxValLink* p=&ivl;
    l = p->idx_next;
    while ((l != NULL) && l->marked())
      l=l->idx_next;
    p->idx_next=l;
  }
  forceinline bool
  IterIdx::operator()(void) const {
    return l != NULL;
  }
  forceinline void
  IterIdx::operator++(void) {
    IdxValLink* p=l;
    l = p->idx_next;
    while ((l != NULL) && l->marked())
      l=l->idx_next;
    p->idx_next=l;
  }
  forceinline int
  IterIdx::val(void) const {
    assert(!l->marked());
    return l->idx;
  }



  /**
   * \brief Value iterator for values in index-value map
   *
   * Note that the iterated value sequence is not strictly
   * increasing (might contain duplicates).
   */
  class IterVal {
  private:
    const IdxValLink* l;
  public:
    IterVal(void);
    IterVal(const IdxValLink&);
    void init(const IdxValLink&);
    bool operator()(void) const;
    void operator++(void);
    int  val(void) const;
  };

  forceinline
  IterVal::IterVal(void) {}
  forceinline
  IterVal::IterVal(const IdxValLink& ivl)
    : l(ivl.val_next) {}
  forceinline void
  IterVal::init(const IdxValLink& ivl) {
    l = ivl.val_next;
  }
  forceinline bool
  IterVal::operator()(void) const {
    return l != NULL;
  }
  forceinline void
  IterVal::operator++(void) {
    l=l->val_next;
  }
  forceinline int
  IterVal::val(void) const {
    assert(!l->marked());
    return l->val;
  }




  /**
   * \brief Class for index-value map
   *
   */
  class IdxValMap {
  private:
    /// Sorting pointers to (index,value) pairs in value order
    class ByVal {
    public:
      bool operator()(IdxValLink*&, IdxValLink*&);
    };
    size_t _size;
    IdxValLink iv[1];
  public:
    /// Allocating and initializing the data structure
    static IdxValMap* allocate(int);
    template <class ViewA> void init(int*,ViewA);

    /// Pruning from variables on data structure
    template <class ViewA> void prune_idx(ViewA);
    template <class ViewB> void prune_val(ViewB);

    /// Telling data structure to variables: returns true if at fixpoint
    template <class ViewA, class ViewB>
    ExecStatus tell(Space*,ViewA,ViewB);

    size_t size(void) const;
    static void operator delete(void* p,size_t);
  private:
    static void* operator new(size_t);
  };

  forceinline bool
  IdxValMap::ByVal::operator()(IdxValLink*& x, IdxValLink*& y) {
    return x->val < y->val;
  }

  forceinline IdxValMap*
  IdxValMap::allocate(int n) {
    size_t s = sizeof(IdxValMap)+n*sizeof(IdxValLink);
    IdxValMap* ivm = reinterpret_cast<IdxValMap*>(Memory::malloc(s));
    ivm->_size = s;
    return ivm;
  }

  forceinline size_t
  IdxValMap::size(void) const {
    return _size;
  }

  template <class ViewA>
  inline void
  IdxValMap::init(int* a, ViewA ix) {
    // The first element in iv[0] is used as sentinel
    // Enter information sorted by idx
    IdxValLink* by_idx = &iv[1];
    {
      int i = 0;
      ViewValues<ViewA> v(ix);
      while (v()) {
	by_idx[i].idx = v.val();
	by_idx[i].val = a[v.val()];
	++i; ++v;
      }
    }
    int size = ix.size();
    // Create val links sorted by val
    GECODE_AUTOARRAY(IdxValLink*,by_val,size);
    for (int i = size; i--; )
      by_val[i] = &iv[i+1];
    ByVal lt;
    Support::quicksort<IdxValLink*>(by_val,size,lt);
    // Create idx and val links
    for (int i = size-1; i--; ) {
      by_idx[i].idx_next  = by_idx+i+1;
      by_val[i]->val_next = by_val[i+1];
    }
    by_idx[size-1].idx_next  = NULL;
    by_val[size-1]->val_next = NULL;
    // Set up sentinel element: iv[0]
    iv[0].idx_next = &by_idx[0];
    iv[0].val_next = by_val[0];
  }

  template <class ViewA>
  forceinline void
  IdxValMap::prune_idx(ViewA x0) {
    IdxValLink* p = &iv[0];
    IdxValLink* l = p->idx_next;
    ViewRanges<ViewA> i(x0);
    while (i() && (l != NULL)) {
      assert(!l->marked());
      if (l->idx < i.min()) {
	l->mark(); l=l->idx_next; p->idx_next=l;
      } else if (l->idx > i.max()) {
	++i;
      } else {
	p=l; l=l->idx_next;
      }
    }
    p->idx_next = NULL;
    while (l != NULL) { l->mark(); l=l->idx_next; }
  }

  template <class ViewB>
  forceinline void
  IdxValMap::prune_val(ViewB x1) {
    IdxValLink* p = &iv[0];
    IdxValLink* l = p->val_next;
    ViewRanges<ViewB> v(x1);
    while (v() && (l != NULL)) {
      if (l->marked()) {
	l=l->val_next; p->val_next=l;
      } else if (l->val < v.min()) {
	l->mark(); l=l->val_next; p->val_next=l;
      } else if (l->val > v.max()) {
	++v;
      } else {
	p=l; l=l->val_next;
      }
    }
    p->val_next = NULL;
    while (l != NULL) { l->mark(); l=l->val_next; }
  }

  template <class ViewA, class ViewB>
  forceinline ExecStatus
  IdxValMap::tell(Space* home, ViewA x0, ViewB x1) {
    IterIdx i(iv[0]);
    if (!i())
      return ES_FAILED;
    Iter::Values::ToRanges<IterIdx> ri(i);
    x0.narrow(home,ri);
    IterVal v(iv[0]); Iter::Values::ToRanges<IterVal> rv(v);
    ExecStatus es = x1.modified() ? ES_NOFIX : ES_FIX;
    x1.narrow(home,rv);
    return es;
  }

  forceinline void
  IdxValMap::operator delete(void* p,size_t) {
    Memory::free(p);
  }




  /*
   * Element propagator proper
   *
   */


  template <class ViewA, class ViewB>
  forceinline
  Int<ViewA,ViewB>::Int(Space* home, IntSharedArray& c0, ViewA y0, ViewB y1)
    : Propagator(home,true), x0(y0), x1(y1), c(c0), ivm(NULL) {
    x0.subscribe(home,this,PC_INT_DOM);
    x1.subscribe(home,this,PC_INT_DOM);
  }

  template <class ViewA, class ViewB>
  ExecStatus
  Int<ViewA,ViewB>::post(Space* home, IntSharedArray& c, ViewA x0, ViewB x1) {
    GECODE_ME_CHECK(x0.gq(home,0));
    GECODE_ME_CHECK(x0.le(home,c.size()));
    (void) new (home) Int<ViewA,ViewB>(home,c,x0,x1);
    return ES_OK;
  }


  template <class ViewA, class ViewB>
  size_t
  Int<ViewA,ViewB>::dispose(Space* home) {
    if (!home->failed()) {
      x0.cancel(home,this,PC_INT_DOM);
      x1.cancel(home,this,PC_INT_DOM);
    }
    c.~IntSharedArray();
    delete ivm;
    (void) Propagator::dispose(home);
    return sizeof(*this);
  }

  template <class ViewA, class ViewB>
  void
  Int<ViewA,ViewB>::flush(void) {
    delete ivm; ivm = NULL;
  }

  template <class ViewA, class ViewB>
  size_t
  Int<ViewA,ViewB>::size(void) const {
    return (ivm != NULL) ? ivm->size() : 0;
  }

  template <class ViewA, class ViewB>
  forceinline
  Int<ViewA,ViewB>::Int(Space* home, bool share, Int& p)
    : Propagator(home,share,p), ivm(NULL) {
    c.update(share,p.c);
    x0.update(home,share,p.x0);
    x1.update(home,share,p.x1);
  }

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


  template <class ViewA, class ViewB>
  PropCost
  Int<ViewA,ViewB>::cost(void) const {
    return PC_BINARY_HI;
  }

  template <class ViewA, class ViewB>
  ExecStatus
  Int<ViewA,ViewB>::propagate(Space* home) {
    if (ivm == NULL) {
      ivm = IdxValMap::allocate(x0.size());
      ivm->init(&c[0],x0);
    } else {
      ivm->prune_idx(x0);
    }
    ivm->prune_val(x1);

    ExecStatus es = ivm->tell(home,x0,x1);
    if (es == ES_FAILED)
      return ES_FAILED;

    return (x0.assigned() || x1.assigned()) ? ES_SUBSUMED : es;
  }

}}}


// STATISTICS: int-prop