5.20.2013 Partial List search technique

Partial list search in Lazarus
Lists are interesting to do programing tricks. In this session we learn how to search partial inputs with only the first part of the list items.


Introduction

In the previous post we have learned a simple list search in Lazarus. Today we have another better example. It searches for the first letters of the list items and shows all the items that matches the first characters of the query. It does not need the whole list item text to find list items. It can search with partial inputs. These partial inputs only have to match the first part of the list item. For example, entering "appl" can bring up "apple", "application". It can search both case sensitively and insensitively.

This kind of code is better for dictionary-type lists. It only matches the first part of the list items. So you can also search huge alphabetically sorted lists with this code.

One disadvantage of this code is that it cannot search from the middle of the list items. For example, writing "pple" will not find "apple".

Algorithm

Algorithm is a game-plan for doing a certain thing. It can be like a sketch for what is to be done. It is usually informal as the programer creates it for himself.

Before starting to write code, it is good idea to sketch up an algorithm. Below is the partial list search algorithm with the case sensitive option.

1. Clear the result list
2. Iterate through the list items
3. Check if the list item's first n letters are same as search query's first n letters.
3a. If match is found then add it to result list.
4. Go to step 2

We can easily convert it to Case Insensitive code by Uppercasing the both comparison strings in step 3. Now read the algorithm again and see if uppercasing the comparison strings would work.

Well... it should.

Now implementing both Case Sensitive and Case Insensitive. The complexity may haunt your mind when implementing case sensitive option. But the basics is that you uppercase the query and comparison string when you search Case Insensitively. This way we destroy case information from the strings. So "AbC", "abc", "ABC", all these becomes "ABC". So if we search the list with "ABC" and we find and item "abc" and we convert it to "ABC" then we will get a match.

1. Store the search query string in a variable query
1a. If searching with case sensitive option then we store the exact query to variable query
1b. If searching without case sensitive option then we uppercase version of the query to variable query
2. Clear the result list

3. Iterate through the original list
4a. If searching case sensitive, store the exact list item in a variable searchitem
4b. If searching case insensitively, we would store list item with uppercasing
5. Compare both the strings query
6. If found a match then add it to result list

Quick Tutorial

Create an Application Project (Project-> New Project-> Application-> OK).

Drop a TEdit, TCheckbox and 2 TListboxes. Name the TCheckbox to chkCase. Listbox1 is our original list where we can add many items to it for testing the search function. So add items to Listbox1. Listbox2 on the other hand is our result list.

Your layout  may resemble this:

Partial list search program in Lazarus

Select the TEdit, then go to Object Inspector -> Events tab. Then click the [...] button in front of OnChange event. Now enter the following:

var
  i: Integer;
  query, searchitem: string;
begin
  if chkCase.Checked = true then
    query := Edit1.Text
  else
    query := UpperCase(Edit1.Text);

  ListBox2.Clear;

  for i := 0 to ListBox1.Count-1 do begin
    if chkCase.Checked = true then
      searchitem := ListBox1.Items[i]
    else
      searchitem := UpperCase(ListBox1.Items[i]);

    if LeftStr(searchitem, Length(query)) = query then
      ListBox2.Items.Add(ListBox1.Items[i]);

  end;
end;

Now run the project (F9 or Run -> Run).

Partial list search program with case senstive option in Lazarus

Now type in "app". You will see matching items in the result list. Now type in "App" and click on the checkbox. You will not see the result change. It is a bug. To fix it, we will have to add a code.

Double click on the TCheckbox and  enter:
begin
  Edit1Change(Sender);
end;

Now run the program again and test yourself.
You can also add buttons for list manipulation to enhance the program, such as Add, Delete, Clear item.

Download Sample Code ZIP

You can download example source code zip file from here: http://db.tt/DLaoSjba
Size: 514 KB
The package contains compiled executable EXE file.

4 comments:

leledumbo said...

You should later post advanced techniques using prefix tree and suffix tree (this onecan search from middle)

Adnan Shameem said...

@leledumbo

It's an honor to hear from you. I've read your blog, and its full of useful and uncommon stuff.

"(this onecan search from middle)"
May be you missed the link?!

I am getting into other projects lately. But I'll try to post on advanced techniques when I get time.

Regards
Adnan

leledumbo said...

> May be you missed the link?!

No, I mean suffix tree can do searching from middle instead of just from first few characters.

> I am getting into other projects lately. But I'll try to post on advanced techniques when I get time.

OK, take it easy

Adnan Shameem said...

@leledumbo

"No, I mean suffix tree can do searching from middle instead of just from first few characters."

Oh! I am afraid I am not aware of this technique. May be you can write about it. It would be great to read about the algorithm!

I was writing articles for the newbies in mind (just like a hobby). So I just used LeftStr() to make them think about how a string search can work through such a basic built-in function.

Searching from the middle can also be done with pos(), if there is no need for fuzzy searching:
if Pos(query, searchitem) <> 0 then // match!

Built-in functions are great for basic stuff. But I believe Suffix/prefix tree can furthermore improve searching when we want to search similar string (not exact string).

So, if you can, please do write about it. It will take me a lot of time to learn and write about it. :-)

Blogger to blogger let me tell you what I think. Through my observation I've learned that Open Source projects are made popular by contents created by users. The more variety content available the more the user grows. Anything from ready-to-use custom functions to tutorials encourage people to use the project more. Consider Blender & PHP. At first, they were nothing. But they had enthusiast users creating tutorials and sample codes until they become widely used. FPC/Lazarus needs content creators. That's why I started writing. You know more than me. If you can write more, the community will benefit more. And someday eventually the benefit will be enjoyed by us all.

Good wishes
Adnan

 
Copyright 2013 LazPlanet
Carbon 12 Blogger template by Blogger Bits. Supported by Bloggermint