LinkedListQueue

Complexity

Total Complexity

10

Size/Duplication

Total Lines	37
Duplicated Lines	0 %

Importance

Changes	1
Bugs	0	Features	0

5 Methods

Rating	Name	Duplication	Size	Complexity
A	size()	0	2	1
A	iterate()	0	6	2
A	enqueue()	0	8	3
A	is_empty()	0	2	1
A	dequeue()	0	9	3

from abc import abstractmethod, ABCMeta


class Queue(object):
    """ Queue interface
    
    """

    __metaclass__ = ABCMeta

    @abstractmethod
    def enqueue(self, item):
        pass

    @abstractmethod
    def dequeue(self):
        pass

    @abstractmethod
    def is_empty(self):
        pass

    @abstractmethod
    def size(self):
        pass

    @staticmethod
    def create():
        return LinkedListQueue()

    @abstractmethod
    def iterate(self):
        pass


class Node(object):

    value = None
    nextNode = None

    def __init__(self, value):
        self.value = value


class LinkedListQueue(Queue):

    first = None
    last = None
    N = 0

    def size(self):
        return self.N

    def iterate(self):
        x = self.first
        while x is not None:
            value = x.value
            x = x.nextNode
            yield value

    def enqueue(self, item):
        old_last = self.last
        self.last = Node(item)
        if old_last is not None:
            old_last.nextNode = self.last
        if self.first is None:
            self.first = self.last
        self.N += 1

    def is_empty(self):
        return self.N == 0

    def dequeue(self):
        if self.is_empty():
            return None
        old_first = self.first
        self.first = old_first.nextNode
        if old_first == self.last:
            self.last = None
        self.N -= 1
        return old_first.value


class ArrayQueue(Queue):

    head = 0
    tail = 0
    s = []

    def __init__(self, capacity=None):
        if capacity is None:
            capacity = 10
        self.s = [0] * capacity

    def iterate(self):
        if self.is_empty():
            return
        for i in range(self.head, self.tail):
            yield self.s[i]

    def enqueue(self, item):
        self.s[self.tail] = item
        self.tail += 1
        if self.tail == len(self.s):
            self.resize(len(self.s) * 2)

    def resize(self, new_size):
        tmp = [0] * new_size
        for i in range(self.head, self.tail):
            tmp[i-self.head] = self.s[i]
        self.s = tmp
        self.tail = self.tail - self.head
        self.head = 0

    def size(self):
        return self.tail - self.head

    def is_empty(self):
        return self.size() == 0

    def dequeue(self):
        if self.is_empty():
            return None

        deleted = self.s[self.head]
        self.head += 1
        if self.size() == len(self.s) // 4:
            self.resize(len(self.s) // 2)
        return deleted