1/*
2 * Copyright (C) 2015 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 AAPT_UTIL_IMMUTABLEMAP_H
18#define AAPT_UTIL_IMMUTABLEMAP_H
19
20#include "util/TypeTraits.h"
21
22#include <utility>
23#include <vector>
24
25namespace aapt {
26
27template <typename TKey, typename TValue>
28class ImmutableMap {
29    static_assert(is_comparable<TKey, TKey>::value, "key is not comparable");
30
31private:
32    std::vector<std::pair<TKey, TValue>> mData;
33
34    explicit ImmutableMap(std::vector<std::pair<TKey, TValue>> data) : mData(std::move(data)) {
35    }
36
37public:
38    using const_iterator = typename decltype(mData)::const_iterator;
39
40    ImmutableMap(ImmutableMap&&) = default;
41    ImmutableMap& operator=(ImmutableMap&&) = default;
42
43    ImmutableMap(const ImmutableMap&) = delete;
44    ImmutableMap& operator=(const ImmutableMap&) = delete;
45
46    static ImmutableMap<TKey, TValue> createPreSorted(
47            std::initializer_list<std::pair<TKey, TValue>> list) {
48        return ImmutableMap(std::vector<std::pair<TKey, TValue>>(list.begin(), list.end()));
49    }
50
51    static ImmutableMap<TKey, TValue> createAndSort(
52            std::initializer_list<std::pair<TKey, TValue>> list) {
53        std::vector<std::pair<TKey, TValue>> data(list.begin(), list.end());
54        std::sort(data.begin(), data.end());
55        return ImmutableMap(std::move(data));
56    }
57
58    template <typename TKey2,
59              typename = typename std::enable_if<is_comparable<TKey, TKey2>::value>::type>
60    const_iterator find(const TKey2& key) const {
61        auto cmp = [](const std::pair<TKey, TValue>& candidate, const TKey2& target) -> bool {
62            return candidate.first < target;
63        };
64
65        const_iterator endIter = end();
66        auto iter = std::lower_bound(mData.begin(), endIter, key, cmp);
67        if (iter == endIter || iter->first == key) {
68            return iter;
69        }
70        return endIter;
71    }
72
73    const_iterator begin() const {
74        return mData.begin();
75    }
76
77    const_iterator end() const {
78        return mData.end();
79    }
80};
81
82} // namespace aapt
83
84#endif /* AAPT_UTIL_IMMUTABLEMAP_H */
85