Simplify and optimize filtered model implementation

RangeFilteredLogModel is gone. The functionality is trivially implemented in
FilteredLogModel now. Changing the range is now O(log n) at worst (was O(n) at
best, for rewriting the arrays). Stacking filtered models is not supported
anymore, which simplifies the code.

2 files changed, 53 insertions, 220 deletions

diff --git a/GstDebugViewer/GUI/models.py b/GstDebugViewer/GUI/models.py
index 9d57b05..e760b2b 100644
--- a/GstDebugViewer/GUI/models.py
+++ b/GstDebugViewer/GUI/models.py
@@ -233,41 +233,6 @@ class FilteredLogModelBase (LogModelBase):
 
         raise NotImplementedError ("index conversion not supported")
 
-    def line_index_to_top (self, line_index):
-
-        _log_indices = [line_index]
-
-        super_index = line_index
-        for model in self._iter_hierarchy ():
-            super_index = model.line_index_to_super (super_index)
-            _log_indices.append (super_index)
-
-        _log_trans = " -> ".join ([str (x) for x in _log_indices])
-        self.logger.debug ("translated index to top: %s", _log_trans)
-
-        return super_index
-
-    def line_index_from_top (self, super_index):
-
-        _log_indices = [super_index]
-
-        line_index = super_index
-        for model in reversed (list (self._iter_hierarchy ())):
-            line_index = model.line_index_from_super (line_index)
-            _log_indices.append (line_index)
-
-        _log_trans = " -> ".join ([str (x) for x in _log_indices])
-        self.logger.debug ("translated index from top: %s", _log_trans)
-
-        return line_index
-
-    def _iter_hierarchy (self):
-
-        model = self
-        while hasattr (model, "super_model") and model.super_model:
-            yield model
-            model = model.super_model
-
 class FilteredLogModel (FilteredLogModelBase):
 
     def __init__ (self, super_model):
@@ -276,29 +241,16 @@ class FilteredLogModel (FilteredLogModelBase):
 
         self.logger = logging.getLogger ("filtered-log-model")
 
-        self.range_model = RangeFilteredLogModel (super_model)
-
         self.filters = []
-        self.super_index = []
-        self.from_super_index = {}
         self.reset ()
         self.__active_process = None
         self.__filter_progress = 0.
 
-    def _iter_hierarchy (self):
-
-        yield self
-        yield self.range_model
-
     def reset (self):
 
-        range_model = self.range_model
-        range_model.reset ()
-        self.line_offsets = range_model.line_offsets
-        self.line_levels = range_model.line_levels
-
-        del self.super_index[:]
-        self.from_super_index.clear ()
+        self.line_offsets = self.super_model.line_offsets
+        self.line_levels = self.super_model.line_levels
+        self.super_index = xrange (len (self.line_offsets))
 
         del self.filters[:]
 
@@ -312,23 +264,14 @@ class FilteredLogModel (FilteredLogModelBase):
         new_line_offsets = []
         new_line_levels = []
         new_super_index = []
-        new_from_super_index = {}
         level_id = self.COL_LEVEL
         func = filter.filter_func
-        if len (self.filters) == 1:
-            # This is the first filter that gets applied.
-            def enum ():
-                i = 0
-                for row, offset in self.iter_rows_offset ():
-                    yield (i, row, offset,)
-                    i += 1
-        else:
-            def enum ():
-                i = 0
-                for row, offset in self.iter_rows_offset ():
-                    line_index = self.super_index[i]
-                    yield (line_index, row, offset,)
-                    i += 1
+        def enum ():
+            i = 0
+            for row, offset in self.iter_rows_offset ():
+                line_index = self.super_index[i]
+                yield (line_index, row, offset,)
+                i += 1
         self.logger.debug ("running filter")
         progress = 0.
         progress_full = float (len (self))
@@ -338,7 +281,6 @@ class FilteredLogModel (FilteredLogModelBase):
                 new_line_offsets.append (offset)
                 new_line_levels.append (row[level_id])
                 new_super_index.append (i)
-                new_from_super_index[i] = len (new_super_index) - 1
             y -= 1
             if y == 0:
                 progress += float (YIELD_LIMIT)
@@ -348,7 +290,6 @@ class FilteredLogModel (FilteredLogModelBase):
         self.line_offsets = new_line_offsets
         self.line_levels = new_line_levels
         self.super_index = new_super_index
-        self.from_super_index = new_from_super_index
         self.logger.debug ("filtering finished")
 
         self.__filter_progress = 1.
@@ -395,112 +336,45 @@ class FilteredLogModel (FilteredLogModelBase):
 
     def line_index_from_super (self, super_line_index):
 
-        if len (self.filters) == 0:
-            # Identity.
-            return super_line_index
-
-        try:
-            return self.from_super_index[super_line_index]
-        except KeyError:
-            raise IndexError ("super index %i not handled" % (super_line_index,))
+        return bisect_left (self.super_index, super_line_index)
 
     def line_index_to_super (self, line_index):
 
-        if len (self.filters) == 0:
-            # Identity.
-            return line_index
-
         return self.super_index[line_index]
 
-    def __filtered_indices_in_range (self, start, stop):
-
-        if start < 0:
-            raise ValueError ("start cannot be negative (got %r)" % (start,))
-
-        super_start = bisect_left (self.super_index, start)
-        super_stop = bisect_left (self.super_index, stop)
+    def set_range (self, super_start, super_stop):
 
-        return super_stop - super_start
+        old_super_start = self.line_index_to_super (0)
+        old_super_stop = self.line_index_to_super (len (self.super_index) - 1) + 1
 
-    def set_range (self, start_index, stop_index):
+        self.logger.debug ("set range (%i, %i), current (%i, %i)",
+                           super_start, super_stop, old_super_start, old_super_stop)
 
-        range_model = self.range_model
-        old_start, old_stop = range_model.line_index_range
-        range_model.set_range (start_index, stop_index)
-
-        if isinstance (self.line_offsets, SubRange):
-            # FIXME: Can only take this shortcut when shrinking the range.
-            self.line_offsets = range_model.line_offsets
-            self.line_levels = range_model.line_levels
+        if len (self.filters) == 0:
+            # Identity.
+            self.super_index = xrange (super_start, super_stop)
+            self.line_offsets = SubRange (self.super_model.line_offsets,
+                                          super_start, super_stop)
+            self.line_levels = SubRange (self.super_model.line_levels,
+                                         super_start, super_stop)
             return
 
-        super_start, super_stop = range_model.line_index_range
-
-        super_start_offset = super_start - old_start
-        if super_start_offset < 0:
+        if super_start < old_super_start:
             # TODO:
             raise NotImplementedError ("Only handling further restriction of the range"
-                                       " (start offset = %i)" % (super_start_offset,))
+                                       " (start offset = %i)" % (start_offset,))
 
-        super_end_offset = super_stop - old_stop
-        if super_end_offset > 0:
+        if super_stop > old_super_stop:
             # TODO:
             raise NotImplementedError ("Only handling further restriction of the range"
-                                       " (end offset = %i)" % (super_end_offset,))
-
-        if super_end_offset < 0:
-            if not self.super_index:
-                # Identity; there are no filters.
-                end_offset = len (self.line_offsets) + super_end_offset
-            else:
-                n_filtered = self.__filtered_indices_in_range (super_stop - super_start,
-                                                               old_stop - super_start)
-                end_offset = len (self.line_offsets) - n_filtered
-            stop = len (self.line_offsets) # FIXME?
-            assert end_offset < stop
-
-            self.__remove_range (end_offset, stop)
-
-        if super_start_offset > 0:
-            if not self.super_index:
-                # Identity; there are no filters.
-                n_filtered = super_start_offset
-                start_offset = n_filtered
-            else:
-                n_filtered = self.__filtered_indices_in_range (0, super_start_offset)
-                start_offset = n_filtered
-
-            if n_filtered > 0:
-                self.__remove_range (0, start_offset)
-
-            from_super = self.from_super_index
-            for i in self.super_index:
-                old_index = from_super[i]
-                del from_super[i]
-                from_super[i - super_start_offset] = old_index - start_offset
-
-            for i in range (len (self.super_index)):
-                self.super_index[i] -= super_start_offset
-
-    def __remove_range (self, start, stop):
-
-        if start < 0:
-            raise ValueError ("start cannot be negative (got %r)" % (start,))
-        if start == stop:
-            return
-        if stop > len (self.line_offsets):
-            raise ValueError ("stop value out of range (got %r)" % (stop,))
-        if start > stop:
-            raise ValueError ("start cannot be greater than stop (got %r, %r)" % (start, stop,))
+                                       " (end offset = %i)" % (stop_offset,))
 
-        self.logger.debug ("removing line range (%i, %i)",
-                           start, stop)
+        start = self.line_index_from_super (super_start)
+        stop = self.line_index_from_super (super_stop)
 
-        del self.line_offsets[start:stop]
-        del self.line_levels[start:stop]
-        for super_index in self.super_index[start:stop]:
-            del self.from_super_index[super_index]
-        del self.super_index[start:stop]
+        self.super_index = SubRange (self.super_index, start, stop)
+        self.line_offsets = SubRange (self.line_offsets, start, stop)
+        self.line_levels = SubRange (self.line_levels, start, stop)
 
 class SubRange (object):
 
@@ -511,6 +385,12 @@ class SubRange (object):
         if start > stop:
             raise ValueError ("need start <= stop (got %r, %r)" % (start, stop,))
 
+        if type (l) == type (self):
+            # Another SubRange, don't stack:
+            start += l.start
+            stop += l.start
+            l = l.l
+
         self.l = l
         self.start = start
         self.stop = stop
@@ -529,51 +409,6 @@ class SubRange (object):
         for i in xrange (self.start, self.stop):
             yield l[i]
 
-class RangeFilteredLogModel (FilteredLogModelBase):
-
-    def __init__ (self, super_model):
-
-        FilteredLogModelBase.__init__ (self, super_model)
-
-        self.logger = logging.getLogger ("range-filtered-model")
-
-        self.line_index_range = None
-
-    def set_range (self, start_index, stop_index):
-
-        self.logger.debug ("setting range to start = %i, stop = %i",
-                           start_index, stop_index)
-
-        self.line_index_range = (start_index, stop_index,)
-        self.line_offsets = SubRange (self.super_model.line_offsets,
-                                      start_index, stop_index)
-        self.line_levels = SubRange (self.super_model.line_levels,
-                                     start_index, stop_index)
-
-    def reset (self):
-
-        self.logger.debug ("reset")
-
-        start_index = 0
-        stop_index = len (self.super_model)
-
-        self.set_range (start_index, stop_index,)
-
-    def line_index_to_super (self, line_index):
-
-        start_index = self.line_index_range[0]
-
-        return line_index + start_index
-
-    def line_index_from_super (self, li):
-
-        start, stop = self.line_index_range
-
-        if li < start or li >= stop:
-            raise IndexError ("not in range")
-
-        return li - start
-
 class LineViewLogModel (FilteredLogModelBase):
 
     def __init__ (self, super_model):
@@ -627,4 +462,3 @@ class LineViewLogModel (FilteredLogModelBase):
 
         path = (line_index,)
         self.row_deleted (path)
-
diff --git a/GstDebugViewer/GUI/window.py b/GstDebugViewer/GUI/window.py
index 75d79a1..4c7e201 100644
--- a/GstDebugViewer/GUI/window.py
+++ b/GstDebugViewer/GUI/window.py
@@ -41,8 +41,7 @@ from GstDebugViewer.GUI.filters import (CategoryFilter,
 from GstDebugViewer.GUI.models import (FilteredLogModel,
                                        LazyLogModel,
                                        LineViewLogModel,
-                                       LogModelBase,
-                                       RangeFilteredLogModel)
+                                       LogModelBase)
 
 def action (func):
 
@@ -119,8 +118,8 @@ class LineView (object):
         line_index = path[0]
         line_model = view.get_model ()
         log_model = self.log_view.get_model ()
-        top_index = line_model.line_index_to_top (line_index)
-        log_index = log_model.line_index_from_top (top_index)
+        super_index = line_model.line_index_to_super (line_index)
+        log_index = log_model.line_index_from_super (super_index)
         path = (log_index,)
         self.log_view.scroll_to_cell (path, use_align = True, row_align = .5)
         sel = self.log_view.get_selection ()
@@ -131,7 +130,7 @@ class LineView (object):
         log_model = view.get_model ()
         line_index = path[0]
 
-        top_line_index = log_model.line_index_to_top (line_index)
+        super_index = log_model.line_index_to_super (line_index)
         line_model = self.line_view.get_model ()
         if line_model is None:
             return
@@ -143,14 +142,14 @@ class LineView (object):
         else:
             position = 0
         if len (line_model) > 1:
-            other_index = line_model.line_index_to_top (position - 1)
+            other_index = line_model.line_index_to_super (position - 1)
         else:
             other_index = -1
-        if other_index == top_line_index and position != 1:
+        if other_index == super_index and position != 1:
             # Already have the line.
             pass
         else:
-            line_model.insert_line (position, top_line_index)
+            line_model.insert_line (position, super_index)
             self.clear_action.props.sensitive = True
 
     def handle_log_view_selection_changed (self, selection):
@@ -165,7 +164,7 @@ class LineView (object):
             return
 
         path = model.get_path (tree_iter)
-        line_index = model.line_index_to_top (path[0])
+        line_index = model.line_index_to_super (path[0])
 
         if len (line_model) == 0:
             line_model.insert_line (0, line_index)
@@ -409,7 +408,7 @@ class Window (object):
             super_index = None
             self.logger.debug ("no line selected")
         else:
-            super_index = model.line_index_to_top (line_index)
+            super_index = model.line_index_to_super (line_index)
             self.logger.debug ("pushing selected line %i (abs %i)",
                                line_index, super_index)
 
@@ -419,7 +418,7 @@ class Window (object):
         if vis_range is not None:
             start_path, end_path = vis_range
             start_index = start_path[0]
-            self.default_start_index = model.line_index_to_top (start_index)
+            self.default_start_index = model.line_index_to_super (start_index)
 
     def update_model (self, model = None):
 
@@ -445,7 +444,7 @@ class Window (object):
         if selected_index is not None:
 
             try:
-                select_index = model.line_index_from_top (selected_index)
+                select_index = model.line_index_from_super (selected_index)
             except IndexError as exc:
                 self.logger.debug ("abs line index %i filtered out, not reselecting",
                                    selected_index)
@@ -467,7 +466,7 @@ class Window (object):
                     yield i
             for current_index in traverse ():
                 try:
-                    target_index = model.line_index_from_top (current_index)
+                    target_index = model.line_index_from_super (current_index)
                 except IndexError:
                     continue
                 else:
@@ -574,16 +573,16 @@ class Window (object):
             return
 
         if after:
-            first_index = model.line_index_to_top (0)
-            last_index = model.line_index_to_top (filtered_line_index)
+            first_index = model.line_index_to_super (0)
+            last_index = model.line_index_to_super (filtered_line_index)
 
             self.logger.info ("hiding lines after %i (abs %i), first line is abs %i",
                               filtered_line_index,
                               last_index,
                               first_index)
         else:
-            first_index = model.line_index_to_top (filtered_line_index)
-            last_index = model.line_index_to_top (len (model) - 1)
+            first_index = model.line_index_to_super (filtered_line_index)
+            last_index = model.line_index_to_super (len (model) - 1)
 
             self.logger.info ("hiding lines before %i (abs %i), last line is abs %i",
                               filtered_line_index,