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