OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library dart.pkg.collection.canonicalized_map; | |
6 | |
7 import 'dart:collection'; | 5 import 'dart:collection'; |
8 | 6 |
9 import 'utils.dart'; | 7 import 'utils.dart'; |
10 | 8 |
11 /** | 9 typedef C _Canonicalize<C, K>(K key); |
12 * A map whose keys are converted to canonical values of type `C`. | 10 |
13 * | 11 typedef bool _IsValidKey(Object key); |
14 * This is useful for using case-insensitive String keys, for example. It's more | 12 |
15 * efficient than a [LinkedHashMap] with a custom equality operator because it | 13 /// A map whose keys are converted to canonical values of type `C`. |
16 * only canonicalizes each key once, rather than doing so for each comparison. | 14 /// |
17 * | 15 /// This is useful for using case-insensitive String keys, for example. It's |
18 * By default, `null` is allowed as a key. It can be forbidden via the | 16 /// more efficient than a [LinkedHashMap] with a custom equality operator |
19 * `isValidKey` parameter. | 17 /// because it only canonicalizes each key once, rather than doing so for each |
20 */ | 18 /// comparison. |
| 19 /// |
| 20 /// By default, `null` is allowed as a key. It can be forbidden via the |
| 21 /// `isValidKey` parameter. |
21 class CanonicalizedMap<C, K, V> implements Map<K, V> { | 22 class CanonicalizedMap<C, K, V> implements Map<K, V> { |
22 final Function _canonicalize; | 23 final _Canonicalize<C, K> _canonicalize; |
23 | 24 |
24 final Function _isValidKeyFn; | 25 final _IsValidKey _isValidKeyFn; |
25 | 26 |
26 final _base = new Map<C, Pair<K, V>>(); | 27 final _base = new Map<C, Pair<K, V>>(); |
27 | 28 |
28 /** | 29 /// Creates an empty canonicalized map. |
29 * Creates an empty canonicalized map. | 30 /// |
30 * | 31 /// The [canonicalize] function should return the canonical value for the |
31 * The [canonicalize] function should return the canonical value for the given | 32 /// given key. Keys with the same canonical value are considered equivalent. |
32 * key. Keys with the same canonical value are considered equivalent. | 33 /// |
33 * | 34 /// The [isValidKey] function is called before calling [canonicalize] for |
34 * The [isValidKey] function is called before calling [canonicalize] for | 35 /// methods that take arbitrary objects. It can be used to filter out keys |
35 * methods that take arbitrary objects. It can be used to filter out keys that | 36 /// that can't be canonicalized. |
36 * can't be canonicalized. | |
37 */ | |
38 CanonicalizedMap(C canonicalize(K key), {bool isValidKey(Object key)}) | 37 CanonicalizedMap(C canonicalize(K key), {bool isValidKey(Object key)}) |
39 : _canonicalize = canonicalize, | 38 : _canonicalize = canonicalize, |
40 _isValidKeyFn = isValidKey; | 39 _isValidKeyFn = isValidKey; |
41 | 40 |
42 /** | 41 /// Creates a canonicalized map that is initialized with the key/value pairs |
43 * Creates a canonicalized map that is initialized with the key/value pairs of | 42 /// of [other]. |
44 * [other]. | 43 /// |
45 * | 44 /// The [canonicalize] function should return the canonical value for the |
46 * The [canonicalize] function should return the canonical value for the given | 45 /// given key. Keys with the same canonical value are considered equivalent. |
47 * key. Keys with the same canonical value are considered equivalent. | 46 /// |
48 * | 47 /// The [isValidKey] function is called before calling [canonicalize] for |
49 * The [isValidKey] function is called before calling [canonicalize] for | 48 /// methods that take arbitrary objects. It can be used to filter out keys |
50 * methods that take arbitrary objects. It can be used to filter out keys that | 49 /// that can't be canonicalized. |
51 * can't be canonicalized. | |
52 */ | |
53 CanonicalizedMap.from(Map<K, V> other, C canonicalize(K key), | 50 CanonicalizedMap.from(Map<K, V> other, C canonicalize(K key), |
54 {bool isValidKey(Object key)}) | 51 {bool isValidKey(Object key)}) |
55 : _canonicalize = canonicalize, | 52 : _canonicalize = canonicalize, |
56 _isValidKeyFn = isValidKey { | 53 _isValidKeyFn = isValidKey { |
57 addAll(other); | 54 addAll(other); |
58 } | 55 } |
59 | 56 |
60 V operator [](Object key) { | 57 V operator [](Object key) { |
61 if (!_isValidKey(key)) return null; | 58 if (!_isValidKey(key)) return null; |
62 var pair = _base[_canonicalize(key)]; | 59 var pair = _base[_canonicalize(key as K)]; |
63 return pair == null ? null : pair.last; | 60 return pair == null ? null : pair.last; |
64 } | 61 } |
65 | 62 |
66 void operator []=(K key, V value) { | 63 void operator []=(K key, V value) { |
| 64 if (!_isValidKey(key)) return; |
67 _base[_canonicalize(key)] = new Pair(key, value); | 65 _base[_canonicalize(key)] = new Pair(key, value); |
68 } | 66 } |
69 | 67 |
70 void addAll(Map<K, V> other) { | 68 void addAll(Map<K, V> other) { |
71 other.forEach((key, value) => this[key] = value); | 69 other.forEach((key, value) => this[key] = value); |
72 } | 70 } |
73 | 71 |
74 void clear() { | 72 void clear() { |
75 _base.clear(); | 73 _base.clear(); |
76 } | 74 } |
77 | 75 |
78 bool containsKey(Object key) { | 76 bool containsKey(Object key) { |
79 if (!_isValidKey(key)) return false; | 77 if (!_isValidKey(key)) return false; |
80 return _base.containsKey(_canonicalize(key)); | 78 return _base.containsKey(_canonicalize(key as K)); |
81 } | 79 } |
82 | 80 |
83 bool containsValue(Object value) => | 81 bool containsValue(Object value) => |
84 _base.values.any((pair) => pair.last == value); | 82 _base.values.any((pair) => pair.last == value); |
85 | 83 |
86 void forEach(void f(K key, V value)) { | 84 void forEach(void f(K key, V value)) { |
87 _base.forEach((key, pair) => f(pair.first, pair.last)); | 85 _base.forEach((key, pair) => f(pair.first, pair.last)); |
88 } | 86 } |
89 | 87 |
90 bool get isEmpty => _base.isEmpty; | 88 bool get isEmpty => _base.isEmpty; |
91 | 89 |
92 bool get isNotEmpty => _base.isNotEmpty; | 90 bool get isNotEmpty => _base.isNotEmpty; |
93 | 91 |
94 Iterable<K> get keys => _base.values.map((pair) => pair.first); | 92 Iterable<K> get keys => _base.values.map((pair) => pair.first); |
95 | 93 |
96 int get length => _base.length; | 94 int get length => _base.length; |
97 | 95 |
98 V putIfAbsent(K key, V ifAbsent()) { | 96 V putIfAbsent(K key, V ifAbsent()) { |
99 return _base.putIfAbsent(_canonicalize(key), | 97 return _base |
100 () => new Pair(key, ifAbsent())).last; | 98 .putIfAbsent(_canonicalize(key), () => new Pair(key, ifAbsent())) |
| 99 .last; |
101 } | 100 } |
102 | 101 |
103 V remove(Object key) { | 102 V remove(Object key) { |
104 if (!_isValidKey(key)) return null; | 103 if (!_isValidKey(key)) return null; |
105 var pair = _base.remove(_canonicalize(key)); | 104 var pair = _base.remove(_canonicalize(key as K)); |
106 return pair == null ? null : pair.last; | 105 return pair == null ? null : pair.last; |
107 } | 106 } |
108 | 107 |
109 Iterable<V> get values => _base.values.map((pair) => pair.last); | 108 Iterable<V> get values => _base.values.map((pair) => pair.last); |
110 | 109 |
111 String toString() => Maps.mapToString(this); | 110 String toString() => Maps.mapToString(this); |
112 | 111 |
113 bool _isValidKey(Object key) => (key == null || key is K) && | 112 bool _isValidKey(Object key) => |
| 113 (key == null || key is K) && |
114 (_isValidKeyFn == null || _isValidKeyFn(key)); | 114 (_isValidKeyFn == null || _isValidKeyFn(key)); |
115 } | 115 } |
OLD | NEW |