Unhiding in a fully hidden Doubly-Linked List

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

An error occurs when in a fully hidden Doubly-Linked List an element is unhidden. All elements that come after it will also be unhidden.

sage: l = sage.combinat.misc.DoublyLinkedList(xrange(5))
sage: l.hide(0)
sage: l.hide(1)
sage: l.hide(2)
sage: l.hide(3)
sage: l.hide(4)
sage: print l
Doubly linked list of xrange(5): []
sage: l.unhide(1)
sage: print l
Doubly linked list of xrange(5): [1, 2, 3, 4]
sage: l.hide(1)
sage: print l
Doubly linked list of xrange(5): [2, 3, 4]

Upstream: Reported upstream. No feedback yet.

CC: @sagetrac-Rudi @sagetrac-jakobkroeker

Component: combinatorics

Keywords: doubly linked list unhide empty

Branch/Commit: u/foosterhof/ticket/16467 @ f8a86c0

Issue created by migration from https://trac.sagemath.org/ticket/16467

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

Description changed:

--- 
+++ 
@@ -1,15 +1,18 @@
 An error occurs when in a fully hidden Doubly-Linked List an element is unhidden. All elements that come after it will also be unhidden.

-l = sage.combinat.misc.DoublyLinkedList(xrange(5)) -l.hide(0) -l.hide(1) -l.hide(2) -l.hide(3) -l.hide(4) -print l -l.unhide(1) -print l -l.hide(1) -print l +sage: l = sage.combinat.misc.DoublyLinkedList(xrange(5)) +sage: l.hide(0) +sage: l.hide(1) +sage: l.hide(2) +sage: l.hide(3) +sage: l.hide(4) +sage: print l +Doubly linked list of xrange(5): [] +sage: l.unhide(1) +sage: print l +Doubly linked list of xrange(5): [1, 2, 3, 4] +sage: l.hide(1) +sage: print l +Doubly linked list of xrange(5): [2, 3, 4]

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

Branch: u/foosterhof/ticket/16467

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

Commit: 60c0c0f

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

comment:3

This proposal is a revamp of the internal storage, to become an actual doubly linked list, in which elements that have not been defined at initialization can also be inserted and removed. A side effect that occurs, but that in my opinion should not be a problem, is that the order of the elements may change upon removal and re-insertion now.

I do not see this as a problem, as the Doubly Linked List abstract data type has no concept of maintenance of order.

New commits:

60c0c0f

Added insert and remove methods, as well as redid internal storage to become actual Doubly Linked List

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

Upstream: Reported upstream. No feedback yet.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 60c0c0f to f8a86c0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

f8a86c0

Added is_empty method

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:5

The following hangs:

l = sage.combinat.misc.DoublyLinkedList(xrange(5))
l.insert(0)
l

[46c4a3ed-0524-4a7d-a465-68e95557bd76]

comment:6

This poses a useful question:

• Should an object be able to be in the list multiple times?

If so, the data storage plan used now will not work, and a structure using actual Node objects should be used. However, this will either break compatibility, as remove() now takes the object to remove, while then it would require the node containing the object, or it will increase the complexity of remove() from O(1) to O(n) by searching for the node to be removed. Both cases seem highly undesirable to me.

If objects cannot be represented multiple times, this can quite easily be fixed by creating some sort of 'has' dictionary, checking whether an element is already in the list.

What would be most desirable for Sage?

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:7

I'd say double entries should be possible, a DLL should really be able to store any sequence.

How is `remove' currently implemented? I really do not see how it can take O(1) time right now. To remove in O(1) time you must take away the trouble of finding the node (or at least the pointers to next\previous object). Just passing the object still leaves you with that work.

This doubly linked list has hide/unhide, which in my book means that there should be two doubly linked lists in there, one storing a subsequence of the other.

But perhaps it's not all cast in stone and there are more schools of thought on this. I was brought up with the c++ STL implementation of a list, as here http://www.cplusplus.com/reference/list/list/

[156bf7a1-cdbf-4d2b-a578-797e3af0730c]

comment:8

I forgot for a moment that I could simply take a look at the code :) . Anyway, the implementation of remove() takes O(log n) time, not O(1) as advertised in the docstring, since next_value and prev_value are dictionaries.

[fchapoton]

comment:10

tests do not pass