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