Laboratory 10

CSCI 132 Data Structures--Spring 2014

Laboratory 10
Due at the beginning of class, Wednesday, 4/23

In today's lab you will practice working with hash tables.

The code for this lab is available in the directory:

~csci132/labs/lab10

Start the lab as follows:

Copy the code for lab 10 into your labs folder by typing:
Verify that the lab 10 directory contains the following files:
- playLife.cc

1. The game of life revisited--using hash tables

Note:

Early in the semester, we discussed the game of life, and implemented some of the functions in the life.cc class. (See lab2 to recall our earlier assignment). We had to use various tricks to deal with conditions when life objects moved off the assigned grid, as the life game was represented on a finite 2D table. However the real game of life is meant to be played on a grid of infinite dimensions. Cells at any position should be able to be born or to die. Obviously, we cannot implement the game of life on an infinite 2D grid in C++, since we do not have infinite memory. However, we can implement it in a different way, using a hash table. In this implementation, we do not represent every cell on our 2D grid. Instead, we only keep track of which cells are alive. To do this, we use a hash table. If a cell at position (row, col) is alive, it is stored at its corresponding position in the hash table. If it is not alive, it is not represented.

In order to update our life game, we need to calculate new cells that are born and die based on the number of live neighbors. The only cells that can change status are those that are alive or those that are neighbors of the live cells. Our update() function needs only examine these cells. However, it is difficult to traverse a hash table, so in addition to using the hash table to keep track of live cells, we will also use a list that lists all the live cells. The update function will traverse this list and compute which live cells or which neighbors of live cells change status.

Representations: The cells in the grid for the life game are instances of the Cell class (see the file, cell.h, which has the specification and implementation of this class). The data members of this class are two integers: row and col. Because these cells are created dynamically (as each cell is born) and deleted dynamically (when cells die) it is easier to work with pointers to the Cell objects. Thus, both our linked list and hash table contain pointers to cells in each location as opposed to the cells themselves. In addition, the Hash_table class uses chaining to resolve collisions. Thus each occupied position in the hash table will contain a pointer to a linked list of pointers to cell objects. An example from the text of such an "indirect" linked list is shown below:

The Life class

life.h

List<Cell *> *living; //A pointer to a linked list of pointers to cell objects
Hash_table *is_living; //A pointer to an instance of the Hash_table class

life.cc

row

column

In addition this class has several member functions:
Public member functions:

Life(); //constructor function
void initialize(); //read in initial configuration
void print(); //print out current configuration
void update(); //compute living cells in next generation from current generation
~Life(); //destructor function

bool retrieve(int row, int col)const; //retrieve the value of a cell at position (row, col)
Error_code insert(int row, int col); //insert a new living cell at position (row, col)
int neighbor_count(int row, int col)const; //count the number of living neighbors of the cell at (row, col)

The Hash_table class (see the hash.h file) has one private data member:

List<Cell *> table[hash_size]; // hash table of pointers to linked lists of pointers to cells.

The Hash_table class also has the following public member functions:

Error_code insert(Cell *new_entry); //insert a pointer to the cell, new_entry, into the table
bool retrieve(int row, int col)const; //return true if the cell at position (row, col) is in the table.

These classes make use of the functions and definitions of a linked list provided in the List class (see list.h and list.cc).

Your task:
Nearly the entire program has been implemented for you, however there are several functions that need to be completed. Your task is to fill in the function stubs for the following functions:

Fill in these functions in the Hash_table class:

Error_code insert(Cell *new_entry); //insert a pointer to the cell, *new_entry, into the table
bool retrieve(int row, int col)const; //return true if the cell at position (row, col) is in the table.

Fill in this function in the Life class:

int neighbor_count(int row, int col)const; //count the number of living neighbors of the cell at (row, col)

You may find the following comments helpful:

Implementing the insert() function for the Hash_table class:

First, compute the position for insertion by computing the hash function for the row and column for *new_entry. The hash function has been provided for you. Recall that since new_entry is a pointer to a Cell object, you access the data members using the arrow notation.
Store the result of the hash function in an integer variable named probe.
Before inserting the cell pointer, first search the list at that position to make sure the item is not already there. Use the sequential_search function (provided for you and described below) to search the list.
If a pointer to a cell with the same row and col is found, return the Error_code duplicate_error.
Otherwise, insert your new_entry pointer into the linked list at the computed location of the table array (insert it at position 0 of the list). Return the result of inserting your new_entry into the list at the given table location (use the list insert function).

The sequential_search() function is specified as follows:

Error_code sequential_search(const List &search_list, int my_row, int my_col, int &location)

The first parameter is the list to be searched, the second and third parameters are the row and col keys to be searched for in the cells of the list, and the fourth parameter is the location of the cell pointer if it is found in the list.

Implementing the retrieve() function for the Hash_table class:

As with the insert function, start by computing the table location using a call to the hash function.
Use the sequential_search function to determine whether the cell in question is present in the linked list at the given table location.
If the cell is present, return true.
Otherwise return false.

Implementing the neighbor_count() function for the Life class:

Loop through the 3 x 3 grid from row-1, col-1 to row+1, col+1 (use a nested for loop).
For each cell in the grid, retrieve the value from the hash table, *is_living. The value will be true if the cell is present (i.e. living) and false otherwise. Recall that since is_living is a pointer to the Hash_table class, hence use the arrow notation to access the Hash_table retrieve() function.
For each cell found to be living, increment the count.
After counting the 3x3 grid, subtract the value of the central cell (which is not its own neighbor).
Return the total.

Compile your program with the following compile command:

g++ -g -Wall playLife.cc -o playLife

Test out your program by entering the following pairs of integers:

Recall that this pattern will oscillate back and forth from vertical to horizontal in successive generations.

2. Practicing with Radix sort

Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay Ron Jan

3. Computing hash functions

10 100 32 45 58 126 3 29 200 400 0

a) Determine the hash addresses and find how many collisions occur when these keys are reduced by applying the operation %hash_size.

b) Determine the hash addresses and find how many collisions occur when these keys are first folded by adding their digits together (in ordinary decimal representation) and then applying %hash_size.

What To Turn In.

A printout of your hash.cc file
A printout of the neighbor_count() function for the life class.
Written solutions to problems 2 and 3.
Submit your lab with the submit function:

Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file (e.g. specification of the stack class).

Reminder.
Be sure to save a copy of each file in your labs directory. It is your responsibility to keep the copies of all programs written for this course until your graded assignment is returned.