Software Design Using C++

Fifth Advanced Windows Forms Example

The Idea

You can see the design of the app and its overall operation in this picture. Note that the ListView shows the index number for each row of the hash table (which is essentially an array). The second column shows the key value contained in that entry (with -1 used to mark an empty location and -2 used to mark an entry that has been deleted). The last column shows (using 1, 2, 3, etc.) the order in which the rows of the table were accessed in order to carry out the desired operation. In this case, the user placed 41 into the text box for the key and then clicked on the button labeled Insert. Note that the box labeled "Result:" says that the insert succeeded. This was, by the way, a fairly expensive insert (in terms of processing time) as the app had to check indices 7, 9, 11, 13, 15, 0, and 2 before finding a location (either empty or deleted) into which to place the new key of 41. It would be more typical for a hash table to also include data associated with each key, but this was omitted to keep the demo simpler. Finally, notice that the rehash function is evidently one that adds 2 to the index value (with wraparound if adding 2 would go beyond the end of the table).

Getting Started

Designing the Form

Below these 4 items is a row of 3 buttons. From left to right, make their names InsertButton, DeleteButton, and LookupButton. Make their Text properties to be Insert, Delete, and Lookup respectively.

We set up the ListView control much like the one used in the Second Advanced Windows Forms Example. Put this control under the others and resize it to fill most of the lower three-fourths of the form. Change its name to HashTableListView. Change the Bold Property under Font to True. Also set the ForeColor to Blue, GridLines to True, and the View property to Details.

You can adjust the TabIndex and TabStop properties of the controls if you wish. Save all of your files. Also right click on the new project in Solution Explorer and set this project to be the startup project.

Coding HashTableClass

First, let's set up HashTableClass. In Solution Explorer right click on "Header Files" under your project. Select Add, Add New Item. Click on the Header File icon and fill in hash.h as the name of the new file. Then copy in the code for this file from this hash.h file.

We use PrimeSize to hold the size of the hash table. This should always be a prime number. For our demo we use 17, but this could be changed here. We will need to mark slots in the hash table array as empty or deleted on occasion, so we set up constants for these (-1 and -2 respectively). Since we are just going to store integers in our hash table, KeyType is the same as an int, but that could be changed to something else here (such as type long). We create a type called TableArrayType to make it easy to set up our table array later. We also have a type called OrderArrayType. This is the type for the array that will hold the numbers that indicate the order in which the array slots are accessed, that is, the so-called rehash path.

Next we have the actual definition of HashTableClass. In the public section we have a constructor as well as Insert, Delete, Lookup, Empty, and Full functions. TableArray, which holds the hash table data, and OrderArray, which holds the rehash path information, are also in the public section. Typically the array for the hash table would be made private and there would be no OrderArray. The latter is added to make our hash table demo more informative. The arrays fields are made public so that we will have easy access when we go to display their data on our form. (The usual design is make the data fields private and to provide public "get" functions to retrieve whatever data might be needed. In our app we use the quick and easy solution instead.) In the private section of the class is NumItems, which indicates how many keys are currently in the hash table, as well as the hash and rehash functions. More details on the functions of this class will be given below when we examine the code for each.

Let's next fill in the code for the functions for HashTableClass. Use Solution Explorer to right click on "Source Files" for your project. Select Add, Add New Item. Click on the C++ File icon and fill in hash.cpp as the file name. Copy in the needed code from this version of the hash.cpp file. Note that it has been modified to include the stdafx.h header file used by Visual Studio to give access to commonly used header files.

Since hash.cpp is going to need access to hash.h, let's include it in stdafx.h as its comments suggest. Thus stdafx.h should look like this:

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
#pragma once

#define WIN32_LEAN_AND_MEAN   // Exclude rarely-used stuff from Windows headers
// C RunTime Header Files
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <tchar.h>

// TODO: reference additional headers your program requires here
#include "hash.h"

Now back to the hash.cpp file. Copy into it the code from this version of the hash.cpp file. The constructor for the HashTableClass sets NumItems to 0 and initializes the TableArray to hold all -1's, the EmptyItem constant. The OrderArray is set up to contain all 0's (whereas 1, 2, 3, etc is used when we later show the rehash path).

The Empty and Full functions return a boolean value to tell you whether the hash table is empty or full, respectively. To do this, they simply check to see if NumItems matches 0 or the maximum value. It was a good idea to include this NumItems field in our class, right?

Next, let's move to the bottom of the hash.cpp file and check out the Hash and Rehash functions. The Hash takes as its only parameter the key that we are working with. (We may be trying to do an insert of it, a delete, or a lookup.) The hash function value is just the value of Key % PrimeSize, where % is the mod operator, the one that gives the remainder after integer division. For example, 4 % 17 is 4 itself, 17 % 17 is 0, and 21 % 17 is 4 again (since 17 * 1 + 4 = 21). The Rehash function is rather similar. Its only parameter is Index, which is intended to hold the current index that we have hashed or rehashed to in our table. The Rehash function then uses (Index + 2) % PrimeSize as the rehash value. In most cases this is simply the index value 2 bigger than the current one. However, it wraps around if we would fall off the end of the array. For example, (16 + 2) % 17 = 1.

Now that we know how the Hash and Rehash functions work, we can look at the Insert function. The only parameter to this function is the key that we want to insert from the table. Note that we assume that we are not inserting a duplicate of an item that is already in the table. (If we allowed this, our code to delete from the table would not work correctly.) Since we want to show the user the rehash path used during the insertion process (even if it is the trivial case of trying one slot, it is empty, and we just insert there), we first place 0's in all locations of OrderArray so as to wipe out any old rehash path information. If the table is full we simply return false so as to say that the insertion failed. Otherwise, we hash the key to get an index to try in the table. At this point we also place a 1 into OrderArray at this same index to indicate that this is the first array slot that we tried. If the table slot at this index is marked as empty or deleted, then we insert our key at this location. We also increment NumItems, of course. If this location was not empty or deleted, we rehash that index to produce a new one to check. As you can see, this checking is done in a loop that allows a maximum of PrimeSize indices to be tried. Since our rehash function does not repeat any indices in this number of times around the loop, the loop must terminate (if for no other reason) when every single index in the table has been checked to see if it is empty or deleted. Note that every time we check a table location, the corresponding slot in OrderArray has the next sequence number placed into it. Thus the rehash path gets recorded as 1, 2, 3, etc.

The design of the Delete function is similar, so less will be said about it. We don't even try deletion if the table is empty, since in that case there is nothing to delete. The hashing and rehashing are very similar. Each time around the loop we check the current index in TableArray, but in this case we are looking for a key that matches that supplied as the parameter to our Delete function. If we find a match, we mark this array slot as deleted. If we ever reach an empty location we give up the search for the key to be deleted, as it could not be beyond this spot. (This is why we use distinct markers for empty and deleted, by the way.)

The Lookup function is much like the previous two. However, it has an additional parameter, the reference parameter Index, which is to hold the index where we found the key for which we were looking. After examining the code for the previous functions, you should be able to easily figure out this one, so we will not say more about it here.

Save all of your files before continuing.

Code Additions to Form1.h

#pragma once

#include "stdafx.h"   // Added to get access to HashTableClass.

In the same file, find the beginning of the Form1 class and adjust it as shown here: The comments indicate the additions. First, we add to this class a private pointer field, HTPtr. Then in the constructor for this class we set HTPtr to point to a newly created object belonging to HashTableClass. This object is our hash table and is initially empty.

public __gc class Form1 : public System::Windows::Forms::Form
{
private:
   HashTableClass * HTPtr;   // Set up pointer variable.

public:
   Form1(void)
      {
      InitializeComponent();
      HTPtr = new HashTableClass();   // Create a hash table object and have HTPtr point to it.
      }

As in our previous example, the Fourth Advanced Windows Forms Example we need a way when the app ends to free up the memory used by that hash table object. We again try a quick and dirty method: placing the code to free up this object inside of the existing Dispose method of the Form1 class:

void Dispose(Boolean disposing)
{
    delete HTPtr;   // Added to get rid of unmanaged HashTableClass object.
    if (disposing && components)
        {
        components->Dispose();
        }
    __super::Dispose(disposing);
}

At the bottom of Form1.h, put the function prototypes for the click handlers for the 3 buttons as well as for the helping function DisplayTable. The easiest way to do this may be to double click on each button in Design View for Form1.h and then to use Class View's Add Function wizard, but you may prefer to just write all of the code by hand. In any case, the bottom of your Form1.h file should look like this:

    /* Click handler for the InsertButton.
       This function takes the number from the input box, KeyTextBox, and inserts it,
       if possible, into the hash table.  This function also displays the resulting
       hash table on the form.
    */
    private: System::Void InsertButton_Click(System::Object * sender, System::EventArgs * e);

    /* Click handler for the DeleteButton.
       This function takes the number from the input box, KeyTextBox, and deletes it,
       if possible, from the hash table.  This function also displays the resulting
       hash table on the form.
    */
    private: System::Void DeleteButton_Click(System::Object * sender, System::EventArgs * e);

    /* Click handler for the LookupButton.
       This function takes the number from the input box, KeyTextBox, and finds it,
       if possible, in the hash table.  The index of where it was found is displayed.
       This function also displays the resulting hash table on the form.
    */
    private: System::Void LookupButton_Click(System::Object * sender, System::EventArgs * e);

    /* This helping function displays the current hash table on the form.
    */
    private: System::Void DisplayTable(void);

};
}

The comments help to explain what each function does. Save all of your files before going on.

Code Additions to Form1.cpp

/* Click handler for the InsertButton.
   This function takes the number from the input box, KeyTextBox, and inserts it,
   if possible, into the hash table.  This function also displays the resulting
   hash table on the form.
*/
System::Void Form1::InsertButton_Click(System::Object * sender, System::EventArgs * e)
   {
   KeyType Key;

   ResultTextBox->Clear();
   HashTableListView->Clear();

   HashTableListView->Columns->Add(S"Index", 64, HorizontalAlignment::Right);
   HashTableListView->Columns->Add(S"Key", 64, HorizontalAlignment::Right);
   HashTableListView->Columns->Add(S"Order", 64, HorizontalAlignment::Right);

   try
      {
      Key = KeyTextBox->Text->ToInt32(NULL);
      // Insert Key into the table:
      if (HTPtr->Insert(Key))
         ResultTextBox->Text = S"Insert succeeded";
      else
         ResultTextBox->Text = S"Insert failed";
      }
   catch (...)
      {
      ResultTextBox->Text = S"Invalid key";
      }

   DisplayTable();
   }

As you can see, the above function begins by clearing out any old information from ResultTextBox and the ListView that displays the hash table. We then set up this ListView control so that it begins with the column labels "Index", "Key", and "Order". If you have forgotten how this works, refer to the Second Advanced Windows Forms Example.

The key to be inserted is then retrieved from KeyTextBox. The Insert function from HashTableClass is then used on the hash table object that HTPtr points to, in the hope of inserting our key value into the table. Since the Insert function returns true or false to tell us if it worked, we check that and place an appropriate matching message into ResultTextBox. If an exception is raised (probably due to bad data in KeyTextBox, we put the helpful "Invalid key" message into ResultTextBox. Finally, we use the helping function DisplayTable to display the hash table and associated rehash path information on our form.

Next we add the code for the delete button's click handler to the same Form1.cpp file. Make it match this:

/* Click handler for the DeleteButton.
   This function takes the number from the input box, KeyTextBox, and deletes it,
   if possible, from the hash table.  This function also displays the resulting
   hash table on the form.
*/
System::Void Form1::DeleteButton_Click(System::Object * sender, System::EventArgs * e)
   {
   KeyType Key;

   ResultTextBox->Clear();
   HashTableListView->Clear();

   HashTableListView->Columns->Add(S"Index", 64, HorizontalAlignment::Right);
   HashTableListView->Columns->Add(S"Key", 64, HorizontalAlignment::Right);
   HashTableListView->Columns->Add(S"Order", 64, HorizontalAlignment::Right);

   try
      {
      Key = KeyTextBox->Text->ToInt32(NULL);
      // Delete Key from the table:
      if (HTPtr->Delete(Key))
         ResultTextBox->Text = S"Delete succeeded";
      else
         ResultTextBox->Text = S"Delete failed";
      }
   catch (...)
      {
      ResultTextBox->Text = S"Invalid key";
      }

   DisplayTable();
   }

The coding for this function is similar to the previous one. It clears out the same 2 output boxes and sets up the 3 column headings. Then it retrieves the key from KeyTextBox and uses the HashTableClass's Delete function to attempt to delete this key from the hash table object that HTPtr is pointing to. Depending on the true/false return value from the Delete function, an appropriate message is placed in ResultTextBox. As before, if whatever is in KeyTextBox cannot be converting to an integer, an Invalid key" message is placed into ResultTextBox. At the end, DisplayTable is used to display the current hash table contents (including the rehash path info).

Now copy into the bottom of the same file the following code for our final click handler:

/* Click handler for the LookupButton.
   This function takes the number from the input box, KeyTextBox, and finds it,
   if possible, in the hash table.  The index of where it was found is displayed.
   This function also displays the resulting hash table on the form.
*/
System::Void Form1::LookupButton_Click(System::Object * sender, System::EventArgs * e)
   {
   KeyType Key;
   int Index;

   ResultTextBox->Clear();
   HashTableListView->Clear();

   HashTableListView->Columns->Add(S"Index", 64, HorizontalAlignment::Right);
   HashTableListView->Columns->Add(S"Key", 64, HorizontalAlignment::Right);
   HashTableListView->Columns->Add(S"Order", 64, HorizontalAlignment::Right);

   try
      {
      Key = KeyTextBox->Text->ToInt32(NULL);
      // Lookup Key in the table:
      if (HTPtr->Lookup(Key, Index))
         ResultTextBox->Text = String::Concat(S"Found at ", Index.ToString());
      else
         ResultTextBox->Text = S"Lookup failed";
      }
   catch (...)
      {
      ResultTextBox->Text = S"Invalid key";
      }

   DisplayTable();
   }

Since the code for this function is so similar to the previous two, little needs to be said about it. Note the use of the Concat function to concatenate 2 strings, in this case the message "Found at " and a string containing the index number where the desired key was located in the hash table.

Finally, copy into the bottom of our Form1.cpp file the following code for our helping function:

/* This helping function displays the current hash table on the form.
*/
System::Void Form1::DisplayTable(void)
   {
   int k;
   ListViewItem * Item;

   for (k = 0; k < PrimeSize; k++)
      {
      Item = new ListViewItem(k.ToString());
      Item->SubItems->Add(HTPtr->TableArray[k].ToString());
      Item->SubItems->Add(HTPtr->OrderArray[k].ToString());
      HashTableListView->Items->Add(Item);
      }
   }

This function loops through all PrimeSize lines of the table. For each line it displays the index, the key from this line of the table, and the OrderArray number for this index (so that the rehash path can be seen). The code used to do this is similar to that used in the Second Advanced Windows Forms Example, so refer to it if need be.

Building and Testing the App

In testing the insert button, test cases where the new key is inserted directly, as well as cases where rehashing has to be used. Here is a picture of an example. Note that the key to be inserted, 47, hashed to index 13, which was in use. The algorithm then rehashed to index 15, which was also in use, and then to index 0, which was available. Thus the 47 was inserted at index 0. Not the wraparound to index 0. In testing insertion be careful not to insert duplicate items as our code does not handle that.

For testing the delete button, try cases where the key to be deleted is found at the index hashed to as well as cases where a rehash path has to be found to locate the key. Here is a picture of the latter case. Also check cases where the key to be deleted is not present, both with and without rehashing.

For testing the lookup button, first try looking for items that are present, both those that are found directly at the location hashed to and those that require rehashing. For the latter, be sure to check the case where a deleted item has to be skipped over. Here is a picture of such a case. Note that the 13 hashed to index 13, but the item there was not the key 13. Thus the algorithm rehashed to 15, which was marked as deleted. The algorithm correctly kept going, rehashing to location 0, which had a key that did not match the desired 13. Then it rehashed to index 2, where the 13 was finally found. Notice that the message "Found at 2" did get displayed in the text box for the overall result.

In testing the lookup button, also be sure to test cases where the lookup should fail because the desired key is not in the table. Don't just test for keys that, if they were present, would be directly at the index hashed to. Also test keys that are not present and that cause the rehash function to be used, especially the case where a deleted item is in the rehash path and needs to be skipped over. Here is a picture of this case. We try to delete the key 16, which obviously hashes to index 16. Since that location is marked as deleted, the algorithm rehashes to index 1 where there is no match, then to index 3 with no match, and finally to index 5 which is an empty location. That is where the lookup stops. The conclusion is that 16 cannot be in the table and thus cannot be deleted.