data-structures/include/data_structures/circular_array.h at main · scar027/data-structures · GitHub

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
#ifndef DATA_STRUCTURES_CIRCULAR_ARRAY_H
#define DATA_STRUCTURES_CIRCULAR_ARRAY_H

#include <stdexcept>
#include <vector>

namespace DataStructures {

template <typename T>
class CircularArray {
public:
	CircularArray() : CircularArray(1) {}

	explicit CircularArray(size_t init_size)
		: arr(init_size), start(0), end(0), size(0)
	{
	}

	void add_first(const T& val)
	{
		if (is_full()) {
			resize(arr.size() * 2);
		}
		start = (start - 1 + int(arr.size())) % int(arr.size());
		arr[static_cast<size_t>(start)] = val;
		size++;
	}

	void add_last(const T& val)
	{
		if (is_full()) {
			resize(arr.size() * 2);
		}
		arr[static_cast<size_t>(end)] = val;
		end = (end + 1) % int(arr.size());
		size++;
	}

	T del_first()
	{
		if (is_empty()) {
			throw std::out_of_range("Array is empty");
		}
		T val = arr[static_cast<size_t>(start)];
		arr[static_cast<size_t>(start)] = T();
		start = (start + 1) % int(arr.size());
		size--;
		if (size > 0 && int(size) == int(arr.size()) / 4) {
			resize(arr.size() / 2);
		}
		return val;
	}

	T del_last()
	{
		if (is_empty()) {
			throw std::out_of_range("Array is empty");
		}
		end = (end - 1 + int(arr.size())) % int(arr.size());
		T val = arr[static_cast<size_t>(end)];
		arr[static_cast<size_t>(end)] = T();
		size--;
		if (size > 0 && int(size) == int(arr.size()) / 4) {
			resize(arr.size() / 2);
		}
		return val;
	}

	T get_first() const
	{
		if (is_empty()) {
			throw std::out_of_range("Array is empty");
		}
		return arr[static_cast<size_t>(start)];
	}

	T get_last() const
	{
		if (is_empty()) {
			throw std::out_of_range("Array is empty");
		}
		return arr[static_cast<size_t>((end - 1 + int(arr.size())) %
					       int(arr.size()))];
	}

	bool is_full() const { return size == arr.size(); }

	size_t get_size() const { return size; }

	bool is_empty() const { return size == 0; }

private:
	std::vector<T> arr;
	int start;
	int end;
	size_t size;

	void resize(size_t new_size)
	{
		std::vector<T> new_arr(new_size);
		for (size_t i = 0; i < size; i++) {
			new_arr[i] = arr[static_cast<size_t>((start + int(i)) %
							     int(arr.size()))];
		}
		arr = std::move(new_arr);
		start = 0;
		end = int(size);
	}
};

} // namespace DataStructures

#endif // DATA_STRUCTURES_CIRCULAR_ARRAY_H