Map.c

////////////////////////////////////////////////////////////////////////
// COMP2521 18x1 ... the Fury of Dracula
// Map.c: an implementation of a Map type
// You can change this as much as you want!
//
// 2017-11-30   v1.0    Team Dracula <cs2521@cse.unsw.edu.au>

#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>
#include <stdbool.h>
#include "Map.h"
#include "Places.h"

typedef struct vNode *VList;
struct vNode {
    LocationID  v;    // ALICANTE, etc
    TransportID type; // ROAD, RAIL, BOAT
    VList       next; // link to next node
};

struct map {
    int nV; // #vertices
    int nE; // #edges
    VList connections[NUM_MAP_LOCATIONS]; // array of lists
};

static void addConnections(Map);
static int checkifAlreadyConnected(int array[], int length, LocationID check);

// Create a new empty graph (for a map)
// #Vertices always same as NUM_PLACES
Map
newMap (void)
{
    Map g = malloc (sizeof *g);
    if (g == NULL) err (EX_OSERR, "couldn't allocate Map");

    (*g) = (struct map){
        .nV = NUM_MAP_LOCATIONS,
        .nE = 0,
        .connections = { NULL }
    };

    addConnections (g);
    return g;
}

// Remove an existing graph
void
disposeMap (Map g)
{
    // wait, what?
    if (g == NULL) return;

    for (int i = 0; i < g->nV; i++) {
        VList curr = g->connections[i];
        while (curr != NULL) {
            VList next = curr->next;
            free (curr);
            curr = next;
        }
    }
    free (g);
}

static VList
insertVList (VList L, LocationID v, TransportID type)
{
    VList new = malloc (sizeof(struct vNode));
    if (new == NULL) err (EX_OSERR, "couldn't allocate vNode");

    (*new) = (struct vNode){
        .v = v,
        .type = type,
        .next = L
    };
    return new;
}

static int
inVList (VList L, LocationID v, TransportID type)
{
    for (VList cur = L; cur != NULL; cur = cur->next)
        if (cur->v == v && cur->type == type)
            return 1;

    return 0;
}

// Add a new edge to the Map/Graph
static void
addLink (Map g, LocationID start, LocationID end, TransportID type)
{
    assert (g != NULL);

    // don't add edges twice
    if (inVList (g->connections[start], end, type)) return;

    g->connections[start] = insertVList(g->connections[start],end,type);
    g->connections[end] = insertVList(g->connections[end],start,type);
    g->nE++;
}

static const char *
typeToString (TransportID t)
{
    switch (t) {
    case ROAD: return "road";
    case RAIL: return "rail";
    case BOAT: return "boat";
    default:   return "????";
    }
}

// Display content of Map/Graph
void
showMap (Map g)
{
    assert (g != NULL);

    printf ("V=%d, E=%d\n", g->nV, g->nE);
    for (int i = 0; i < g->nV; i++)
        for (VList n = g->connections[i]; n != NULL; n = n->next)
            printf ("%s connects to %s by %s\n",
                idToName (i), idToName (n->v), typeToString (n->type));
}

// Return count of nodes
int
numV (Map g)
{
    assert (g != NULL);
    return g->nV;
}

// Return count of edges of a particular type
int
numE (Map g, TransportID type)
{
    assert (g != NULL);
    assert (0 <= type && type <= ANY);

    int nE = 0;
    for (int i = 0; i < g->nV; i++)
        for (VList n = g->connections[i]; n != NULL; n = n->next)
            if (n->type == type || type == ANY)
                nE++;

    return nE;
}

// Add edges to Graph representing map of Europe
static void
addConnections (Map g)
{
#define IS_SENTINEL(x) ((x).v == -1 && (x).w == -1 && (x).t == ANY)
    for (int i = 0; ! IS_SENTINEL (CONNECTIONS[i]); i++)
        addLink (g, CONNECTIONS[i].v, CONNECTIONS[i].w, CONNECTIONS[i].t);
}

int connections(Map g, LocationID start, LocationID end, TransportID type[])
{
    int connCount = 0;
    assert(g != NULL);
    VList n = g->connections[start];

    while (n != NULL){
        if (n->v == end){
            type[connCount] = n->type;
            connCount++;
        } else if (n->type == BOAT){
            VList m = g->connections[n->v];
            while (m != NULL){
                if (m->v == end){
                    type[connCount] = n->type;
                    connCount++;
                }
                m = m->next;
            }
        }


        n = n->next;
    }
   return connCount;
}

int numberOfConnections(Map g, LocationID start, bool road, bool rail, bool sea)
{
    int connCount = 1;
    assert(g != NULL);
    VList n = g->connections[start];
    int i = 1;
    int arr[50] = {0};
    arr[0] = start;
    while (n != NULL){
        if (((n->type == ROAD) && road == 1) || ((n->type == RAIL) && rail == 1) || ((n->type == BOAT) && sea == 1)){
            if (checkifAlreadyConnected(arr, i, n->v) == 1){
                connCount++;
                arr[i] = n->v;
                i++;
            }
        }
        n = n->next;

    }
   return connCount;
}

int * locationsConnected (Map g, LocationID start, int arraySize, bool road, bool rail, bool sea){
    assert (g != NULL);
    VList n = g->connections[start];
    int i = 1;
    int *arr = malloc(15*sizeof(int));
    arr[0] = start;
    while (n != NULL){
        if ((checkifAlreadyConnected(arr, i, n->v) == 1) && ((n->type == ROAD && road == 1) || (n->type == RAIL && rail == 1) || (n->type == BOAT && sea == 1))){
            arr[i] = n->v;
            i++;
        }
        n = n->next;
    }
    if (n == NULL){
        arr[i+1] = '\0';
    }
    int *b = arr;

    return b;
}
static int checkifAlreadyConnected(int array[], int length, LocationID check){
    int i  = 0;
    while ( i < length){
        if (array[i] == check){
            return 0;
        }
        i++;
    }
    return 1;
}