/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2004
 *
 *  Last modified:
 *     $Date: 2008-01-31 18:29:16 +0100 (Thu, 31 Jan 2008) $ by $Author: tack $
 *     $Revision: 6017 $
 *
 *  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.
 *
 */

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 = static_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]);
    GECODE_ME_CHECK(x0.narrow_v(home,i,false));
    IterVal v(iv[0]);
    if (shared(x0,x1)) {
      GECODE_ME_CHECK(x1.inter_v(home,v,false));
      return ES_NOFIX;
    } else {
      GECODE_ME_CHECK(x1.narrow_v(home,v,false));
      return ES_FIX;
    }
  }

  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), x0(y0), x1(y1), c(c0), ivm(NULL) {
    force(home);
    x0.subscribe(home,this,PC_INT_DOM);
    x1.subscribe(home,this,PC_INT_DOM);
  }

  template <class ViewA, class ViewB>
  forceinline size_t
  Int<ViewA,ViewB>::dispose(Space* home) {
    unforce(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>
  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()));
    if (x0.assigned()) {
      GECODE_ME_CHECK(x1.eq(home,c[x0.val()]));
    } else {
      (void) new (home) Int<ViewA,ViewB>(home,c,x0,x1);
    }
    return ES_OK;
  }


  template <class ViewA, class ViewB>
  size_t
  Int<ViewA,ViewB>::allocated(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(home,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(ModEventDelta) const {
    return PC_BINARY_HI;
  }

  template <class ViewA, class ViewB>
  inline Support::Symbol
  Int<ViewA,ViewB>::ati(void) {
    return Reflection::mangle<ViewA,ViewB>("Gecode::Int::Element::Int");
  }

  template <class ViewA, class ViewB>
  Reflection::ActorSpec
  Int<ViewA,ViewB>::spec(const Space* home, Reflection::VarMap& m) const {
    Reflection::ActorSpec s(ati());
    return s << x0.spec(home, m)
             << x1.spec(home, m)
             << Reflection::Arg::newIntArray(c);
  }

  template <class ViewA, class ViewB>
  void
  Int<ViewA,ViewB>::post(Space* home, Reflection::VarMap& vars,
                         const Reflection::ActorSpec& spec) {
    spec.checkArity(3);
    ViewA x0(home, vars, spec[0]);
    ViewB x1(home, vars, spec[1]);
    Reflection::IntArrayArg* a = spec[2]->toIntArray();
    IntSharedArray is(a->size());
    for (int i=a->size(); i--; ) {
      is[i] = (*a)[i];
    }
    (void) new (home) Int<ViewA,ViewB>(home, is, x0, x1);
  }

  template <class ViewA, class ViewB>
  ExecStatus
  Int<ViewA,ViewB>::propagate(Space* home, ModEventDelta) {
    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(this,home) : es;
  }

}}}


// STATISTICS: int-prop