---

more/gen/binary_heap.h

Go to the documentation of this file.

//  Copyright (C) 2001  Petter Urkedal (petter.urkedal@matfys.lth.se)
//
//  This file is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//
//  This file is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
//  As a special exception, you may use this file as part of a free
//  software library without restriction.  Specifically, if other files
//  instantiate templates or use macros or inline functions from this
//  file, or you compile this file and link it with other files to
//  produce an executable, this file does not by itself cause the
//  resulting executable to be covered by the GNU General Public
//  License.  This exception does not however invalidate any other
//  reasons why the executable file might be covered by the GNU General
//  Public License.
//
//  $Id: binary_heap.h,v 1.1 2002/05/30 18:01:37 petter_urkedal Exp $


#ifndef MORE_GEN_BINARY_HEAP_H
#define MORE_GEN_BINARY_HEAP_H

#include <algorithm>
#include <functional>

namespace more {
namespace gen {

  template< typename T, typename Prec = std::less<T> >
    struct binary_heap {
        typedef std::size_t size_type;
        typedef std::ptrdiff_t difference;

        binary_heap() : n(0), n_max(16), p(new T[n_max] - 1) {}
        ~binary_heap() { delete[] (p + 1); }

        void insert(T const& x);
        T const& front() const { return p[1]; }
        void pop_front();
        bool empty() const { return n == 0; }
      private:
        void expand();
        size_type n;
        size_type n_max;
        T* p;
        Prec prec;
    };

  template<typename T, typename Prec>
    inline void
    binary_heap<T, Prec>::insert(T const& x) {
        size_type i = ++n;
        if (n >= n_max)
            expand();
        while (i > 1 && prec(x, p[i/2])) {
            p[i] = p[i/2];
            i /= 2;
        }
        p[i] = x;
    }

  template<typename T, typename Prec>
    inline void
    binary_heap<T, Prec>::expand() {
        T* old = p;
        n_max *= 2;
        p = new T[n_max] - 1;
        std::copy(old + 1, old + n + 1, p + 1);
        delete[] (old + 1);
    }

  template<typename T, typename Prec>
    inline void
    binary_heap<T, Prec>::pop_front() {
        size_type i = 1;
        for (;;) {
            size_type j = i*2;
            if (j >= n) {
                p[i] = p[n];
                break;
            }
            if (prec(p[j + 1], p[j]))
                ++j;
            if (!prec(p[j], p[n])) {
                p[i] = p[n];
                break;
            }
            p[i] = p[j];
            i = j;
        }
        --n;
    }
}}

#endif

---