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 std::copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
166 return *this;
167 }
168
169 // copy operator
170 template <class TYPE, bool AllowDuplicate>
171 SortedVector<TYPE, AllowDuplicate>& SortedVector<TYPE, AllowDuplicate>::operator=(const SortedVector<TYPE, true>& rhs)
172 {
173 vec_.clear();
174
175 if (AllowDuplicate) {
176 std::copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
177 } else {
178 // AllowDuplicate to Not AllowDuplicate
179 std::unique_copy(rhs.Begin(), rhs.End(), std::back_inserter(vec_));
180 }
181
182 return *this;
183 }
184
185 template <class TYPE, bool AllowDuplicate>
IndexOf(const TYPE & item)186 ssize_t SortedVector<TYPE, AllowDuplicate>::IndexOf(const TYPE& item) const
187 {
188 if (vec_.empty()) {
189 return NOT_FOUND;
190 }
191
192 auto it = std::lower_bound(std::begin(vec_), std::end(vec_), item);
193 if (it == vec_.end() || !(*it == item)) {
194 return NOT_FOUND;
195 }
196 return it - vec_.begin();
197 }
198
199 template <class TYPE, bool AllowDuplicate>
OrderOf(const TYPE & item)200 size_t SortedVector<TYPE, AllowDuplicate>::OrderOf(const TYPE& item) const
201 {
202 auto it = std::upper_bound(vec_.begin(), vec_.end(), item);
203 return it - vec_.begin();
204 }
205
206 template <class TYPE, bool AllowDuplicate>
Add(const TYPE & item)207 ssize_t SortedVector<TYPE, AllowDuplicate>::Add(const TYPE& item)
208 {
209 ssize_t index = IndexOf(item);
210 if (index != NOT_FOUND && !AllowDuplicate) {
211 return ADD_FAIL;
212 }
213
214 auto it = std::upper_bound(vec_.begin(), vec_.end(), item);
215 it = vec_.insert(it, item);
216 return it - vec_.begin();
217 }
218
219 template <class TYPE, bool AllowDuplicate>
SortedVector(const std::vector<TYPE> & invec)220 SortedVector<TYPE, AllowDuplicate>::SortedVector(const std::vector<TYPE>& invec)
221 {
222 if (invec.empty()) {
223 return;
224 }
225
226 std::vector<TYPE> newvector(invec);
227 std::sort(newvector.begin(), newvector.end());
228 if (AllowDuplicate) {
229 vec_.swap(newvector);
230 } else {
231 std::unique_copy(newvector.begin(), newvector.end(), std::back_inserter(vec_));
232 }
233 }
234
235 template <class TYPE, bool AllowDuplicate>
Merge(const std::vector<TYPE> & invec)236 size_t SortedVector<TYPE, AllowDuplicate>::Merge(const std::vector<TYPE>& invec)
237 {
238 SortedVector<TYPE, AllowDuplicate> sortedVector(invec);
239 Merge(sortedVector);
240 return vec_.size();
241 }
242
243 template <class TYPE, bool AllowDuplicate>
Merge(const SortedVector<TYPE,AllowDuplicate> & sortedVector)244 size_t SortedVector<TYPE, AllowDuplicate>::Merge(const SortedVector<TYPE, AllowDuplicate>& sortedVector)
245 {
246 std::vector<TYPE> newVec;
247 std::merge(vec_.begin(), vec_.end(), sortedVector.Begin(), sortedVector.End(), std::back_inserter(newVec));
248 if (!AllowDuplicate) {
249 vec_.clear();
250 std::unique_copy(newVec.begin(), newVec.end(), std::back_inserter(vec_));
251 } else {
252 vec_.swap(newVec);
253 }
254 return vec_.size();
255 }
256
257 } // namespace OHOS
258 #endif
259