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 <cutils/log.h>
25
26#include <utils/Vector.h>
27#include <utils/VectorImpl.h>
28#include <utils/TypeHelpers.h>
29
30// ---------------------------------------------------------------------------
31
32namespace android {
33
34template <class TYPE>
35class SortedVector : private SortedVectorImpl
36{
37    friend class Vector<TYPE>;
38
39public:
40            typedef TYPE    value_type;
41
42    /*!
43     * Constructors and destructors
44     */
45
46                            SortedVector();
47                            SortedVector(const SortedVector<TYPE>& rhs);
48    virtual                 ~SortedVector();
49
50    /*! copy operator */
51    const SortedVector<TYPE>&   operator = (const SortedVector<TYPE>& rhs) const;
52    SortedVector<TYPE>&         operator = (const SortedVector<TYPE>& rhs);
53
54    /*
55     * empty the vector
56     */
57
58    inline  void            clear()             { VectorImpl::clear(); }
59
60    /*!
61     * vector stats
62     */
63
64    //! returns number of items in the vector
65    inline  size_t          size() const                { return VectorImpl::size(); }
66    //! returns whether or not the vector is empty
67    inline  bool            isEmpty() const             { return VectorImpl::isEmpty(); }
68    //! returns how many items can be stored without reallocating the backing store
69    inline  size_t          capacity() const            { return VectorImpl::capacity(); }
70    //! sets the capacity. capacity can never be reduced less than size()
71    inline  ssize_t         setCapacity(size_t size)    { return VectorImpl::setCapacity(size); }
72
73    /*!
74     * C-style array access
75     */
76
77    //! read-only C-style access
78    inline  const TYPE*     array() const;
79
80    //! read-write C-style access. BE VERY CAREFUL when modifying the array
81    //! you must keep it sorted! You usually don't use this function.
82            TYPE*           editArray();
83
84            //! finds the index of an item
85            ssize_t         indexOf(const TYPE& item) const;
86
87            //! finds where this item should be inserted
88            size_t          orderOf(const TYPE& item) const;
89
90
91    /*!
92     * accessors
93     */
94
95    //! read-only access to an item at a given index
96    inline  const TYPE&     operator [] (size_t index) const;
97    //! alternate name for operator []
98    inline  const TYPE&     itemAt(size_t index) const;
99    //! stack-usage of the vector. returns the top of the stack (last element)
100            const TYPE&     top() const;
101
102    /*!
103     * modifying 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
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
124    inline  ssize_t         removeAt(size_t index)  { return removeItemsAt(index); }
125
126protected:
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// SortedVector<T> can be trivially moved using memcpy() because moving does not
137// require any change to the underlying SharedBuffer contents or reference count.
138template<typename T> struct trait_trivial_move<SortedVector<T> > { enum { value = true }; };
139
140// ---------------------------------------------------------------------------
141// No user serviceable parts from here...
142// ---------------------------------------------------------------------------
143
144template<class TYPE> inline
145SortedVector<TYPE>::SortedVector()
146    : SortedVectorImpl(sizeof(TYPE),
147                ((traits<TYPE>::has_trivial_ctor   ? HAS_TRIVIAL_CTOR   : 0)
148                |(traits<TYPE>::has_trivial_dtor   ? HAS_TRIVIAL_DTOR   : 0)
149                |(traits<TYPE>::has_trivial_copy   ? HAS_TRIVIAL_COPY   : 0))
150                )
151{
152}
153
154template<class TYPE> inline
155SortedVector<TYPE>::SortedVector(const SortedVector<TYPE>& rhs)
156    : SortedVectorImpl(rhs) {
157}
158
159template<class TYPE> inline
160SortedVector<TYPE>::~SortedVector() {
161    finish_vector();
162}
163
164template<class TYPE> inline
165SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) {
166    SortedVectorImpl::operator = (rhs);
167    return *this;
168}
169
170template<class TYPE> inline
171const SortedVector<TYPE>& SortedVector<TYPE>::operator = (const SortedVector<TYPE>& rhs) const {
172    SortedVectorImpl::operator = (rhs);
173    return *this;
174}
175
176template<class TYPE> inline
177const TYPE* SortedVector<TYPE>::array() const {
178    return static_cast<const TYPE *>(arrayImpl());
179}
180
181template<class TYPE> inline
182TYPE* SortedVector<TYPE>::editArray() {
183    return static_cast<TYPE *>(editArrayImpl());
184}
185
186
187template<class TYPE> inline
188const TYPE& SortedVector<TYPE>::operator[](size_t index) const {
189    LOG_FATAL_IF(index>=size(),
190            "%s: index=%u out of range (%u)", __PRETTY_FUNCTION__,
191            int(index), int(size()));
192    return *(array() + index);
193}
194
195template<class TYPE> inline
196const TYPE& SortedVector<TYPE>::itemAt(size_t index) const {
197    return operator[](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