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