Now that we have looked briefly at the technique for maintaining sorted keys in the KeyList application, let’s look at the . code of the project. In the KeyList application (Figure 5.8), to add a new entry, the user must click the Add New button. The program will let the user enter data in the various fields. When done, the user clicks the OK button to commit the changes. (You don’t see this button in Figure 5.8 because it appears, only while the user is entering a new entry; its action is signaled to the program with the click of the Add New button.) The new record will be added to the array DataArray () which is declared as follows:
The element DataArray(i, 0) holds the ISBNof the book, the element Dataarrayfi, 1) holds the publisher, the element DataArray(i, 2) holds the author of the current ·title, and the element DataArray(i,3) holds the book’s title. The is parameter is the index stored in the List’s ItemData property. Following is the code that’s ‘executed when the OK button is clicked
The program reads the data entered by the user in the various fields, searches the list With the SearchO function (explained in the following section) to see if an entry with this key exists, and theft inserts the key in the ListBox ‘control and stores the other fields in the Da~rrayO array. Because the List’s Sorted property is True, the item is automatically inserted in its proper position in the list, The A,rraylndex variable is global and points to the last element of the array.Each time a new element is added, the Arraylndex’ variable incre ases by an incrementof 1. The value of the Arraylndex property is stored in the ItemData array, in the position that corresponds to the newly added element. The following expression is the index of the newly added element in the list:
This expression is used to access the element of the Item Data array that corresponds to this item in the following statement:
list 1. ItemData (list 1 .New Index) Array”Index’
The List’s ItemData array holds the keys to the ar ay, and retrieving a book’s title or author is a simple task once you have its ISBN. Each time the user. clicks on an item in the list, the program extracts the item’s ltemData property and uses it as .an index to access the title’s fields in the DataArrayO array. The code that retrieves .’a record’s fields each fune a new item is selected on the list is shown next.
.Displaying a Record
If no item has been selected in the list, the progr.1m clears the contents of the various fields. If an element has l1een, selected in the list, the progHm will display the matching record’s fields on the corresponding textboxes, by calling the ShoWRecordsO subroutine. The ShowButtonsO subroutine hides the OK and Cancel buttons and displays. the Delete and Add New buttons. This action normally takes place after the user has added a new record and’ clicked the OK button. It’s possible, however, to abandon the entry of a new record by. clicking an eIemen to the list
Locating an Item in the ListBox Conter
The of function locates a specific item in the list. The Listbox vontrol doesn’t providea specific method, but you can find out whether a specific ite-m exists in the list and its.index (if it exists) by setting the control’s Iext property the desired value. The text property of the LlstBox control can also be set to a specific value at runtime. If you set it to the value of-a specific list item from within your code, the item is automatically selected and the Listlndexproperty is the item’s Index value.
The SearchO functidn uses this trick to locate the item whose key has been ” . entered in the TextBox control. The SearchO function’s codeis shown next
The Search () Function
To locate an item in the ListBox control, you can provide a textbox where the user can enter a string. In the TextBox control’s Change event, you must insert the following code to call the Searcht) function to locate the item whose key is entered in the TextBox control. To program the Change event handler of the ISBN textbox so that it can also locate items in the list, use the following code.
The ISBN TextBox’s Change Event Handler
This is how the KeyList application works. You can locate items in the list by using the mouse or entering their key in the ISBN box. However, this’ technique can’t match partial keys. In other words, if the ISBN value doesn’t match an entry in the list exactly, no item will be selected. For example, suppose the list contains the key 1984-2030-3. The ISBN values 1984-2030 or 1984-20 won’t cause a partial match as one would expect. .
Ideally, the application should highlight the first item in the list that matches, even partially, the key value in the ISBN box ..If its first five digits make it unique, then there’s no reason to’ type the remaining digits. To perform partial matches on the list’s items, you must use a more advanced searching technique; which is described next.
Searching a Sorted List
In this section we’ll revise the KeyList application to incorporate the feature of partial matching. The revised application is called BSearch (for Binary Search), and you’ll find it in the BSearch folder on the CD. As the user types chara-cters in the ISBN field, the program selects the first item in the IJstBox control that matches the
partial entry of the ISBN field. This is a standard operation of the ListBox control. If the ListBox control has the focus and the user types characters, the matching item in the control is selected automatic ••lly. This operation is duplicated in the ISBN TextBox control for two reasons:
• Convenience When users type characters in the TextBox control, they can see the string and edit it.
• Practicality The algorithm that implements the search is practical, and it’s likely that you’ll use it in your applications.
Searching for a specific item ir.a sorted arrangement of data is a common operation, and it can be implemented efficiently with the Binaru Search algorithm. The . Binary Search algorithm starts by comparing the desired element with the middle’ derytent of the sorted ~t (or array) ..If it’s alphabetically or numerically larger dement of the list, the upper half of the list is rejected without further consideration. If the opposite is true, the lower half of the list is rejected. The same process continues with the selected half of the list. Another half is rejected again, and the algorithm continues until it finds a single element, which should be the desired one. If not, the element is not in the list. Figure 5.10 shows-the steps in locating an item in a sorted list with eight items. The items rejected at each step are marked in gray.
Suppose you have a list with 1,024 elements: After the first comparison, 512 elements will be rejected. Of the 512 remaining elements; 256 will be rejected ‘ with the second comparison. After the third comparison, only 128 of the initial , 1,024 elements will be left. If this process continues, the size of the list will, be reduced to 64 elements, then to.32, then to 16, and so on down to a single, element. It will take only ten comparisons to reduce the 1,024 elements to a sutgle element, which should bethe desired one. The Binary-Search algorijhmexploits the sorted list and is extremely efficient.