-
Notifications
You must be signed in to change notification settings - Fork 0
/
reorderbuffer.py
126 lines (105 loc) · 3.37 KB
/
reorderbuffer.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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
# -*- coding: utf-8 -*-
class ReorderBuffer:
def __init__(self, init_v=0):
self.buffer_data = {}
self.buffer_idx = set()
self.pfirst = init_v # the next ID to pick
self.plast = init_v # one over the last ordered ID
def put(self, idx, data):
self.buffer_data[idx] = data
self.buffer_idx.add(idx)
if idx == self.plast:
self.__move_last__()
def top(self):
if self.pfirst < self.plast:
idx = self.pfirst
data = self.buffer_data[idx]
return idx, data
return None, None
def get_one(self):
if self.pfirst < self.plast:
idx = self.pfirst
data = self.buffer_data.pop(idx)
self.pfirst += 1
return idx, data
return None, None
def get(self, n:int=0):
if n == 0:
n = self.plast - self.pfirst
res_i = []
res_d = []
while self.pfirst < self.plast and n > 0:
idx = self.pfirst
data = self.buffer_data.pop(idx)
self.pfirst += 1
res_i.append(idx)
res_d.append(data)
n -= 1
return res_i, res_d
def move_and_check(self, target_idx, n:int=0):
if n == 0:
n = self.plast - self.pfirst
while self.pfirst < self.plast and n > 0:
idx = self.pfirst
self.buffer_data.pop(idx)
self.pfirst += 1
n -= 1
if idx == target_idx:
return True
return False
# size related
def size(self):
return len(self.buffer_data)
def size_inorder(self):
return self.plast - self.pfirst
def size_unorder(self):
return len(self.buffer_data) - self.size_inorder()
# helpers
def __move_last__(self):
while self.plast in self.buffer_idx:
self.buffer_idx.remove(self.plast)
self.plast += 1
# %% test
def __test1__():
idxes = [7, 4, 9, 0, 5, 2, 3, 1, 6, 8]
rb=ReorderBuffer()
for idx in idxes:
print('put:',idx)
rb.put(idx*10, idx)
print(' size:',rb.size(), rb.size_inorder(), rb.size_unorder())
i,d = rb.get()
print(' get:',i,d)
print(' idx:',rb.buffer_idx)
print('finish:', rb.size(), rb.buffer_idx, rb.buffer_data)
def __test2__():
idxes = [7, 4, 9, 0, 5, 2, 3, 1, 6, 8]
rb=ReorderBuffer()
for idx in idxes:
print('put:',idx)
rb.put(idx*10, idx)
print(' size:',rb.size(), rb.size_inorder(), rb.size_unorder())
i,d = rb.get(2)
print(' get:',i,d)
print(' idx:',rb.buffer_idx)
while True:
print('pick')
i,d = rb.get(2)
if len(i) == 0:
break
print(' size:',rb.size(), rb.size_inorder(), rb.size_unorder())
print(' get:',i,d)
print(' idx:',rb.buffer_idx)
def __test3__():
import numpy as np
idxes = np.arange(10)
np.random.shuffle(idxes)
print('order:',idxes)
rb=ReorderBuffer()
for idx in idxes:
print('put:',idx)
rb.put(idx*10, idx)
print(' size:',rb.size(), rb.size_inorder(), rb.size_unorder())
i,d = rb.get()
print(' get:',i,d)
print(' idx:',rb.buffer_idx)
print('finish:', rb.size(), rb.buffer_idx, rb.buffer_data)