LimitedHeap.h

Go to the documentation of this file.

#ifndef __GfxTL_LIMITEDHEAP_HEADER__
#define __GfxTL_LIMITEDHEAP_HEADER__
#include <algorithm>
#include <functional>
#include <vector>
 
#include <GfxTL/FlatCopyVector.h>
#include <GfxTL/StdContainerAdaptor.h>
 
namespace GfxTL
{
    template <class T,
              class PredicateT = std::less<T>,
              template <class> class ContainerT = FlatCopyVector>
    class LimitedHeap : public ContainerT<T>
    {
    public:
        typedef typename ContainerT<T>::value_type value_type;
        typedef typename ContainerT<T>::size_type size_type;
        typedef PredicateT PredicateType;
        typedef ContainerT<T> BaseType;
 
        LimitedHeap() : _limit(-1), _instances(0)
        {
        }
 
        LimitedHeap(size_type limit) : _limit(limit), _instances(0)
        {
            BaseType::reserve(limit);
        }
 
        LimitedHeap(const PredicateType& pred) : m_pred(pred), _limit(-1), _instances(0)
        {
            BaseType::reserve(_limit);
        }
 
        LimitedHeap(size_type limit, const PredicateType& pred) :
            m_pred(pred), _limit(limit), _instances(0)
        {
            BaseType::reserve(limit);
        }
 
        void
        Limit(size_type limit)
        {
            _limit = limit;
            BaseType::reserve(limit + 1);
        }
 
        size_type
        Limit() const
        {
            return _limit;
        }
 
        void
        Predicate(const PredicateType& pred)
        {
            m_pred = pred;
        }
 
        const PredicateType&
        Predicate() const
        {
            return m_pred;
        }
 
        void
        clear()
        {
            BaseType::clear();
            _instances = 0;
        }
 
        void
        MakeHeap()
        {
            size_type iend = BaseType::size();
            for (size_type i = BaseType::size() >> 1; i > 0; --i)
            {
                Heapify(i - 1, iend);
            }
        }
 
        void
        SortHeap()
        {
            if (!BaseType::size())
            {
                return;
            }
            for (size_type i = BaseType::size() - 1; i > 0; --i)
            {
                T tmp = BaseType::at(i);
                BaseType::at(i) = BaseType::at(0);
                BaseType::at(0) = tmp;
                Heapify(0, i);
            }
        }
 
        void
        AssertHeap()
        {
            if (BaseType::size() < _limit)
            {
                MakeHeap();
            }
        }
 
        void
        PushHeap(const value_type& t)
        {
            if (BaseType::size() < _limit)
            {
                BaseType::push_back(t);
                if (BaseType::size() == _limit)
                {
                    MakeHeap();
                    _instances = CountInstances(0);
                }
            }
            else
            {
                if (m_pred(BaseType::front(), t)) // front < t
                {
                    return; // t > front
                }
                if (m_pred(t, BaseType::front())) // t < front?
                {
                    if (_instances > 1)
                    {
                        if (BaseType::size() + 1 - _instances >= _limit)
                        {
                            // remove instances
                            for (size_type i = 0; i < _instances; ++i)
                            {
                                std::swap(BaseType::front(), BaseType::back());
                                BaseType::pop_back();
                                Heapify(0, BaseType::size());
                            }
                            BaseType::push_back(t);
                            BubbleDown();
                            _instances = CountInstances(0);
                            return;
                        }
                        BaseType::push_back(t);
                        BubbleDown();
                        return;
                    }
                    BaseType::front() = t;
                    Heapify(0, BaseType::size());
                    _instances = CountInstances(0);
                    return;
                }
                // t == front;
                BaseType::push_back(t);
                BubbleDown();
                ++_instances;
            }
        }
 
    private:
        void
        Heapify(size_type i, size_type iend)
        {
            using namespace std;
            size_type max;
            while ((max = (i << 1) + 1) < iend)
            {
                if (max + 1 < iend && m_pred(BaseType::at(max), BaseType::at(max + 1)))
                {
                    ++max;
                }
                if (!m_pred(BaseType::at(i), BaseType::at(max)))
                {
                    break;
                }
                std::swap(BaseType::at(i), BaseType::at(max));
                i = max;
            }
        }
 
        void
        BubbleDown()
        {
            using namespace std;
            if (BaseType::size() == 1)
            {
                return;
            }
            size_type i = BaseType::size() - 1, j;
            while (i && m_pred(BaseType::at(j = ((i + 1) >> 1) - 1), BaseType::at(i)))
            {
                std::swap(BaseType::at(i), BaseType::at(j));
                i = j;
            }
        }
 
        size_type
        CountInstances(size_type i) const
        {
            size_type child = (i << 1) + 1;
            if (child >= BaseType::size())
            {
                return 1;
            }
            size_type instances = 0;
            if (!m_pred(BaseType::at(child), BaseType::at(i)))
            {
                instances = CountInstances(child);
            }
            ++child;
            if (child >= BaseType::size())
            {
                return 1 + instances;
            }
            if (!m_pred(BaseType::at(child), BaseType::at(i)))
            {
                instances += CountInstances(child);
            }
            return 1 + instances;
        }
 
    private:
        PredicateType m_pred;
        size_type _limit;
        size_type _instances;
    };
 
    template <class T, template <class> class ContainerT = FlatCopyVector>
    class AssumeUniqueLimitedHeap : public ContainerT<T>
    {
    public:
        typedef typename ContainerT<T>::value_type value_type;
        typedef typename ContainerT<T>::size_type size_type;
        typedef ContainerT<T> BaseType;
 
        AssumeUniqueLimitedHeap() : _limit(-1)
        {
        }
 
        AssumeUniqueLimitedHeap(size_type limit) : _limit(limit)
        {
            BaseType::reserve(limit);
        }
 
        void
        Limit(size_type limit)
        {
            _limit = limit;
            BaseType::reserve(limit + 1);
        }
 
        size_type
        Limit() const
        {
            return _limit;
        }
 
        void
        MakeHeap()
        {
            size_type iend = BaseType::size();
            for (size_type i = BaseType::size() >> 1; i > 0; --i)
            {
                Heapify(i - 1, iend);
            }
        }
 
        void
        SortHeap()
        {
            if (!BaseType::size())
            {
                return;
            }
            for (size_type i = BaseType::size() - 1; i > 0; --i)
            {
                T tmp = BaseType::at(i);
                BaseType::at(i) = BaseType::at(0);
                BaseType::at(0) = tmp;
                Heapify(0, i);
            }
        }
 
        void
        AssertHeap()
        {
            if (BaseType::size() < _limit)
            {
                MakeHeap();
            }
        }
 
        void
        PushHeap(const value_type& t)
        {
            if (BaseType::size() < _limit)
            {
                BaseType::push_back(t);
                if (BaseType::size() == _limit)
                {
                    MakeHeap();
                }
            }
            else
            {
                if (t >= BaseType::front())
                {
                    return;
                }
                BaseType::front() = t;
                Heapify(0, BaseType::size());
            }
        }
 
    private:
        void
        Heapify(size_type i, size_type iend)
        {
            size_type max;
            while ((max = (i << 1) + 1) < iend)
            {
                if (max + 1 < iend && BaseType::at(max) < BaseType::at(max + 1))
                {
                    ++max;
                }
                if (BaseType::at(i) >= BaseType::at(max))
                {
                    break;
                }
                std::swap(BaseType::at(i), BaseType::at(max));
                i = max;
            }
        }
 
        void
        BubbleDown()
        {
            if (BaseType::size() == 1)
            {
                return;
            }
            size_type i = BaseType::size() - 1, j;
            while (i && BaseType::at(i) > BaseType::at(j = ((i + 1) >> 1) - 1))
            {
                std::swap(BaseType::at(i), BaseType::at(j));
                i = j;
            }
        }
 
    private:
        size_type _limit;
    };
}; // namespace GfxTL
 
#endif