Greetings. I 'spotted' a TODO on searching 'backwards' and decided to have a go at it. Basically, I implemented the Search Previous feature. I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say. Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards? Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon. Thanks, Jo?o
Hello, On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-) Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
diff -r ccdc02768890 dw/findtext.cc --- a/dw/findtext.cc Sun Feb 01 17:21:41 2009 -0300 +++ b/dw/findtext.cc Tue Feb 03 19:24:11 2009 +0000 @@ -66,8 +66,9 @@ hlIterator = NULL; }
-FindtextState::Result FindtextState::search (const char *key, bool caseSens) +FindtextState::Result FindtextState::search (const char *key, bool caseSens, bool backwards) { + if (!widget || *key == 0) // empty keys are not found return NOT_FOUND;
@@ -91,13 +92,19 @@ if (iterator) delete iterator; iterator = new CharIterator (widget); - iterator->next (); + + if(backwards) { + /* Go to end */ + while(iterator->next () ) ; + iterator->prev(); //We don't want to be at CharIterator::END. + } else + iterator->next (); } else newKey = false;
bool firstTrial = !wasHighlighted || newKey;
- if (search0 ()) { + if (backwards ? search0Backwards () : search0 ()) { // Highlighlighting is done with a clone. hlIterator = iterator->cloneCharIterator (); for (int i = 0; key[i]; i++) @@ -116,10 +123,15 @@ // Nothing found anymore, reset the state for the next trial. delete iterator; iterator = new CharIterator (widget); - iterator->next (); + if(backwards) { + /* Go to end */ + while(iterator->next () ) ; + iterator->prev(); //We don't want to be at CharIterator::END. + } else + iterator->next ();
// We expect a success. - Result result2 = search (key, caseSens); + Result result2 = search (key, caseSens, backwards); assert (result2 == SUCCESS); return RESTART; } @@ -179,6 +191,46 @@ return false; }
+/* + * Search backwards. + */ +bool FindtextState::search0Backwards () +{ + if (iterator->getChar () == CharIterator::END) + return false; + + bool equal=false; + int l = strlen (key); + int j = l; + + /* get before the word */ + for (int i = 0; i < l+1; i++) + iterator->prev (); + + do { + + if (charsEqual (iterator->getChar (), key[l==1 ? 0 : j], caseSens)) { + + if((j==0 && equal) || l==1) { return true; } + equal=true; + + } else if(j!=l) { + + /* Restart the search */ + equal=false; + j=l; + continue; /* Do not iterate back when restarting the search. */ + + } + + if(!iterator->prev()) return false; /* No more text where to search */ + + j--; + + } while(true); + +} + bool FindtextState::search0 () { if (iterator->getChar () == CharIterator::END) diff -r ccdc02768890 dw/findtext.hh --- a/dw/findtext.hh Sun Feb 01 17:21:41 2009 -0300 +++ b/dw/findtext.hh Tue Feb 03 19:24:11 2009 +0000 @@ -62,6 +62,7 @@ static int *createNexttab (const char *key, bool caseSens); bool unhighlight (); bool search0 (); + bool search0Backwards ();
inline static bool charsEqual (char c1, char c2, bool caseSens) { return caseSens ? c1 == c2 : tolower (c1) == tolower (c2) || @@ -72,7 +73,7 @@ ~FindtextState ();
void setWidget (Widget *widget); - Result search (const char *key, bool caseSens); + Result search (const char *key, bool caseSens, bool backwards); void resetSearch (); };
diff -r ccdc02768890 dw/layout.hh --- a/dw/layout.hh Sun Feb 01 17:21:41 2009 -0300 +++ b/dw/layout.hh Tue Feb 03 19:24:11 2009 +0000 @@ -255,8 +255,8 @@ emitter.connectLayout (receiver); }
/** \brief See dw::core::FindtextState::search. */ - inline FindtextState::Result search (const char *str, bool caseSens) - { return findtextState.search (str, caseSens); } + inline FindtextState::Result search (const char *str, bool caseSens, int backwards) + { return findtextState.search (str, caseSens, backwards); }
/** \brief See dw::core::FindtextState::resetSearch. */ inline void resetSearch () { findtextState.resetSearch (); } diff -r ccdc02768890 src/findbar.cc --- a/src/findbar.cc Sun Feb 01 17:21:41 2009 -0300 +++ b/src/findbar.cc Tue Feb 03 19:24:11 2009 +0000 @@ -63,7 +63,21 @@
if (key[0] != '\0') a_UIcmd_findtext_search(a_UIcmd_get_bw_by_widget(fb), - key, case_sens); + key, case_sens, false); +} + +/* + * Find previous occurrence of input key + */ +void Findbar::searchBackwards_cb(Widget *, void *vfb) +{ + Findbar *fb = (Findbar *)vfb; + const char *key = fb->i->text(); + bool case_sens = fb->check_btn->value(); + + if (key[0] != '\0') + a_UIcmd_findtext_search(a_UIcmd_get_bw_by_widget(fb), + key, case_sens, true); }
/* @@ -96,7 +110,7 @@ int button_width = 70; int gap = 2; int border = 2; - int input_width = width - (2 * border + 3 * (button_width + gap)); + int input_width = width - (2 * border + 4 * (button_width + gap)); int x = border; height -= 2 * border;
@@ -121,7 +135,6 @@ i->clear_tab_to_focus(); i->set_click_to_focus();
- // TODO: search previous would be nice next_btn = new HighlightButton(x, border, button_width, height, "Next"); x += button_width + gap; next_btn->tooltip("Find next occurrence of the search phrase"); @@ -129,6 +142,12 @@ next_btn->add_shortcut(KeypadEnter); next_btn->callback(search_cb, this); next_btn->clear_tab_to_focus(); + + prev_btn= new HighlightButton(x, border, button_width, height, "Previous"); + prev_btn->tooltip("Find previous occurrence of the search phrase"); + prev_btn->callback(searchBackwards_cb, this); + prev_btn->clear_tab_to_focus(); + x += button_width + gap;
check_btn = new CheckButton(x, border, 2*button_width, height, "Case-sensitive"); diff -r ccdc02768890 src/findbar.hh --- a/src/findbar.hh Sun Feb 01 17:21:41 2009 -0300 +++ b/src/findbar.hh Tue Feb 03 19:24:11 2009 +0000 @@ -16,12 +16,13 @@ */ class Findbar : public Group { Button *clrb; - HighlightButton *hide_btn, *next_btn; + HighlightButton *hide_btn, *next_btn, *prev_btn; CheckButton *check_btn; xpmImage *hideImg; Input *i;
static void search_cb (Widget *, void *); + static void searchBackwards_cb (Widget *, void *); //add static void search_cb2 (Widget *, void *); static void hide_cb (Widget *, void *);
diff -r ccdc02768890 src/uicmd.cc --- a/src/uicmd.cc Sun Feb 01 17:21:41 2009 -0300 +++ b/src/uicmd.cc Tue Feb 03 19:24:11 2009 +0000 @@ -17,6 +17,8 @@ #include <math.h> /* for rint */ #include <fltk/Widget.h> #include <fltk/TabGroup.h> +#include <fltk/Button.h> +#include <fltk/InvisibleBox.h>
#include "dir.h" #include "ui.hh" @@ -964,13 +1032,13 @@ }
/* - * Search for next occurrence of key. + * Search for next/previous occurrence of key. */ -void a_UIcmd_findtext_search(BrowserWindow *bw, const char *key, int case_sens) +void a_UIcmd_findtext_search(BrowserWindow *bw, const char *key, int case_sens, int backwards) { Layout *l = (Layout *)bw->render_layout;
- switch (l->search(key, case_sens)) { + switch (l->search(key, case_sens, backwards)) { case FindtextState::RESTART: a_UIcmd_set_msg(bw, "No further occurrences of \"%s\". " "Restarting from the top.", key); diff -r ccdc02768890 src/uicmd.hh --- a/src/uicmd.hh Sun Feb 01 17:21:41 2009 -0300 +++ b/src/uicmd.hh Tue Feb 03 19:24:11 2009 +0000 @@ -34,7 +34,7 @@ void a_UIcmd_add_bookmark(BrowserWindow *bw, const DilloUrl *url); void a_UIcmd_fullscreen_toggle(BrowserWindow *bw); void a_UIcmd_findtext_dialog(BrowserWindow *bw); -void a_UIcmd_findtext_search(BrowserWindow *bw,const char *key,int case_sens); +void a_UIcmd_findtext_search(BrowserWindow *bw,const char *key,int case_sens, int backwards); void a_UIcmd_findtext_reset(BrowserWindow *bw); void a_UIcmd_focus_main_area(BrowserWindow *bw); void a_UIcmd_focus_location(void *vbw); diff -r ccdc02768890 test/dw_find_test.cc --- a/test/dw_find_test.cc Sun Feb 01 17:21:41 2009 -0300 +++ b/test/dw_find_test.cc Tue Feb 03 19:24:11 2009 +0000 @@ -44,7 +44,7 @@ static void findCallback (::fltk::Widget *widget, void *data) { //switch(layout->search ("worm", true)) { - switch(layout->search ("WORM", false)) { + switch(layout->search ("WORM", false, false)) { case FindtextState::SUCCESS: resultLabel->label("SUCCESS"); break;
_______________________________________________ Dillo-dev mailing list Dillo-dev@dillo.org http://lists.auriga.wearlab.de/cgi-bin/mailman/listinfo/dillo-dev
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer. OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard. Thanks, Jo?o
On Tue, Feb 03, 2009 at 11:54:56PM +0000, Jo?o Ricardo Louren?o wrote:
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer.
OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard.
Reversing the word (needle) we are searching for is no problem. It's supposed to be rather small and we only need to reverse it once. The point is to avoid the backtracking. So that every letter in the text (haystack) is only visited once. Regards, Johannes
Thanks,
Jo?o
_______________________________________________ Dillo-dev mailing list Dillo-dev@dillo.org http://lists.auriga.wearlab.de/cgi-bin/mailman/listinfo/dillo-dev
On Wed, Feb 04, 2009 at 08:51:26AM +0100, Hofmann Johannes wrote:
On Tue, Feb 03, 2009 at 11:54:56PM +0000, Jo?o Ricardo Louren?o wrote:
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer.
OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard.
Reversing the word (needle) we are searching for is no problem. It's supposed to be rather small and we only need to reverse it once. The point is to avoid the backtracking. So that every letter in the text (haystack) is only visited once.
If reversing the needle is all it takes, go ahead. If the code is simple and it takes twice the time a forward search, go ahead too. Backward search is much less used than forward search and it's better to have it than not, and unless the delay is annoying there's no compelling need to optimize. -- Cheers Jorge.-
Qua, 2009-02-04 ?s 10:35 -0300, Jorge Arellano Cid escreveu:
On Wed, Feb 04, 2009 at 08:51:26AM +0100, Hofmann Johannes wrote:
On Tue, Feb 03, 2009 at 11:54:56PM +0000, Jo?o Ricardo Louren?o wrote:
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer.
OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard.
Reversing the word (needle) we are searching for is no problem. It's supposed to be rather small and we only need to reverse it once. The point is to avoid the backtracking. So that every letter in the text (haystack) is only visited once.
If reversing the needle is all it takes, go ahead. If the code is simple and it takes twice the time a forward search, go ahead too. Backward search is much less used than forward search and it's better to have it than not, and unless the delay is annoying there's no compelling need to optimize.
Thanks for the answer. OK, I think I worked it out, but the string is being reversed everytime we search backwards, to maintain compatibility with forward searching. Of course an alternative is to store it as private member, what do you think? I couldn't find any function for reversing a C-String in dillo's code, so I put my own as a static member in FindtextState, should I move it elsewhere? I tested multiple cases and it seems (to me) that this one is bugless, maybe you'll find a nasty/dirty bug I caused, but time will tell :) Also, the reverse string function was the only one added, all the rest was only altered. Thanks for the support, Jo?o
Qui, 2009-02-05 ?s 20:56 +0000, Jo?o Ricardo Louren?o escreveu:
Qua, 2009-02-04 ?s 10:35 -0300, Jorge Arellano Cid escreveu:
On Wed, Feb 04, 2009 at 08:51:26AM +0100, Hofmann Johannes wrote:
On Tue, Feb 03, 2009 at 11:54:56PM +0000, Jo?o Ricardo Louren?o wrote:
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote:
Greetings.
I 'spotted' a TODO on searching 'backwards' and decided to have a go at it.
Great.
Basically, I implemented the Search Previous feature.
I must say I have difficulties understanding the code behind FindtextState::search0(), so I did not base my code on it at all. Sure it could possibly be optimized, but it seems to do the job for now, I haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
Additionally, I did not set any hotkeys for the search-previous action, maybe something like SHIFT+RETURN, since RETURN handles searching forwards?
Also, I did not add any tests, and I only altered a line to make them compilable, but I might add some tests soon.
Thanks,
Jo?o
Thanks for your answer.
OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard.
Reversing the word (needle) we are searching for is no problem. It's supposed to be rather small and we only need to reverse it once. The point is to avoid the backtracking. So that every letter in the text (haystack) is only visited once.
If reversing the needle is all it takes, go ahead. If the code is simple and it takes twice the time a forward search, go ahead too. Backward search is much less used than forward search and it's better to have it than not, and unless the delay is annoying there's no compelling need to optimize.
Thanks for the answer.
OK, I think I worked it out, but the string is being reversed everytime we search backwards, to maintain compatibility with forward searching. Of course an alternative is to store it as private member, what do you think?
I couldn't find any function for reversing a C-String in dillo's code, so I put my own as a static member in FindtextState, should I move it elsewhere?
I tested multiple cases and it seems (to me) that this one is bugless, maybe you'll find a nasty/dirty bug I caused, but time will tell :)
Also, the reverse string function was the only one added, all the rest was only altered.
Thanks for the support,
Jo?o
(Apart from the fact I didn't attach any patch...) Scratch that, my bad, that patch contained various bugs. The first kind of bug related to a typo which I now fixed. The second kind because of me interpreting code the wrong way and the third one because of the particular case of searching for things either at the beggining or at the end of the page. I think I fixed all of them and have an updated patch, excuse me for my previous mistakes... Jo?o
On Thu, Feb 05, 2009 at 10:04:32PM +0000, Jo?o Ricardo Louren?o wrote:
Qui, 2009-02-05 ?s 20:56 +0000, Jo?o Ricardo Louren?o escreveu:
Qua, 2009-02-04 ?s 10:35 -0300, Jorge Arellano Cid escreveu:
On Wed, Feb 04, 2009 at 08:51:26AM +0100, Hofmann Johannes wrote:
On Tue, Feb 03, 2009 at 11:54:56PM +0000, Jo?o Ricardo Louren?o wrote:
Ter, 2009-02-03 ?s 21:39 +0100, Hofmann Johannes escreveu:
Hello,
On Tue, Feb 03, 2009 at 07:48:18PM +0000, Jo?o Ricardo Louren?o wrote: > Greetings. > > I 'spotted' a TODO on searching 'backwards' and decided to have a go at > it.
Great.
> > Basically, I implemented the Search Previous feature. > > I must say I have difficulties understanding the code behind > FindtextState::search0(), so I did not base my code on it at all. Sure > it could possibly be optimized, but it seems to do the job for now, I > haven't found any bugs, if you find any, please do say.
FindtextState implements the Knuth-Morris-Pratt algorithm http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm for efficient searching. It is pretty clever but a bit tricky. I see some issues in your implementation. E.g. try to search for 'ab' in a string 'abababa'. Even more tricky is searching for ababb in abababb, i.e. the prefix matches, but once it no longer does you would need to backtrack. The easiest but inefficient way to implement searching is doing a strcmp() at every text position. The Knuth-Morris-Pratt algorithm avoids that. I think it would be best to adapt search0 somehow to allow backward searching - it's more or less the same thing as forward searching anyway. Some ugly edge cases when switching between forward and backward maybe :-)
Thanks for working on that, Johannes
> > Additionally, I did not set any hotkeys for the search-previous action, > maybe something like SHIFT+RETURN, since RETURN handles searching > forwards? > > Also, I did not add any tests, and I only altered a line to make them > compilable, but I might add some tests soon. > > Thanks, > > Jo?o
Thanks for your answer.
OK, I am still trying to 'go deep' with the KMP algorithm, but I have got (provisory) working search0Backwards() replacement. How efficient do you think it is to handle the word by reversing it? Rephrasing that, do you think there is a 'really' better way of searching backwards, than reversing the word and searching backwards? As far as code-changes it takes very few lines and I have a working example of it. However, the extra reversing work might hit us hard.
Reversing the word (needle) we are searching for is no problem. It's supposed to be rather small and we only need to reverse it once. The point is to avoid the backtracking. So that every letter in the text (haystack) is only visited once.
If reversing the needle is all it takes, go ahead. If the code is simple and it takes twice the time a forward search, go ahead too. Backward search is much less used than forward search and it's better to have it than not, and unless the delay is annoying there's no compelling need to optimize.
Thanks for the answer.
OK, I think I worked it out, but the string is being reversed everytime we search backwards, to maintain compatibility with forward searching. Of course an alternative is to store it as private member, what do you think?
Not necessary
I couldn't find any function for reversing a C-String in dillo's code, so I put my own as a static member in FindtextState, should I move it elsewhere?
Let's leave it there until needed.
I tested multiple cases and it seems (to me) that this one is bugless, maybe you'll find a nasty/dirty bug I caused, but time will tell :)
Now the "real world" test begins.
Scratch that, my bad, that patch contained various bugs. The first kind of bug related to a typo which I now fixed. The second kind because of me interpreting code the wrong way and the third one because of the particular case of searching for things either at the beggining or at the end of the page. I think I fixed all of them and have an updated patch, excuse me for my previous mistakes...
Committed! It has some changes: - Mainly whitespace (i.e. indentation). Please review them. - Added Shift+Enter as keyboard shortcut. - Simpler implementation of rev. It feels good! -- Cheers Jorge.-
Nice! I notice that if I search backward for a space, it won't loop back to the end after reaching the top.
Dom, 2009-02-08 ?s 20:59 +0000, corvid escreveu:
Nice!
I notice that if I search backward for a space, it won't loop back to the end after reaching the top.
Thanks for reporting that. I've been digging through the code, seeking for an explanation, but can't seem to find it. Any ideas? It's odd that it happens only with a space, and I've been checking and it *seems* that the code finds the character, what can be wrong? Anyway, I'll keep digging... Jo?o
On Mon, Feb 09, 2009 at 06:11:36PM +0000, Jo?o Ricardo Louren?o wrote:
Dom, 2009-02-08 ?s 20:59 +0000, corvid escreveu:
Nice!
I notice that if I search backward for a space, it won't loop back to the end after reaching the top.
Thanks for reporting that.
I've been digging through the code, seeking for an explanation, but can't seem to find it. Any ideas?
It's odd that it happens only with a space, and I've been checking and it *seems* that the code finds the character, what can be wrong?
Anyway, I'll keep digging...
Please assign less priority to this bug, than to the close-tab button. -- Cheers Jorge.-
participants (4)
-
corvid＠lavabit.com -
jcid＠dillo.org -
Johannes.Hofmann＠gmx.de -
jorl17.8＠gmail.com