pe_queue.h

#ifndef PE_QUEUE_H_
#define PE_QUEUE_H_

#include "typedefs.h"

class LPChare;
struct LPToken;

// Priority queue of LPToken pointers weighted by timestamp. The heap is
// maintained as an array of LPToken pointers. The pointers are not owned by the
// queue. The queue must update the index and timestamp entries in the token.
// This allows us to find an entry in the heap in constant time when given a
// pointer to an LPToken, allowing us to update the token with a new timestamp
// and reposition it in the queue accordingly.
class PEQueue {
  private:
    unsigned capacity, size;
    LPToken** heap;

    // Swaps the queue entries at the two indices and updates their index fields.
    void swap(unsigned, unsigned);

    // Repositions entries located at the given index.
    void pull_up(unsigned);
    void push_down(unsigned);

    // Compares the entries at the given indices, and returns the index of the
    // smallest entry.
    unsigned smallest(unsigned, unsigned) const;
    unsigned largest(unsigned, unsigned) const;

    // Helper methods for accessing parents and children based on indices.
    bool has_parent(unsigned) const;
    bool has_left(unsigned) const;
    bool has_right(unsigned) const;
    unsigned parent(unsigned) const;
    unsigned left(unsigned) const;
    unsigned right(unsigned) const;
  public:
    PEQueue();
    ~PEQueue();

    // Returns the token on top of the queue.
    // TODO: We may also want to be able to see the second token.
    LPToken* top() const;
    LPToken* second() const;

    // Inserts and removes tokens from the queue.
    void insert(LPToken*, Time);
    void remove(LPToken*);

    // Updates the given token with a new timestamp, and repositions it.
    void update(LPToken*, Time);

    // TODO: Temporary direct access for iteration purposes
    int get_size() const { return size; }
    LPToken** as_array() const { return heap; }
};

#endif