-
Notifications
You must be signed in to change notification settings - Fork 0
/
rdeque.py
78 lines (66 loc) · 1.75 KB
/
rdeque.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
68
69
70
71
72
73
74
75
76
77
78
class rdeque(object):
__slots__ = ['right', 'left']
def __init__(self, right = []):
self.right = right[:]
self.left = []
def len(self):
return len(self.left) + len(self.right)
def iadd(self, other):
tmp = other.left[:]
tmp.reverse()
self.right += tmp
self.right += other.right
def append(self, value):
self.right.append(value)
def appendleft(self, value):
self.left.append(value)
def extend(self, values):
self.right += values
def extendleft(self, values):
tmp = values[:]
tmp.reverse()
self.left += tmp
def pop(self):
if not self.right:
mid = len(self.left) + 1 >> 1
self.right = self.left[:mid]
self.right.reverse()
del self.left[:mid]
if self.right:
return self.right.pop()
raise IndexError('pop from empty list')
def popleft(self):
if not self.left:
mid = len(self.right) + 1 >> 1
self.left = self.right[:mid]
self.left.reverse()
del self.right[:mid]
if self.left:
return self.left.pop()
raise IndexError('pop from empty list')
def popn(self, n):
if n < 0:
raise IndexError('list index out of range')
i = len(self.right) - n
if i >= 0:
result = self.right[i:]
del self.right[i:]
return result
i = -i
if len(self.left) >= i > 0:
result = self.left[:i]
result.reverse()
result += self.right
del self.left[:i]
self.right = []
return result
raise IndexError('list index out of range')
def reverse(self):
self.left, self.right = self.right, self.left
def top(self):
i = len(self.right) - 1
if i >= 0:
return self.right[i]
if self.left:
return self.left[0]
raise IndexError('list index out of range')