Software Design Using C++
Fifth Advanced Windows Forms Example
The Idea
The main idea is to create a Windows forms app that displays a hash table. Furthermore,
it lets the user insert, delete, or lookup items one at a time. The hash table is displayed
in a ListView that shows not just the hash table data, but also the order (1, 2, 3, etc.) in
which the slots of the table are accessed when doing a given operation (insert, delete, or lookup).
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
Create a new Windows forms app, named something like hashtable or hashdemo.
Change FormBorderStyle to Fixed3D, MaximizeBox to False, and Text to "Hash Demo".
Resize the form as needed so that it is about the same size as that shown in
our picture of the running app.
Designing the Form
Go ahead and place the needed controls on the form. As you can see, there is a label with "Key:"
as the text and next to it a TextBox. Make the name of the TextBox to be KeyTextBox and clear out
its Text property. Then there is a label with "Result:" as the text and next to it another TextBox.
Change the name of this box to ResultTextBox and clear out the Text property so that it is the empty
string. You can make this box readonly if you wish, since it is only used for output, not input.
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
The code for the hash table itself is based on the concepts discussed in the
Hash Tables page, though the particular project
on that page stored the hash table on disk whereas here we keep our small hash table in main memory.
Another difference is that there we were more interested in a functional hash table.
Here the main point is to create an app that illustrates how the hash table works.
Thus we show the rehash path for every insert, delete, or lookup. Although we produce
a functional hash table, it is not as powerful as the one under the
Hash Tables page.
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
Change the top of your Form1.h code to include stdafx.h . Thus it should begin like this:
#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
At the bottom of Form1.cpp place the following code for the click handler for
the insert button:
/* 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
At this point save all of your files. Then build and run your application to
see that it works reasonably. The running app should look like the one shown in
our picture of the running 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.
Back to the main page for Software Design Using C++
|