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