-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdeque
More file actions
executable file
·49 lines (37 loc) · 894 Bytes
/
Copy pathdeque
File metadata and controls
executable file
·49 lines (37 loc) · 894 Bytes
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
#!/usr/bin/python2.7
import bisect
import collections
# Fast queue that allows fast removal from head and sorted
# insert.
class FastQueue:
def __init__(self):
self.__deque = collections.deque()
def __len__(self):
return len(self.__deque)
def __str__(self):
a = []
for elem in self.__deque:
a.append(str(elem))
return "[" + ",".join(a) + "]"
def head(self):
return self.__deque.popleft()
def insert(self, obj):
index = bisect.bisect_left(self.__deque, obj)
self.__deque.rotate(-index)
self.__deque.appendleft(obj)
self.__deque.rotate(index)
def content(self):
return self.__deque
A = FastQueue()
for x in range(5):
A.insert(3 * x)
print A
print A.head()
print A
A.insert(7)
print A
print 'pop and insert'
k = A.head()
print 'k = ', k
A.insert(k)
print A