ImmutableMap.h revision 7ff3ee19f4b831a526baf4b928d1ac172d070d82
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 "util/TypeTraits.h" 217ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 227ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#include <utility> 237ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#include <vector> 247ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 257ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskinamespace aapt { 267ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 277ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskitemplate <typename TKey, typename TValue> 287ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskiclass ImmutableMap { 297ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski static_assert(is_comparable<TKey, TKey>::value, "key is not comparable"); 307ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 317ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskiprivate: 327ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski std::vector<std::pair<TKey, TValue>> mData; 337ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 347ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski explicit ImmutableMap(std::vector<std::pair<TKey, TValue>> data) : mData(std::move(data)) { 357ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 367ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 377ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinskipublic: 387ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski using const_iterator = typename decltype(mData)::const_iterator; 397ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 407ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski ImmutableMap(ImmutableMap&&) = default; 417ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski ImmutableMap& operator=(ImmutableMap&&) = default; 427ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 437ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski ImmutableMap(const ImmutableMap&) = delete; 447ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski ImmutableMap& operator=(const ImmutableMap&) = delete; 457ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 467ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski static ImmutableMap<TKey, TValue> createPreSorted( 477ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski std::initializer_list<std::pair<TKey, TValue>> list) { 487ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return ImmutableMap(std::vector<std::pair<TKey, TValue>>(list.begin(), list.end())); 497ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 507ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 517ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski static ImmutableMap<TKey, TValue> createAndSort( 527ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski std::initializer_list<std::pair<TKey, TValue>> list) { 537ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski std::vector<std::pair<TKey, TValue>> data(list.begin(), list.end()); 547ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski std::sort(data.begin(), data.end()); 557ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return ImmutableMap(std::move(data)); 567ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 577ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 587ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski template <typename TKey2, 597ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski typename = typename std::enable_if<is_comparable<TKey, TKey2>::value>::type> 607ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski const_iterator find(const TKey2& key) const { 617ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski auto cmp = [](const std::pair<TKey, TValue>& candidate, const TKey2& target) -> bool { 627ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return candidate.first < target; 637ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski }; 647ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 657ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski const_iterator endIter = end(); 667ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski auto iter = std::lower_bound(mData.begin(), endIter, key, cmp); 677ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski if (iter == endIter || iter->first == key) { 687ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return iter; 697ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 707ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return endIter; 717ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 727ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 737ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski const_iterator begin() const { 747ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return mData.begin(); 757ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 767ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 777ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski const_iterator end() const { 787ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski return mData.end(); 797ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski } 807ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski}; 817ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 827ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski} // namespace aapt 837ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski 847ff3ee19f4b831a526baf4b928d1ac172d070d82Adam Lesinski#endif /* AAPT_UTIL_IMMUTABLEMAP_H */ 85