Laboratory

Objectives

Assessment

Deadline

16 December 2018, 23:59:59
6 January 2019, 23:59:59

Marks
3
Submission
give cs2521 lab03

This lab should be done individually.

Setting up

Create a directory for this lab, change into it, and retrieve the files with the fetch command:

2521 fetch lab03
'./btree.h' -> '/web/cs2521/19T0/week03/files.ln/btree.h'
'./item_btree_node.h' -> '/web/cs2521/19T0/week03/files.ln/item_btree_node.h'
'./item.h' -> '/web/cs2521/19T0/week03/files.ln/item.h'
'./item_int.h' -> '/web/cs2521/19T0/week03/files.ln/item_int.h'
'./queue.cse32.o' -> '/web/cs2521/19T0/week03/files.ln/queue.cse32.o'
'./queue.cse64.o' -> '/web/cs2521/19T0/week03/files.ln/queue.cse64.o'
'./queue.h' -> '/web/cs2521/19T0/week03/files.ln/queue.h'
'./testable.h' -> '/web/cs2521/19T0/week03/files.ln/testable.h'
./
Makefile
btree.c
test_btree.c

This will have provided you with several files (as you may have guessed by its output):

Makefile
contains build rules.
btree.h
A binary tree interface. Do not change this file.
btree.c
A partial implementation of a binary tree; you need to modify this to finish implementing the interface.
test_btree.c
A stub for you to write tests in.
item.h
A generic Item type. Do not change this file.
item_int.h
Support for ints as Items. Do not change this file.
item_btree_node.h
Support for BTreeNodes as Items. Do not change this file.
queue.h
A Queue ADT interface. Do not change this file.
queue.cse32.o
A Queue ADT implementation, which we’ve provided as a precompiled binary for 32-bit CSE systems.
queue.cse64.o
A Queue ADT implementation, which we’ve provided as a precompiled binary for 64-bit CSE systems. (You probably don’t need this file.)

Download all the files.

The provided code contains tags marking unused variables. You should remove these tags as you implement those functions.

The syntax for manipulating function pointers is sufficiently opaque that type aliases are almost a requirement for legible code.

Exercise 0: test_btree.c

In test_btree.c, for each of the following tasks, you must write assert(3)-based unit tests to test your functions. You will lose half the marks for that exercise if you don’t have reasonable tests.

Exercise 1: Count Leaves (0.5 marks)

In btree.c, implement the function btree_size_leaf:

/** Returns the number of leaf nodes in the tree. */
size_t btree_size_leaf (BTreeNode tree);

Exercise 2: [thud] (0.5 marks)

In btree.c, implement the function btree_drop:

/** Destroy a tree, releasing all resources it requires. */
void btree_drop (BTreeNode tree);

Exercise 3: Keep a Level(-Order) Head (1 mark)

In btree.c, there’s some very useful mechanics for traversing a tree. btree.h only exposes one function, btree_traverse, which takes a tree, and two parameters describing what to do: a btree_traversal, an enumeration describing prefix-, infix-, postfix-, and level-order, and a btree_visitor_fp, which is either NULL or a pointer to a void-returning function that takes a btree_node reference. If the last argument is NULL, it returns an array of btree_node pointers, otherwise it returns NULL.

This seems all a bit opaque, so here’s an example that produces an array:

size_t n_nodes = btree_size (tree)
BTreeNode *nodes =
	btree_traverse (tree, BTREE_TRAVERSE_PREFIX, NULL);

for (size_t i = 0; i < n_nodes; i++) {
	BTreeNode node = nodes[i];
	Item nvalue = btree_node_value (node);

	char *str = item_show (nvalue);
	printf ("%s ", str);
	free (str);
}

free (nodes);

And here’s an example that prints the nodes as it goes.

static void node_print (BTreeNode node)
{
	Item nvalue = btree_node_value (node);

	char *str = item_show (nvalue);
	printf ("%s ", str);
	free (str);
}

btree_traverse (tree, BTREE_TRAVERSE_PREFIX, node_print);

There’s some code to make that work; if you’re interested, have a close read of btree_traverse and btree_traverse_visit. We’ll talk more about stateful iteration later on in the course.

In btree.c, you should implement the function btree_traverse_level, which performs the level-order traversal of a binary tree.

static void btree_traverse_level (btree_node *, traverse_state *);

Here’s a diagram to give you an idea of how a level-order traversal scans the nodes in a tree:

The output from this traversal would be .

A level-order traversal cannot be done recursively — at least, not easily — and is instead typically implemented using a queue of items. The algorithm is roughly:

level_order bst = do
	q = new Queue
	q.join bst.root
	while q.size > 0 do
		node = q.leave
		visit node
		q.join node.left  if exists node.left
		q.join node.right if exists node.right
	end
end

We’ve provided a Queue ADT interface and implementation, but with a twist: we’ve only given you a compiled object for the implementation. (You’ll want to do this exercise on CSE.)

We’ve also changed how Item works a little, so you need to explicitly turn values into Items, and explicitly turn Items back into values: for ints, use int_item_new to make an Item, and int_item to retrieve the value; for BTreeNodes, use BTreeNode_item_new to make an Item, and BTreeNode_item to retrieve the value.

Exercise 4: BSTs and Function Pointers (1 mark)

Write a function

size_t btree_count_if (BTreeNode tree, btree_pred_fp pred);

which traverses a binary tree, and counts the number of items in the tree for which the application of pred returns a true value.

For example, given the tree

and a function

bool even_p (Item n);

which returns true if n is even, and false otherwise –

– calling

n_even_elems = btree_count_if (tree, even_p);

would return the value 3 in n_even_elems.

You will need to write some predicate functions, including even_p, odd_p, and negative_p.

In your test_btree.c file, when you write test cases to test your function, write a suite of tests that use all predicates (even_p, odd_p, negative_p).

Submitting

You must get the lab marked by your tutor in your lab.

Submit your work with the give command, like so:

give cs2521 lab03 btree.c test_btree.c

Or, if you are working from home, upload the relevant file(s) to the lab03 activity on WebCMS3 or on Give Online.