17ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski/* 27ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * Copyright (C) 2015 The Android Open Source Project 37ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * 47ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 57ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * you may not use this file except in compliance with the License. 67ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * You may obtain a copy of the License at 77ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * 87ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 97ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * 107ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * Unless required by applicable law or agreed to in writing, software 117ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 127ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * See the License for the specific language governing permissions and 147ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski * limitations under the License. 157ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski */ 167ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 177ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#ifndef AAPT_UTIL_IMMUTABLEMAP_H 187ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#define AAPT_UTIL_IMMUTABLEMAP_H 197ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 207ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#include <utility> 217ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#include <vector> 227ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 23ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski#include "util/TypeTraits.h" 24ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski 257ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskinamespace aapt { 267ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 277ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskitemplate <typename TKey, typename TValue> 287ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskiclass ImmutableMap { 29cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski static_assert(is_comparable<TKey, TKey>::value, "key is not comparable"); 30cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 31cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski public: 32ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski using const_iterator = 33ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski typename std::vector<std::pair<TKey, TValue>>::const_iterator; 34cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 35cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski ImmutableMap(ImmutableMap&&) = default; 36cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski ImmutableMap& operator=(ImmutableMap&&) = default; 37cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 38ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski static ImmutableMap<TKey, TValue> CreatePreSorted( 39cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::initializer_list<std::pair<TKey, TValue>> list) { 40cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return ImmutableMap( 41cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::vector<std::pair<TKey, TValue>>(list.begin(), list.end())); 42cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 43cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 44ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski static ImmutableMap<TKey, TValue> CreateAndSort( 45cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::initializer_list<std::pair<TKey, TValue>> list) { 46cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::vector<std::pair<TKey, TValue>> data(list.begin(), list.end()); 47cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski std::sort(data.begin(), data.end()); 48cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return ImmutableMap(std::move(data)); 49cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 50cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 51cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski template <typename TKey2, typename = typename std::enable_if< 52cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski is_comparable<TKey, TKey2>::value>::type> 53cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski const_iterator find(const TKey2& key) const { 54cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski auto cmp = [](const std::pair<TKey, TValue>& candidate, 55cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski const TKey2& target) -> bool { 56cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return candidate.first < target; 57cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski }; 58cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski 59ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski const_iterator end_iter = end(); 60ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski auto iter = std::lower_bound(data_.begin(), end_iter, key, cmp); 61ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski if (iter == end_iter || iter->first == key) { 62cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski return iter; 637ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 64ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski return end_iter; 65cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski } 667ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 67ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski const_iterator begin() const { return data_.begin(); } 68ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski 69ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski const_iterator end() const { return data_.end(); } 70ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski 71ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski private: 72ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski DISALLOW_COPY_AND_ASSIGN(ImmutableMap); 73ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski 74ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski explicit ImmutableMap(std::vector<std::pair<TKey, TValue>> data) 75ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski : data_(std::move(data)) {} 767ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 77ce5e56e243d262a9b65459c3bd0bb9eaadd40628Adam Lesinski std::vector<std::pair<TKey, TValue>> data_; 787ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski}; 797ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 80cacb28f2d60858106e2819cc7d95a65e8bda890bAdam Lesinski} // namespace aapt 817ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 827ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#endif /* AAPT_UTIL_IMMUTABLEMAP_H */ 83