Skip to content
Snippets Groups Projects
JarJarPQ.h 1.36 KiB
Newer Older
Marcus M. Darden's avatar
Marcus M. Darden committed
#ifndef JARJAR_PQ_H
#define JARJAR_PQ_H

#include "Eecs281PQ.h"

#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>

//A bad priority queue that linearly searches for the maximum element every
//time it is requested. You do not need to implement this; it is already done
//for you.
template<typename TYPE, typename COMP_FUNCTOR = std::less<TYPE>>
class JarJarPQ  : public Eecs281PQ<TYPE, COMP_FUNCTOR> {
public:
    typedef unsigned size_type;

    template<typename InputIterator>
    JarJarPQ(InputIterator start, InputIterator end, COMP_FUNCTOR comp = COMP_FUNCTOR())
        : data(start, end)
    {
        this->compare = comp;
    }

    JarJarPQ(COMP_FUNCTOR comp = COMP_FUNCTOR()) {
        this->compare = comp;
    }

    virtual void push(const TYPE& val) {
        data.push_back(val);
    }

    virtual void pop() {
        assert(!data.empty());

        typename std::vector<TYPE>::iterator it = std::max_element(data.begin(), data.end(), this->compare);
        std::iter_swap(it, std::prev(data.end()));
        data.pop_back();
    }

    virtual const TYPE& top() const {
        return *std::max_element(data.begin(), data.end(), this->compare);
    }

    virtual size_type size() const {
        return data.size();
    }

    virtual bool empty() const {
        return data.empty();
    }

private:
    std::vector<TYPE> data;
};

#endif