1/**************************************************************************/
2/* bin_sorted_array.h */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#ifndef BIN_SORTED_ARRAY_H
32#define BIN_SORTED_ARRAY_H
33
34#include "core/templates/local_vector.h"
35#include "core/templates/paged_array.h"
36
37template <class T>
38class BinSortedArray {
39 PagedArray<T> array;
40 LocalVector<uint64_t> bin_limits;
41
42 // Implement if elements need to keep track of their own index in the array.
43 _FORCE_INLINE_ virtual void _update_idx(T &r_element, uint64_t p_idx) {}
44
45 _FORCE_INLINE_ void _swap(uint64_t p_a, uint64_t p_b) {
46 SWAP(array[p_a], array[p_b]);
47 _update_idx(array[p_a], p_a);
48 _update_idx(array[p_b], p_b);
49 }
50
51public:
52 uint64_t insert(T &p_element, uint64_t p_bin) {
53 array.push_back(p_element);
54 uint64_t new_idx = array.size() - 1;
55 _update_idx(p_element, new_idx);
56 bin_limits[0] = new_idx;
57 if (p_bin != 0) {
58 new_idx = move(new_idx, p_bin);
59 }
60 return new_idx;
61 }
62
63 uint64_t move(uint64_t p_idx, uint64_t p_bin) {
64 ERR_FAIL_UNSIGNED_INDEX_V(p_idx, array.size(), -1);
65
66 uint64_t current_bin = bin_limits.size() - 1;
67 while (p_idx > bin_limits[current_bin]) {
68 current_bin--;
69 }
70
71 if (p_bin == current_bin) {
72 return p_idx;
73 }
74
75 uint64_t current_idx = p_idx;
76 if (p_bin > current_bin) {
77 while (p_bin > current_bin) {
78 uint64_t swap_idx = 0;
79
80 if (current_bin == bin_limits.size() - 1) {
81 bin_limits.push_back(0);
82 } else {
83 bin_limits[current_bin + 1]++;
84 swap_idx = bin_limits[current_bin + 1];
85 }
86
87 if (current_idx != swap_idx) {
88 _swap(current_idx, swap_idx);
89 current_idx = swap_idx;
90 }
91
92 current_bin++;
93 }
94 } else {
95 while (p_bin < current_bin) {
96 uint64_t swap_idx = bin_limits[current_bin];
97
98 if (current_idx != swap_idx) {
99 _swap(current_idx, swap_idx);
100 }
101
102 if (current_bin == bin_limits.size() - 1 && bin_limits[current_bin] == 0) {
103 bin_limits.resize(bin_limits.size() - 1);
104 } else {
105 bin_limits[current_bin]--;
106 }
107 current_idx = swap_idx;
108 current_bin--;
109 }
110 }
111
112 return current_idx;
113 }
114
115 void remove_at(uint64_t p_idx) {
116 ERR_FAIL_UNSIGNED_INDEX(p_idx, array.size());
117 uint64_t new_idx = move(p_idx, 0);
118 uint64_t swap_idx = array.size() - 1;
119
120 if (new_idx != swap_idx) {
121 _swap(new_idx, swap_idx);
122 }
123
124 if (bin_limits[0] > 0) {
125 bin_limits[0]--;
126 }
127
128 array.pop_back();
129 }
130
131 void set_page_pool(PagedArrayPool<T> *p_page_pool) {
132 array.set_page_pool(p_page_pool);
133 }
134
135 _FORCE_INLINE_ const T &operator[](uint64_t p_index) const {
136 return array[p_index];
137 }
138
139 _FORCE_INLINE_ T &operator[](uint64_t p_index) {
140 return array[p_index];
141 }
142
143 int get_bin_count() {
144 if (array.size() == 0) {
145 return 0;
146 }
147 return bin_limits.size();
148 }
149
150 int get_bin_start(int p_bin) {
151 ERR_FAIL_COND_V(p_bin >= get_bin_count(), ~0U);
152 if ((unsigned int)p_bin == bin_limits.size() - 1) {
153 return 0;
154 }
155 return bin_limits[p_bin + 1] + 1;
156 }
157
158 int get_bin_size(int p_bin) {
159 ERR_FAIL_COND_V(p_bin >= get_bin_count(), 0);
160 if ((unsigned int)p_bin == bin_limits.size() - 1) {
161 return bin_limits[p_bin] + 1;
162 }
163 return bin_limits[p_bin] - bin_limits[p_bin + 1];
164 }
165
166 void reset() {
167 array.reset();
168 bin_limits.clear();
169 bin_limits.push_back(0);
170 }
171
172 BinSortedArray() {
173 bin_limits.push_back(0);
174 }
175
176 virtual ~BinSortedArray() {
177 reset();
178 }
179};
180
181#endif // BIN_SORTED_ARRAY_H
182