Author: Tomas Rutkauskas
How to do a binary search on an alphasorted TListView
Answer:
If you want to use a fast searching algorithm (binary search for example) the
listview has to be sorted on the column you do the duplicate check on. If it is not
sorted you have to use the listviews FindCaption or FindData method, which does a
linear search. To sort a listview use its AlphaSort or CustomSort methods.
A binary search on a alphasorted listview for a caption would be something like
this (untested!):
1 {
2 Function ListviewBinarySearch
3
4 Parameters:
5
6 listview:
7 listview to search, assumed to be sorted, must be <> nil.
8
9 Item:
10 item caption to search for, cannot be empty
11
12 index:
13 returns the index of the found item, or the index where the item should be inserted
14 if it is not already in the list. Returns True if there is an item with the passed
15 caption in the list, false otherwise.
16
17 Description:
18 Uses a binary search and assumes that the listview is sorted ascending on the
19 caption of the listitems. The search is case-sensitive, like the default alpha-sort
20 routine used by the TListview class.
21
22 Note:
23 We use the lstrcmp function for string comparison since it is the function used by
24 the default alpha sort routine. If the listview is sorted by another means (e.g.
25 OnCompare event) this needs to be changed, the comparison method used must always
26 be the same one used to sort the listview, or the search will not work!
27
28 Error Conditions: none
29 Created: 31.10.99 by P. Below
30 }
31
32 function ListviewBinarySearch(listview: TListview; const Item: string; var index:
33 Integer): Boolean;
34 var
35 first, last, pivot, res: Integer;
36 begin
37 Assert(Assigned(listview));
38 Assert(Length(item) > 0);
39 Result := false;
40 index := 0;
41 if listview.items.count = 0 then
42 Exit;
43 first := 0;
44 last := listview.items.count - 1;
45 repeat
46 pivot := (first + last) div 2;
47 res := lstrcmp(PChar(item), Pchar(listview.items[pivot].caption));
48 if res = 0 then
49 begin
50 { Found the item, return its index and exit. }
51 index := pivot;
52 result := true;
53 Break;
54 end
55 else if res > 0 then
56 begin
57 { Item is larger than item at pivot }
58 first := pivot + 1;
59 end
60 else
61 begin
62 { Item is smaller than item at pivot }
63 last := pivot - 1;
64 end;
65 until
66 last < first;
67 index := first;
68 end;
|