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
30namespace android {
31
32template <typename KEY, typename VALUE>
33class KeyedVector
34{
35public:
36    typedef KEY    key_type;
37    typedef VALUE  value_type;
38
39    inline                  KeyedVector();
40
41    /*
42     * empty the vector
43     */
44
45    inline  void            clear()                     { mVector.clear(); }
46
47    /*!
48     * vector stats
49     */
50
51    //! returns number of items in the vector
52    inline  size_t          size() const                { return mVector.size(); }
53    //! returns wether or not the vector is empty
54    inline  bool            isEmpty() const             { return mVector.isEmpty(); }
55    //! returns how many items can be stored without reallocating the backing store
56    inline  size_t          capacity() const            { return mVector.capacity(); }
57    //! setst the capacity. capacity can never be reduced less than 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     * modifying 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
90private:
91            SortedVector< key_value_pair_t<KEY, VALUE> >    mVector;
92};
93
94// KeyedVector<KEY, VALUE> can be trivially moved using memcpy() because its
95// underlying SortedVector can be trivially moved.
96template<typename KEY, typename VALUE> struct trait_trivial_move<KeyedVector<KEY, VALUE> > {
97    enum { value = trait_trivial_move<SortedVector< key_value_pair_t<KEY, VALUE> > >::value };
98};
99
100
101// ---------------------------------------------------------------------------
102
103/**
104 * Variation of KeyedVector that holds a default value to return when
105 * valueFor() is called with a key that doesn't exist.
106 */
107template <typename KEY, typename VALUE>
108class DefaultKeyedVector : public KeyedVector<KEY, VALUE>
109{
110public:
111    inline                  DefaultKeyedVector(const VALUE& defValue = VALUE());
112            const VALUE&    valueFor(const KEY& key) const;
113
114private:
115            VALUE                                           mDefault;
116};
117
118// ---------------------------------------------------------------------------
119
120template<typename KEY, typename VALUE> inline
121KeyedVector<KEY,VALUE>::KeyedVector()
122{
123}
124
125template<typename KEY, typename VALUE> inline
126ssize_t KeyedVector<KEY,VALUE>::indexOfKey(const KEY& key) const {
127    return mVector.indexOf( key_value_pair_t<KEY,VALUE>(key) );
128}
129
130template<typename KEY, typename VALUE> inline
131const VALUE& KeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
132    ssize_t i = this->indexOfKey(key);
133    assert(i>=0);
134    return mVector.itemAt(i).value;
135}
136
137template<typename KEY, typename VALUE> inline
138const VALUE& KeyedVector<KEY,VALUE>::valueAt(size_t index) const {
139    return mVector.itemAt(index).value;
140}
141
142template<typename KEY, typename VALUE> inline
143const KEY& KeyedVector<KEY,VALUE>::keyAt(size_t index) const {
144    return mVector.itemAt(index).key;
145}
146
147template<typename KEY, typename VALUE> inline
148VALUE& KeyedVector<KEY,VALUE>::editValueFor(const KEY& key) {
149    ssize_t i = this->indexOfKey(key);
150    assert(i>=0);
151    return mVector.editItemAt(i).value;
152}
153
154template<typename KEY, typename VALUE> inline
155VALUE& KeyedVector<KEY,VALUE>::editValueAt(size_t index) {
156    return mVector.editItemAt(index).value;
157}
158
159template<typename KEY, typename VALUE> inline
160ssize_t KeyedVector<KEY,VALUE>::add(const KEY& key, const VALUE& value) {
161    return mVector.add( key_value_pair_t<KEY,VALUE>(key, value) );
162}
163
164template<typename KEY, typename VALUE> inline
165ssize_t KeyedVector<KEY,VALUE>::replaceValueFor(const KEY& key, const VALUE& value) {
166    key_value_pair_t<KEY,VALUE> pair(key, value);
167    mVector.remove(pair);
168    return mVector.add(pair);
169}
170
171template<typename KEY, typename VALUE> inline
172ssize_t KeyedVector<KEY,VALUE>::replaceValueAt(size_t index, const VALUE& item) {
173    if (index<size()) {
174        mVector.editItemAt(index).value = item;
175        return index;
176    }
177    return BAD_INDEX;
178}
179
180template<typename KEY, typename VALUE> inline
181ssize_t KeyedVector<KEY,VALUE>::removeItem(const KEY& key) {
182    return mVector.remove(key_value_pair_t<KEY,VALUE>(key));
183}
184
185template<typename KEY, typename VALUE> inline
186ssize_t KeyedVector<KEY, VALUE>::removeItemsAt(size_t index, size_t count) {
187    return mVector.removeItemsAt(index, count);
188}
189
190// ---------------------------------------------------------------------------
191
192template<typename KEY, typename VALUE> inline
193DefaultKeyedVector<KEY,VALUE>::DefaultKeyedVector(const VALUE& defValue)
194    : mDefault(defValue)
195{
196}
197
198template<typename KEY, typename VALUE> inline
199const VALUE& DefaultKeyedVector<KEY,VALUE>::valueFor(const KEY& key) const {
200    ssize_t i = this->indexOfKey(key);
201    return i >= 0 ? KeyedVector<KEY,VALUE>::valueAt(i) : mDefault;
202}
203
204}; // namespace android
205
206// ---------------------------------------------------------------------------
207
208#endif // ANDROID_KEYED_VECTOR_H
209