binary search ResLayout list, ThreadView

diff --git a/src/FukuiNoNamari/thread_view.py b/src/FukuiNoNamari/thread_view.py
index 6323435..dd13da1 100644 (file)
--- a/src/FukuiNoNamari/thread_view.py
+++ b/src/FukuiNoNamari/thread_view.py
@@ -531,7 +531,6 @@ class ThreadView(gtk.HBox):
 
     def initialize_buffer(self):
         self.res_layout_list = []
-        self.layout_posY_map = [(0, [])]
 
     def add_layout(self, res_layout):
         if (len(self.res_layout_list) != 0):
@@ -542,10 +541,6 @@ class ThreadView(gtk.HBox):
         res_layout.list_index = len(self.res_layout_list)
         self.res_layout_list.append(res_layout)
 
-        if len(self.layout_posY_map[len(self.layout_posY_map)-1][1]) == 128:
-            self.layout_posY_map.append((res_layout.posY, []))
-        self.layout_posY_map[len(self.layout_posY_map)-1][1].append(res_layout)
-
         x, y = res_layout.get_pixel_size()
         self.adjustment.upper = res_layout.posY + y
         self.redraw()
@@ -577,8 +572,6 @@ class ThreadView(gtk.HBox):
             self.vscrollbar.set_value(top_layout.posY - delta)
 
     def relayout(self):
-        self.layout_posY_map = [(0, [])]
-
         width = self.drawingarea.allocation.width
         sum_height = 0
         for layout in self.res_layout_list:
@@ -587,10 +580,6 @@ class ThreadView(gtk.HBox):
             x, y = layout.get_pixel_size()
             sum_height += y
 
-            if len(self.layout_posY_map[len(self.layout_posY_map)-1][1])==128:
-                self.layout_posY_map.append((layout.posY, []))
-            self.layout_posY_map[len(self.layout_posY_map)-1][1].append(layout)
-
         self.vscrollbar.set_range(0, sum_height)
         self.change_vscrollbar_visible()
 
@@ -683,18 +672,36 @@ class ThreadView(gtk.HBox):
             x, self.transform_coordinate_gdk_to_adj(y), layout)
 
     def get_layout_on_y(self, y):
-        layout_list = None
-        for pos, lay_lst in self.layout_posY_map:
-            if pos > y:
-                break
-            layout_list = lay_lst
-        if layout_list:
-            layout = None
-            for lay in layout_list:
-                if lay.posY > y:
-                    break
-                layout = lay
-            return layout
+
+        def binary_search(lst, start, end, func):
+
+            if end - start <= 0:
+                return None
+
+            m = (start + end) / 2
+            ret = func(lst[m])
+
+            if ret == 0:
+                return m
+            if ret > 0:
+                return binary_search(lst, start, m, func)
+            return binary_search(lst, m+1, end, func)
+
+        def on_y(layout, _y):
+            top = layout.posY
+            width, height = layout.get_pixel_size()
+            bottom = top + height
+            if _y >= top and _y < bottom:
+                return 0
+            if _y < top:
+                return 1
+            return -1
+
+        ret = binary_search(
+            self.res_layout_list, 0, len(self.res_layout_list),
+            lambda x: on_y(x, y))
+        if ret is not None:
+            return self.res_layout_list[ret]
         return None
 
     def ptrpos_to_layout(self, x, y):