This repository has been archived by the owner on Mar 21, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ArrayQueue.py
67 lines (58 loc) · 1.73 KB
/
ArrayQueue.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
29
30
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
import numpy as np
from Interfaces import Queue
class ArrayQueue(Queue):
def __init__(self):
self.n = 0
self.j = 0
self.a = self.new_array(1)
def new_array(self, n: int) ->np.array:
return np.zeros(n, np.object)
def resize(self):
'''
Resize the array
'''
b = self.new_array(max(1, 2*self.n))
for i in range(0, self.n):
b[i] = self.a[(self.j + i) % len(self.a)]
self.a = b
self.j = 0
def add(self, x : np.object) :
'''
shift all j > i one position to the right
and add element x in position i
'''
if (self.n + 1) > len(self.a):
self.resize()
self.a[(self.j + self.n) % len(self.a)] = x
self.n = self.n + 1
return True
def remove(self) -> np.object :
'''
remove the first element in the queue
'''
if (self.size() == 0):
raise IndexError("ArrayQueue: IndexError: Removed element that does not exist")
x = self.a[self.j]
self.j = ((self.j + 1) % len(self.a))
self.n = self.n - 1
if len(self.a) >= (3 * self.n): self.resize()
return x
def size(self) :
return self.n
def __str__(self):
s = "["
for i in range(0, self.n):
s += "%r" % self.a[(i + self.j) % len(self.a)]
if i < self.n-1:
s += ","
return s + "]"
def __iter__(self):
self.iterator = 0
return self
def __next__(self):
if self.iterator < self.n:
x = self.a[self.iterator]
self.iterator +=1
else:
raise StopIteration()
return x