1 /*
2 * Copyright (c) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef UTILS_BASE_SORTED_VECTOR_H
17 #define UTILS_BASE_SORTED_VECTOR_H
18
19 #include <algorithm>
20 #include <functional>
21 #include <iostream>
22 #include <sys/types.h>
23 #include <vector>
24
25 namespace OHOS {
26
27 template <class TYPE, bool AllowDuplicate = true>
28 class SortedVector {
29
30 public:
31 using value_type = TYPE;
32 using size_type = std::size_t;
33 using iterator = typename std::vector<TYPE>::iterator;
34 using const_iterator = typename std::vector<TYPE>::const_iterator;
35
36 // cont and dest
37
38 SortedVector();
39
40 SortedVector(const SortedVector<TYPE, false>& rhs);
41
42 SortedVector(const SortedVector<TYPE, true>& rhs);
43
44 SortedVector(const std::vector<TYPE>& orivect);
45
~SortedVector()46 virtual ~SortedVector() {};
47 // copy operator
48 SortedVector<TYPE, AllowDuplicate>& operator=(const SortedVector<TYPE, false>& rhs);
49 SortedVector<TYPE, AllowDuplicate>& operator=(const SortedVector<TYPE, true>& rhs);
50
Clear()51 inline void Clear() { vec_.clear(); }
Size()52 inline size_t Size() const { return vec_.size(); }
IsEmpty()53 inline bool IsEmpty() const { return vec_.empty(); }
Capacity()54 inline size_t Capacity() const { return vec_.capacity(); }
55
SetCapcity(size_t size)56 ssize_t SetCapcity(size_t size)
57 {
58 if (size < vec_.capacity()) {
59 return CAPCITY_NOT_CHANGED;
60 }
61
62 vec_.reserve(size);
63 return size;
64 }
65
66 // Cstyle access
67 // when use it , you should make sure it sorted~!
Array()68 inline const TYPE* Array() const { return vec_.data(); };
EditArray()69 TYPE* EditArray() { return vec_.data(); };
70
71 ssize_t IndexOf(const TYPE& item) const;
72 size_t OrderOf(const TYPE& item) const;
73
74 // accessors
75 inline const TYPE& operator[](size_t index) const { return vec_[index]; }
76
Back()77 const TYPE& Back() const { return vec_.back(); }
Front()78 const TYPE& Front() const { return vec_.front(); }
PopBack()79 void PopBack() { return vec_.pop_back(); }
80
MirrorItemAt(ssize_t index)81 const TYPE& MirrorItemAt(ssize_t index) const
82 {
83 if (index < 0) {
84 return *(vec_.end() + index);
85 }
86 return *(vec_.begin() + index);
87 };
88
89 // modify the array
90 ssize_t Add(const TYPE& item);
EditItemAt(size_t index)91 TYPE& EditItemAt(size_t index)
92 {
93 return vec_[index];
94 }
95
96 // merge a vector into this one
97 size_t Merge(const std::vector<TYPE>& invec);
98 size_t Merge(const SortedVector<TYPE, AllowDuplicate>& sortedVector);
99
100 // erase an item at index
Erase(size_t index)101 iterator Erase(size_t index)
102 {
103 if (index >= vec_.size()) {
104 return vec_.end();
105 }
106 return vec_.erase(vec_.begin() + index);
107 }
108
Begin()109 iterator Begin()
110 {
111 return vec_.begin();
112 }
113
Begin()114 const_iterator Begin() const
115 {
116 return vec_.begin();
117 }
118
End()119 iterator End()
120 {
121 return vec_.end();
122 }
123
End()124 const_iterator End() const
125 {
126 return vec_.end();
127 }
128
129 static const ssize_t NOT_FOUND = -1;
130 static const ssize_t ADD_FAIL = -1;
131 static const ssize_t CAPCITY_NOT_CHANGED = -1;
132
133 private:
134 std::vector<TYPE> vec_;
135 };
136
137 template <class TYPE, bool AllowDuplicate>
SortedVector()138 inline SortedVector<TYPE, AllowDuplicate>::SortedVector()
139 : vec_() {}
140
141 template <class TYPE, bool AllowDuplicate>
SortedVector(const SortedVector<TYPE,false> & rhs)142 SortedVector<TYPE, AllowDuplicate>::SortedVector(const SortedVector<TYPE, false>& rhs)
143 {
144 // this class: AllowDuplicate or Not AllowDuplicate same type
145 std::copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
146 }
147
148 template <class TYPE, bool AllowDuplicate>
SortedVector(const SortedVector<TYPE,true> & rhs)149 SortedVector<TYPE, AllowDuplicate>::SortedVector(const SortedVector<TYPE, true>& rhs)
150 {
151
152 if (AllowDuplicate) {
153 std::copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
154 } else {
155 // AllowDuplicate to Not AllowDuplicate
156 std::unique_copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
157 }
158 }
159
160 // copy operator
161 template <class TYPE, bool AllowDuplicate>
162 SortedVector<TYPE, AllowDuplicate>& SortedVector<TYPE, AllowDuplicate>::operator=(const SortedVector<TYPE, false>& rhs)
163 {
164 // this class: AllowDuplicate or Not AllowDuplicate same type
165 vec_.clear();
166 std::copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
167 return *this;
168 }
169
170 // copy operator
171 template <class TYPE, bool AllowDuplicate>
172 SortedVector<TYPE, AllowDuplicate>& SortedVector<TYPE, AllowDuplicate>::operator=(const SortedVector<TYPE, true>& rhs)
173 {
174 vec_.clear();
175
176 if (AllowDuplicate) {
177 std::copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
178 } else {
179 // AllowDuplicate to Not AllowDuplicate
180 std::unique_copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
181 }
182
183 return *this;
184 }
185
186 template <class TYPE, bool AllowDuplicate>
IndexOf(const TYPE & item)187 ssize_t SortedVector<TYPE, AllowDuplicate>::IndexOf(const TYPE& item) const
188 {
189 if (vec_.empty()) {
190 return NOT_FOUND;
191 }
192
193 auto it = std::lower_bound(std::begin(vec_), std::end(vec_), item);
194 if (it == vec_.end() || !(*it == item)) {
195 return NOT_FOUND;
196 }
197 return it - vec_.begin();
198 }
199
200 template <class TYPE, bool AllowDuplicate>
OrderOf(const TYPE & item)201 size_t SortedVector<TYPE, AllowDuplicate>::OrderOf(const TYPE& item) const
202 {
203 auto it = std::upper_bound(vec_.begin(), vec_.end(), item);
204 return it - vec_.begin();
205 }
206
207 template <class TYPE, bool AllowDuplicate>
Add(const TYPE & item)208 ssize_t SortedVector<TYPE, AllowDuplicate>::Add(const TYPE& item)
209 {
210 ssize_t index = IndexOf(item);
211 if (index != NOT_FOUND && !AllowDuplicate) {
212 return ADD_FAIL;
213 }
214
215 auto it = std::upper_bound(vec_.begin(), vec_.end(), item);
216 it = vec_.insert(it, item);
217 return it - vec_.begin();
218 }
219
220 template <class TYPE, bool AllowDuplicate>
SortedVector(const std::vector<TYPE> & invec)221 SortedVector<TYPE, AllowDuplicate>::SortedVector(const std::vector<TYPE>& invec)
222 {
223 if (invec.empty()) {
224 return;
225 }
226
227 std::vector<TYPE> newvector(invec);
228 std::sort(newvector.begin(), newvector.end());
229 if (AllowDuplicate) {
230 vec_.swap(newvector);
231 } else {
232 std::unique_copy(newvector.begin(), newvector.end(), std::back_inserter(vec_));
233 }
234 }
235
236 template <class TYPE, bool AllowDuplicate>
Merge(const std::vector<TYPE> & invec)237 size_t SortedVector<TYPE, AllowDuplicate>::Merge(const std::vector<TYPE>& invec)
238 {
239 SortedVector<TYPE, AllowDuplicate> sortedVector(invec);
240 Merge(sortedVector);
241 return vec_.size();
242 }
243
244 template <class TYPE, bool AllowDuplicate>
Merge(const SortedVector<TYPE,AllowDuplicate> & sortedVector)245 size_t SortedVector<TYPE, AllowDuplicate>::Merge(const SortedVector<TYPE, AllowDuplicate>& sortedVector)
246 {
247 std::vector<TYPE> newVec;
248 std::merge(vec_.begin(), vec_.end(), sortedVector.Begin(), sortedVector.End(), std::back_inserter(newVec));
249 if (!AllowDuplicate) {
250 vec_.clear();
251 std::unique_copy(newVec.begin(), newVec.end(), std::back_inserter(vec_));
252 } else {
253 vec_.swap(newVec);
254 }
255 return vec_.size();
256 }
257
258 } // namespace OHOS
259 #endif
260