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