SortedVector.h revision a040114bcba4b202a289a6e8fafd808f779f865c
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> 255void 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> 265void 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> 270void 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> 275void 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> 280void 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