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