Skip to content

Structures

LiFoStack

Last-In-First-Out (LIFO) stack implementation using linked nodes.

A stack data structure that follows the LIFO principle where elements are added and removed from the same end.

Attributes:

Name Type Description
_tail Node

The tail node of the stack.
_cursor Node

Current position for iteration.
_len int

Number of elements in the stack.

Methods:

Name Description
push

Pushes an element onto the top of the stack.
get

Returns but does not remove the top element.
pop

Removes and returns the top element.
is_head

Checks if the stack is at the head position.
Source code in apps/annotator/code/utils/structures.py 
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
class LiFoStack:
    """
    Last-In-First-Out (LIFO) stack implementation using linked nodes.

    A stack data structure that follows the LIFO principle where elements
    are added and removed from the same end.

    Attributes
    ----------
    _tail : Node
        The tail node of the stack.
    _cursor : Node
        Current position for iteration.
    _len : int
        Number of elements in the stack.

    Methods
    -------
    push(elem)
        Pushes an element onto the top of the stack.
    get(indx=None, raise_exception=False)
        Returns but does not remove the top element.
    pop(raise_exception=False)
        Removes and returns the top element.
    is_head(self)
        Checks if the stack is at the head position.
    """
    _tail = Node()
    _cursor = _tail
    _len = 0

    def __init__(self,from_list:'list'= None) -> None:
        if from_list is not None: i=0; [ self.push(elem) for elem in from_list ]

    def __str__(self):
        cur = self._tail.get_prev()
        out = ""
        max_len = 0
        # can be improved but for now is just for debug purposes
        while cur is not None:
            max_len = max(max_len, len(str(cur.value)))
            out += "| " + str(cur.value) + " |\n"
            cur = cur.get_prev()
        if out=="":
            out= "empty"
        return out + "⎿"+"⎽"*max_len+"⎽⎽⎽⎽"+"⏌ "

    def __iter__(self):
        return self

    def __next__(self):
        node = self._cursor.get_prev()
        if node is not None:
            self._cursor = node
            return node.value
        else:
            self._cursor = self._tail
            raise StopIteration()

    def __len__(self):
        return self._len

    def is_head(self):
        return self._tail.get_prev() is None

    def push(self,elem):
        """
        Pushes an element onto the top of the stack.

        Parameters
        ----------
        elem : any
            The element to be pushed onto the stack.
        """
        curr_tail = self._tail
        curr_tail.value = elem
        self._tail = Node().set_prev(curr_tail)
        self._cursor = self._tail
        self._len += 1

    def get(self,indx=None,raise_exception=False):
        """
        Returns but does not remove the top element of the stack.

        Parameters
        ----------
        indx : int, optional
            Currently unused parameter.
        raise_exception : bool, default=False
            If True, raises an exception when stack is empty.

        Returns
        -------
        any or None
            The top element of the stack, or None if stack is empty
            and raise_exception is False.

        Raises
        ------
        Exception
            If the stack is empty and raise_exception is True.
        """
        tail = self._tail
        if tail.get_prev() is None:
            if raise_exception:
                raise Exception("Popping from an empty stack")
            else:
                return None
        return tail.get_prev().value

    def pop(self,raise_exception=False):
        """
        Removes and returns the top element of the stack.

        Parameters
        ----------
        raise_exception : bool, default=False
            If True, raises an exception when stack is empty.

        Returns
        -------
        any or None
            The top element of the stack, or None if stack is empty
            and raise_exception is False.
        """
        value = self.get(raise_exception)
        if value is not None:
            self._tail = self._tail.get_prev()
            self._len -= 1
        return value

get(indx=None, raise_exception=False)

Returns but does not remove the top element of the stack.

Parameters:

Name Type Description Default
indx int

Currently unused parameter.

 None
raise_exception bool

If True, raises an exception when stack is empty.

 False

Returns:

Type Description
any or None

The top element of the stack, or None if stack is empty and raise_exception is False.

Raises:

Type Description
Exception

If the stack is empty and raise_exception is True.
Source code in apps/annotator/code/utils/structures.py 
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
def get(self,indx=None,raise_exception=False):
    """
    Returns but does not remove the top element of the stack.

    Parameters
    ----------
    indx : int, optional
        Currently unused parameter.
    raise_exception : bool, default=False
        If True, raises an exception when stack is empty.

    Returns
    -------
    any or None
        The top element of the stack, or None if stack is empty
        and raise_exception is False.

    Raises
    ------
    Exception
        If the stack is empty and raise_exception is True.
    """
    tail = self._tail
    if tail.get_prev() is None:
        if raise_exception:
            raise Exception("Popping from an empty stack")
        else:
            return None
    return tail.get_prev().value

pop(raise_exception=False)

Removes and returns the top element of the stack.

Parameters:

Name Type Description Default
raise_exception bool

If True, raises an exception when stack is empty.

 False

Returns:

Type Description
any or None

The top element of the stack, or None if stack is empty and raise_exception is False.
Source code in apps/annotator/code/utils/structures.py 
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
def pop(self,raise_exception=False):
    """
    Removes and returns the top element of the stack.

    Parameters
    ----------
    raise_exception : bool, default=False
        If True, raises an exception when stack is empty.

    Returns
    -------
    any or None
        The top element of the stack, or None if stack is empty
        and raise_exception is False.
    """
    value = self.get(raise_exception)
    if value is not None:
        self._tail = self._tail.get_prev()
        self._len -= 1
    return value

push(elem)

Pushes an element onto the top of the stack.

Parameters:

Name Type Description Default
elem any

The element to be pushed onto the stack.

 required
Source code in apps/annotator/code/utils/structures.py 
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
def push(self,elem):
    """
    Pushes an element onto the top of the stack.

    Parameters
    ----------
    elem : any
        The element to be pushed onto the stack.
    """
    curr_tail = self._tail
    curr_tail.value = elem
    self._tail = Node().set_prev(curr_tail)
    self._cursor = self._tail
    self._len += 1

Node

A node class for implementing linked data structures.

Attributes:

Name Type Description
value any

The value stored in the node.
_prev Node or None

Reference to the previous node in the structure.

Methods:

Name Description
set_prev

Sets the previous node reference and returns self.
get_prev

Returns the previous node reference.
Source code in apps/annotator/code/utils/structures.py 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Node:
    """
    A node class for implementing linked data structures.

    Attributes
    ----------
    value : any
        The value stored in the node.
    _prev : Node or None
        Reference to the previous node in the structure.

    Methods
    -------
    set_prev(prev)
        Sets the previous node reference and returns self.
    get_prev()
        Returns the previous node reference.
    """
    def __init__(self,value=None):
        self.value = value
        self._prev:Node or None = None

    def set_prev(self,prev) -> 'Node':
        self._prev = prev 
        return self

    def get_prev(self) -> 'Node or None':
        return self._prev