SortedVector.h revision 006ba85e981d66ecf262a0ba0b2a6160b1923f24 
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 "tinyutils/Vector.h"
25#include "tinyutils/VectorImpl.h"
26#include "tinyutils/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                |(traits<TYPE>::has_trivial_assign ? HAS_TRIVIAL_ASSIGN : 0))
146                )
147{
148}
149
150template<class TYPE> inline
151SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
152    : SortedVectorImpl(rhs) {
153}
154
155template<class TYPE> inline
156SortedVector<TYPE>::~SortedVector() {
157    finish_vector();
158}
159
160template<class TYPE> inline
161SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) {
162    SortedVectorImpl::operator = (rhs);
163    return *this;
164}
165
166template<class TYPE> inline
167const SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const {
168    SortedVectorImpl::operator = (rhs);
169    return *this;
170}
171
172template<class TYPE> inline
173const TYPE* SortedVector<TYPE>::array() const {
174    return static_cast<const TYPE *>(arrayImpl());
175}
176
177template<class TYPE> inline
178TYPE* SortedVector<TYPE>::editArray() {
179    return static_cast<TYPE *>(editArrayImpl());
180}
181
182
183template<class TYPE> inline
184const TYPE& SortedVector<TYPE>::operator[](size_t index) const {
185    assert( index<size() );
186    return *(array() + index);
187}
188
189template<class TYPE> inline
190const TYPE& SortedVector<TYPE>::itemAt(size_t index) const {
191    return operator[](index);
192}
193
194template<class TYPE> inline
195const TYPE& SortedVector<TYPE>::mirrorItemAt(ssize_t index) const {
196    assert( (index>0 ? index : -index)<size() );
197    return *(array() + ((index<0) ? (size()-index) : index));
198}
199
200template<class TYPE> inline
201const TYPE& SortedVector<TYPE>::top() const {
202    return *(array() + size() - 1);
203}
204
205template<class TYPE> inline
206ssize_t SortedVector<TYPE>::add(const TYPE& item) {
207    return SortedVectorImpl::add(&item);
208}
209
210template<class TYPE> inline
211ssize_t SortedVector<TYPE>::indexOf(const TYPE& item) const {
212    return SortedVectorImpl::indexOf(&item);
213}
214
215template<class TYPE> inline
216size_t SortedVector<TYPE>::orderOf(const TYPE& item) const {
217    return SortedVectorImpl::orderOf(&item);
218}
219
220template<class TYPE> inline
221ssize_t SortedVector<TYPE>::merge(const Vector<TYPE>& vector) {
222    return SortedVectorImpl::merge(reinterpret_cast<const VectorImpl&>(vector));
223}
224
225template<class TYPE> inline
226ssize_t SortedVector<TYPE>::merge(const SortedVector<TYPE>& vector) {
227    return SortedVectorImpl::merge(reinterpret_cast<const SortedVectorImpl&>(vector));
228}
229
230template<class TYPE> inline
231ssize_t SortedVector<TYPE>::remove(const TYPE& item) {
232    return SortedVectorImpl::remove(&item);
233}
234
235template<class TYPE> inline
236ssize_t SortedVector<TYPE>::removeItemsAt(size_t index, size_t count) {
237    return VectorImpl::removeItemsAt(index, count);
238}
239
240// ---------------------------------------------------------------------------
241
242template<class TYPE>
243void SortedVector<TYPE>::do_construct(void* storage, size_t num) const {
244    construct_type( reinterpret_cast<TYPE*>(storage), num );
245}
246
247template<class TYPE>
248void SortedVector<TYPE>::do_destroy(void* storage, size_t num) const {
249    destroy_type( reinterpret_cast<TYPE*>(storage), num );
250}
251
252template<class TYPE>
253void SortedVector<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
254    copy_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
255}
256
257template<class TYPE>
258void SortedVector<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
259    splat_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(item), num );
260}
261
262template<class TYPE>
263void SortedVector<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
264    move_forward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
265}
266
267template<class TYPE>
268void SortedVector<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
269    move_backward_type( reinterpret_cast<TYPE*>(dest), reinterpret_cast<const TYPE*>(from), num );
270}
271
272template<class TYPE>
273int SortedVector<TYPE>::do_compare(const void* lhs, const void* rhs) const {
274    return compare_type( *reinterpret_cast<const TYPE*>(lhs), *reinterpret_cast<const TYPE*>(rhs) );
275}
276
277}; // namespace android
278
279
280// ---------------------------------------------------------------------------
281
282#endif // ANDROID_SORTED_VECTOR_H
283