f4.py

f4.py

from __future__ import print_function


class Node(object):
    def __init__(self, data, next=None, random=None):
        self.data = data
        self.next = next
        self.random = random

    def __repr_ref(self, ref):
        data = ref and ref.data
        flag = ref and getattr(ref, 'flag', '')
        return '{} ({})'.format(data if data is not None else '-',
                                flag if flag is not None else '-')

    def __repr__(self):
        return 'Node({})<{}, {}, {}>'.format(getattr(self, 'flag', ''),
                                             self.data,
                                             self.__repr_ref(self.next),
                                             self.__repr_ref(self.random))

    def __iter__(self):
        node = self
        yield node
        while node.next:
            node = node.next
            yield node


    def _create_copy_objects(self):
        """step 1
        create `copy` object with `base` data
        set next references:
        - `copy.next` to `base.random`
        - `base.random` to `copy` object

        so:
        - base still know about next node and know about copy
        - copy object have real data and reference to `base.random`
        - we still can get base random as `base.random.next`
        - we can get copy random as `copy.next.random`

        complexity of one iteration = O(n)
        """
        base_node = self
        copy_first = None
        while base_node:
            copy_node = Node(base_node.data, next=base_node.random)
            base_node.random = copy_node
            if not copy_first:
                copy_first = copy_node
            base_node = base_node.next

        return copy_first


    def _resolve_copy_random(self):
        """step 2
        set next references:
        - `copy.random` to `copy` like initial base random

        so:
        - we have result as in previous step
        - we also have right `copy.random` references

        complexity of one iteration = O(n)
        """
        base_node = self
        while base_node:
            copy_node = base_node.random
            copy_node.random = copy_node.next and copy_node.next.random
            base_node = base_node.next


    def _back_base_random_and_set_copy_next(self):
        """step 3
        set next references:
        - `base.random` to initial base random
        - `copy.next` like base next

        so we have complete copy

        complexity of one iteration = O(n)
        """
        base_node = self
        copy_prev = None
        while base_node:
            copy_node = base_node.random
            base_node.random = copy_node.next
            copy_node.next = None
            if copy_prev:
                copy_prev.next = copy_node
            copy_prev = copy_node
            base_node = base_node.next


    def copy(self):
        """full linked list copy

        create copy objects complexity = O(n)
        resolve copy random complexity = O(n)
        back base random and set copy next = O(n)

        so overall complexity = O(n) + O(n) + O(n) = O(3n) => O(n)
        """
        copy_first = self._create_copy_objects()
        self._resolve_copy_random()
        self._back_base_random_and_set_copy_next()
        return copy_first


### TEST ###


def _generate_test_data():
    """just test data:
    - plain references
    - self references
    - cycle references
    - null references
    """
    t = [Node(0), Node(1), Node(2), Node(3), Node(4), Node(5), Node(6), Node(7)]
    t[0].next, t[0].random = t[1], t[3]
    t[1].next, t[1].random = t[2], t[2]
    t[2].next, t[2].random = t[3], t[1]
    t[3].next, t[3].random = t[4], t[3]
    t[4].next, t[4].random = t[5], t[7]
    t[5].next, t[5].random = t[6], t[5]
    t[6].next, t[6].random = t[7], None
    t[7].next, t[7].random = None, t[4]
    return t


def _increment_node_flag():
    """increment Node object flag to see differences for copy output"""
    global Node
    Node = type('Node', (Node,), {'flag': getattr(Node, 'flag', -1) + 1})


if __name__ == '__main__':
    _increment_node_flag()
    test_data = _generate_test_data()
    _increment_node_flag()

    old_base = str(test_data)
    copy = str(list(test_data[0].copy()))
    new_base = str(test_data)

    print('Base:', old_base)
    print('Copy:', copy)
    print()
    print('Base before:', old_base)
    print('Base after :', new_base)
    print('Base not changed:', old_base == new_base)