Re: [Rhythmbox-devel] searching

[Benjamin Otte <in7y118 public uni-hamburg de>]

On 7 May 2003, Colin Walters wrote:

> > The attached file [...]
>
> Hm, I don't see an attachment...maybe a list filter ate it?
>
Considering that I sent the file directly to you so there was no filter in
between I think I have to blame it on the time. ;)

Use this one.

Benjamin
/* GStreamer
 * Copyright (c) 2003 Benjamin Otte <in7y118@public.uni-hamburg.de>
 *
 * search.c: Simple search dialog
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include <gtk/gtk.h>
#include <libxml/parser.h>
#include <string.h>

#define LIBRARY ".gnome2/net-rhythmbox/library.xml"

typedef gunichar ** PartyPattern;

/* 0 - 100 */
static inline gint
party_pattern_cost_replace (gunichar from, gunichar to)
{
  return from == to ? 0 : 100;
}
/* 0 - 100 */
static inline gint
party_pattern_cost_delete (gunichar c)
{
  return 100;
}
/* 0 - 100 */
static inline gint
party_pattern_cost_insert (gunichar c)
{
  return 100;
}
/**
 * party_pattern_compare_word:
 * @needle: The word that is looked for
 * @haystack: The word to find
 *
 * Computes a percentage of how well needle is found in haystack.
 *
 * Return: the similarity from 0 to 100
 */
static gint
party_pattern_compare_word (gunichar *needle, gunichar *haystack)
{
  gunichar *walk;
  guint *costs;
  guint temp_cost, tmp, best, i;
  guint needle_length = 0;

  /* compute Levenshtein distance between the 2 strings */
  g_assert (needle);
  g_assert (haystack);

  /* get length of needle */
  walk = needle;
  while (*walk) {
    needle_length++;
    walk++;
  }

  /* initialize array */
  costs = g_new (guint, needle_length + 1);
  costs[0] = 0;
  walk = needle;
  for (i = 1; i <= needle_length; i++, walk++) {
    costs[i] = costs[i - 1] + party_pattern_cost_insert (*walk);
  }
  
  /* do matrix calculation */
  for (; *haystack; haystack++) {
    temp_cost = costs[0] + 1; /* cheap start/end */
    walk = needle;
    for (i = 0; i < needle_length; i++, walk++) {
      best = costs[i] + party_pattern_cost_replace (*haystack, *walk);
      tmp = costs[i + 1] + party_pattern_cost_delete (*haystack);
      if (tmp < best)
	best = tmp;
      tmp = temp_cost + party_pattern_cost_insert (*walk);
      if (tmp < best)
	best = tmp;
      costs[i] = temp_cost;
      temp_cost = best;
    }
    costs[needle_length] = (temp_cost <= costs[needle_length]) ? 
                           temp_cost : costs[needle_length] + 1; /* cheap start/end */
  }

  best = costs[needle_length];
  g_free (costs);

  /* now we need to calculate the similarity somehow */
  best = 100 - MIN (100, 2 * best / needle_length);
  return best;
}
/**
 * party_pattern_compare:
 * @needle: The text that is looked for
 * @haystack: The text to find
 *
 * Computes a percentage of how well needle is found in haystack.
 *
 * Return: the similarity from 0 to 100
 */
static gint
party_pattern_compare (PartyPattern needle, PartyPattern haystack)
{
  PartyPattern loop;
  gint best_match, ret = 100;

  while (*needle) {
    loop = haystack;
    best_match = 0;
    while (*loop) {
      best_match = MAX (best_match, party_pattern_compare_word (*needle, *loop));
      if (best_match == 100)
	break;
      loop++;
    }
    ret *= best_match;
    ret /= 100;
    needle++;
  }

  return ret;
}
/**
 * party_pattern_free:
 * @pattern: the pattern to free
 *
 * Frees a party_pattern.
 **/
static void
party_pattern_free (PartyPattern pattern)
{
  if (pattern) {
    g_free (pattern[0]);
    g_free (pattern);
  }
}
/**
 * party_pattern_from_utf8:
 * @text: Text to convert
 *
 * Converts a text to the format used by libparty to do text comparisons.
 *
 * Returns: A value to be used in text comparisons. Free with party_pattern_free.
 **/
static PartyPattern
party_pattern_from_utf8 (gchar *text) {
  GSList *words, *firstword;
  gunichar *unicode, *cur_write, *cur_read;
  gboolean new_word = TRUE;
  gint i, wordcount = 1;
  PartyPattern ret;

  g_return_val_if_fail (text != NULL, NULL);

  cur_write = cur_read = unicode = g_utf8_to_ucs4_fast (text, -1, NULL);

  /* we may fail here, we expect valid utf-8 */
  g_return_val_if_fail (unicode != NULL, NULL);

  words = g_slist_prepend (NULL, unicode);

  /* now normalize this text */
  while (*cur_read) {
    switch (g_unichar_type (*cur_read)) {
      case G_UNICODE_UNASSIGNED:
        g_warning ("unassigned unicode character type found");
        /* fall through */
      case G_UNICODE_CONTROL:
      case G_UNICODE_FORMAT:
      case G_UNICODE_PRIVATE_USE:
      case G_UNICODE_SURROGATE:
      case G_UNICODE_LINE_SEPARATOR:
      case G_UNICODE_PARAGRAPH_SEPARATOR:
      case G_UNICODE_SPACE_SEPARATOR:
        /* remove these and start a new word */
        if (!new_word) {
	  /* end current word if it isn't ended yet */
	  *cur_write++ = 0;
          new_word = TRUE;
	}
        
        break;
      case G_UNICODE_COMBINING_MARK:
      case G_UNICODE_ENCLOSING_MARK:
      case G_UNICODE_NON_SPACING_MARK:
      case G_UNICODE_CONNECT_PUNCTUATION:
      case G_UNICODE_DASH_PUNCTUATION:
      case G_UNICODE_CLOSE_PUNCTUATION:
      case G_UNICODE_FINAL_PUNCTUATION:
      case G_UNICODE_INITIAL_PUNCTUATION:
      case G_UNICODE_OTHER_PUNCTUATION:
      case G_UNICODE_OPEN_PUNCTUATION:
        /* remove these */
        break;
      case G_UNICODE_LOWERCASE_LETTER:
      case G_UNICODE_MODIFIER_LETTER:
      case G_UNICODE_OTHER_LETTER:
      case G_UNICODE_TITLECASE_LETTER:
      case G_UNICODE_UPPERCASE_LETTER:
        /* convert to lower (?) case */
        *cur_read = g_unichar_tolower (*cur_read);
        /* ... and fall through */
      case G_UNICODE_DECIMAL_NUMBER:
      case G_UNICODE_LETTER_NUMBER:
      case G_UNICODE_OTHER_NUMBER:
      case G_UNICODE_CURRENCY_SYMBOL:
      case G_UNICODE_MODIFIER_SYMBOL:
      case G_UNICODE_MATH_SYMBOL:
      case G_UNICODE_OTHER_SYMBOL:
        /* keep these unchanged */
	*cur_write = *cur_read;
	if (new_word) {
	  if (cur_write != unicode) {/* first insert has been done above */
	    words = g_slist_prepend (words, cur_write);
	    wordcount++;
	  }
	  new_word = FALSE;
	}
        cur_write++;
        break;    
      default:
        g_warning ("unknown unicode character type found");
        break;
    }
    cur_read++;
  }
  if (!new_word) {
    *cur_write++ = 0;
  }

  ret = g_new (gunichar *, wordcount + 1); 
  firstword = words;
  for (i = wordcount - 1; i >= 0; i--) {
    ret[i] = (gunichar *) words->data;
    words = g_slist_next (words);
  }
  g_slist_free (firstword);
  ret[wordcount] = NULL;
  
  return ret;
}

/*** JUNK TO GET THIS THING DOING SOMETHING ***********************************/

typedef struct {
  gchar *name;
  gint rating;
  PartyPattern pattern;
  GtkTreeIter iter;
} Song;

static GSList *
parse_rb_file (char *filename) {
  xmlDocPtr doc;
  xmlNodePtr library, cur, song;
  gchar *s, *info;
  GSList *ret = NULL;

  doc = xmlParseFile (filename);
  if (doc == NULL) 
    return NULL;

  library = xmlDocGetRootElement (doc);
  if (cur == NULL) {
    g_warning ("empty document");
    xmlFreeDoc (doc);
    return NULL;
  }
  
  if (xmlStrcmp(library->name, (const xmlChar *) "rhythmbox_library")) {
    g_printerr ("document of the wrong type");
    xmlFreeDoc (doc);
    return NULL;
  }

  cur = library->xmlChildrenNode;
  while (cur) {
    if (xmlGetProp (cur, "type") && 
        strcmp (xmlGetProp (cur, "type"), "RBNodeSong") == 0) {
      song = cur->xmlChildrenNode;
      info = NULL;
      while (song) {
        s = xmlGetProp (song, "id");
        if (s &&
	   (strcmp (s, "0") == 0 ||
	    strcmp (s, "3") == 0 ||
	    strcmp (s, "4") == 0)) {
	  if (info) {
	    s = g_strconcat (info, " ", xmlNodeListGetString(doc, song->xmlChildrenNode, 1), NULL);
	    g_free (info);
	    info = s;
	  } else {
	    info = xmlNodeListGetString(doc, song->xmlChildrenNode, 1);
	  }
	}
        song = song->next;
      }
      if (info)
        ret = g_slist_prepend (ret, info);
    }
    cur = cur->next;
  }

  return ret;
}
typedef struct {
  GtkEntry *entry;
  GSList *list;
  GtkListStore *store;
} SearchData;
static void
cb_search (GtkButton *button, gpointer data)
{
  PartyPattern a, b;
  SearchData *search_data = (SearchData *) data;

  GSList *list = search_data->list;
  a = party_pattern_from_utf8 ((gchar *) gtk_entry_get_text (search_data->entry));
  while (list) {
    Song *song = ((Song *) list->data);
    b = song->pattern;
    song->rating = party_pattern_compare (a, b);
    gtk_list_store_set (search_data->store, &song->iter,
			0, song->rating,
			-1);
    list = g_slist_next (list);
  }
}
static GtkListStore *
create_model (GSList *data)
{
  GtkListStore *store;

  store = gtk_list_store_new (2, G_TYPE_UINT, G_TYPE_STRING);

  /* add data to the list store */
  while (data) {
    Song *song = data->data;
    data = g_slist_next (data);
  
    gtk_list_store_append (store, &song->iter);
    gtk_list_store_set (store, &song->iter,
			  0, song->rating,
			  1, song->name,
			  -1);
  }

  return store;
}
static void
add_columns (GtkTreeView *treeview)
{
  GtkCellRenderer *renderer;
  GtkTreeViewColumn *column;

  /* ratings */
  renderer = gtk_cell_renderer_text_new ();
  column = gtk_tree_view_column_new_with_attributes ("Rating", renderer, "text", 0, NULL);
  gtk_tree_view_column_set_sort_column_id (column, 0);
  gtk_tree_view_append_column (treeview, column);
  /* ratings */
  renderer = gtk_cell_renderer_text_new ();
  column = gtk_tree_view_column_new_with_attributes ("Title", renderer, "text", 1, NULL);
  gtk_tree_view_append_column (treeview, column);
}
static GtkWidget *
setup_window (GSList *data) {
  GtkWidget *window;
  GtkWidget *box;
  GtkWidget *hbox;
  GtkWidget *search;
  GtkWidget *results;
  SearchData *search_data;

  search_data = g_new (SearchData, 1);
  search_data->list = data;

  window = gtk_window_new(GTK_WINDOW_TOPLEVEL);
  g_signal_connect (G_OBJECT (window), "destroy", G_CALLBACK (gtk_main_quit), NULL);

  box = gtk_vbox_new (FALSE, 2);
  gtk_container_add (GTK_CONTAINER(window), box);

  hbox = gtk_hbox_new (FALSE, 2); 
  gtk_box_pack_start (GTK_BOX (box), hbox, FALSE, FALSE, 0);

  search = gtk_entry_new ();
  gtk_entry_set_activates_default (GTK_ENTRY (search), TRUE);
  search_data->entry = GTK_ENTRY (search);
  gtk_box_pack_start (GTK_BOX (hbox), search, TRUE, TRUE, 0);
  
  search = gtk_button_new_with_label ("Search");
  GTK_WIDGET_SET_FLAGS (search, GTK_CAN_DEFAULT);
  g_signal_connect (G_OBJECT (search), "clicked", (GCallback) cb_search, search_data);
  gtk_box_pack_end (GTK_BOX (hbox), search, FALSE, FALSE, 0);
  gtk_window_set_default (GTK_WINDOW (window), search);
  
  search_data->store = create_model (data);
  results = gtk_tree_view_new_with_model (GTK_TREE_MODEL (search_data->store));
  gtk_tree_view_set_headers_clickable (GTK_TREE_VIEW (results), TRUE);
  
  search = gtk_scrolled_window_new (NULL, NULL);
  gtk_scrolled_window_set_policy (GTK_SCROLLED_WINDOW (search), GTK_POLICY_AUTOMATIC, GTK_POLICY_AUTOMATIC);
  gtk_container_add (GTK_CONTAINER (search), results);
  gtk_box_pack_end (GTK_BOX (box), search, TRUE, TRUE, 0);
  add_columns (GTK_TREE_VIEW (results));

  return window;
}
int
main (int argc, char **argv) {
  GSList *titles, *songs = NULL;
  GtkWidget *window;
  Song *song;
  gchar *library;

  gtk_init (&argc, &argv);
  
  if (argc > 1) {
    library = g_locale_to_utf8 (argv[1], -1, NULL, NULL, NULL);
  } else {
    library = g_build_filename (g_get_home_dir (), LIBRARY, NULL);
  }
  titles = songs = parse_rb_file (library);

  while (titles) {
    song = g_new (Song, 1);
    song->name = (gchar *) titles->data;
    song->rating = 100;
    song->pattern = party_pattern_from_utf8 (song->name);
    titles->data = song;
    titles = g_slist_next (titles);
  }
  window = setup_window (songs);

  gtk_widget_show_all (window);
  gtk_main ();

  return 0;
}