// stack.h
typedef struct StackRep *Stack;

Stack newStack (int);               // set up empty stack
void dropStack (Stack);             // remove unwanted stack
void StackPush (Stack, Item);       // insert an Item on top of stack
Item StackPop (Stack);              // remove Item from top of stack
bool StackIsEmpty (Stack);          // check whether stack is empty

// EOF

#define MAXITEMS 10
#include "stack.h"

typedef struct StackRep {
    Item *item;
    int top;
} StackRep;

// set up empty stack
Stack newStack (int n)
{
    Stack s;
    s = malloc (sizeof (StackRep));
    assert (s != NULL);
    s->item = malloc (n * sizeof (Item));
    assert (s->item != NULL);
    s->top = -1;
    return s;
}

// remove unwanted stack
void dropStack (Stack s)
{
    assert (s != NULL);
    free (s->item);
    free (s);
}

// insert Item on top of stack
void StackPush (Stack s, Item it)
{
    assert (s->top < MAXITEMS - 1);
    s->top++;
    int i = s->top;
    s->item[i] = it;
}

// remove Item from top of stack
Item StackPop (Stack s)
{
    assert (s->top > -1);
    int i = s->top;
    Item it = s->item[i];
    s->top--;
    return it;
}

// check whether stack is empty
bool StackIsEmpty (Stack s)
{
    return (s->top < 0);
}

// queue.h
typedef struct QueueRep *Queue;

Queue newQueue (int);               // set up empty queue
void dropQueue (Queue);             // remove unwanted queue
void QueueJoin (Queue, Item);       // insert Item at back of queue
Item QueueLeave (Queue);            // remove Item from front of queue
bool QueueIsEmpty (Queue);          // check whether queue is empty

// EOF

#include "queue.h"

typedef struct QueueRep {
    Item *item;   // array to hold Items
    int front;  // next Item to be removed
    int back;    // last Item added
    int nitems;   // # Items currently in queue
    int maxitems; // size of array
} QueueRep;

// set up empty queue
Queue newQueue (int n)
{
    Queue q = malloc (sizeof (QueueRep));
    assert (q != NULL);
    q->item = malloc (n * sizeof (Item));
    assert (q->item != NULL);
    q->front = q->back = 0;
    q->nitems = 0;
    q->maxitems = n;
    return q;
}

// remove unwanted queue
void dropQueue (Queue q)
{
    assert (q != NULL);
    free (q->item);
    free (q);
}

// insert item on top of queue
void QueueJoin (Queue q, Item it)
{
    assert (q->nitems < q->maxitems);
    q->item[q->front] = it;
    q->nitems++;
    q->front = (q->front + 1) % q->maxitems;
}

// remove item from front of queue
Item QueueLeave (Queue q)
{
    assert (q->nitems > 0);
    Item it = q->item[q->back];
    q->nitems--;
    q->back = (q->back + 1) % q->maxitems;
    return it;
}

// check whether queue is empty
bool QueueIsEmpty (Queue q)
{
    return (q->nitems == 0);
}

// list.h
typedef struct ListRep *List;

// create new, empty List
List newList (void);
// destroy a List
void freeList (List);
// display as one Item per line
void showList (List);               
// append one Item to List
void ListInsert (List, Item);
// delete first occurrence of Item from List;
// if Item does not occur in List, no effect
void ListDelete (List, Item);
// return number of elements in a list
int ListLength(List);

// EOF

#include "list.h"

typedef struct ListNode {
   int  data;  // value of this list item
   struct ListNode *next;
               // pointer to node containing next element
} ListNode;
typedef struct ListRep {
   int  size;  // number of elements in list
   ListNode *first;  // node containing first value
   ListNode *last;  // node containing last value
} ListRep;

// create a new empty List
List newList (void)
{
    ListRep *L;
    L = malloc (sizeof (ListRep));
    assert (L != NULL);
    L->size = 0;
    L->first = NULL;
    L->last = NULL;
    return L;
}

// free up all space associated with list
void freeList (List L)
{
    ListNode *curr, *next;
    assert (L != NULL);
    curr = L->first;
    while (curr != NULL) {
        next = curr->next;
        free (curr);
        curr = next;
    }
    free (L);
}

// display list as one integer per line on stdout
void showList (List L)
{
    ListNode *curr;
    curr = L->first;
    while (curr != NULL) {
        show (curr->data);
        printf ("\n");
        curr = curr->next;
    }
}

// create a new ListNode with value it
// (this function is local to this ADT)
static ListNode *newListNode (Item it)
{
    ListNode *n;
    n = malloc (sizeof (ListNode));
    assert (n != NULL);
    n->data = it;
    n->next = NULL;
    return n;
}

// apppend one Item to the end of a list
void ListInsert (List L, Item it)
{
    assert (L != NULL);
    ListNode *n;
    n = newListNode (it);
    if (L->first == NULL)
        L->first = L->last = n;
    else {
        L->last->next = n;
        L->last = n;
    }
    L->size++;
}

// remove an item from a List
void ListDelete (List L, Item it)
{
    assert (L != NULL);
    ListNode *curr, *prev;
    prev = NULL;
    curr = L->first;
    while (curr != NULL && !eq (curr->data, it)) {
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL)
        return;
    if (prev == NULL)
        L->first = curr->next;
    else
        prev->next = curr->next;
    if (L->last == curr)
        L->last = prev;
    L->size--;
    free (curr);
}

// return number of elements in a list
int ListLength (List L)
{
    assert (L != NULL);
    return L->size;
}

// pqueue.h
typedef struct PQueueRep *PQueue;

// create new empty priority queue
PQueue newPQueue(int size);
// add item to priority queue
void PQJoin(PQueue q, Item it);
// remove item from priority queue
Item PQLeave(PQueue q);
// free up priority queue
void dropPQueue(PQueue q);

// EOF

// pqueue_heaparray.c

#include "pqueue.h"

static void fixUp (Item a[], int k);
static void fixDown (Item a[], int k, int N);

struct PQueueRep {
    int nItems;  // count of items
    Item *items; // heap-array of Items
    int size;   // size of array
};

// create a new empty queue
PQueue newPQueue (int size)
{
    PQueue q = malloc (sizeof (struct PQueueRep));
    assert (q != NULL);
    // indexes start from 1
    q->items = malloc (sizeof (Item) * (size + 1));
    assert (q->items != NULL);
    q->nItems = 0;
    q->size = size;
    return q;
}

// add a new item into the queue
void
PQJoin (PQueue q, Item it)
{
    assert (q != NULL && q->nItems < q->size);
    q->nItems++;
    q->items[q->nItems] = it;
    fixUp (q->items, q->nItems);
}

// remove item from priority queue
Item
PQLeave (PQueue q)
{
    assert (q != NULL && q->nItems > 0);
    swap (q->items, 1, q->nItems);
    q->nItems--;
    fixDown (q->items, 1, q->nItems);
    return q->items[q->nItems + 1];
}

// free up priority queue
void dropPQueue (PQueue q)
{
    assert (q != NULL);
    free (q->items);
    free (q);
}

static void fixUp (Item a[], int k)
{
    while (k > 1 && less (a[k / 2], a[k])) {
        swap (a, k, k / 2);
        k = k / 2; // integer division
    }
}

static void fixDown (Item a[], int k, int N)
{
    while (2 * k <= N) {
        int j = 2 * k;
        // choose larger of two children
        if (j < N && less (a[j], a[j + 1]))
            j++;
        if (!less (a[k], a[j]))
            break;
        swap (a, k, j);
        k = j;
    }
}

// sort_insertion.c

void insertionSort (int a[], int lo, int hi)
{
    int i, j, val;
    for (i = lo + 1; i <= hi; i++) {
        val = a[i];
        for (j = i; j > lo; j--) {
            if (!less (val, a[j - 1]))
                break;
            a[j] = a[j - 1];
        }
        a[j] = val;
    }
}

// sort_selection.c

void selectionSort (int a[], int lo, int hi)
{
    int i, j, min;
    for (i = lo; i < hi; i++) {
        min = i;
        for (j = i + 1; j <= hi; j++) {
            if (less (a[j], a[min]))
                min = j;
        }
        swap (&a[i], &a[min]);
    }
}

// sort_bubble.c

void bubbleSort (int a[], int lo, int hi)
{
    int i, j, nswaps;
    for (i = lo; i < hi; i++) {
        nswaps = 0;
        for (j = hi; j > i; j--) {
            if (less (a[j], a[j - 1])) {
                swap (&a[j], &a[j - 1]);
                nswaps++;
            }
        }
        if (nswaps == 0)
            break;
    }
}

// sort_qsort_m3.c

void quicksort (Item a[], int lo, int hi)
{
    int i; // index of pivot
    if (hi <= lo) return;
    medianOfThree (a, lo, hi);
    i = partition (a, lo + 1, hi - 1);
    quicksort (a, lo, i - 1);
    quicksort (a, i + 1, hi);
}

void medianOfThree (Item a[], int lo, int hi)
{
    int mid = (lo + hi) / 2;
    if (less (a[mid], a[lo])) swap (a, lo, mid);
    if (less (a[hi], a[mid])) swap (a, mid, hi);
    if (less (a[mid], a[lo])) swap (a, lo, mid);
    // now, we have a[lo] ≤ a[mid] ≤ a[hi]
    // swap a[mid] to a[lo+1] to use as pivot
    swap (a, lo + 1, mid);
}

int partition (Item a[], int lo, int hi)
{
    Item v = a[lo]; // pivot
    int i = lo + 1, j = hi;
    for (;;) {
        while (less (a[i], v) && i < j) i++;
        while (less (v, a[j]) && j > i) j--;
        if (i == j) break;
        swap (a, i, j);
    }
    j = less (a[i], v) ? i : i - 1;
    swap (a, lo, j);
    return j;
}

// sort_merge.c

void mergesort (Item a[], int lo, int hi)
{
    int mid = (lo + hi) / 2; // mid point
    if (hi <= lo)
        return;
    mergesort (a, lo, mid);
    mergesort (a, mid + 1, hi);
    merge (a, lo, mid, hi);
}

static void merge (Item a[], int lo, int mid, int hi)
{
    int nitems = hi - lo + 1;
    Item *tmp = malloc (nitems * sizeof (Item));

    // scan both segments, copying to tmp
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        if (less (a[i], a[j]))
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    // copy items from unfinished segment
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];

    // copy tmp back to main array
    for (i = lo, k = 0; i <= hi; i++, k++)
        a[i] = tmp[k];

    free (tmp);
}

// sort_heap.c
#include "pqueue.h"

// Brute-force heapsort.
void HeapSort (Item a[], int lo, int hi)
{
    PQueue pq = newPQueue (hi - lo + 1);
    int i;
    for (i = lo; i <= hi; i++) {
        PQJoin (pq, a[i]);
    }
    for (i = hi; i >= lo; i--) {
        Item it = PQLeave (pq);
        a[i] = it;
    }
}

// bsearch_array.c

// search for key k in array a[]
// - returns index of location for k
// - doesn't indicate whether key is actually there or not
int findInArray (Item k, Item a[], int lo, int hi)
{
    if (hi <= lo)
        return lo;
    int mid = (hi + lo) / 2;
    int diff = cmp (k, key (a[mid]));
    if (diff < 0)
        return findInArray (k, a, lo, mid);
    else if (diff > 0)
        return findInArray (k, a, mid + 1, hi);
    else
        return mid;
}

// tree.h

typedef struct Node *Tree;

// create an empty Tree
Tree newTree();
// free memory associated with Tree
void dropTree(Tree);
// display a Tree (sideways)
void showTree(Tree);
// insert a new item into a Tree
Tree TreeInsert(Tree, Item);
Tree TreeInsertAtRoot(Tree, Item);
Tree TreeInsertRandom(Tree, Item);
// delete item with given key from Tree
Tree TreeDelete(Tree, Key);
// check whether item with given key is in Tree
int TreeFind(Tree, Key);
// compute depth of Tree
int TreeDepth(Tree);
// count #nodes in Tree
int TreeNumNodes(Tree);
// fetch i'th (from left) item from Tree
Item *get_ith(Tree, int);
// partition Tree around i'th Item
Tree partition(Tree, int);
// rotate Tree left/right around root
Tree rotateR(Tree);
Tree rotateL(Tree);

// EOF

#include "tree.h"
int size(Tree);

typedef struct Node *Link;
typedef struct Node {
    Item value;
    int nnodes;
    Link left, right;
} Node;

// make a new node containing an Item
static Link newNode (Item it)
{
    Link new = malloc (sizeof (Node));
    assert (new != NULL);
    new->value = it;
    new->left = new->right = NULL;
    return new;
}

// create a new empty Tree
Tree newTree ()
{
    return NULL;
}

// free memory associated with Tree
void dropTree (Tree t)
{
    if (t == NULL) return;
    dropTree (t->left);
    dropTree (t->right);
    free (t);
}

// display a Tree (sideways)
void showTree (Tree t)
{
    void doShowTree (Tree);
    doShowTree (t);
}

// insert a new value into a Tree
Tree TreeInsert (Tree t, Item it)
{
    if (t == NULL)
        return newNode (it);
    int diff = cmp (key (it), key (t->value));
    if (diff == 0)
        t->value = it;
    else if (diff < 0)
        t->left = TreeInsert (t->left, it);
    else if (diff > 0)
        t->right = TreeInsert (t->right, it);
    return t;
}

// insert a new value as root of Tree
Tree insertAtRoot (Tree t, Item it)
{
    if (t == NULL)
        return newNode (it);
    int diff = cmp (key (it), key (t->value));
    if (diff == 0)
        t->value = it;
    else if (diff < 0) {
        t->left = insertAtRoot (t->left, it);
        printf ("rotateR(%d)\n", t->value);
        t = rotateR (t);
    } else if (diff > 0) {
        t->right = insertAtRoot (t->right, it);
        printf ("rotateL(%d)\n", t->value);
        t = rotateL (t);
    }
    return t;
}

Tree insertRandom (Tree t, Item it)
{
    if (t == NULL)
        return newNode (it);
    // 1 in 3 chance of doing root insert
    int chance = rand () % 3;
    if (chance == 0)
        t = insertAtRoot (t, it);
    else
        t = TreeInsert (t, it);
    return t;
}

// delete item with given key from Tree
Tree TreeDelete (Tree t, Key k)
{
    Tree deleteRoot (Tree);

    if (t == NULL)
        return NULL;
    int diff = cmp (k, key (t->value));
    if (diff == 0)
        t = deleteRoot (t);
    else if (diff < 0)
        t->left = TreeDelete (t->left, k);
    else if (diff > 0)
        t->right = TreeDelete (t->right, k);
    return t;
}

// delete root of tree
Tree deleteRoot (Tree t)
{
    Link newRoot;
    // if no subtrees, tree empty after delete
    if (t->left == NULL && t->right == NULL) {
        free (t);
        return NULL;
    }
    // if only right subtree, make it the new root
    else if (t->left == NULL && t->right != NULL) {
        newRoot = t->right;
        free (t);
        return newRoot;
    }
    // if only left subtree, make it the new root
    else if (t->left != NULL && t->right == NULL) {
        newRoot = t->left;
        free (t);
        return newRoot;
    }
    // else (t->left != NULL && t->right != NULL)
    // so has two subtrees
    // - find inorder successor (grab value)
    // - delete inorder successor node
    // - move its value to root
    Link succ = t->right; // not null!
    while (succ->left != NULL) {
        succ = succ->left;
    }
    int succVal = succ->value;
    t = TreeDelete (t, succVal);
    t->value = succVal;
    return t;
}

// check whether item with given key is in Tree
int TreeFind (Tree t, Key k)
{
    if (t == NULL)
        return 0;
    int res, diff = cmp (k, key (t->value));
    if (diff < 0)
        res = TreeFind (t->left, k);
    else if (diff > 0)
        res = TreeFind (t->right, k);
    else // (diff == 0)
        res = 1;
    return res;
}

// compute depth of Tree
int TreeDepth (Tree t)
{
    if (t == NULL)
        return 0;
    else {
        int ldepth = TreeDepth (t->left);
        int rdepth = TreeDepth (t->right);
        // return 1 + (ldepth > rdepth)?ldepth:rdepth;
        if (ldepth > rdepth)
            return 1 + ldepth;
        else
            return 1 + rdepth;
    }
}

// count #nodes in Tree
int TreeNumNodes (Tree t)
{
    if (t == NULL) return 0;
    return 1 + TreeNumNodes (t->left) + TreeNumNodes (t->right);
}

// fetch i'th (from left) item from Tree
Item *get_ith (Tree t, int i)
{
    if (t == NULL)
        return NULL;
    assert (0 <= i && i < size (t));
    int n = size (t->left); // #nodes to left of root
    if (i < n)
        return get_ith (t->left, i);
    if (i > n)
        return get_ith (t->right, i - n - 1);
    return &(t->value);
}

// partition Tree around i'th Item
Tree partition (Tree t, int i)
{
    if (t == NULL)
        return NULL;
    assert (0 <= i && i < size (t));
    int n = size (t->left);
    if (i < n) {
        t->left = partition (t->left, i);
        t = rotateR (t);
    }
    if (i > n) {
        t->right = partition (t->right, i - n - 1);
        t = rotateL (t);
    }
    return t;
}

// rotate Tree right around node
Link rotateR (Link n1)
{
    if (n1 == NULL)
        return n1;
    Link n2 = n1->left;
    if (n2 == NULL)
        return n1;
    n1->left = n2->right;
    n2->right = n1;
    return n2;
}

// rotate Tree left around node
Link rotateL (Link n2)
{
    if (n2 == NULL)
        return n2;
    Link n1 = n2->right;
    if (n1 == NULL)
        return n2;
    n2->right = n1->left;
    n1->left = n2;
    return n1;
}

// tree_splay.c

#define L left
#define R right

// Other operations are as for BSTs
Tree insertSplay (Tree t, Item it)
{
    if (t == NULL)
        return newNode (it);
    int diff = cmp (key (it), key (t->value));
    if (diff == 0)
        t->value = it;
    else if (diff < 0) {
        if (t->L == NULL) {
            t->L = newNode (it);
            t->nnodes++;
        }
        int ldiff = cmp (key (it), key (t->L->value));
        if (ldiff < 0) {
            // Case 1: left-child of left-child
            t->L->L = insertSplay (t->L->L, it);
            t->L->nnodes++;
            t->nnodes++;
            t = rotateR (t);
        } else if (ldiff > 0) {
            // Case 2: right-child of left-child
            t->L->R = insertSplay (t->L->R, it);
            t->L->nnodes++;
            t->nnodes++;
            t->L = rotateL (t->L);
        }
        return rotateR (t);
    } else if (diff > 0) {
        if (t->R == NULL) {
            t->R = newNode (it);
            t->nnodes++;
        }
        int rdiff = cmp (key (it), key (t->R->value));
        if (rdiff < 0) {
            // Case 3: left-child of right-child
            t->R->L = insertSplay (t->R->L, it);
            t->R->nnodes++;
            t->nnodes++;
            t->R = rotateR (t->R);
        } else if (rdiff > 0) {
            // Case 4: right-child of right-child
            t->R->R = insertSplay (t->R->R, it);
            t->R->nnodes++;
            t->nnodes++;
            t = rotateL (t);
        }
        return rotateL (t);
    } else
        t->value = it;
    return t;
}

// search Tree for item with key k
Item *searchSplay (Tree *t, Key k)
{
    Link root = *t;
    if (root == NULL)
        return NULL;
    root = splay (root, k);
    *t = root;
    if (key (root->value) == k)
        return &(root->value);
    else
        return NULL;
}

// tree_avl.c

// Other operations are as for BSTs
Tree insertAVL (Tree t, Item it)
{
    if (t == NULL)
        return newNode (it);
    int diff = cmp (key (it), key (t->value));
    if (diff == 0) {
        t->value = it;
    } else if (diff < 0) {
        t->left = insertAVL (t->left, it);
        t->nnodes = count (t);
    } else if (diff > 0) {
        t->right = insertAVL (t->right, it);
        t->nnodes = count (t);
    }

    int dL = depth (t->left);
    int dR = depth (t->right);
    if ((dL - dR) > 1) t = rotateR (t);
    else if ((dR - dL) > 1) t = rotateL (t);
    return t;
}

#include "tree_234.h"

typedef struct node {
    int order;   // 2, 3 or 4
    Item data[3];  // items in node
    Tree child[4]; // links to subtrees
} Node;

// create new 2-3-4 node
static Node *newNode (Item it)
{
    Node *new = malloc (sizeof (Node));
    assert (new != NULL);
    new->order = 2;
    new->data[0] = it;
    new->child[0] = new->child[1] = NULL;
    return new;
}

// search for item with key k
Item *search (Tree t, Key k)
{
    if (t == NULL)
        return NULL;
    int i;
    int diff;
    int nitems = t->order - 1;
    // find relevant slot in items
    for (i = 0; i < nitems; i++) {
        diff = cmp (k, key (t->data[i]));
        if (diff <= 0)
            break;
    }
    if (diff == 0)
        // match; return result
        return &(t->data[i]);
    else
        // keep looking in relevant subtree
        return search (t->child[i], k);
}

// insert new Item into Tree
Tree
insert (Tree t, Item it)
{
    /* algorithm:
    find leaf node where Item belongs (via search)
    if not full (i.e. order < 4) {
        insert Item in this node, order++
    }
    else if node is full (i.e. contains 3 Items) {
        split into two 2-nodes as leaves
        promote middle element to parent
        insert item into appropriate leaf 2-node
        if parent is a 4-node {
            continue split/promote upwards
            if promote to root, and root is a 4-node {
                split root node
                add new root node
                promote middle item to new root
            }
        }
    }
    */
}

// tree_rb.c

typedef enum { RED, BLACK } color_t;
typedef struct Node *Link;
typedef struct TreeRep *Tree;
struct TreeRep {
    Link root;
};
typedef struct Node {
    Item value;  // actual data
    color_t colour; // colour of link to parent
    Link left;   // left subtree
    Link right;  // right subtree
} Node;

// make new node to hold supplied Item
Node *newNode (Item it, color_t c)
{
    Node *new = malloc (sizeof (Node));
    assert (new != NULL);
    new->value = it;
    new->colour = c;
    new->left = new->right = NULL;
    return new;
}

// search for Item with given key
Item *search (Link t, Key k)
{
    if (t == NULL)
        return NULL;
    int diff = cmp (k, key (t->value));
    if (diff < 0)
        return search (t->left, k);
    else if (diff > 0)
        return search (t->right, k);
    else // matches
        return &(t->value);
}

// insert new Item into tree
#define L left
#define R right
#define isRed(t) ((t) != NULL && (t)->colour == RED)

void insert (Tree t, Item it)
{
    t->root = insertRB (t->root, it, 0);
    t->root->colour = RED;
}

Link insertRB (Link t, Item it, int inRight)
{
    if (t == NULL)
        return newNode (it, RED);
    // node is a 4-node; lift it
    if (isRed (t->L) && isRed (t->R)) {
        t->colour = RED;
        t->L->colour = BLACK;
        t->R->colour = BLACK;
    }
    int diff = cmp (key (it), key (t->value));
    if (diff == 0)
        t->value = it;
    else if (diff < 0) {
        t->L = insertRB (t->L, it, 0);
        if (isRed (t) && isRed (t->L) && inRight)
            t = rotateR (t);
        if (isRed (t->L) && isRed (t->L->L)) {
            t = rotateR (t);
            t->colour = BLACK;
            t->R->colour = RED;
        }
    } else if (diff > 0) {
        t->R = insertRB (t->R, it, 1);
        if (isRed (t) && isRed (t->R) && !inRight)
            t = rotateL (t);
        if (isRed (t->R) && isRed (t->R->R)) {
            t = rotateL (t);
            t->colour = BLACK;
            t->L->colour = RED;
        }
    }
    return t;
}
// other operations as for BSTs

// hashtable.h
typedef struct HashTabRep *HashTable;

// create an empty HashTable
HashTable newHashTable(int);
// free memory associated with HashTable
void dropHashTable(HashTable);
// insert a new value into a HashTable
void hashTableInsert(HashTable, Item);
// delete a value from a HashTable
void hashTableDelete(HashTable, Key);
// get Item from HashTable using Key
Item *hashTableSearch(HashTable, Key);

// EOF

#include "hashtable.h"
#include "list.h"  // use Lists of Items

typedef struct HashTabRep {
    List *lists; // lists of Items
    int nslots;  // # elements in array
    int nitems;  // # items stored in HashTable
} HashTabRep;

// convert key to index
static int hash (Key k, int N)
{
    int h = keyhash (k); // convert key to int
    return h % N;
}

// create an empty HashTable
HashTable newHashTable (int N)
{
    HashTable new = malloc (sizeof (HashTable));
    assert (new != NULL);
    new->lists = malloc (N * sizeof (List));
    assert (new->lists != NULL);
    int i;
    for (i = 0; i < N; i++)
        new->lists[i] = newList ();
    new->nslots = N;
    new->nitems = 0;
    return new;
}

// free memory associated with HashTable
void dropHashTable (HashTable ht)
{
    free (ht->lists);
    free (ht);
}

// insert a new value into a HashTable
void hashTableInsert (HashTable ht, Item it)
{
    Key k = key (it);
    int i = hash (k, ht->nslots);
    ListInsert (ht->lists[i], it);
}

// delete a value from a HashTable
void hashTableDelete (HashTable ht, Key k)
{
    int i = hash (k, ht->nslots);
    ListDelete (ht->lists[i], k);
}

// get Item from HashTable using Key
Item *hashTableSearch (HashTable ht, Key k)
{
    int i = hash (k, ht->nslots);
    return ListSearch (ht->lists[i], k);
}

#include "hashtable.h"

typedef struct HashTabRep {
    Item *items; // lists of Items
    int nslots;  // # elements in array
    int nitems;  // # items stored in HashTable
} HashTabRep;

// convert key to index
static int hash (Key k, int N)
{
    int h = keyhash (k); // convert key to int
    return h % N;
}

// create an empty HashTable
HashTable newHashTable (int N)
{
    HashTabRep *new = malloc (sizeof (HashTabRep));
    assert (new != NULL);
    new->items = malloc (N * sizeof (Item));
    assert (new->items != NULL);
    int i;
    for (i = 0; i < N; i++)
        new->items[i] = NoItem;
    new->nslots = N;
    new->nitems = 0;
    return new;
}

// free memory associated with HashTable
void dropHashTable (HashTable ht)
{
    free (ht->items);
    free (ht);
}

// insert a new value into a HashTable
void hashTableInsert (HashTable ht, Item it)
{
    int N = ht->nslots;
    Item *data = ht->items;
    Key k = key (it);
    int ix, j, i = hash (k, N);
    for (j = 0; j < N; j++) {
        ix = (i + j) % N;
        if (cmp (k, key (data[ix])) == 0) break;
        else if (data[ix] == NoItem) break;
    }
    if (j < N) {
        data[ix] = it;
        ht->nitems++;
    }
}

// delete a value from a HashTable
void hashTableDelete (HashTable ht, Key k)
{
    int N = ht->nslots;
    Item *data = ht->items;
    int ix, j, i = hash (k, N);
    for (j = 0; j < N; j++) {
        ix = (i + j) % N;
        if (cmp (k, key (data[ix])) == 0)
            break;
        else if (data[ix] == NoItem)
            return; // k not in table
    }
    data[ix] = NoItem;
    ht->nitems--;
    // clean up probe path
    j = ix + 1;
    while (data[j] != NoItem) {
        Item it = data[j];
        data[j] = NoItem;
        ht->nitems--;
        insert (ht, it);
        j = (j + 1) % N;
    }
}

// get Item from HashTable using Key
Item *hashTableSearch (HashTable ht, Key k)
{
    int N = ht->nslots;
    Item *data = ht->items;
    int j, i = hash (k, N);
    for (j = 0; j < N; j++) {
        int ix = (i + j) % N;
        if (cmp (k, key (data[ix])) == 0)
            return &(data[ix]);
    }
    return NULL;
}

// graph.h

// visible data structures for Graphs
typedef struct GraphRep *Graph;
// vertices denoted by integers 0..N-1
typedef int Vertex;
// edges are pairs of vertices (end-points)
typedef struct { Vertex v; Vertex w; } Edge;
// auxiliary operations on graphs
int validV(Graph,Vertex); // validity check
Edge mkEdge(Graph, Vertex, Vertex); // edge creation
int neighbours(Graph, Vertex, Vertex); // edge existence
// core operations on graphs
// make new graph with nV vertices
Graph newGraph(int nV);
// free memory allocated to graph
void dropGraph(Graph);
// show "printable" representation of graph
void showGraph(Graph);
// add new edge to a graph
void insertE(Graph, Edge);
// remove an edge from a graph
void removeE(Graph, Edge);
// returns #vertices & array of edges
int edges(Graph, Edge *, int);

// EOF

#include "graph.h"

// is a vertex valid in a given Graph?
int validV (Graph g, Vertex v)
{
    return (g != NULL && v >= 0 && v < g->nV);
}
// make an Edge value
Edge mkEdge (Graph g, Vertex v, Vertex w)
{
    assert (validV (g, v) && validV (g, w));
    Edge e = {v, w}; // struct assignment
    return e;
}

// graph_adjmatrix.c

typedef struct GraphRep {
    int nV;       // #vertices
    int nE;       // #edges
    bool **edges; // matrix of booleans
} GraphRep;

// check whether two vertices are connected
int neighbours (Graph g, Vertex v, Vertex w)
{
    assert (validV (g, v) && validV (g, w));
    return g->edges[v][w];
}

// make new graph with nV vertices
Graph newGraph (int nV)
{
    assert (nV >= 0);
    Graph g = malloc (sizeof (GraphRep));
    g->nV = nV;
    g->nE = 0;
    g->edges = malloc (nV * sizeof (bool *));
    for (int i = 0; i < nV; i++) {
        g->edges[i] = malloc (nV * sizeof (bool));
        for (int j = 0; j < nV; j++)
            g->edges[i][j] = false;
    }
    return g;
}

// free memory allocated to graph
void dropGraph (Graph g)
{
    assert (g != NULL);
    int i;
    for (i = 0; i < g->nV; i++)
        free (g->edges[i]);
    free (g->edges);
    free (g);
}

// show "printable" representation of graph
void showGraph (Graph g)
{
    assert (g != NULL);
    printf ("V=%d, E=%d\n", g->nV, g->nE);
    int i, j;
    for (i = 0; i < g->nV; i++) {
        int nshown = 0;
        for (j = i + 1; j < g->nV; j++) {
            if (g->edges[i][j] != 0) {
                printf ("%d-%d ", i, j);
                nshown++;
            }
        }
        if (nshown > 0)
            printf ("\n");
    }
}

// add new edge to a graph
void insertE (Graph g, Edge e)
{
    assert (g != NULL);
    assert (validV (g, e.v) && validV (g, e.w));
    if (g->edges[e.v][e.w])
        return;
    g->edges[e.v][e.w] = 1;
    g->edges[e.w][e.v] = 1;
    g->nE++;
}

// remove an edge from a graph
void removeE (Graph g, Edge e)
{
    assert (g != NULL);
    assert (validV (g, e.v) && validV (g, e.w));
    if (!g->edges[e.v][e.w])
        return;
    g->edges[e.v][e.w] = 0;
    g->edges[e.w][e.v] = 0;
    g->nE--;
}

// returns #vertices & array of edges
int edges (Graph g, Edge *es, int nE)
{
    assert (g != NULL && es != NULL);
    assert (nE >= g->nE);
    int i, j, n = 0;
    for (i = 0; i < g->nV; i++) {
        for (j = i + 1; j < g->nV; j++) {
            if (g->edges[i][j] != 0) {
                assert (n < nE);
                es[n++] = mkEdge (g, i, j);
            }
        }
    }
    return n;
}

// graph_adjmatrix.c

typedef struct vNode *VList;
struct vNode { Vertex v; VList next; };
VList insertVList (VList, Vertex);
VList deleteVList (VList, Vertex);
void freeVList (VList);
int length (VList);
struct GraphRep {
    int nV;       // #vertices
    int nE;       // #edges
    VList *edges; // array of lists
};

// check whether two vertices are connected
int neighbours (Graph g, Vertex v, Vertex w)
{
    assert (validV (g, v) && validV (g, w));
    VList curr;
    curr = g->edges[v];
    while (curr != NULL) {
        if (curr->v == w)
            return 1;
    }
    return 0;
}
// make new graph with nV vertices
Graph newGraph (int nV)
{
    Graph g = malloc (sizeof (struct GraphRep));
    g->nV = nV;
    g->nE = 0;
    g->edges = calloc (nV, sizeof (VList));
    return g;
}

// free memory allocated to graph
void dropGraph (Graph g)
{
    assert (g != NULL);
    int i;
    for (i = 0; i < g->nV; i++)
        freeVList (g->edges[i]);
    free (g);
}

// show "printable" representation of graph
void showGraph (Graph g)
{
    assert (g != NULL);
    printf ("V=%d, E=%d\n", g->nV, g->nE);
    int i;
    for (i = 0; i < g->nV; i++) {
        struct vNode *n = g->edges[i];
        while (n != NULL) {
            printf ("%d-%d ", i, n->v);
            n = n->next;
        }
        if (g->edges[i] != NULL)
            printf ("\n");
    }
}

// add new edge to a graph
void insertE (Graph g, Edge e)
{
    assert (g != NULL);
    assert (validV (g, e.v) && validV (g, e.w));
    int orig = length (g->edges[e.v]);
    g->edges[e.v] = insertVList (g->edges[e.v], e.w);
    g->edges[e.w] = insertVList (g->edges[e.w], e.v);
    if (length (g->edges[e.v]) > orig)
        g->nE++;
}

// remove an edge from a graph
void removeE (Graph g, Edge e)
{
    assert (g != NULL);
    assert (validV (g, e.v) && validV (g, e.w));
    int orig = length (g->edges[e.v]);
    g->edges[e.v] = deleteVList (g->edges[e.v], e.w);
    g->edges[e.w] = deleteVList (g->edges[e.w], e.v);
    if (length (g->edges[e.v]) < orig)
        g->nE--;
}

// returns #vertices & array of edges
int edges (Graph g, Edge *es, int nE)
{
    VList curr;
    assert (g != NULL && es != NULL);
    assert (nE >= g->nE);
    int w, n = 0;
    for (w = 0; w < g->nV; w++) {
        curr = g->edges[w];
        while (curr != NULL) {
            if (w < curr->v)
                es[n++] = mkEdge (g, w, curr->v);
            curr = curr->next;
        }
    }
    return n;
}

// to your chosen graph implementation, add:

bool *visited;  // array of booleans
               // indexed by vertex 0..V-1

// DFS : depth-first search
int hasPathDFS (Graph g, Vertex src, Vertex dest)
{
    int i;
    visited = malloc (g->nV * sizeof (bool));
    for (i = 0; i < g->nV; i++)
        visited[i] = false;
    return dfsPathCheck (g, src, dest);
}

int dfsPathCheck (Graph g, Vertex v, Vertex dest)
{
    visited[v] = true;
    Vertex w;
    for (w = 0; w < g->nV; w++) {
        if (g->edges[v][w] && w == dest)
            return 1; // found path
        if (g->edges[v][w] && !visited[w])
            return dfsPathCheck (g, w, dest);
    }
    return 0; // no path from src to dest
}

// BFS : breadth-first search
int hasPathBFS (Graph g, Vertex src, Vertex dest)
{
    int *visited = calloc (g->nV, sizeof (bool));
    Queue q = newQueue (g->nV);
    QueueJoin (q, src);
    int isFound = 0;
    while (!QueueIsEmpty (q) && !isFound) {
        Vertex y, x = QueueLeave (q);
        if (visited[x]) continue;
        visited[x] = true;
        for (y = 0; y < g->nV; y++) {
            if (!g->edges[x][y]) continue;
            if (y == dest) {
                isFound = 1;
                break;
            }
            if (!visited[y]) {
                QueueJoin (q, y);
            }
        }
    }
    free (visited);
    return isFound;
}

// to your chosen graph implementation, add:

int
findPath (Graph g, Vertex src, Vertex dest)
{
    int i;
    // array of "been visited" flags
    int *visited = malloc (g->nV * sizeof (int));
    for (i = 0; i < g->nV; i++) visited[i] = 0;
    // array of path predecessor vertices
    Vertex *path = malloc (g->nV * sizeof (Vertex));
    Queue q = newQueue (g->nV);
    QueueJoin (q, src);
    visited[src] = 1;
    int isFound = 0;
    while (!QueueIsEmpty (q) && !isFound) {
        Vertex y, x = QueueLeave (q);
        for (y = 0; y < g->nV; y++) {
            if (!g->edges[x][y]) continue;
            path[y] = x;
            if (y == dest) {
                isFound = 1;
                break;
            }
            if (!visited[y]) {
                QueueJoin (q, y);
                visited[y] = 1;
            }
        }
    }
    if (isFound) {
        // display path in dest..src order
        Vertex v;
        for (v = dest; v != src; v = path[v])
            printf ("%d<-", v);
        printf ("%d\n", src);
    }

    return isFound;
}

// to your chosen graph implementation, add:

int *componentOf;  // array of component ids
                   // indexed by vertex 0..V-1
int ncounted;      // # vertices included so far

void components (Graph g)
{
    void dfsComponents (Graph, Vertex, int);
    int i, comp = 0;
    componentOf = malloc (g->nV * sizeof (int));
    for (i = 0; i < g->nV; i++)
        componentOf[i] = -1;
    ncounted = 0;
    while (ncounted < g->nV) {
        Vertex v;
        for (v = 0; v < g->nV; v++)
            if (componentOf[v] == -1)
                break;
        dfsComponents (g, v, comp);
        comp++;
    }
    // componentOf[] is now set
}

void dfsComponents (Graph g, Vertex v, int c)
{
    componentOf[v] = c;
    ncounted++;
    Vertex w;
    for (w = 0; w < g->nV; w++) {
        if (g->edges[v][w] && componentOf[w] == -1)
            dfsComponents (g, w, c);
    }
}

// to your chosen graph implementation, add:

int *visited; // array of nV bools
int HamiltonR (Graph g, Vertex v, Vertex w, int d)
{
    int t;
    if (v == w) return (d == 0) ? 1 : 0;
    visited[v] = 1;
    for (t = 0; t < g->nV; t++) {
        if (!neighbours (g, v, t)) continue;
        if (visited[v] == 1) continue;
        if (HamiltonR (g, t, w, d - 1)) return 1;
    }
    visited[v] = 0;
    return 0;
}

int hasHamiltonPath (Graph g, Vertex src, Vertex dest)
{
    visited = calloc (g->nV, sizeof (int));
    int res = HamiltonR (g, src, dest, g->nV - 1);
    free (visited);
    return res;
}

// Same interface as for simple graphs
// Representation changes:
// - essentially the same data structures
// - if using adjacency matrix, no longer symmetric
// - if using adjacency lists, no longer store (v,w) and (w,v)

// to your chosen graph implementation, add:

int **tc; // VxV matrix indicating reachability

// is there some path from src to dest
int reachable (Graph g, Vertex src, Vertex dest)
{
    if (g->tc == NULL)
        makeClosure (g);
    return g->tc[src][dest];
}

// build transitive closure matrix
void makeClosure (Graph g)
{
    int i, s, t, V = g->nV;
    tc = makeMatrix (V, V, 0);
    for (s = 0; s < V; s++) {
        for (t = 0; t < V; t++)
            tc[s][t] = g->edges[s][t];
    }
    for (i = 0; i < V; i++) {
        for (s = 0; s < V; s++) {
            if (tc[s][i] == 0)
                continue;
            for (t = 0; t < V; t++)
                if (tc[i][t] == 1)
                    tc[s][t] = 1;
        }
    }
    g->tc = tc;
}

// build an empty VxV matrix
int **makeMatrix (int nrows, int ncols, int init)
{
    int i, j;
    int **m = malloc (nrows * sizeof (int *));
    assert (m != NULL);
    for (i = 0; i < nrows; i++) {
        m[i] = malloc (ncols * sizeof (int));
        assert (m[i] != NULL);
        for (j = 0; j < ncols; j++)
            m[i][j] = init;
    }
    return m;
}

// wgraph.h

// visible data structures for Graphs
typedef struct GraphRep *Graph;
// vertices denoted by integers 0..N-1
typedef int Vertex;
// edges are end-points + weight
typedef struct { Vertex src; Vertex dest; float weight; } Edge;
// auxiliary operations on graphs
int validV(Graph,Vertex); // validity check
Edge mkEdge(Graph, Vertex, Vertex, float); // edge creation
int neighbours(Graph, Vertex, Vertex); // edge existence
float compareE(Edge e1, Edge e2); // compare edge weights
// core operations on graphs
// make new graph with nV vertices
Graph newGraph(int nV);
// free memory allocated to graph
void dropGraph(Graph);
// show "printable" representation of graph
void showGraph(Graph);
// add new edge to a graph
void insertE(Graph, Edge);
// remove an edge from a graph
void removeE(Graph, Edge);
// returns #vertices & array of edges
int edges(Graph, Edge *, int);

typedef Graph MSTree; // an MST is a specialised Graph

// EOF

#include "wgraph.h"

// is a vertex valid in a given Graph?
int validV (Graph g, Vertex v)
{
    return (g != NULL && v >= 0 && v < g->nV);
}

// make an Edge value
Edge mkEdge (Graph g, Vertex v, Vertex w, float weight)
{
    assert (validV (g, v) && validV (g, w));
    return (Edge) { .src = v, .dest = w, .weight = weight };
}
// compare Edge weights
float
compareE (Edge e1, Edge e2)
{
    return e1.weight - e2.weight;
}

// wgraph_adjmatrix.c

// since 0 is a valid weight, can't use it for "no edge"
// need a distinguished value to indicate "no edge"
#define NO_EDGE FLT_MAX  // imaginary distinguished float value
typedef struct GraphRep {
    int    nV;    // #vertices
    int    nE;    // #edges
    float **edges; // matrix of weights
} GraphRep;

// check whether two vertices are connected
int neighbours (Graph g, Vertex v, Vertex w)
{
    assert (validV (g, v) && validV (g, w));
    return (g->edges[v][w] != NO_EDGE);
}

// make new graph with nV vertices
Graph newGraph (int nV)
{
    assert (nV >= 0);
    int i, j;
    float **e = malloc (nV * sizeof (float *));
    assert (e != NULL);
    for (i = 0; i < nV; i++) {
        e[i] = malloc (nV * sizeof (float));
        assert (e[i] != NULL);
        for (j = 0; j < nV; j++)
            e[i][j] = NO_EDGE;
    }
    Graph g = malloc (sizeof (GraphRep));
    assert (g != NULL);
    g->nV = nV;
    g->nE = 0;
    g->edges = e;
    return g;
}

// free memory allocated to graph
void dropGraph (Graph g)
{
    assert (g != NULL);
    int i;
    for (i = 0; i < g->nV; i++)
        free (g->edges[i]);
    free (g->edges);
    free (g);
}

// show "printable" representation of graph
void showGraph (Graph g)
{
    assert (g != NULL);
    printf ("V=%d, E=%d\n", g->nV, g->nE);
    int i, j;
    for (i = 0; i < g->nV; i++) {
        int nshown = 0;
        for (j = i + 1; j < g->nV; j++) {
            float wt = g->edges[i][j];
            if (wt != NO_EDGE) {
                printf ("%d-%0.1f-%d ", i, wt, j);
                nshown++;
            }
        }
        if (nshown > 0)
            printf ("\n");
    }
}

// add new edge to a graph
void insertE (Graph g, Edge e)
{
    assert (g != NULL);
    Vertex v = e.src, w = e.dest;
    assert (validV (g, v) && validV (g, w));
    if (g->edges[v][w] == NO_EDGE)
        g->nE++;
    g->edges[v][w] = e.weight;
}

// remove an edge from a graph
void removeE (Graph g, Edge e)
{
    assert (g != NULL);
    Vertex v = e.src, w = e.dest;
    assert (validV (g, v) && validV (g, w));
    if (g->edges[v][w] == NO_EDGE)
        return;
    g->edges[v][w] = NO_EDGE;
    g->edges[w][v] = NO_EDGE;
    g->nE--;
}

// returns #vertices & array of edges
int edges (Graph g, Edge *es, int nE)
{
    assert (g != NULL && es != NULL);
    assert (nE >= g->nE);
    int i, j, n = 0;
    for (i = 0; i < g->nV; i++) {
        for (j = i + 1; j < g->nV; j++) {
            if (g->edges[i][j] != NO_EDGE) {
                assert (n < nE);
                es[n++] = mkEdge (g, i, j, g->edges[i][j]);
            }
        }
    }
    return n;
}

// wgraph_mst_kruskal.c

// assumes existence of list-of-edges ADT
MSTree kruskalFindMST (Graph g)
{
    Graph mst = newGraph (); // MST initially empty
    EdgeList eList;          // sorted list of edges
    int i;
    Edge e;
    int eSize = sizeof (Edge);
    edges (eList, g->nE, g);
    eList = qsort (sorted, g->nE, eSize, compareE);
    for (i = 0; mst->nE < g->nV - 1; i++) {
        e = eList[i];
        insertE (mst, e);
        if (hasCycle (mst))
            removeE (mst, e);
    }
}

// wgraph_mst_prim.c

// assumes existence of set-of-edges ADT
// assumes existence of set-of-vertices ADT
MSTree primFindMST(Graph g)
{
    EdgeSet mst = {}; //MST initially empty
    VertexSet vSet = {0}; // start vertex
    EdgeSet fringe = {}; //edges at "fringe"
    Vertex curr, s, t;  Edge e;  float w;
    fringe = edgesAt(0);
    while (card(vSet) < g->nV) {
        find e in fringe with minimum cost
        fringe = exclude(fringe, e)
        (s,curr,w) = e
        vSet = VSInclude(vSet, curr)
        mst = ESInclude(mst, e)
        foreach (e in edgesAt(curr)) {
            (s,t,w) = e  // s == curr
            if (!isElem(t,vSet))
                fringe = ESInclude(fringe,e)
        }
    }
}

// wgraph_sssp_dijkstra.c
#include "pqueue.h"

float *dist; // dist[d] = distance of shortest path from s..d
Vertex *pred; // pred[v] = predecessor of v in shortest path

// assumes existence of set-of-vertices ADT
// assumes existence of priority queue ADT
// abstract algorithm only ...
MSTree shortestPath (Graph g, Vertex s)
{
    VertexSet vSet = {};        // visited vertices
    PQueue todo = newPQueue (); // edges to be considered
    float *dist = malloc (g->nV * sizeof (float));
    for (int i = 0; i < g->nV; i++) dist[i] = MAXFLOAT;
    dist[s] = 0.0;
    Vertex *pred = malloc (g->nV * sizeof (Vertex));
    for (i = 0; i < g->nV; i++) pred[i] = -1;
    Vertex v, w, s, t;
    Edge e;
    float wt;
    PQueueJoin (todo, s, dist[s]);
    while (!PQueueIsEmpty (todo)) {
        v = PQueueLeave (todo);
        if (isElem (vSet, v)) continue;
        vSet = VSInclude (vSet, v);
        foreach (e = (v, w, wt) in edgesAt (v)) {
            if (dist[v] + wt < dist[w]) {
                dist[w] = dist[v] + wt;
                pred[w] = v;
                PQueueJoin (todo, w, dist[w]);
            }
        }
    }
}