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