1. template <class T>
2.  
3. T min(T a, T b) {
4.  
5.     return (a > b) ? b : a;
6.  
7. }
8.  
9.  
10.  
11. template <class T>
12.  
13. T max(T a, T b) {
14.  
15.     return (a < b) ? b : a;
16.  
17. }
18.  
19.  
20.  
21. template <class T, int N>
22.  
23. struct Vqs {
24.  
25.  
26.  
27.     Vqs();
28.  
29.  
30.  
31.     unsigned int count();
32.  
33.     bool empty();
34.  
35.     bool full();
36.  
37.     void clear();
38.  
39.     void print();
40.  
41.  
42.  
43.     T& get_front();
44.  
45.     T& get_back();
46.  
47.     T& pop_back();
48.  
49.     void push_back(T v);
50.  
51.     T& pop_front();
52.  
53.  
54.  
55.     void set(int index, T value);
56.  
57.     T& get(int index);
58.  
59.     int insert(int i, T in[], int count);
60.  
61.     int sai(int i, int count, T indata[]);
62.  
63.     int del(int i, int count);
64.  
65.  
66.  
67.     int front;
68.  
69.     int back;
70.  
71.     T data[N];
72.  
73. };
74.  
75.  
76.  
77. template <class T, int N>
78.  
79. void Vqs<T, N>::clear() {
80.  
81.     front = 0;
82.  
83.     back = 0;
84.  
85. }
86.  
87.  
88.  
89. template <class T, int N>
90.  
91. Vqs<T, N>::Vqs() {
92.  
93.     clear();
94.  
95. }
96.  
97.  
98.  
99. template <class T, int N>
100.  
101. bool Vqs<T, N>::empty() {
102.  
103.     return front == back;
104.  
105. }
106.  
107.  
108.  
109. template <class T, int N>
110.  
111. bool Vqs<T, N>::full() {
112.  
113.     return back - front == N;
114.  
115. }
116.  
117.  
118.  
119. template <class T, int N>
120.  
121. unsigned int Vqs<T, N>::count() {
122.  
123.     return back - front;
124.  
125. }
126.  
127.  
128.  
129. template <class T, int N>
130.  
131. void Vqs<T, N>::print() {
132.  
133.  
134.  
135.     int i = 0;
136.  
137.     int end = back - front;
138.  
139.     std::cout << "\n";
140.  
141.  
142.  
143.     while (i < end) {
144.  
145.         std::cout << data[(front + i++) % N] << ", ";
146.  
147.     }
148.  
149. }
150.  
151.  
152.  
153. template <class T, int N>
154.  
155. T& Vqs<T, N>::get_front() {
156.  
157.     return data[front % N];
158.  
159. }
160.  
161.  
162.  
163. template <class T, int N>
164.  
165. T& Vqs<T, N>::get_back() {
166.  
167.     return data[(back - 1) % N];
168.  
169. }
170.  
171.  
172.  
173. template <class T, int N>
174.  
175. T& Vqs<T, N>::get(int index) {
176.  
177.     return data[index];
178.  
179. }
180.  
181.  
182.  
183. template <class T, int N>
184.  
185. void Vqs<T, N>::set(int i, T value) {
186.  
187.     data[(front + i) % N] = value;
188.  
189. }
190.  
191.  
192.  
193. template <class T, int N>
194.  
195. void Vqs<T, N>::push_back(T v) {
196.  
197.  
198.  
199.     if (front + N == back) {
200.  
201.         ++front;
202.  
203.     }
204.  
205.  
206.  
207.     data[back++ % N] = v;
208.  
209. }
210.  
211.  
212.  
213. template <class T, int N>
214.  
215. T& Vqs<T, N>::pop_back() {
216.  
217.  
218.  
219.     assert(front != back);
220.  
221.     return data[--back % N];
222.  
223. }
224.  
225.  
226.  
227. template <class T, int N>
228.  
229. T& Vqs<T, N>::pop_front() {
230.  
231.  
232.  
233.     assert(front != back);
234.  
235.     return data[front++ % N];
236.  
237. }
238.  
239.  
240.  
241. template <class T, int N>
242.  
243. int Vqs<T, N>::sai(int i, int count, T indata[]) {
244.  
245.  
246.  
247.     int after_i = back - front - i;
248.  
249.  
250.  
251.     if (after_i < 0) {
252.  
253.         return 0;
254.  
255.     }
256.  
257.  
258.  
259.     //init
260.  
261.     int b_count, b_after_i, startj, to_delete;
262.  
263.  
264.  
265.     if (count < 0) {
266.  
267.         startj = i - 1;
268.  
269.         to_delete = ::min(after_i, -count);
270.  
271.     }
272.  
273.     else
274.  
275.     {
276.  
277.         startj = ::max(N - count, after_i) - 1;
278.  
279.         b_count = back + count;
280.  
281.         b_after_i = back - after_i;
282.  
283.     }
284.  
285.  
286.  
287.     //process
288.  
289.     int src, dst;
290.  
291.  
292.  
293.     for (int j = startj; j >= 0; --j) {
294.  
295.         if (count < 0) {
296.  
297.             dst = front + to_delete + j;
298.  
299.             src = dst - to_delete;
300.  
301.         }
302.  
303.         else {
304.  
305.             dst = b_after_i + count + j;
306.  
307.             src = dst - count;
308.  
309.         }
310.  
311.         data[dst % N] = data[src % N];
312.  
313.     }
314.  
315.  
316.  
317.     // postprocess
318.  
319.     if (count < 0) {
320.  
321.         front += to_delete;
322.  
323.         return to_delete;
324.  
325.     }
326.  
327.     else {
328.  
329.  
330.  
331.         int front_candidate = b_count - N;
332.  
333.  
334.  
335.         if (front_candidate > front) {
336.  
337.             front = ::min(front_candidate, b_after_i);
338.  
339.         }
340.  
341.  
342.  
343.         back = ::min(b_count, b_after_i + N);
344.  
345.  
346.  
347.         for (int j = 0; j < count; ++j) {
348.  
349.             data[(front + i + j) % N] = indata[j];
350.  
351.         }
352.  
353.  
354.  
355.         return count;
356.  
357.     }
358.  
359. }
360.  
361.  
362.  
363. template <class T, int N>
364.  
365. int Vqs<T, N>::del(int i, int count) {
366.  
367.     return sai(i, -count, nullptr);
368.  
369. }
370.  
371.  
372.  
373. template <class T, int N>
374.  
375. int Vqs<T, N>::insert(int i, T in[], int count) {
376.  
377.     return sai(i, count, in);
378.  
379. }
380.  
381.