0 Replies - 667 Views - Last Post: 04 August 2019 - 06:27 PM Rate Topic: -----

#1 WellYesButNo   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 1
  • Joined: 04-August 19

Composition: multiple references to the same object

Posted 04 August 2019 - 06:27 PM

This is code from the book: Data Structures and Algorithms in Python. Essentially the class inherits a doubly linked list and then keeps track of each position with a "position" object that references each node. This allows constant lookup/insertion/deletion.

What I can not figure out is the design and flow of the position objects.

We can create nodes and in turn create position objects that reference these nodes using
_make_position(self, node)
Makes sense. However, every time we access a node that same function gets called, creating duplicate object references to the same node. What is more confusing is that after debugging and keeping track of the position objects, sometimes they change and sometimes they don't. On top of that, the debug console gives different output as opposed to just running the class.

Driver Code used:
new2 = PositionalList()
pos1 = new2.add_first(11)
pos2 = new2.add_first(12)
pos3 = new2.add_before(pos1, 99)

note: the following print statements were included to keep track of the memory of each position and node object
print(self, node, ": " , end = '')

Running PositionalList class:
<__main__.PositionalList.Position object at 0x01780470> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x01764C88> :
<__main__.PositionalList.Position object at 0x01780530> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x01764CB0> :
<__main__.PositionalList.Position object at 0x01780550> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x01764CD8> :
<__main__.PositionalList.Position object at 0x01780570> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x01764CB0> :
<__main__.PositionalList.Position object at 0x01780570>
<__main__.PositionalList.Position object at 0x01780570> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x01764CB0> :
<__main__.PositionalList.Position object at 0x01780570>

Debug Console with the same output:
<__main__.PositionalList.Position object at 0x0413D050> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x04137670> :
<__main__.PositionalList.Position object at 0x0413D8D0> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x03ED8800> :
<__main__.PositionalList.Position object at 0x0413DC90> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x04137CB0> :
<__main__.PositionalList.Position object at 0x0413DD50> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x03ED8800> :
<__main__.PositionalList.Position object at 0x0413DD50>
<__main__.PositionalList.Position object at 0x0413DED0> <_DoublyLinkedBased._DoublyLinkedBase._Node object at 0x03ED8800> :
<__main__.PositionalList.Position object at 0x0413DED0>

Running the code with no debug shows the last four position objects are equal (reasonable), but the debug console gives two different position objects.
My main question is about the calls to
. This should create two different position objects, which is what the debugger shows, but the non debugger console shows the same position object was used on each call. How is this possible?
Also, is there any way to avoid the creation of duplicate position objects?
class PositionalList(_DoublyLinkedBase):
    """A sequential container of elements allowing positional access."""

    # -------------------------- nested Position class --------------------------
    class Position:
        """An abstraction representing the location of a single element.

        Note that two position instaces may represent the same inherent
        location in the list.  Therefore, users should always rely on
        syntax 'p == q' rather than 'p is q' when testing equivalence of

        def __init__(self, container, node):
            """Constructor should not be invoked by user."""
            self._container = container
            print(self, node, ": " , end = '')
            self._node = node

        def element(self):
            """Return the element stored at this Position."""
            return self._node._element

        def __eq__(self, other):
            """Return True if other is a Position representing the same location."""
            return type(other) is type(self) and other._node is self._node

        def __ne__(self, other):
            """Return True if other does not represent the same location."""
            return not (self == other)  # opposite of __eq__

    # ------------------------------- utility methods -------------------------------
    def _validate(self, p):
        """Return position's node, or raise appropriate error if invalid."""
        if not isinstance(p, self.Position):
            raise TypeError('p must be proper Position type')
        if p._container is not self:
            raise ValueError('p does not belong to this container')
        if p._node._next is None:  # convention for deprecated nodes
            raise ValueError('p is no longer valid')
        return p._node

    def _make_position(self, node):
        """Return Position instance for given node (or None if sentinel)."""
        if node is self._header or node is self._trailer:
            return None  # boundary violation
            return self.Position(self, node)  # legitimate position

    # ------------------------------- accessors -------------------------------
    def first(self):
        """Return the first Position in the list (or None if list is empty)."""
        return self._make_position(self._header._next)

    def before(self, p):
        """Return the Position just before Position p (or None if p is first)."""
        node = self._validate(p)
        return self._make_position(node._prev)

    def after(self, p):
        """Return the Position just after Position p (or None if p is last)."""
        node = self._validate(p)
        return self._make_position(node._next)

    def __iter__(self):
        """Generate a forward iteration of the elements of the list."""
        cursor = self.first()
        while cursor is not None:
            yield cursor.element()
            cursor = self.after(cursor)

    # ------------------------------- mutators -------------------------------
    # override inherited version to return Position, rather than Node
    def _insert_between(self, e, predecessor, successor):
        """Add element between existing nodes and return new Position."""
        node = super()._insert_between(e, predecessor, successor)
        return self._make_position(node)

    def add_first(self, e):
        """Insert element e at the front of the list and return new Position."""
        return self._insert_between(e, self._header, self._header._next)

    def add_last(self, e):
        """Insert element e at the back of the list and return new Position."""
        return self._insert_between(e, self._trailer._prev, self._trailer)

    def add_before(self, p, e):
        """Insert element e into list before Position p and return new Position."""
        original = self._validate(p)
        return self._insert_between(e, original._prev, original)

Is This A Good Question/Topic? 1
  • +

Page 1 of 1