Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I finally had some time to fiddle around with this. I got a little carried away. It's long, but I'm pasting it anyway. I added <code>set_item</code>, <code>insert</code>, <code>delete</code>, <code>find</code>, and <code>find_left</code> methods, as well as some private methods to allow low-level manipulation that breaks the cursor abstraction. I also added a <code>move_cursor</code> method that throws an <code>IndexError</code> for index tuples that are out of range or point to a non-toplevel object. </p> <p>Basically, it (should) be guaranteed that as long as you use public functions only, the cursor always points to a top-level object, and insertions and deletions all happen at the top level. From here, you should be able to safely implement <code>__getitem__</code>, <code>__setitem__</code>, <code>__delitem__</code>, etc, and maybe even <code>__getslice__</code>, <code>__setslice__</code>.</p> <p>However, there are a couple of wrinkles. The restriction that the cursor always points to a toplevel object makes it very easy to iterate over the nested list as though it were a flat list. But it also means that the cursor can't point at lower-level objects, and hence some kinds of insertions can't happen using <code>insert</code> alone. For example, say you have three lists:</p> <pre><code>&gt;&gt;&gt; l1 = [1, 2, 3, 4] &gt;&gt;&gt; l2 = [5, 6, 7, 8] &gt;&gt;&gt; l3 = [l1, l2] &gt;&gt;&gt; l3 [[1, 2, 3, 4], [5, 6, 7, 8]] </code></pre> <p>Now put this nested structure in a NLI, move to <code>5</code>, and try to insert.</p> <pre><code>&gt;&gt;&gt; nli = NestedListIter(l3) &gt;&gt;&gt; nli.find(5) &gt;&gt;&gt; nli.insert(9) &gt;&gt;&gt; nli.nested_list [[1, 2, 3, 4], [9, 5, 6, 7, 8]] </code></pre> <p>As you can see, you can insert something into <code>l2</code>, but you can't easily insert something into <code>l3</code>. In fact, to do so right now, you have to use a private function, which breaks the cursor abstraction in an unpleasant way:</p> <pre><code>&gt;&gt;&gt; nli._insert_at(nli.stack[:-1], 10) &gt;&gt;&gt; nli.nested_list [[1, 2, 3, 4], 10, [9, 5, 6, 7, 8]] &gt;&gt;&gt; nli.get_item() Traceback (most recent call last): File "&lt;stdin&gt;", line 1, in &lt;module&gt; File "nestedlistiterator.py", line 130, in get_item return self._get_item_at(self.stack) File "nestedlistiterator.py", line 39, in _get_item_at item = item[i] TypeError: 'int' object is unsubscriptable </code></pre> <p>There are surely ways to implement a safe public <code>insert_between_branches</code> method, but they involve more complication than I care to bother with right now. </p> <p>Another problem appears when one tries to insert a value after <code>4</code>. As you've seen, you can insert a value into <code>l2</code> before <code>5</code>, but if you move the cursor to <code>4</code> and <code>insert</code>, you'll quickly realize that you can't insert something after <code>4</code> inside <code>l1</code>.</p> <pre><code>&gt;&gt;&gt; nli.go_to_head() &gt;&gt;&gt; nli.find(4) &gt;&gt;&gt; nli.insert(11) &gt;&gt;&gt; nli.nested_list [[1, 2, 3, 11, 4], 10, [9, 5, 6, 7, 8]] </code></pre> <p>From the perspective of flat access, inserting after 4 and inserting before 5 are the same thing, but from the perspective of the nested list, they are different. Since <code>insert</code> is effectively a <code>left_insert</code>, this problem could be partially rectified with a <code>right_insert</code> method (which would, in turn, be unable to insert at the beginning of l1). </p> <p>These problems could probably be dealt with more generally by allowing the cursor to point to lower-level objects, but that would make flat access more complicated. In short, any attempt to rectify these problems will lead to greater complexity, either on the flat or the nested side of the interface. </p> <p>(That is actually why I still prefer the simple <a href="https://stackoverflow.com/questions/6548996/navigate-manually-with-a-cursor-through-nested-lists-by-only-providing-left-a/6549443#6549443"><code>enumerate_nested</code></a> method! A proper tree structure with values at all nodes (and not just top-level nodes) might also be simpler and better. But this was fun to code nonetheless.)</p> <pre><code>import collections class NestedListIter(object): '''A mutable container that enables flat traversal of a nested tree of lists. nested_list should contain only a list-like mutable sequence. To preserve a clear demarcation between 'leaves' and 'branches', empty sequences are not allowed as toplevel objects.''' def __init__(self, nested_list): if not nested_list: raise ValueError, 'nested_list must be a non-empty sequence' self.nested_list = nested_list # at some point, vet this to make sure self.go_to_head() # it contains no empty sequences def _is_sequence(self, item=None): '''Private method to test whether an item is a non-string sequence. If item is None, test current item.''' if item is None: item = self._get_item_at(self.stack) return isinstance(item, collections.Sequence) and not isinstance(item, basestring) def _is_in_range(self, index_tuple=None): '''Private method to test whether an index is in range. If index is None, test current index.''' if index_tuple is None: index_tuple = self.stack if any(x &lt; 0 for x in index_tuple): return False try: self._get_item_at(index_tuple) except IndexError: return False else: return True def _get_item_at(self, index_tuple): '''Private method to get item at an arbitrary index, with no bounds checking.''' item = self.nested_list for i in index_tuple: item = item[i] return item def _set_item_at(self, index_tuple, value): '''Private method to set item at an arbitrary index, with no bounds checking. Throws a ValueError if value is an empty non-string sequence.''' if self._is_sequence(value) and not value: raise ValueError, "Cannot set an empty list!" containing_list = self._get_item_at(index_tuple[:-1]) containing_list[index_tuple[-1]] = value def _insert_at(self, index_tuple, value): '''Private method to insert item at an arbitrary index, with no bounds checking. Throws a ValueError if value is an empty non-string sequence.''' if self._is_sequence(value) and not value: raise ValueError, "Cannot insert an empty list!" containing_list = self._get_item_at(index_tuple[:-1]) containing_list.insert(index_tuple[-1], value) def _delete_at(self, index_tuple): '''Private method to delete item at an arbitrary index, with no bounds checking. Recursively deletes a resulting branch of empty lists.''' containing_list = self._get_item_at(index_tuple[:-1]) del containing_list[index_tuple[-1]] if not self._get_item_at(index_tuple[:-1]): self._delete_at(index_tuple[:-1]) def _increment_stack(self): '''Private method that tires to increment the top value of the stack. Returns True on success, False on failure (empty stack).''' try: self.stack[-1] += 1 except IndexError: return False else: return True def _decrement_stack(self): '''Private method that tries to decrement the top value of the stack. Returns True on success, False on failure (empty stack).''' try: self.stack[-1] -= 1 except IndexError: return False else: return True def go_to_head(self): '''Move the cursor to the head of the nested list.''' self.stack = [] while self._is_sequence(): self.stack.append(0) def go_to_tail(self): self.stack = [] '''Move the cursor to the tail of the nested list.''' while self._is_sequence(): self.stack.append(len(self.get_item()) - 1) def right(self): '''Move cursor one step right in the nested list.''' while self._increment_stack() and not self._is_in_range(): self.stack.pop() if not self.stack: self.go_to_tail() return False while self._is_sequence(): self.stack.append(0) return True def left(self): '''Move cursor one step left in the nested list.''' while self._decrement_stack() and not self._is_in_range(): self.stack.pop() if not self.stack: self.go_to_head() return False while self._is_sequence(): self.stack.append(len(self.get_item()) - 1) return True def move_cursor(self, index_tuple): '''Move cursor to the location indicated by index_tuple. Raises an error if index_tuple is out of range or doesn't correspond to a toplevel object.''' item = self._get_item_at(index_tuple) if self._is_sequence(item): raise IndexError, 'index_tuple must point to a toplevel object' def get_item(self): '''Get the item at the cursor location.''' return self._get_item_at(self.stack) def set_item(self, value): '''Set the item a the cursor locaiton.''' return self._set_item_at(self.stack, value) def insert(self, value): '''Insert an item at the cursor location. If value is a sequence, cursor moves to the first toplevel object in value after insertion. Otherwise, cursor does not move.''' temp_stack = self.stack[:] self.left() self._insert_at(temp_stack, value) self.right() def delete(self): '''Deete an item at the cursor location. Cursor does not move.''' temp_stack = self.stack[:] self.left() self._delete_at(temp_stack) self.right() def iterate(self): '''Iterate over the values in nested_list in sequence''' self.go_to_head() yield self.get_item() while self.right(): yield self.get_item() def iterate_left(self): '''Iterate over the values in nested_list in reverse.''' self.go_to_tail() yield self.get_item() while self.left(): yield self.get_item() def find(self, value): '''Search for value in nested_list; move cursor to first location of value.''' for i in self.iterate(): if i == value: break def find_left(self, value): '''Search for value backwards in nested_list; move cursor to last location of value.''' for i in self.iterate_left(): if i == value: break def _NLI_Test(): l = [1, 2, 3, ['a', 'b', 'c'], 4, ['d', 'e', [100, 200, 300]], 5, ['a', 'b', 'c'], 6] nli = NestedListIter(l) print nli.nested_list for i in nli.iterate(): print i, print for i in nli.iterate_left(): print i, print nli.go_to_head() for i in range(5): nli.right() nli.insert('cow') nli.insert(['c', ['o', 'w']]) print nli.nested_list nli.find('cow') print nli.get_item() nli.delete() print nli.nested_list nli.find('c') nli.delete() print nli.nested_list nli.find_left('w') nli.delete() nli.find('o') nli.delete() print nli.nested_list print nli.nested_list == l nli.find(100) nli.set_item(100.1) print nli.nested_list if __name__ == '__main__': _NLI_Test() </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POConvert list of positions [4, 1, 2] of arbitrary length to an index for a nested list
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USsenderle
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POConvert list of positions [4, 1, 2] of arbitrary length to an index for a nested list
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload