Laboratory Solutions

// COMP2521 19T0 ... lab 01: a linked list implementation
//
// 2018-11-24	Jashank Jeremy <jashank.jeremy@unsw.edu.au>
// YYYY-mm-dd	Your Name Here <zNNNNNNN@student.unsw.edu.au>

#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>

#include "lists.h"

/** Traverses and prints the list. */
void list_print (link list)
{
	link curr = list;
	while (curr != NULL) {
		printf ("[%d]->", curr->item);
		curr = curr->next;
	}
	puts ("|");
}

/** Create a new node, initialised with the item provided.
 * Return a pointer to node (link) */
link node_new (Item it)
{
	struct node *new = malloc (sizeof *new);
	if (new == NULL)
		err (EX_OSERR, "couldn't allocate %zu bytes", sizeof *new);
	(*new) = (struct node){ .item = it, .next = NULL };
	return new;
}

/** Insert a new node into a given non-empty list.
 * The node is inserted directly after the head of the list. */
void list_insert_next (link list, link node)
{
	assert (list != NULL);
	assert (node != NULL);

	node->next = list->next;
	list->next = node;
}

/** Return the sum of all items in list */
int list_sum_items (link list)
{
	int sum = 0;
	for (link curr = list; curr != NULL; curr = curr->next)
		sum += curr->item;
	return sum;
}

/** Frees all memory used in the list */
void list_drop (link list)
{
	for (link tmp, curr = list;
		 curr != NULL;
		 curr = tmp)
	{
		tmp = curr->next;
		free (curr);
		if (tmp == list) break;
	}
}


/** Create a circular list with the specified number of nodes,
 * with each link storing data from 1 to the number of nodes. */
link clist_new (int n_nodes)
{
	assert (n_nodes >= 0);

	link head = NULL;
	link prev = NULL;

	for (int i = 1; i <= n_nodes; i++) {
		link node = node_new ((Item) i);
		if (head == NULL)
			head = prev = node;

		prev->next = node;
		node->next = head;
		prev = node;
	}

	return head;
}

/** print the data in a circular fashion starting from any node */
void clist_print (link clist)
{
	for (link curr = clist; curr != NULL; curr = curr->next) {
		printf ("[%d]->", curr->item);
		if (curr->next == clist) break;
	}
	puts ("...");
}


static dlink dnode_new (Item it)
{
	struct dnode *new = malloc (sizeof *new);
	if (new == NULL)
		err (EX_OSERR, "couldn't allocate %zu bytes", sizeof *new);
	(*new) = (struct dnode){ .item = it, .next = NULL, .prev = NULL };
	return new;
}

/** Create a double-linked list which contains the same values,
 * in the same order as 'list' */
dlink dlist_new_from_list (link list)
{
	dlink dhead = NULL;
	dlink dtail = NULL;

	for (link curr = list; curr != NULL; curr = curr->next) {
		dlink dnode = dnode_new (curr->item);
		if (dhead == NULL) {
			dhead = dnode;
		} else {
			dtail->next = dnode;
			dnode->prev = dtail;
		}
		dtail = dnode;
	}

	return dhead;
}

/** Print a doubly-linked list. */
void dlist_print (dlink list)
{
	printf ("|");
	for (dlink curr = list; curr != NULL; curr = curr->next)
		printf ("-[%d]-", curr->item);
	puts ("|");
}

/** Frees all the memory used in the double-linked list */
void dlist_drop (dlink list)
{
	for (dlink tmp, curr = list; curr != NULL; curr = tmp) {
		tmp = curr->next;
		free (curr);
	}
}

// COMP2521 19T0 ... lab 01: test a linked list implementation
//
// 2018-11-24	Jashank Jeremy <jashank.jeremy@unsw.edu.au>
// YYYY-mm-dd	Your Name Here <zNNNNNNN@student.unsw.edu.au>

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "lists.h"

int main (void)
{
	/**
	 * These tests follow the create/mutate/inspect pattern discussed in
	 * lectures: we create a well-known state, we perform a simple
	 * operation, and we verify that the state has changed in ways we
	 * expect, _including_ in those places we expect no change to occur.
	 *
	 * You should, of course, do a better job of carving up your tests
	 * into more neatly contained test cases than I've done here.  My
	 * intent here is to very clearly spell out the rigour needed in
	 * testing even these apparently-simple functions.
	**/

	////////////////////////////////////////////////////////////////////

	puts ("Test 1: `list_print' empty list");
	link list = NULL;
	list_print (list);

	puts ("Test 2: `node_new' and `list_insert_next'");
	link ln1 = node_new (1);
	assert (ln1->item == 1);
	assert (ln1->next == NULL);

	link ln2 = node_new (2);
	list_insert_next (ln1, ln2);
	assert (ln1->item == 1);
	assert (ln1->next == ln2);
	assert (ln2->item == 2);
	assert (ln2->next == NULL);

	link ln3 = node_new (3);
	list_insert_next (ln1, ln3);
	assert (ln1->item == 1);
	assert (ln1->next == ln3);
	assert (ln3->item == 3);
	assert (ln3->next == ln2);
	assert (ln2->item == 2);
	assert (ln2->next == NULL);

	puts ("Test 3: `list_print' "
	      "(expected `[1]->[3]->[2]->|' and sublists)");
	list_print (ln1);
	list_print (ln3);
	list_print (ln2);

	////////////////////////////////////////////////////////////////////

	puts ("Test 4: `list_sum_items'");
	assert (list_sum_items (list) == 0);
	assert (list_sum_items (ln1) == 1 + 3 + 2);

	////////////////////////////////////////////////////////////////////

	puts ("Test 5: `clist_new'");
	link cl1 = clist_new (4);
	assert (cl1 != NULL);
	assert (cl1->item == 1);
	assert (cl1->next != NULL && cl1->next != cl1);
	link cl2 = cl1->next;
	assert (cl2->item == 2);
	assert (cl2->next != NULL);
	assert (cl2->next != cl1);
	assert (cl2->next != cl2);
	link cl3 = cl2->next;
	assert (cl3->item == 3);
	assert (cl3->next != NULL);
	assert (cl3->next != cl1);
	assert (cl3->next != cl2);
	assert (cl3->next != cl3);
	link cl4 = cl3->next;
	assert (cl4->item == 4);
	assert (cl4->next != NULL);
	assert (cl4->next != cl2);
	assert (cl4->next != cl3);
	assert (cl4->next != cl4);
	assert (cl4->next == cl1);

	puts ("Test 6: `clist_print'");
	clist_print (cl1);
	clist_print (cl2);
	clist_print (cl3);
	clist_print (cl4);

	////////////////////////////////////////////////////////////////////

	puts ("Test 7: `dlist_new_from_list' on empty list");
	dlink dl = dlist_new_from_list (list);
	assert (dl == NULL);

	puts ("Test 8: `dlist_new_from_list'");
	dlink dl1 = dlist_new_from_list (ln1);
	dlink dl2, dl3;
	assert (dl1 != NULL);
	assert (dl1->item == 1);
	assert (dl1->prev == NULL);
	assert (dl1->next != NULL && dl1->next != dl1);
	dl3 = dl1->next;
	assert (dl3->item == 3);
	assert (dl3->prev == dl1);
	assert (dl3->next != NULL && dl3->next != dl1);
	dl2 = dl3->next;
	assert (dl2->item == 2);
	assert (dl2->prev == dl3);
	assert (dl2->next == NULL);

	puts ("Test 9: `dlist_print'");
	dlist_print (dl1);
	dlist_print (dl3);
	dlist_print (dl2);

	////////////////////////////////////////////////////////////////////

	puts ("Test 10: `list_drop' on LL and CLL");
	list_drop (ln1);
	list_drop (cl1);
	puts ("Test 11: `dlist_drop'");
	dlist_drop (dl1);

	puts ("\nAll tests passed.  You are awesome!");
	return EXIT_SUCCESS;
}