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 stagefright {
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 
55     inline  void            clear()             { VectorImpl::clear(); }
56 
57     /*!
58      * vector stats
59      */
60 
61     //! returns number of items in the vector
62     inline  size_t          size() const                { return VectorImpl::size(); }
63     //! returns wether or not the vector is empty
64     inline  bool            isEmpty() const             { return VectorImpl::isEmpty(); }
65     //! returns how many items can be stored without reallocating the backing store
66     inline  size_t          capacity() const            { return VectorImpl::capacity(); }
67     //! setst the capacity. capacity can never be reduced less than 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
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
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
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
152 SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
153     : SortedVectorImpl(rhs) {
154 }
155 
156 template<class TYPE> inline
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
174 const TYPE* SortedVector<TYPE>::array() const {
175     return static_cast<const TYPE *>(arrayImpl());
176 }
177 
178 template<class TYPE> inline
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
191 const TYPE& SortedVector<TYPE>::itemAt(size_t index) const {
192     return operator[](index);
193 }
194 
195 template<class TYPE> inline
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
202 const TYPE& SortedVector<TYPE>::top() const {
203     return *(array() + size() - 1);
204 }
205 
206 template<class TYPE> inline
207 ssize_t SortedVector<TYPE>::add(const TYPE& item) {
208     return SortedVectorImpl::add(&item);
209 }
210 
211 template<class TYPE> inline
212 ssize_t SortedVector<TYPE>::indexOf(const TYPE& item) const {
213     return SortedVectorImpl::indexOf(&item);
214 }
215 
216 template<class TYPE> inline
217 size_t SortedVector<TYPE>::orderOf(const TYPE& item) const {
218     return SortedVectorImpl::orderOf(&item);
219 }
220 
221 template<class TYPE> inline
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
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
232 ssize_t SortedVector<TYPE>::remove(const TYPE& item) {
233     return SortedVectorImpl::remove(&item);
234 }
235 
236 template<class TYPE> inline
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>
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>
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>
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>
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>
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>
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>
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 stagefright
280 
281 
282 // ---------------------------------------------------------------------------
283 
284 #endif // ANDROID_PIXELFLINGER_SORTED_VECTOR_H
285