1 /*
2 * Copyright 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_PIXELFLINGER_SORTED_VECTOR_H
18 #define ANDROID_PIXELFLINGER_SORTED_VECTOR_H
19
20 #include <assert.h>
21 #include <stdint.h>
22 #include <sys/types.h>
23
24 #include "Vector.h"
25 #include "VectorImpl.h"
26 #include "TypeHelpers.h"
27
28 // ---------------------------------------------------------------------------
29
30 namespace android {
31 namespace tinyutils {
32
33 template <class TYPE>
34 class SortedVector : private SortedVectorImpl
35 {
36 public:
37 typedef TYPE value_type;
38
39 /*!
40 * Constructors and destructors
41 */
42
43 SortedVector();
44 SortedVector(const SortedVector<TYPE>& rhs);
45 virtual ~SortedVector();
46
47 /*! copy operator */
48 const SortedVector<TYPE>& operator = (const SortedVector<TYPE>& rhs) const;
49 SortedVector<TYPE>& operator = (const SortedVector<TYPE>& rhs);
50
51 /*
52 * empty the vector
53 */
54
clear()55 inline void clear() { VectorImpl::clear(); }
56
57 /*!
58 * vector stats
59 */
60
61 //! returns number of items in the vector
size()62 inline size_t size() const { return VectorImpl::size(); }
63 //! returns wether or not the vector is empty
isEmpty()64 inline bool isEmpty() const { return VectorImpl::isEmpty(); }
65 //! returns how many items can be stored without reallocating the backing store
capacity()66 inline size_t capacity() const { return VectorImpl::capacity(); }
67 //! setst the capacity. capacity can never be reduced less than size()
setCapacity(size_t size)68 inline ssize_t setCapacity(size_t size) { return VectorImpl::setCapacity(size); }
69
70 /*!
71 * C-style array access
72 */
73
74 //! read-only C-style access
75 inline const TYPE* array() const;
76
77 //! read-write C-style access. BE VERY CAREFUL when modifying the array
78 //! you ust keep it sorted! You usually don't use this function.
79 TYPE* editArray();
80
81 //! finds the index of an item
82 ssize_t indexOf(const TYPE& item) const;
83
84 //! finds where this item should be inserted
85 size_t orderOf(const TYPE& item) const;
86
87
88 /*!
89 * accessors
90 */
91
92 //! read-only access to an item at a given index
93 inline const TYPE& operator [] (size_t index) const;
94 //! alternate name for operator []
95 inline const TYPE& itemAt(size_t index) const;
96 //! stack-usage of the vector. returns the top of the stack (last element)
97 const TYPE& top() const;
98 //! same as operator [], but allows to access the vector backward (from the end) with a negative index
99 const TYPE& mirrorItemAt(ssize_t index) const;
100
101 /*!
102 * modifing the array
103 */
104
105 //! add an item in the right place (and replace the one that is there)
106 ssize_t add(const TYPE& item);
107
108 //! editItemAt() MUST NOT change the order of this item
editItemAt(size_t index)109 TYPE& editItemAt(size_t index) {
110 return *( static_cast<TYPE *>(VectorImpl::editItemLocation(index)) );
111 }
112
113 //! merges a vector into this one
114 ssize_t merge(const Vector<TYPE>& vector);
115 ssize_t merge(const SortedVector<TYPE>& vector);
116
117 //! removes an item
118 ssize_t remove(const TYPE&);
119
120 //! remove several items
121 inline ssize_t removeItemsAt(size_t index, size_t count = 1);
122 //! remove one item
removeAt(size_t index)123 inline ssize_t removeAt(size_t index) { return removeItemsAt(index); }
124
125 protected:
126 virtual void do_construct(void* storage, size_t num) const;
127 virtual void do_destroy(void* storage, size_t num) const;
128 virtual void do_copy(void* dest, const void* from, size_t num) const;
129 virtual void do_splat(void* dest, const void* item, size_t num) const;
130 virtual void do_move_forward(void* dest, const void* from, size_t num) const;
131 virtual void do_move_backward(void* dest, const void* from, size_t num) const;
132 virtual int do_compare(const void* lhs, const void* rhs) const;
133 };
134
135
136 // ---------------------------------------------------------------------------
137 // No user serviceable parts from here...
138 // ---------------------------------------------------------------------------
139
140 template<class TYPE> inline
SortedVector()141 SortedVector<TYPE>::SortedVector()
142 : SortedVectorImpl(sizeof(TYPE),
143 ((traits<TYPE>::has_trivial_ctor ? HAS_TRIVIAL_CTOR : 0)
144 |(traits<TYPE>::has_trivial_dtor ? HAS_TRIVIAL_DTOR : 0)
145 |(traits<TYPE>::has_trivial_copy ? HAS_TRIVIAL_COPY : 0)
146 |(traits<TYPE>::has_trivial_assign ? HAS_TRIVIAL_ASSIGN : 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 tinyutils
279 } // namespace android
280
281
282 // ---------------------------------------------------------------------------
283
284 #endif // ANDROID_PIXELFLINGER_SORTED_VECTOR_H
285