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