|
Hi There,
I have a virtual listview that I load up anywhere from 20,000 to 200,000 records into. The virtual listview handles this no problem at all. I am using the CSortedArray by PJ Naughter class to store a array of custom objects. I can sort the array very fast no problems.
My issue occurs when I have to do a keyword search. I have to be able to allow the user to search as they type into a text box. So the user starts off with a FULL list of ALL the items appearing in the virtual listview, as the type keys into the textbox the virtual listview starts drilling down and only showing items that have the letters being typed in the name. so simple example:
List
====
Greg
John
Steve
George
If the user types G in the text box the list will now look like below
List
====
Greg
George
I have this working using a simple for loop to loop through all the items at each keystroke and remove any items from the list that do not match the keys typed. However, when my list gets to 30,000 or higher the search begins to take up WAY too much CPU. Is there some faster way I can do search like this using the CSortedArry?
Thanks
Greg
|
|
|
|
|
Hi
You can use a Thread to process a binary search. The when search finish you can select or show the item(s)
David
|
|
|
|
|
ah ok thank you!
Do you know if there is any examples of where I can find how to do this?
Thanks,
Greg
|
|
|
|
|
If I understand correctly, you have a list of ordered elements, and a partial match. Binary search will help, but won't be exactly what you want.
To do something similar, I use a binary search which does a length restricted string comparison to find an element which matches, and then backs up to find the first match. For my application this approach is fine, since I only have a few items in each such grouping. Your mileage may vary.
However, a better approach, which someone has already suggested, might be to have a small array of indices into the array, keyed by first letter. Essentially something like this:
typedef struct index
{
TCHAR chr;
int start;
} INDEX;
CArray<INDEX, INDEX&>> ix;
INDEX in;
ix.RemoveAll();
in.chr = _T('\0');
in.start = -1;
for(i = 0; i < nElements; i++)
{
// get first char of this item...
chr = ....;
if (in.chr!=chr)
{
// make a new index entry
in.chr = chr;
in.start = i;
ix.Add(in);
}
}
in.chr = _T('\0');
in.start = nElements;
ix.Add(in);
To do your search, look in the ix array for a matching first character, get the start index from the matching entry, and the stop index from the next entry 
This gives you a smaller space to do additional matching if necessary.
Steve S
Developer for hire
|
|
|
|
|
Greg Ellis wrote: I have this working using a simple for loop to loop through all the items at each keystroke and remove any items from the list that do not match the keys typed. However, when my list gets to 30,000 or higher the search begins to take up WAY too much CPU.
With that many items, you are going to eat up a lot of CPU time anyway. A map or hash table would allow for more efficient searching, but with an array (even a sorted one), you are still going to be stuck with an O(n) operation. Additionally, if you have 30,000 items in the list, and your search will only find 1 entry, the list control has to do a LOT of work to remove 29,999 items. So don't be surprised to see a CPU/Memory spike for a second or two.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Instead of using a single array to hold all the data, why not break it up into say 27 arrays (one for each letter of the alphabet and numbers). You would have to create an algorithm for adding items to the correct array and choosing the correct array depending on the first character entered.
|
|
|
|
|
Try something like this. It uses binary searches so it will be many, many times faster then using linear searches. It’s a simple console app which reads in words from a file (each word in the file separated by any white space). It is not limited to only matching a single charcter; you can match all words which start with "act" for example.
------------------------
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
struct PrefixMatchLess : std::binary_function<std::string, std::string, bool>
{
bool operator()(const std::string &s, const std::string &prefix) const
{
const std::string sub = s.substr(0, prefix.length());
return sub<prefix;
}
};
struct PrefixMatchGreater : std::binary_function<std::string, std::string, bool>
{
bool operator()(const std::string &prefix, const std::string &s) const
{
const std::string sub = s.substr(0, prefix.length());
return sub>prefix;
}
};
int main()
{
// For notational convenience.
using namespace std;
typedef vector<string> StringList_t;
typedef istream_iterator<string> StringInIt_t;
typedef ostream_iterator<string> StringOutIt_t;
// Open the word list.
ifstream ifs("C:\\Words.txt");
if (!ifs)
{
cerr << "Failed to open word list!" << endl;
return 1;
}
// List for words.
StringList_t words;
// Read in the word list.
copy(StringInIt_t(ifs), StringInIt_t(), back_inserter(words));
// Sort the list and remove duplicates.
sort(words.begin(), words.end());
words.erase(unique(words.begin(), words.end()), words.end());
// Output the word list (diagnostic).
cout << "Word list:" << endl;
copy(words.begin(), words.end(), StringOutIt_t(cout, "\n"));
cout << endl;
for(;;)
{
// Get the prefix to search for.
string word;
cout << "Enter search prefix (! quit): ";
cin >> word;
// Check if the user wants to quit.
if (word=="!")
{
break; // Quit.
}
cout << endl;
// Calculate range.
StringList_t::iterator b = lower_bound(words.begin(), words.end(), word, PrefixMatchLess());
StringList_t::iterator e = upper_bound(b, words.end(), word, PrefixMatchGreater());
// Output results.
cout << "Matching words:" << endl;
copy(b, e, StringOutIt_t(cout, "\n"));
cout << endl;
}
return 0;
}
Steve
|
|
|
|
|
I am a beginner trying to clear the edit box of a combobox in drop list mode after making a selection from the list.
after selecting a list box entry, the control places a copy of it in the edit box by default, apparently using the SelectString member and the message WM_SETTEXT as part of the controls windows procedure.
when the dropdown type is used, ->SetEditSel and ->Clear etc will empty the edit box, (though not very elegantly). but the dropdown type still allows users enter text in the edit box (which is confusing and non-functional)
the drop list type prevents user edits of the edit box, but ->SetEditSel and ->Clear etc no longer appears to clear the edit box to pretty things up after selection.
I have tired many things already, and am considering trying to trap WM_SETTEXT or paint over the edit box somehow
I wonder if I am not missing some ridiculously minor thing (as I was before I realized the drop list type prevented user edits to the edit box)
Any suggestions about what I can do with/to my combobox control to prevent, clear or overwrite unwanted edit box text matching my selection in the list box?
Thanks to all...
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
I'm not exactly sure what the issue here is.  For a combobox having the CBS_DROPDOWNLIST style, once a selection is made, the dropdown part of the control goes away and the edit part of the control reflects whatever was selected. What's to clear?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
Thanks for your response!
I want the edit box to clear to blank - or to paste in a standard text like "select items here->"
The user knows what they selected - why do they need to see it again? Especially long after the selection is made?
I suppose I can clear the whole control and repopulate the list box, but I think this would slow things down alot
I dont want the user to be able to make changes in the edit box, because it is primarily being used to select a set of only occasionally changin items and it is confusing if they can enter text etc. I chose droplist to prevent edit box text entry, but then i getthe selection pasted in after the user selects which will not clear using ->Clear();
since i like the way the drop list behaves to prevent user entry, I am trying to make it work by finding a way to clear the unwanted pasting of text into the edit box
I am guessing that I can subclass the control and then trap the message that pastes the text in the edit box, but my reading suggests that I cant just eliminate windows messages without messing things up
I do not understand why ->Clear() does not work
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
lctrncs wrote: I want the edit box to clear to blank...
At what point?
lctrncs wrote: ...or to paste in a standard text like "select items here->"
Before or after a selection is made?
lctrncs wrote: The user knows what they selected - why do they need to see it again? Especially long after the selection is made?
This doesn't make any sense. The control will retain the selected item until another item is selected.
lctrncs wrote: ...but then i getthe selection pasted in after the user selects...
If the control has the CBS_DROPDOWNLIST style, pasting is not possible.
I'm still unclear as to what you want cleared. If I type text into a combobox having the CBS_DROPDOWN style and then select an item from the dropdown list, whatever I typed in is automatically overwritten. Are you seeing something different?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
Thank you for responding!
I want to clear the edit box so the user does not have to look at the last thing they selected until they select something else
I suppose I could completely clear the control and repopulate the list box, but this would slow things down I think
How come pControl->Clear works in dropdown but not in drop list?
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
lctrncs wrote: I want to clear the edit box so the user does not have to look at the last thing they selected until they select something else
Huh? If I select something from such a combobox, and it immediately clears itself, how am I to know what, if anything, was selected? That seems very counterintuitive.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
DavidCrow wrote: Huh? If I select something from such a combobox, and it immediately clears itself, how am I to know what, if anything, was selected. That seems very counterintuitive.
How do you get a dropdown list edit box to immediately clear itself?
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
lctrncs wrote: How do you get a dropdown list edit box to immediately clear itself?
m_cb.InsertString(0, "");
m_cb.SetCurSel(0);
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
Thanks for all your help!
However,
DavidCrow wrote: m_cb.InsertString(0, "");m_cb.SetCurSel(0);
appears to solve the clearing problem only for the Dropdown Style combobox (providing much more acceptable appearance), but sadly does not clear the edit box for the Drop List style.
In drop list mode my OnSelchangeCombo function sends a WM_SETTEXT right before leaving the function and ignoring:
->InsertString(0,"",0); //(overridden InsertString)
->SetWindowText("");
->SetDlgItemText( IDC_COMBO, "")
even though it executes lines like:
->GetCurSel();
immediately before the ->InsertString etc.
Subsequent attempts in my DisplayDialog function to clear the Drop List edit box employing the
->InsertString(0,"",0); //(overridden InsertString)
->SetWindowText("");
->SetDlgItemText( IDC_COMBO, "")
edit box are also unsuccessful.
Could the Drop List style be refusing to allow me to change the edit box because I have the "Owner Draw" selection set to "No?"
Thanks again for your assistance to date.
I appreciate it a great deal.
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
lctrncs wrote: ...the edit box for the Drop List style.
This appears to be the root of the confusion. For a combobox having the CBS_DROPDOWNLIST style, there is no edit control. It's actually a static control.
lctrncs wrote: In drop list mode my OnSelchangeCombo function sends a WM_SETTEXT...
What control is this message targeted for?
lctrncs wrote: Could the Drop List style be refusing to allow me to change the edit box...
Is the edit box a separate control that you are updating based on the combobox selection?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
It does appear as if we are having trouble communicating...
DavidCrow wrote: This appears to be the root of the confusion. For a combobox having the CBS_DROPDOWNLIST style, there is no edit control. It's actually a static control.
In Drop List style, the edit box does not go away.
It is still there but it is static and will not accept user text and a mouse click opens the dropdown. When you select an item in the dropdown, the control inserts the text you selected (apparently employing SelectString and WM_SETTEXT) into the now "static" edit box (one would think if it were truly static that it would not change ata all).
It is this inserted text I hope to clear in Drop List style.
DavidCrow wrote: What control is this message targeted for?
According the Spy++, the CCombobox control sends the WM_SETTEXT message as the last event in my OnSelchange function. Since the message begins with "WM_, I believe that means that it is a windows message, and I assume that it is sent to the parent dialog in which the combobox control exists and plays a role in the painting of the text in the control's edit box.
DavidCrow wrote: Is the edit box a separate control that you are updating based on the combobox selection?
You appear to suggest that the edit box associated with the combobox we have been discussing becomes a separate control when it is in Drop List mode.
I suppose that it is possible for the edit box to change to a different control when one changes the control's style, but I find it difficult to believe that just changing a combobox's style turns it into two separate controls.
Thank you for all your assistance. I have managed to find a satisfactory workaround using the DropDown style. While I would prefer to use the Drop List, I can live with what I have now - and will revisit this problem again later.
Thanks again.
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
lctrncs wrote: ...(one would think if it were truly static that it would not change ata all).
It's definitely a static control and not an edit control that has been merely made read-only. You can confirm this via Spy++. The "combo" part comes from it being a listbox coupled with either a static control or an edit control. What the control is comprised of is irrelevant, however.
lctrncs wrote: It is this inserted text I hope to clear in Drop List style.
Why? If the user selected it from the combobox, why clear it? Would that not be ultimately confusing? How would they then know what, if anything, has been selected? I've never seen a combobox behave in this fashion. Do you have an example?
lctrncs wrote: You appear to suggest that the edit box associated with the combobox we have been discussing becomes a separate control when it is in Drop List mode.
No, it simply does not exist. Furthermore, I don't recall ever having to interact with a combobox in this way. Once a selection has been made, it stays "made" until the list is dropped down and some other selection is made.
lctrncs wrote: I find it difficult to believe that just changing a combobox's style turns it into two separate controls.
A combobox has always been two-controls-in-one, even back with Windows 3.x.
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I am using the combobox as a method for selecting records in a database. Since the record is displayed once the user selects the text, there is no longer a need to display duplicate information in the combobox - and it looks funky if it remains displayed.
While I thought I had a useful workaround earlier, I am not as happy with it now as I thought I would be.
I never was one to do things the same way as everyone else, so my unique approach to the combobox does not surprise me that much. I thought about tree controls and list boxes, but I need something that remains hidden most of the time.
So what do you think about painting over the edit control to hide the selected text, or trapping the WM_SETTEXT?
I am very tired and would very much like to find a solution soon. I have been trying to solve this problem for a very long time!
Suggestions?
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
lctrncs wrote: I am using the combobox as a method for selecting records in a database.
Why not use a list control?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I do not have very much real estate in my database dialog. I like the idea of having a one line control open up to display a multiline area for the selection of records. If I went with the list control, I would need a much larger dialog and my users would have to fool around with scroll bars more.
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
Would it be possible to break your dialog up into multiple pages and use a property sheet?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
I suppose it would be possible. However, I am trying to keep things simple and user friendly.
"For a successful technology, reality must take precedence over public relations, for nature cannot be fooled." Richard Feynman, Minority Report to the Official Report on the Space Shuttle Challenger Crash
|
|
|
|
|
Following what I think you are trying to do, you are using the wrong control. ComboBoxes are designed to select an option and display it until the selection is changed. Clearing it goes against what it was designed for. You should either use a ListBox or a List Control for what I think you are trying to do.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
