list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 23, 4:12 am, Steven D'Aprano <st... at REMOVE-THIS-
cybersource.com.au> wrote:
>
>
> An alternative would be to do exactly what you want lists to do: track
> the start of the list. Untested:
>
>     def recurse(prefix_lines):
>         start = 0
>         end = len(prefix_lines)
>         while start < end:
>             prefix, line = prefix_lines[start]
>             if line == '':
>                 start += 1
>                 append('')
>             else:
>                 block_size = get_block(prefix_lines)
>                 if block_size == 1:
>                     start += 1
>                     if line == pass_syntax:
>                         pass
>                     elif line.startswith(flush_left_syntax):
>                         append(line[len(flush_left_syntax):])
>                     elif line.startswith(flush_left_empty_line):
>                         append('')
>                     else:
>                         append(prefix + leaf_method(line))
>                 else:
>                     block = prefix_lines[:block_size]
>                     start = block_size
>                     branch_method(output, block, recurse)
>         return
>
> No more O(N) deletions. Problem solved.
>

A minor modification of your solution does work, but it also slightly
+ complicates the implementation.  Keeping track of the start variable
requires bookkeeping not just in recurse(), but also in methods that
it calls.  This is a pretty small program, so it's acceptable to pass
around an offset variable to anybody else who might want to be
consuming the list.

 ############ Generic indentation stuff follows

-def get_indented_block(prefix_lines):
-    prefix, line = prefix_lines[0]
+def get_indented_block(prefix_lines, start):
+    prefix, line = prefix_lines[start]
     len_prefix = len(prefix)
     i = 1
-    while i < len(prefix_lines):
-        new_prefix, line = prefix_lines[i]
+    while i + start  < len(prefix_lines):
+        new_prefix, line = prefix_lines[start+i]
         if line and len(new_prefix) <= len_prefix:
             break
         i += 1
-    while i-1 > 0 and prefix_lines[i-1][1] == '':
+    while i-1 > 0 and prefix_lines[start+i-1][1] == '':
         i -= 1
     return i

@@ -190,15 +190,16 @@
             ):
     append = output.append
     def recurse(prefix_lines):
-        while prefix_lines:
-            prefix, line = prefix_lines[0]
+        start = 0
+        while start < len(prefix_lines):
+            prefix, line = prefix_lines[start]
             if line == '':
-                prefix_lines.pop(0)
+                start += 1
                 append('')
             else:
-                block_size = get_block(prefix_lines)
+                block_size = get_block(prefix_lines, start)
                 if block_size == 1:
-                    prefix_lines.pop(0)
+                    start += 1
                     if line == pass_syntax:
                         pass
                     elif line.startswith(flush_left_syntax):
@@ -208,8 +209,8 @@
                     else:
                         append(prefix + leaf_method(line))
                 else:
-                    block = prefix_lines[:block_size]
-                    prefix_lines = prefix_lines[block_size:]
+                    block = prefix_lines[start:start+block_size]
+                    start += block_size
                     branch_method(output, block, recurse)
         return
     prefix_lines = map(indentation_method, lines)