1 /*
2 * Copyright (C) 2005 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ANDROID_SORTED_VECTOR_H
18 #define ANDROID_SORTED_VECTOR_H
19
20 #include <assert.h>
21 #include <stdint.h>
22 #include <sys/types.h>
23
24 #include <utils/Vector.h>
25 #include <utils/VectorImpl.h>
26 #include <utils/TypeHelpers.h>
27
28 // ---------------------------------------------------------------------------
29
30 namespace android {
31
32 template <class TYPE>
33 class SortedVector : private SortedVectorImpl
34 {
35 friend class Vector<TYPE>;
36
37 public:
38 typedef TYPE value_type;
39
40 /*!
41 * Constructors and destructors
42 */
43
44 SortedVector();
45 SortedVector(const SortedVector<TYPE>& rhs);
46 virtual ~SortedVector();
47
48 /*! copy operator */
49 const SortedVector<TYPE>& operator = (const SortedVector<TYPE>& rhs) const;
50 SortedVector<TYPE>& operator = (const SortedVector<TYPE>& rhs);
51
52 /*
53 * empty the vector
54 */
55
clear()56 inline void clear() { VectorImpl::clear(); }
57
58 /*!
59 * vector stats
60 */
61
62 //! returns number of items in the vector
size()63 inline size_t size() const { return VectorImpl::size(); }
64 //! returns wether or not the vector is empty
isEmpty()65 inline bool isEmpty() const { return VectorImpl::isEmpty(); }
66 //! returns how many items can be stored without reallocating the backing store
capacity()67 inline size_t capacity() const { return VectorImpl::capacity(); }
68 //! setst the capacity. capacity can never be reduced less than size()
setCapacity(size_t size)69 inline ssize_t setCapacity(size_t size) { return VectorImpl::setCapacity(size); }
70
71 /*!
72 * C-style array access
73 */
74
75 //! read-only C-style access
76 inline const TYPE* array() const;
77
78 //! read-write C-style access. BE VERY CAREFUL when modifying the array
79 //! you ust keep it sorted! You usually don't use this function.
80 TYPE* editArray();
81
82 //! finds the index of an item
83 ssize_t indexOf(const TYPE& item) const;
84
85 //! finds where this item should be inserted
86 size_t orderOf(const TYPE& item) const;
87
88
89 /*!
90 * accessors
91 */
92
93 //! read-only access to an item at a given index
94 inline const TYPE& operator [] (size_t index) const;
95 //! alternate name for operator []
96 inline const TYPE& itemAt(size_t index) const;
97 //! stack-usage of the vector. returns the top of the stack (last element)
98 const TYPE& top() const;
99 //! same as operator [], but allows to access the vector backward (from the end) with a negative index
100 const TYPE& mirrorItemAt(ssize_t index) const;
101
102 /*!
103 * modifing the array
104 */
105
106 //! add an item in the right place (and replace the one that is there)
107 ssize_t add(const TYPE& item);
108
109 //! editItemAt() MUST NOT change the order of this item
editItemAt(size_t index)110 TYPE& editItemAt(size_t index) {
111 return *( static_cast<TYPE *>(VectorImpl::editItemLocation(index)) );
112 }
113
114 //! merges a vector into this one
115 ssize_t merge(const Vector<TYPE>& vector);
116 ssize_t merge(const SortedVector<TYPE>& vector);
117
118 //! removes an item
119 ssize_t remove(const TYPE&);
120
121 //! remove several items
122 inline ssize_t removeItemsAt(size_t index, size_t count = 1);
123 //! remove one item
removeAt(size_t index)124 inline ssize_t removeAt(size_t index) { return removeItemsAt(index); }
125
126 protected:
127 virtual void do_construct(void* storage, size_t num) const;
128 virtual void do_destroy(void* storage, size_t num) const;
129 virtual void do_copy(void* dest, const void* from, size_t num) const;
130 virtual void do_splat(void* dest, const void* item, size_t num) const;
131 virtual void do_move_forward(void* dest, const void* from, size_t num) const;
132 virtual void do_move_backward(void* dest, const void* from, size_t num) const;
133 virtual int do_compare(const void* lhs, const void* rhs) const;
134 };
135
136
137 // ---------------------------------------------------------------------------
138 // No user serviceable parts from here...
139 // ---------------------------------------------------------------------------
140
141 template<class TYPE> inline
SortedVector()142 SortedVector<TYPE>::SortedVector()
143 : SortedVectorImpl(sizeof(TYPE),
144 ((traits<TYPE>::has_trivial_ctor ? HAS_TRIVIAL_CTOR : 0)
145 |(traits<TYPE>::has_trivial_dtor ? HAS_TRIVIAL_DTOR : 0)
146 |(traits<TYPE>::has_trivial_copy ? HAS_TRIVIAL_COPY : 0))
147 )
148 {
149 }
150
151 template<class TYPE> inline
SortedVector(const SortedVector<TYPE> & rhs)152 SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
153 : SortedVectorImpl(rhs) {
154 }
155
156 template<class TYPE> inline
~SortedVector()157 SortedVector<TYPE>::~SortedVector() {
158 finish_vector();
159 }
160
161 template<class TYPE> inline
162 SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) {
163 SortedVectorImpl::operator = (rhs);
164 return *this;
165 }
166
167 template<class TYPE> inline
168 const SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const {
169 SortedVectorImpl::operator = (rhs);
170 return *this;
171 }
172
173 template<class TYPE> inline
array()174 const TYPE* SortedVector<TYPE>::array() const {
175 return static_cast<const TYPE *>(arrayImpl());
176 }
177
178 template<class TYPE> inline
editArray()179 TYPE* SortedVector<TYPE>::editArray() {
180 return static_cast<TYPE *>(editArrayImpl());
181 }
182
183
184 template<class TYPE> inline
185 const TYPE& SortedVector<TYPE>::operator[](size_t index) const {
186 assert( index<size() );
187 return *(array() + index);
188 }
189
190 template<class TYPE> inline
itemAt(size_t index)191 const TYPE& SortedVector<TYPE>::itemAt(size_t index) const {
192 return operator[](index);
193 }
194
195 template<class TYPE> inline
mirrorItemAt(ssize_t index)196 const TYPE& SortedVector<TYPE>::mirrorItemAt(ssize_t index) const {
197 assert( (index>0 ? index : -index)<size() );
198 return *(array() + ((index<0) ? (size()-index) : index));
199 }
200
201 template<class TYPE> inline
top()202 const TYPE& SortedVector<TYPE>::top() const {
203 return *(array() + size() - 1);
204 }
205
206 template<class TYPE> inline
add(const TYPE & item)207 ssize_t SortedVector<TYPE>::add(const TYPE& item) {
208 return SortedVectorImpl::add(&item);
209 }
210
211 template<class TYPE> inline
indexOf(const TYPE & item)212 ssize_t SortedVector<TYPE>::indexOf(const TYPE& item) const {
213 return SortedVectorImpl::indexOf(&item);
214 }
215
216 template<class TYPE> inline
orderOf(const TYPE & item)217 size_t SortedVector<TYPE>::orderOf(const TYPE& item) const {
218 return SortedVectorImpl::orderOf(&item);
219 }
220
221 template<class TYPE> inline
merge(const Vector<TYPE> & vector)222 ssize_t SortedVector<TYPE>::merge(const Vector<TYPE>& vector) {
223 return SortedVectorImpl::merge(reinterpret_cast<const VectorImpl&>(vector));
224 }
225
226 template<class TYPE> inline
merge(const SortedVector<TYPE> & vector)227 ssize_t SortedVector<TYPE>::merge(const SortedVector<TYPE>& vector) {
228 return SortedVectorImpl::merge(reinterpret_cast<const SortedVectorImpl&>(vector));
229 }
230
231 template<class TYPE> inline
remove(const TYPE & item)232 ssize_t SortedVector<TYPE>::remove(const TYPE& item) {
233 return SortedVectorImpl::remove(&item);
234 }
235
236 template<class TYPE> inline
removeItemsAt(size_t index,size_t count)237 ssize_t SortedVector<TYPE>::removeItemsAt(size_t index, size_t count) {
238 return VectorImpl::removeItemsAt(index, count);
239 }
240
241 // ---------------------------------------------------------------------------
242
243 template<class TYPE>
do_construct(void * storage,size_t num)244 void SortedVector<TYPE>::do_construct(void* storage, size_t num) const {
245 construct_type( reinterpret_cast<TYPE*>(storage), num );
246 }
247
248 template<class TYPE>
do_destroy(void * storage,size_t num)249 void SortedVector<TYPE>::do_destroy(void* storage, size_t num) const {
250 destroy_type( reinterpret_cast<TYPE*>(storage), num );
251 }
252
253 template<class TYPE>
do_copy(void * dest,const void * from,size_t num)254 void SortedVector<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
255 copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
256 }
257
258 template<class TYPE>
do_splat(void * dest,const void * item,size_t num)259 void SortedVector<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
260 splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num );
261 }
262
263 template<class TYPE>
do_move_forward(void * dest,const void * from,size_t num)264 void SortedVector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
265 move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
266 }
267
268 template<class TYPE>
do_move_backward(void * dest,const void * from,size_t num)269 void SortedVector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
270 move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
271 }
272
273 template<class TYPE>
do_compare(const void * lhs,const void * rhs)274 int SortedVector<TYPE>::do_compare(const void* lhs, const void* rhs) const {
275 return compare_type( *reinterpret_cast<const TYPE*>(lhs), *reinterpret_cast<const TYPE*>(rhs) );
276 }
277
278 }; // namespace android
279
280
281 // ---------------------------------------------------------------------------
282
283 #endif // ANDROID_SORTED_VECTOR_H
284