StacksQueues/Python/ArrayDeque

See code on git.charlesreid1.com: https://charlesreid1.com:3000/cs/python/src/master/stacks-queues-deques/deque/ArrayDeque.py

Double-ended queue (deque) implemented using an underlying array-based structure - a list. (See also: Arrays/Python

ArrayDeque test

if __name__=="__main__":
    d = ArrayDeque()
    for i,c in enumerate("ABCDEFGHIJKLMNOP"):
        d.add_first(c)
        print(d)

    for j in range(100):
        try:
            d.delete_first()
            print(d)
        except Empty:
            pass

    print("Length of d: {0}".format(len(d)))

    for i,c in enumerate("12345"):
        d.add_last(c)
        print(d)

    for j in range(4):
        d.delete_last()
        print(d)

    print("final:")
    print(d)

ArrayDeque class

"""
Deque (double-ended queue) ADT

ArrayDeque: implements an array-based double-ended queue

A deque object D implements the following core methods:
    * D.add_first : add the item to the front of the deque
    * D.add_last : add the item to the end of the deque
    * D.delete_first : remove and return the ifrst item from the deque
    * D.delete_last : remove and return the last item from the deque

Additional convenience methods:
    * D.first : peek at first item
    * D.last : peek at last item
    * D.is_empty : returns True if deque has no elements
    * D.__len__ : length
    * D.__str__ : turn into string)

Private utility methods:
    * D._resize : resize the deque (dynamic growth/shrinkage)

"""

class Empty(Exception):
    pass

class ArrayDeque:
    """
    """
    def __init__(self):
        INIT_CAP = 10
        self._first = 0
        self._data = [None]*INIT_CAP
        self._n = 0

    def __len__(self):
        """length of deque"""
        return self._n

    def __str__(self):
        """string representation of deque"""
        return str(self._data)

    def is_empty(self):
        """returns true if deque is empty"""
        return self._n==0

    def add_first(self, e):
        """add item to beginning of deque"""
        if(self._n==len(self._data)):
            self._resize(2*self._n)
        # First minus one because moving one index ahead of first
        addix = (self._first - 1)%len(self._data)
        self._data[addix] = e
        self._first = addix
        self._n += 1

    def add_last(self, e):
        """add item to end of deque"""
        if(self._n==len(self._data)):
            self._resize(2*self._n)
        # First plus n: jumping to the next open index,
        # which must be index first + n.
        # If there are n items starting at first, then they will be
        # at first through (first + n - 1).
        # Next open index is at first + n.
        addix = (self._first + self._n)%(len(self._data))
        self._data[addix] = e
        self._n += 1

    def delete_first(self):
        if(not self.is_empty()):
            ret = self._data[self._first]
            self._data[self._first] = None
            self._first = (self._first + 1)%(len(self._data))
            self._n -= 1

            # If we're down to smaller than a quarter occupied,
            # cut array size in half.
            if(self._n < len(self._data)//4):
                self._resize(len(self._data)//2)

        else:
            raise Empty("oops, empty deque")

    def delete_last(self):
        if(not self.is_empty()):
            getix = (self._first + self._n - 1)%(len(self._data))
            ret = self._data[getix]
            self._data[getix] = None
            self._n -= 1

            # If we're down to smaller than a quarter occupied,
            # cut array size in half.
            if(self._n < len(self._data)//4):
                self._resize(len(self._data)//2)

        else:
            raise Empty("oops, empty deque")

    def _resize(self,newcap):
        """private method: resize the underlying array"""
        old = self._data
        self._data = [None]*newcap
        walk = self._first

        # Need to pay close attention here:
        # range over each of the n elements
        for k in range(self._n):
            self._data[k] = old[walk]
            # Increment walk after the update, not before
            walk += 1
            walk %= len(old)

        self._first = 0

ArrayDeque test output

$ python ArrayDeque.py
[None, None, None, None, None, None, None, None, None, 'A']
[None, None, None, None, None, None, None, None, 'B', 'A']
[None, None, None, None, None, None, None, 'C', 'B', 'A']
[None, None, None, None, None, None, 'D', 'C', 'B', 'A']
[None, None, None, None, None, 'E', 'D', 'C', 'B', 'A']
[None, None, None, None, 'F', 'E', 'D', 'C', 'B', 'A']
[None, None, None, 'G', 'F', 'E', 'D', 'C', 'B', 'A']
[None, None, 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
[None, 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, 'O', 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, 'P', 'O', 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, 'O', 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, 'N', 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, 'M', 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, 'L', 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, 'K']
['J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, None, 'G', 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, 'F', 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, 'E', 'D', 'C', 'B', 'A', None, None, None, None, None, None, None, None, None, None]
['D', 'C', 'B', 'A', None, None, None, None, None, None]
[None, 'C', 'B', 'A', None, None, None, None, None, None]
[None, None, 'B', 'A', None, None, None, None, None, None]
['A', None, None, None, None]
[None, None]
Length of d: 0
['1', None]
['1', '2']
['1', '2', '3', None]
['1', '2', '3', '4']
['1', '2', '3', '4', '5', None, None, None]
['1', '2', '3', '4', None, None, None, None]
['1', '2', '3', None, None, None, None, None]
['1', '2', None, None, None, None, None, None]
['1', None, None, None]
final:
['1', None, None, None]