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_KEYED_VECTOR_H 18#define ANDROID_KEYED_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/Errors.h> 26#include <utils/SortedVector.h> 27#include <utils/TypeHelpers.h> 28 29// --------------------------------------------------------------------------- 30 31namespace android { 32 33template <typename KEY, typename VALUE> 34class KeyedVector 35{ 36public: 37 typedef KEY key_type; 38 typedef VALUE value_type; 39 40 inline KeyedVector(); 41 42 /* 43 * empty the vector 44 */ 45 46 inline void clear() { mVector.clear(); } 47 48 /*! 49 * vector stats 50 */ 51 52 //! returns number of items in the vector 53 inline size_t size() const { return mVector.size(); } 54 //! returns whether or not the vector is empty 55 inline bool isEmpty() const { return mVector.isEmpty(); } 56 //! returns how many items can be stored without reallocating the backing store 57 inline size_t capacity() const { return mVector.capacity(); } 58 //! sets the capacity. capacity can never be reduced less than size() 59 inline ssize_t setCapacity(size_t size) { return mVector.setCapacity(size); } 60 61 // returns true if the arguments is known to be identical to this vector 62 inline bool isIdenticalTo(const KeyedVector& rhs) const; 63 64 /*! 65 * accessors 66 */ 67 const VALUE& valueFor(const KEY& key) const; 68 const VALUE& valueAt(size_t index) const; 69 const KEY& keyAt(size_t index) const; 70 ssize_t indexOfKey(const KEY& key) const; 71 const VALUE& operator[] (size_t index) const; 72 73 /*! 74 * modifying the array 75 */ 76 77 VALUE& editValueFor(const KEY& key); 78 VALUE& editValueAt(size_t index); 79 80 /*! 81 * add/insert/replace items 82 */ 83 84 ssize_t add(const KEY& key, const VALUE& item); 85 ssize_t replaceValueFor(const KEY& key, const VALUE& item); 86 ssize_t replaceValueAt(size_t index, const VALUE& item); 87 88 /*! 89 * remove items 90 */ 91 92 ssize_t removeItem(const KEY& key); 93 ssize_t removeItemsAt(size_t index, size_t count = 1); 94 95private: 96 SortedVector< key_value_pair_t<KEY, VALUE> > mVector; 97}; 98 99// --------------------------------------------------------------------------- 100 101/** 102 * Variation of KeyedVector that holds a default value to return when 103 * valueFor() is called with a key that doesn't exist. 104 */ 105template <typename KEY, typename VALUE> 106class DefaultKeyedVector : public KeyedVector<KEY, VALUE> 107{ 108public: 109 inline DefaultKeyedVector(const VALUE& defValue = VALUE()); 110 const VALUE& valueFor(const KEY& key) const; 111 112private: 113 VALUE mDefault; 114}; 115 116// --------------------------------------------------------------------------- 117 118template<typename KEY, typename VALUE> inline 119KeyedVector<KEY,VALUE>::KeyedVector() 120{ 121} 122 123template<typename KEY, typename VALUE> inline 124bool KeyedVector<KEY,VALUE>::isIdenticalTo(const KeyedVector<KEY,VALUE>& rhs) const { 125 return mVector.array() == rhs.mVector.array(); 126} 127 128template<typename KEY, typename VALUE> inline 129ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const { 130 return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) ); 131} 132 133template<typename KEY, typename VALUE> inline 134const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const { 135 ssize_t i = this->indexOfKey(key); 136 LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__); 137 return mVector.itemAt(i).value; 138} 139 140template<typename KEY, typename VALUE> inline 141const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const { 142 return mVector.itemAt(index).value; 143} 144 145template<typename KEY, typename VALUE> inline 146const VALUE& KeyedVector<KEY,VALUE>::operator[] (size_t index) const { 147 return valueAt(index); 148} 149 150template<typename KEY, typename VALUE> inline 151const KEY& KeyedVector<KEY,VALUE>::keyAt(size_t index) const { 152 return mVector.itemAt(index).key; 153} 154 155template<typename KEY, typename VALUE> inline 156VALUE& KeyedVector<KEY,VALUE>::editValueFor(const KEY& key) { 157 ssize_t i = this->indexOfKey(key); 158 LOG_ALWAYS_FATAL_IF(i<0, "%s: key not found", __PRETTY_FUNCTION__); 159 return mVector.editItemAt(static_cast<size_t>(i)).value; 160} 161 162template<typename KEY, typename VALUE> inline 163VALUE& KeyedVector<KEY,VALUE>::editValueAt(size_t index) { 164 return mVector.editItemAt(index).value; 165} 166 167template<typename KEY, typename VALUE> inline 168ssize_t KeyedVector<KEY,VALUE>::add(const KEY& key, const VALUE& value) { 169 return mVector.add( key_value_pair_t<KEY,VALUE>(key, value) ); 170} 171 172template<typename KEY, typename VALUE> inline 173ssize_t KeyedVector<KEY,VALUE>::replaceValueFor(const KEY& key, const VALUE& value) { 174 key_value_pair_t<KEY,VALUE> pair(key, value); 175 mVector.remove(pair); 176 return mVector.add(pair); 177} 178 179template<typename KEY, typename VALUE> inline 180ssize_t KeyedVector<KEY,VALUE>::replaceValueAt(size_t index, const VALUE& item) { 181 if (index<size()) { 182 mVector.editItemAt(index).value = item; 183 return static_cast<ssize_t>(index); 184 } 185 return BAD_INDEX; 186} 187 188template<typename KEY, typename VALUE> inline 189ssize_t KeyedVector<KEY,VALUE>::removeItem(const KEY& key) { 190 return mVector.remove(key_value_pair_t<KEY,VALUE>(key)); 191} 192 193template<typename KEY, typename VALUE> inline 194ssize_t KeyedVector<KEY, VALUE>::removeItemsAt(size_t index, size_t count) { 195 return mVector.removeItemsAt(index, count); 196} 197 198// --------------------------------------------------------------------------- 199 200template<typename KEY, typename VALUE> inline 201DefaultKeyedVector<KEY,VALUE>::DefaultKeyedVector(const VALUE& defValue) 202 : mDefault(defValue) 203{ 204} 205 206template<typename KEY, typename VALUE> inline 207const VALUE& DefaultKeyedVector<KEY,VALUE>::valueFor(const KEY& key) const { 208 ssize_t i = this->indexOfKey(key); 209 return i >= 0 ? KeyedVector<KEY,VALUE>::valueAt(i) : mDefault; 210} 211 212}; // namespace android 213 214// --------------------------------------------------------------------------- 215 216#endif // ANDROID_KEYED_VECTOR_H 217