heap.h

/********************************************************************
 * Copyright (C) 2015 Liangliang Nan <liangliang.nan@gmail.com>
 * https://3d.bk.tudelft.nl/liangliang/
 *
 * This file is part of Easy3D. If it is useful in your research/work,
 * I would be grateful if you show your appreciation by citing it:
 * ------------------------------------------------------------------
 *      Liangliang Nan.
 *      Easy3D: a lightweight, easy-to-use, and efficient C++ library
 *      for processing and rendering 3D data.
 *      Journal of Open Source Software, 6(64), 3255, 2021.
 * ------------------------------------------------------------------
 *
 * Easy3D is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License Version 3
 * as published by the Free Software Foundation.
 *
 * Easy3D 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, see <http://www.gnu.org/licenses/>.
 ********************************************************************/
 
#ifndef EASY3D_CORE_HEAP_H
#define EASY3D_CORE_HEAP_H
 
#include <vector>
 
namespace easy3d {
 
    template<class HeapEntry, class HeapInterface>
    class Heap : private std::vector<HeapEntry> {
    public:
        typedef Heap<HeapEntry, HeapInterface> This;
 
        Heap() : HeapVector() {}
 
        explicit Heap(const HeapInterface &i) : HeapVector(), interface_(i) {}
 
        ~Heap() = default;
 
        void clear() { HeapVector::clear(); }
 
        bool empty() { return HeapVector::empty(); }
 
        unsigned int size() { return (unsigned int) HeapVector::size(); }
 
        void reserve(unsigned int n) { HeapVector::reserve(n); }
 
        void reset_heap_position(HeapEntry h) {
            interface_.set_heap_position(h, -1);
        }
 
        bool is_stored(HeapEntry h) {
            return interface_.get_heap_position(h) != -1;
        }
 
        void insert(HeapEntry h) {
            This::push_back(h);
            upheap(size() - 1);
        }
 
        HeapEntry front() {
            assert(!empty());
            return entry(0);
        }
 
        void pop_front() {
            assert(!empty());
            interface_.set_heap_position(entry(0), -1);
            if (size() > 1) {
                entry(0, entry(size() - 1));
                HeapVector::resize(size() - 1);
                downheap(0);
            } else
                HeapVector::resize(size() - 1);
        }
 
        void remove(HeapEntry h) {
            int pos = interface_.get_heap_position(h);
            interface_.set_heap_position(h, -1);
 
            assert(pos != -1);
            assert((unsigned int) pos < size());
 
            // last item ?
            if ((unsigned int) pos == size() - 1)
                HeapVector::resize(size() - 1);
 
            else {
                entry(pos, entry(size() - 1)); // move last elem to pos
                HeapVector::resize(size() - 1);
                downheap(pos);
                upheap(pos);
            }
        }
 
        void update(HeapEntry h) {
            int pos = interface_.get_heap_position(h);
            assert(pos != -1);
            assert((unsigned int) pos < size());
            downheap(pos);
            upheap(pos);
        }
 
        bool check() {
            bool ok(true);
            unsigned int i, j;
            for (i = 0; i < size(); ++i) {
                if (((j = left(i)) < size()) &&
                    interface_.greater(entry(i), entry(j))) {
                    std::cerr << "Heap condition violated\n";
                    ok = false;
                }
                if (((j = right(i)) < size()) &&
                    interface_.greater(entry(i), entry(j))) {
                    std::cerr << "Heap condition violated\n";
                    ok = false;
                }
            }
            return ok;
        }
 
    private:
        // typedef
        typedef std::vector<HeapEntry> HeapVector;
 
        void upheap(unsigned int idx) {
            HeapEntry h = entry(idx);
            unsigned int parentIdx;
 
            while ((idx > 0) && interface_.less(h, entry(parentIdx = parent(idx)))) {
                entry(idx, entry(parentIdx));
                idx = parentIdx;
            }
 
            entry(idx, h);
        }
 
        void downheap(unsigned int idx) {
            HeapEntry h = entry(idx);
            unsigned int childIdx;
            unsigned int s = size();
 
            while (idx < s) {
                childIdx = left(idx);
                if (childIdx >= s)
                    break;
 
                if ((childIdx + 1 < s) &&
                    (interface_.less(entry(childIdx + 1), entry(childIdx))))
                    ++childIdx;
 
                if (interface_.less(h, entry(childIdx)))
                    break;
 
                entry(idx, entry(childIdx));
                idx = childIdx;
            }
 
            entry(idx, h);
        }
 
        inline HeapEntry entry(unsigned int idx) {
            assert(idx < size());
            return (This::operator[](idx));
        }
 
        inline void entry(unsigned int idx, HeapEntry h) {
            assert(idx < size());
            This::operator[](idx) = h;
            interface_.set_heap_position(h, idx);
        }
 
        inline unsigned int parent(unsigned int i) { return (i - 1) >> 1; }
 
        inline unsigned int left(unsigned int i) { return (i << 1) + 1; }
 
        inline unsigned int right(unsigned int i) { return (i << 1) + 2; }
 
        HeapInterface interface_;
    };
 
//=============================================================================
} // namespace easy3d
 
#endif  // EASY3D_CORE_HEAP_H