Circle Tape

circular_circular.py

from typing import Any, Iterable, Union
import weakref


class CircleNode:
    """
    A node inside a circular list (linked list node)

    This object is used to have lists without end, and are quite useful when time comes.

    You should use this when:
    - Object indexes don't matter
    - You need to know what's near an item in a list
    - You need to loop through the items in a list an undefined amount of times

    You should NOT use this when:
    - You need to get a item in a list by it's index
    - You need to sort the values
    - You just need a place to store related data

    :ivar value: The value which was assigned for the node to hold
    :vartype value: Any
    :ivar next: The next node in relation to this node (aka to the right of it)
    :vartype next: CircleNode or None
    :ivar prev: The previous node in relation to this node (aka to the left of it)
    :vartype prev: CircleNode or None
    """

    def __init__(self, value: Any, prev: 'CircleNode'=None, next: 'CircleNode'=None):
        """
        Constructor for CircleNode

        :param value: The value of the node
        :type value: Any
        :param prev: The previous node (if None, it will be self however next must also be None)
        :type prev: CircleNode
        :param next: The next node (if None, it will be self however prev must also be None)
        :type next: CircleNode
        """
        self.value = value
        if not any([prev, next]):
            self.prev = self
            self.next = self
        elif all([prev, next]):
            self.prev = prev
            self.next = next
        else:
            raise ValueError("You cannot have only 1 None for prev and next, must be all or nothing.")

    def _fix_neighbors(self):
        self.prev.next = self
        self.next.prev = self

    def add_left(self, value: Any) -> 'CircleNode':
        """
        Create a node to the left of this one

        By left, it means the created node becomes this node's previous node. All close nodes will be adjusted to the
        change. If CircleNode is inherited, this method adjusts to the child class being used.

        :param value: The value for the node to hold
        :type value: Any
        :return: The circle node that was added to the left
        :rtype: CircleNode
        """
        new_node = self.__class__(value, self.prev, self)
        new_node._fix_neighbors()
        return new_node

    def walk(self, distance: int) -> 'CircleNode':
        """
        Fetch a node a specified distance away

        If the distance provided is positive, it will get the node to the right. If the distance is negative, than it
        will get the node to the left. You can put it 0 and it will return itself.

        :param distance: A positive or negative distance away from the current node
        :type distance: int
        :return: The circle node the specified distance away
        :rtype: CircleNode
        """
        current_node = self
        while distance:
            if distance > 0:
                distance -= 1
                current_node = current_node.next
            else:
                distance += 1
                current_node = current_node.prev
        return current_node


    def pop(self) -> Any:
        """
        Remove this node from the circle

        This will adjust all neighbors and have them skip this node. The next and prev properties will be set to None,
        which means that all methods will raise an error (not a pretty one) if you try to use them.

        :return: The value of this node
        :rtype: Any
        """
        self.prev.next = self.next
        self.next.prev = self.prev
        self.prev, self.next = None, None
        return self.value

    def add_right(self, value: Any) -> 'CircleNode':
        """
        Create a node to the right of this one

        By right, it means the created node becomes this node's next node. All close nodes will be adjusted to the
        change. If CircleNode is inherited, this method adjusts to the child class being used,

        :param value: The value that the node should hold
        :type value: Any
        :return: The circle node that was added to the right
        :rtype: CircleNode
        """
        new_node = self.__class__(value, self, self.next)
        new_node._fix_neighbors()
        return new_node

    def __iter__(self):
        """
        Yield nodes inside the circle

        This is a generator that yields all the nodes in the circle, starting with this one. It will stop once it
        reaches this node. This should always yield at least once.

        :return: A generator that yields nodes
        :rtype: generator
        """
        yield self
        c = self.next
        while c is not self:
            yield c
            c = c.next

    def __len__(self) -> int:
        """
        Return the amount of nodes in the circle

        Because the node instances don't keep track of the added nodes, if you have many nodes this could be a
        somewhat expensive process.

        :return: The amount of nodes in the circle
        :rtype: int
        """
        for i, _ in enumerate(self):
            pass
        return i + 1


def make_circle(items: Iterable[Any]) -> Union[CircleNode, None]:
    """
    Create a circle of nodes based on the input

    The values the iterator yields will act as a node's value. The order in which items are yielded is maintained, and
    the item that is yielded first will be returned. If no items are yielded, None is returned.

    :param items: Any object that's iterable
    :type items: Iterable[Any]
    :return: Either a circle node, or None if the iterator didn't yield anything
    :rtype: Union[CircleNode, None]
    """
    current_node = None
    for value in items:
        if not current_node:
            current_node = CircleNode(value)
        else:
            current_node = current_node.add_right(value)
    return None if not current_node else current_node.next


class WeakCircleNode(CircleNode):
    """
    A weakref version of CircleNode

    Because this class inherits CircleNode, it's advised you check it out. This version of CircleNode doesn't increase
    the reference count to the value using weakref.ref . When the value is forgotten, it will automatically remove the
    node from the circle. This can be very useful if let's say you're making a game where people fight in turns. If
    someone is eliminated and no references are left to the object, it will be removed automatically.

    :ivar value: The value provided. If no references to it are left, the value is None
    :vartype value: Any
    :ivar next: The next node in relation to this node (aka to the right of it)
    :vartype next: CircleNode or None
    :ivar prev: The previous node in relation to this node (aka to the left of it)
    :vartype prev: CircleNode or None
    """

    def __init__(self, value: Any, prev: 'WeakCircleNode'=None, next: 'WeakCircleNode'=None):
        self._value = None  # type: weakref.ref
        self._finalizer = None  # type: weakref.finalize
        super().__init__(value, prev, next)

    @property
    def value(self) -> Union[None, Any]:
        return self._value()

    @value.setter
    def value(self, val: Any) -> None:
        if self._value is not None:
            self._finalizer.detach()

        self._value = weakref.ref(val)
        self._finalizer = weakref.finalize(val, self.pop)


def make_weak_circle(items: Iterable[Any]) -> Union[WeakCircleNode, None]:
    """
    Create a weak circle of nodes based on the input

    The values the iterator yields will act as a node's value. Because only weak refernces are made to the values
    yielded, it's advised that you don't use a generator that doesn't store the values. The order in which items are
    yielded is maintained, and the item that is yielded first will be returned. If no items are yielded, None is
    returned.

    :param items: Any object that's iterable
    :type items: Iterable[Any]
    :return: Either a weak circle node, or None if the iterator didn't yield anything
    :rtype: Union[WeakCircleNode, None]
    """
    current_node = None
    for value in items:
        if not current_node:
            current_node = WeakCircleNode(value)
        else:
            current_node = current_node.add_right(value)
    return None if not current_node else current_node.next

circular_tests.py

import unittest

from circular import CircleNode, make_circle, make_weak_circle, WeakCircleNode

class CircleNodeTests(unittest.TestCase):

    DATA = ["a", "b", "c", 1, 2, 3, True, False]

    def test_make(self):
        node = make_circle(self.DATA)
        self.assertEqual(node.prev.value, False)
        self.assertEqual(node.next.value, "b")
        self.assertEqual(node.value, "a")

    def test_add_left(self):
        node = CircleNode("foo")
        current_node = node.add_left(None)
        self.assertIs(current_node.next, node)
        self.assertIsNot(current_node.prev.next, node)

    def test_add_right(self):
        node = CircleNode("bar")
        current_node = node.add_right(None)
        self.assertIs(current_node.prev, node)
        self.assertIsNot(current_node.next.prev, node)

    def test_iter(self):
        circle = make_circle(self.DATA)
        for i, node in enumerate(circle):
            if i == 0:
                self.assertIs(node, circle)
            elif i == 1:
                self.assertEqual(node.value, "b")
            elif i == 2:
                self.assertEqual(node.value, "c")
            elif i == 3:
                self.assertEqual(node.value, 1)

    def test_walk(self):
        circle = make_circle(self.DATA)
        self.assertEqual(circle.walk(2).value, "c")
        self.assertEqual(circle.walk(-2).value, True)
        self.assertEqual(circle.walk(0).value, "a")

    def test_remove(self):
        first_node = make_circle(self.DATA)
        prev_node, next_node = first_node.prev, first_node.next
        self.assertEqual(first_node.pop(), "a")
        self.assertIs(prev_node.next, next_node)
        self.assertIs(first_node.prev, None)
        self.assertIs(next_node.prev, prev_node)
        self.assertIs(first_node.next, None)


    def test_len(self):
        circle = make_circle(self.DATA)
        self.assertEqual(len(circle), 8)
        circle.add_left(None)
        self.assertEqual(len(circle), 9)
        prev_node = circle.prev
        circle.pop()
        self.assertEqual(len(prev_node), 8)


class WeakReferable:
    pass


class WeakCircleNodeTests(unittest.TestCase):

    DATA = [WeakReferable(), WeakReferable(), WeakReferable()]

    def test_inheritance(self):
        values = [WeakReferable(), WeakReferable()]
        node = WeakCircleNode(values[0])
        other_node = node.add_right(values[1])
        self.assertIsInstance(other_node, WeakCircleNode)

    def test_reference(self):
        d = self.DATA.copy()
        circle = make_weak_circle(d)
        del d[1]
        self.assertEqual(len(circle), 2)
        circle.add_left(WeakReferable())
        self.assertEqual(len(circle), 2)