main page modules namespaces classes files
Gecode home

search for 

static-pqueue.hh

Go to the documentation of this file.

/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *     Guido Tack <tack@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2002
 *     Guido Tack, 2004
 *
 *  Last modified:
 *     $Date: 2006-08-04 16:05:34 +0200 (Fri, 04 Aug 2006) $ by $Author: schulte $
 *     $Revision: 3514 $
 *
 *  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.
 *
 */

#ifndef __GECODE_SUPPORT_PQUEUE_HH__
#define __GECODE_SUPPORT_PQUEUE_HH__

#include "gecode/kernel.hh"

#include <cassert>
#include <algorithm>

/*
 * The shared queue
 *
 */

namespace Gecode { namespace Support {

  template <class T, class Less>
  class PQueue  {
  private:
    class SharedPQueue  {
    public:
      int n;
      int size;
      unsigned int ref;
      Less l;
      T pq[1];

      static SharedPQueue* allocate(int n, const Less& l);
      void fixdown(void);
      void fixup(int n);
    };
    SharedPQueue* spq;

  public:
    PQueue(void);
    PQueue(int n, const Less& l);
    void init(int, const Less&);
    PQueue(const PQueue& p);
    const PQueue& operator=(const PQueue&);
    ~PQueue(void);

    bool empty(void) const;
    void insert(const T& x);
    void remove(void);
    T& top(void);
    void fix(void);

    void update(const PQueue<T,Less>& p, bool share);
  };

  template <class T, class Less>
  forceinline typename PQueue<T,Less>::SharedPQueue*
  PQueue<T,Less>::SharedPQueue::allocate(int n, const Less& l) {
    SharedPQueue* spq
      = reinterpret_cast<SharedPQueue*>
      (Memory::malloc(sizeof(SharedPQueue) + (n-1)*sizeof(T)));
    spq->size = n;
    spq->n    = 0;
    spq->ref  = 1;
    spq->l    = l;
    return spq;
  }

  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::SharedPQueue::fixdown(void) {
    int k = 0;
    while ((k << 1) < n) {
      int j = k << 1;
      if (j < n-1 && l(pq[j],pq[j+1]))
        j++;
      if (!l(pq[k],pq[j]))
        break;
      std::swap(pq[k], pq[j]);
      k = j;
    }
  }

  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::SharedPQueue::fixup(int k) {
    while (k > 0 && l(pq[k >> 1],pq[k])) {
      std::swap(pq[k],pq[k >> 1]);
      k >>= 1;
    }
  }

  template <class T, class Less>
  forceinline
  PQueue<T,Less>::PQueue(void)
    : spq(NULL) {}

  template <class T, class Less>
  forceinline
  PQueue<T,Less>::PQueue(int n, const Less& l)
    : spq(SharedPQueue::allocate(n,l)) {}

  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::init(int n, const Less& l) {
    spq = SharedPQueue::allocate(n,l);
  }

  template <class T, class Less>
  forceinline
  PQueue<T,Less>::PQueue(const PQueue<T,Less>& p)
    : spq(p.spq) {
    if (spq != NULL)
      spq->ref++;
  }

  template <class T, class Less>
  forceinline const PQueue<T,Less>&
  PQueue<T,Less>::operator =(const PQueue<T,Less>& p) {
    if (this != &p) {
      if ((spq != NULL) && (--spq->ref == 0))
        Memory::free(spq);
      spq = p.spq;
      if (spq != NULL)
        spq->ref++;
    }
    return *this;
  }

  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::update(const PQueue<T,Less>& p, bool share) {
    if (share) {
      spq = p.spq;
      if (spq != NULL)
        spq->ref++;
    } else {
      if (p.spq != NULL) {
        spq = allocate(p.spq->n,p.spq->l);
      } else {
        spq = NULL;
      }
    }
  }

  template <class T, class Less>
  forceinline
  PQueue<T,Less>::~PQueue(void) {
    if ((spq != NULL) && (--spq->ref == 0))
      Memory::free(spq);
  }

  template <class T, class Less>
  forceinline bool
  PQueue<T,Less>::empty(void) const {
    return (spq == NULL) || (spq->n == 0);
  }


  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::insert(const T& x) {
    spq->pq[spq->n++] = x;
    spq->fixup(spq->n-1);
  }

  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::remove(void) {
    spq->pq[0] = spq->pq[--spq->n];
    spq->fixdown();
  }

  template <class T, class Less>
  forceinline T&
  PQueue<T,Less>::top(void) {
    return spq->pq[0];
  }

  template <class T, class Less>
  forceinline void
  PQueue<T,Less>::fix(void) {
    spq->fixdown();
  }

}}

#endif

// STATISTICS: support-any