Colony » Colony Scout

#include "Order.h"

using namespace std;

/** @Brief: Default order constructor */

Order::Order()

{

    orderID = 0;

    orderSource = 0;

    orderDest = 0;

    orderDeadline = 0;

    orderStartTime = 0;

    orderPath = 0;

    orderEstTime = 0; 

}

/** @Brief: Regular order constructor */

Order::Order(int ID, Address source, Address dest, int deadline, int start_time, Path path, int est_time) { 

    orderID = ID;

    orderSource = source;

    orderDest = dest;

    orderDeadline = deadline;

    orderStartTime = start_time;

    orderPath = path;

    orderEstTime = est_time;

}

/** @Brief: Get priority for the PQWrapper */

int Order::getpriority() const { 

    return orderDeadline - orderStartTime; 

}

/** @Brief: Get order ID */

int Order::getid() const {

    return orderID;

}  

/** @Brief: Order comparison function for PQWrapper */

bool CompareOrder::operator()(Order& o1, Order& o2) {

    return o1.getpriority() > o2.getpriority();

}

#ifndef _ORDER_

#define _ORDER_

typedef unsigned int Address;

typedef unsigned int Path;

class Order {

    int orderID;

    Address orderSource, orderDest;

    int orderDeadline, orderStartTime;

    Path orderPath;

    int orderEstTime;

public:

    Order();

    Order(int ID, Address source, Address dest, int deadline, int start_time, Path path, int est_time);

    int getpriority() const;

    int getid() const;

};

class CompareOrder {

    public:

        bool operator()(Order& o1, Order& o2);

};

#endif

#include "PQWrapper.h"

using namespace std;

/** @Brief: Initialize PQWrapper data structures. */

PQWrapper::PQWrapper(unsigned int numElems)

{

    minElems = new Order[numElems];

    arrCapacity = numElems;

    arrContents = 0;

}

/** @Brief: Free allocatetd memory. */

PQWrapper::~PQWrapper()

{

    while (!pq.empty()) pq.pop();

}

/** @Brief: Insert an order into the PQWrapper. */

void PQWrapper::insert(Order o)

{

    int position=0;

    bool foundPosition = false;

    while (!foundPosition && position < arrContents)

    {

        if (o.getpriority() < minElems[position].getpriority()) 

        {

            foundPosition=true;

        } 

        else 

        {

            position++;

        }

    }

    if (foundPosition)

    {

        if (arrContents<arrCapacity)

        {

            for (int i = arrContents; i >=position+1; i--) 

            {

                minElems[i] = minElems[i-1];

            }            

            minElems[position] = o;

            arrContents++;

        } 

        else 

        {

            pq.push(minElems[arrCapacity-1]);

            for (int i = arrContents-1; i >= position+1; i--) 

            {

                minElems[i] = minElems[i-1];

            }            

            minElems[position] = o;

        }

    } 

    else 

    {     

        if (arrContents<arrCapacity) 

        {

            minElems[arrContents] = o;

            arrContents++;

        } else {

            pq.push(o);

        }

    }

}

/** @Brief: Remove and return an Order from the array if 0 <= index < arrContents. */

Order PQWrapper::remove(unsigned int index)

{

    if (index >= arrContents) return minElems[-1];//TODO: can I return null?

    Order toDelete = minElems[index];

    for (int i = index; i < arrContents - 1; i++) 

    {

        minElems[i] = minElems[i+1];

    }

    if (!pq.empty()) 

    {

        minElems[arrContents-1] = pq.top();

        pq.pop();

    } 

    else 

    {

        arrContents--;

    }

    return toDelete;

}

/** @Brief: Return an Order from the array if 0 <= index < arrContents */

Order PQWrapper::peek(unsigned int index) const

{

    if (index >= arrContents)

    {

        return minElems[-1];//TODO: can I return null?

    } 

    else 

    {

        return minElems[index];

    }

}

/** @Brief: Return the size of the minElems array */

unsigned int PQWrapper::arraySize() const

{

    return arrContents;

}

/*

//For testing purposes only

int main() {

    Order a(1,0,0,101,0,0,0);

    Order b(2,0,0,11,0,0,0);

    Order c(3,0,0,91,0,0,0);

    Order d(4,0,0,21,0,0,0);

    Order e(5,0,0,41,0,0,0);

    Order f(6,0,0,81,0,0,0);

    Order g(7,0,0,31,0,0,0);

    Order h(8,0,0,71,0,0,0);

    Order i(9,0,0,51,0,0,0);

    Order j(10,0,0,61,0,0,0);

    PQWrapper pqw(5);

    pqw.insert(a);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(b);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(c);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(d);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(e);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(f);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(g);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(h);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(i);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    pqw.insert(j);

    for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

    cout << endl; 

    for (int i=0;i<10;i++) 

    {

        pqw.remove(0);

        for (int i=0;i<pqw.arraySize();i++) cout << pqw.peek(i).getid() << " ";

        cout << endl; 

    }

    return 0;

}

*/

#ifndef _PQ_WRAPPER_

#define _PQ_WRAPPER_

#include <cstdlib>

#include <queue>

#include <iostream>

#include "Order.h"

class PQWrapper

{

    public:

        PQWrapper(unsigned int numElems);

        ~PQWrapper();

        void insert(Order o);

        Order remove(unsigned int index);

        Order peek(unsigned int index) const;

        unsigned int arraySize() const;

    private:

        Order* minElems;

        unsigned int arrCapacity, arrContents;

        std::priority_queue<Order,std::vector<Order>, CompareOrder> pq;

};

#endif