APCDiGraph.cpp

#include "APCDiGraph.h"
#include "Utils.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <limits>

using namespace std;


//-------------------------------------------------------------------------------------------------
// Function Name:     APCDiGraph
// Purpose:           APCDiGraph default constructor that initializes data members
// Parameters:        none
// Returns:           none
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------
APCDiGraph::APCDiGraph()
{
    apcGraph.clear();
    apcCodes.clear();

    adjacencyMatrix = nullptr;

    start = 0;
    nodeCount = 0;
    weight = nullptr;
    path = nullptr;
    reachedSet.clear();
}


//-------------------------------------------------------------------------------------------------
// Function Name:     ~APCDiGraph
// Purpose:           ~APCDiGraph destructor performs house cleaning when node is destroyed
// Parameters:        none
// Returns:           none
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------
APCDiGraph::~APCDiGraph()
{
    apcGraph.clear();
    apcCodes.clear();

    if (adjacencyMatrix != nullptr)
        delete[] adjacencyMatrix;

    adjacencyMatrix = nullptr;

    initVars();
}


//-------------------------------------------------------------------------------------------------
// Function Name:     initVars
// Purpose:           initVars cleans variables used during the calculateShortestPath function
// Parameters:        none
// Returns:           none
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------
void APCDiGraph::initVars()
{
    if (weight != nullptr)
        delete weight;

    if (path != nullptr)
        delete[] path;

    start = 0;
    nodeCount = 0;
    weight = nullptr;
    path = nullptr;
    reachedSet.clear();
}


//-------------------------------------------------------------------------------------------------
// Function Name:     addNode
// Purpose:           addNode adds a new node to the graph if it isn't already there
// Parameters:        APCNode* apcNode is the node to add
// Returns:           true if the node was added, false otherwise
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------
bool APCDiGraph::addNode(APCNode* apcNode)
{
    if (apcNode == nullptr)
        return false;

    string key = apcNode->getKey();

    APCNodeIterator apcNodeRecord = apcGraph.find(key);

    if (apcNodeRecord != apcGraph.end())
        return false;

    apcGraph[key] = apcNode;
    apcCodes[Utils::toLower(apcNode->getOrigin())] = apcNode->getOrigin();

    return true;
}


//-------------------------------------------------------------------------------------------------------------
// Function Name:     printDiGraph
// Purpose:           displays the list of flights availble in the system
// Parameters:        none
// Returns:           none
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------------------
void APCDiGraph::printDiGraph()
{
    std::cout.imbue(std::locale(""));

    // print the digraph to the display
    cout << endl;
    cout << "Direct Flights" << endl;
    cout << "Source   Dest   Mileage     Cost  " << endl;
    cout << "------   ----   -------   --------" << endl;
    APCDiGraph::APCNodeIterator record = apcGraph.begin();
    while (record != apcGraph.end())
    {
        printDiGraphLine(record->second);
        record++;
    }
    cout << endl;
}


//-------------------------------------------------------------------------------------------------------------
// Function Name:     printDiGraphLine
// Purpose:           displays the formatted digraph information
//
// Parameters:        APCNode*
//
// Returns:           none
// Pre-conditions:    apcNode must be valid
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------------------
void APCDiGraph::printDiGraphLine(APCNode* apcNode)
{
    const int APC_ORIGIN_WIDTH = 6;
    const int APC_DEST_WIDTH = 4;
    const int MILEAGE_WIDTH = 7;
    const int COST_WIDTH = 7;
    const int SPACER_WIDTH = 3;

    if (apcNode == nullptr)
    {
        cout << endl;
        return;
    }

    cout.precision(0);

    // APC Origin
    cout.setf(ios::left, ios::adjustfield);
    cout << setw(APC_ORIGIN_WIDTH) << apcNode->getOrigin();

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // APC Destination
    cout.setf(ios::left, ios::adjustfield);
    cout << setw(APC_DEST_WIDTH) << apcNode->getDestination();

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // mileage
    cout.setf(ios::right, ios::adjustfield);
    cout << setw(MILEAGE_WIDTH) << apcNode->getMileage();

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // cost
    cout.setf(ios::right, ios::adjustfield);
    cout << setw(COST_WIDTH) << Utils::toCurrency(apcNode->getCost());

    cout << endl;
}


//-------------------------------------------------------------------------------------------------
// Function Name:     findAPC
// Purpose:           findAPC determines if a valid airport code is being used
// Parameters:        const string& apc contains the airport code to search for
// Returns:           true if the apc is valid, false otherwise
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------
bool APCDiGraph::findAPC(const string& apc)
{
    string apcLower = Utils::toLower(apc);

    APCCodeIterator apcCodeRecord = apcCodes.find(apcLower);

    if (apcCodeRecord == apcCodes.end())
        return false;

    return true;
}


//-------------------------------------------------------------------------------------------------
// Function Name:     createAdjacencyMatrix
// Purpose:           creates the adjacency matrix from the digraph nodes
// Parameters:        none
// Returns:           none
// Pre-conditions:    the nodes must have been read in and stored in the digraph
// Post-conditions:   the adjacencyMatrix is built and ready to use by the shortest path algorithm
//-------------------------------------------------------------------------------------------------
void APCDiGraph::createAdjacencyMatrix()
{
    int nodeCount = apcCodes.size();
    int totalNodeCount = nodeCount * nodeCount;

    if (adjacencyMatrix != nullptr)
    {
        delete[] adjacencyMatrix;
        adjacencyMatrix = nullptr;
    }

    adjacencyMatrix = new APCNode*[totalNodeCount];

    int memSize = sizeof(nullptr) * totalNodeCount;
    memset(adjacencyMatrix, 0, memSize);

    APCNodeIterator apcNodeRecord = apcGraph.begin();
    while (apcNodeRecord != apcGraph.end())
    {
        APCNode* apcNode = apcNodeRecord->second;

        // what row/column does this node fall into
        int row = findAPCIndex(apcNode->getOrigin());
        int col = findAPCIndex(apcNode->getDestination());

        if(row != -1 && col != -1)
            adjacencyMatrix[(row * nodeCount) + col] = apcNode;

        apcNodeRecord++;
    }
}


//-------------------------------------------------------------------------------------------------
// Function Name:     findAPCIndex
// Purpose:           findAPCIndex is an internal function used to convert apcCode to its index
// Parameters:        const string& apc contains the airport code to search for
// Returns:           the apc index in the APC codes list, -1 otherwise
// Pre-conditions:    apcCodes must have been created by adding apc nodes
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------
int APCDiGraph::findAPCIndex(const string& apcCode)
{
    string lowerAPCCode = Utils::toLower(apcCode);

    int index = 0;
    APCCodeIterator apcCodeRecord = apcCodes.begin();

    while (apcCodeRecord != apcCodes.end())
    {
        if (apcCodeRecord->first.compare(lowerAPCCode) == 0)
            return index;

        index++;
        apcCodeRecord++;
    }

    return -1;
}


//-------------------------------------------------------------------------------------------------
// Function Name:     calculateShortestPath
//
// Purpose:           calculateShortestPath computes the shortest path from origin to all other
//                    reachable nodes in the digraph using E. Dijkstra's Algorithm
//
// Parameters:        const string& apc contains the airport code to use as the origin (start)
// Returns:           true the path was calculated, false otherwise
// Pre-conditions:    adjacencyMatrix and apcCodes must have been created
// Post-conditions:   weight contains the costs for each node
//                    path contains the path from the origin (start) to all others
//-------------------------------------------------------------------------------------------------
bool APCDiGraph::calculateShortestPath(const string& apc)
{
    // make sure existing variables are cleaned up and ready for reuse
    initVars();

    // find the starting node index
    start = findAPCIndex(apc);
    if (start == -1)
        return false;

    nodeCount = apcCodes.size();

    // Step 1: Initialize d[i] = a[start][i] for all [i] in the row
    weight = new double[nodeCount];
    for (int i = 0; i < nodeCount; i++)
    {
        if (adjacencyMatrix[(start*nodeCount) + i] != nullptr)
            weight[i] = adjacencyMatrix[(start*nodeCount) + i]->getCost();
        else
            weight[i] = DBL_MAX;
    }

    // Step 1: Set p[i] = start for all a[i] adjacent to start (not null)
    //                  = -1 otherwise (the value in a[i] is null)
    path = new int[nodeCount];
    for (int i = 0; i < nodeCount; i++)
    {
        if (weight[i] != DBL_MAX)
            path[i] = start;
        else
            path[i] = -1;
    }

    // Step 1: Add start to the reached seet
    reachedSet.clear();
    reachedSet.push_back(start);

    // Step 1: Create a list L of all vertices for which p[i] != -1
    vector<int> L;
    for (int i = 0; i < nodeCount; i++)
    {
        if (path[i] != -1)
            L.push_back(i);
    }

    // Step 2: If L is empty terminate
    while (L.size() > 0)
    {
        // Step 3: Delete from L the vertex i with the least value of d
        //         and add i to the reached set
        vector<int>::iterator itrNode = L.begin();
        int i = *itrNode;
        double cost = weight[i];

        for (vector<int>::iterator itr = L.begin(); itr != L.end(); itr++)
        {
            if (weight[*itr] < cost)
            {
                cost = weight[*itr];
                i = *itr;
                itrNode = itr;
            }
        }

        L.erase(itrNode);

        // Step 3: Add i to reached set
        reachedSet.push_back(i);

        // Step 4: Update d[j] to min(d[j], d[i]+a[i][j] for all unreached vertices j adjacent from i
        for (int j = 0; j < nodeCount; j++)
        {
            if (adjacencyMatrix[(i*nodeCount) + j] != nullptr)
            {
                double newCost = min(weight[j], weight[i] + adjacencyMatrix[(i*nodeCount) + j]->getCost());
                if (newCost != weight[j])
                {
                    weight[j] = newCost;
                    path[j] = i;

                    bool lFound = false;
                    for (vector<int>::iterator itr = L.begin(); itr != L.end(); itr++)
                    {
                        if (*itr == j)
                            lFound = true;
                    }

                    if (!lFound)
                        L.push_back(j);
                }
            }
        }
    }

    return true;
}


//-------------------------------------------------------------------------------------------------------------
// Function Name:     printBestPriceReport
// Purpose:           displays the formatted report to the 
// Parameters:        none
// Returns:           none
// Pre-conditions:    calculateShortestPath must have been performed
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------------------
void APCDiGraph::printBestPriceReport()
{
    if (path == nullptr || reachedSet.size() == 0)
    {
        cout << "Path information not found." << endl;
        return;
    }

    std::cout.imbue(std::locale(""));

    // print the Best Price Report
    cout << endl << endl;
    cout << "Best Price Report" << endl;
    cout << "                                    Connecting Flight Information    " << endl;
    cout << "Source   Dest     Cost    Mileage   Source   Dest     Cost    Mileage" << endl;
    cout << "------   ----   -------   -------   ------   ----   -------   -------" << endl;

    for (int x = 0; x < (int)reachedSet.size(); x++)
    {
        int nodeID = reachedSet[x];

        if (nodeID == start)
            continue;

        // direct and indirect flights with legs
        vector<APCNode*> legs;
        double totalCost = 0.0;
        double totalMileage = 0.0;

        APCNode* apcNode = adjacencyMatrix[(path[nodeID] * nodeCount) + nodeID];
        if (apcNode != nullptr)
        {
            legs.push_back(apcNode);

            totalCost = apcNode->getCost();
            totalMileage = apcNode->getMileage();

            int hops = 0;
            int i = path[nodeID];

            while (i != start)
            {
                APCNode* waypointNode = adjacencyMatrix[(path[i] * nodeCount) + i];
                if (waypointNode != nullptr)
                {
                    legs.push_back(waypointNode);
                    totalCost += waypointNode->getCost();
                    totalMileage += waypointNode->getMileage();
                }

                i = path[i];

                // just to make sure were not out of bounds or in a enternal loop
                hops++;
                if (hops >= nodeCount || i < 0 || i > nodeCount)
                    break;
            }
        }

        // print any legs that were accumulated
        if (legs.size() > 0)
        {
            // first print the Origin to the final Destination along with the total cost and mileage
            string origin = legs[legs.size() - 1]->getOrigin();
            string dest = legs[0]->getDestination();

            printReportHeaderLine(origin, dest, totalCost, totalMileage);

            // iterate and print the legs
            bool printLeadingSpace = false;
            for (int t = (int)legs.size() - 1; t >= 0; t--)
            {
                printReportDetailLine(legs[t], printLeadingSpace);
                printLeadingSpace = true;
            }

            cout << "------   ----   -------   -------   ------   ----   -------   -------" << endl;
        }
    }

    cout << endl << endl;
}


//-------------------------------------------------------------------------------------------------------------
// Function Name:     printReportHeaderLine
// Purpose:           displays the formatted results of the processed line
//
// Parameters:        const string& origin APC
//                    const string& dest APC
//                    const double& totalCost of trip
//                    const double& totalMileage of trip
//
// Returns:           none
// Pre-conditions:    none
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------------------
void APCDiGraph::printReportHeaderLine(const string& origin, const string& dest, const double& totalCost, const double& totalMileage)
{
    const int APC_ORIGIN_WIDTH = 6;
    const int APC_DEST_WIDTH = 4;
    const int COST_WIDTH = 7;
    const int MILEAGE_WIDTH = 7;
    const int SPACER_WIDTH = 3;

    cout.precision(0);

    // APC Origin
    cout.setf(ios::left, ios::adjustfield);
    cout << setw(APC_ORIGIN_WIDTH) << origin;

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // APC Destination
    cout.setf(ios::left, ios::adjustfield);
    cout << setw(APC_DEST_WIDTH) << dest;

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // cost
    cout.setf(ios::right, ios::adjustfield);
    cout << setw(COST_WIDTH) << Utils::toCurrency(totalCost);

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // mileage
    cout.setf(ios::right, ios::adjustfield);
    cout << setw(MILEAGE_WIDTH) << totalMileage;

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';
}


//-------------------------------------------------------------------------------------------------------------
// Function Name:     printReportDetailLine
// Purpose:           displays the formatted results of the processed line
//
// Parameters:        APCNode* apcNode the flight leg details
//                    bool printLeadingSpace (optional) to print leading space for report alignment purposes
//
// Returns:           none
// Pre-conditions:    apcNode must be valid
// Post-conditions:   none
//-------------------------------------------------------------------------------------------------------------
void APCDiGraph::printReportDetailLine(APCNode* apcNode, bool printLeadingSpace)
{
    const int LEADING_SPACE_WIDTH = 36;
    const int APC_ORIGIN_WIDTH = 6;
    const int APC_DEST_WIDTH = 4;
    const int COST_WIDTH = 7;
    const int MILEAGE_WIDTH = 7;
    const int SPACER_WIDTH = 3;

    if (apcNode == nullptr)
    {
        return;
    }

    if (printLeadingSpace)
    {
        cout.setf(ios::left, ios::adjustfield);
        cout << setw(LEADING_SPACE_WIDTH) << ' ';
    }

    cout.precision(0);

    // APC Origin
    cout.setf(ios::left, ios::adjustfield);
    cout << setw(APC_ORIGIN_WIDTH) << apcNode->getOrigin();

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // APC Destination
    cout.setf(ios::left, ios::adjustfield);
    cout << setw(APC_DEST_WIDTH) << apcNode->getDestination();

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // cost
    cout.setf(ios::right, ios::adjustfield);
    cout << setw(COST_WIDTH) << Utils::toCurrency(apcNode->getCost());

    cout.setf(ios::left, ios::adjustfield);
    cout << setw(SPACER_WIDTH) << ' ';

    // mileage
    cout.setf(ios::right, ios::adjustfield);
    cout << setw(MILEAGE_WIDTH) << apcNode->getMileage();

    cout << endl;
}