Changeset 801b7ac for view.c

Timestamp:

Feb 6, 2007, 6:05:13 PM (18 years ago)

Author:

Alejandro R. Sedeño <asedeno@mit.edu>

Branches:

master, barnowl_perlaim, debian, release-1.10, release-1.4, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9

Children:

7a20e4c

Parents:

2566560

Message:

functions.c: tweak owl_function_calculate_topmsg_normal to not suck as
much. This resolves the delay in jumping from the first message to the
last message.

fmtext.c: get rid of a debug message and an unused variable.

view.c: Convert another linear search to binary search.

File:

• view.c (modified) (1 diff)

view.c

@@ -97 +97 @@
 int owl_view_get_nearest_to_msgid(owl_view *v, int targetid)
 {
-  int i, bestdist=-1, bestpos=0, curid, curdist;
+  int first, last, mid = 0, max, bestdist, curid = 0;
 
-  for (i=0; i<owl_view_get_size(v); i++) {
-    curid = owl_message_get_id(owl_view_get_element(v, i));
-    curdist = abs(targetid-curid);
-    if (bestdist<0 || curdist<bestdist) {
-      bestdist = curdist;
-      bestpos = i;
+  first = 0;
+  last = max = owl_view_get_size(v) - 1;
+  while (first <= last) {
+    mid = (first + last) / 2;
+    curid = owl_message_get_id(owl_view_get_element(v, mid));
+    if (curid == targetid) {
+      return(mid);
+    } else if (curid < targetid) {
+      first = mid + 1;
+    } else {
+      last = mid - 1;
     }
   }
-  return (bestpos);
+  bestdist = abs(targetid-curid);
+  if (curid < targetid && mid+1 < max) {
+    curid = owl_message_get_id(owl_view_get_element(v, mid+1));
+    mid = (bestdist < abs(targetid-curid)) ? mid : mid+1;
+  }
+  else if (curid > targetid && mid-1 >= 0) {
+    curid = owl_message_get_id(owl_view_get_element(v, mid-1));
+    mid = (bestdist < abs(targetid-curid)) ? mid : mid-1;
+  }
+  return mid;
 }