Heap.h

#pragma once


#include <libutl/Collection.h>
#include <libutl/Vector.h>


UTL_NS_BEGIN;


class HeapIt;



class Heap : public Collection
{
    UTL_CLASS_DECL(Heap, Collection);
    friend class HeapIt;

public:
    typedef HeapIt iterator;

public:
    Heap(size_t size,
         size_t increment = size_t_max,
         bool owner = true,
         bool multiSet = true,
         Ordering* ordering = nullptr)
    {
        init(size, increment, owner, multiSet, ordering);
    }

    Heap(bool owner, bool multiSet = true)
    {
        init(16, size_t_max, owner, multiSet);
    }

    virtual void steal(Object& rhs);

    virtual size_t innerAllocatedSize() const;



    void
    reserve(size_t newSize)
    {
        _array.grow(newSize);
    }


    virtual Object* find(const Object& key) const;

    iterator findIt(const Object& key) const;

    iterator findIt(const Object& key);

    void
    findIt(const Object& key, BidIt& it) const
    {
        const_cast_this->findIt(key, it);
        IFDEBUG(it.setConst(true));
    }

    virtual void findIt(const Object& key, BidIt& it);

    Object*
    getMax() const
    {
        if (_items == 0)
            return nullptr;
        else
            return _array[0];
    }


    bool
    add(const Object& object)
    {
        return super::add(object);
    }

    virtual bool add(const Object* object);

    void
    add(const Collection& collection)
    {
        super::add(collection);
    }



    virtual void clear();

    Object* pop();

    bool
    remove(const Object* key)
    {
        ASSERTD(key != nullptr);
        return remove(*key);
    }

    virtual bool remove(const Object& key);

    virtual void removeIt(BidIt& it);


    inline iterator begin() const;

    inline iterator begin();

    inline virtual BidIt* beginNew() const;

    inline virtual BidIt* beginNew();

    inline iterator end() const;

    inline iterator end();

    inline virtual BidIt* endNew() const;

    inline virtual BidIt* endNew();

private:
    void init(size_t size = 16,
              size_t increment = size_t_max,
              bool owner = true,
              bool multiSet = true,
              Ordering* ordering = nullptr);

    void deInit();

    inline int
    compareObjects(const Object* lhs, const Object* rhs) const
    {
        return super::compareObjects(lhs, rhs);
    }

    void find(const Object& key, size_t& idx) const;

    void removeIdx(size_t idx);

    void swapUp(size_t idx);

    void swapDown(size_t idx);

private:
    Vector<Object*> _array;
};


UTL_NS_END;


#include <libutl/THeap.h>