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