1
2
3
4
5
6 using System;
7 using System.Concepts;
8 using System.IO;
9
10 namespace System.Collections
11 {
12 public class Map<Key, Value, KeyCompare = Less<Key>>
13 where Key is Semiregular and Value is Semiregular and KeyCompare is Relation and KeyCompare.Domain is Key
14 {
15 public typedef Key KeyType;
16 public typedef Value MappedType;
17 public typedef KeyCompare Compare;
18 public typedef Pair<KeyType, MappedType> ValueType;
19 public typedef TreeType.ConstIterator ConstIterator;
20 public typedef TreeType.Iterator Iterator;
21 private typedef Map<KeyType, MappedType, KeyCompare> Self;
22 private typedef RedBlackTree<KeyType, ValueType, SelectFirst<KeyType, MappedType>, KeyCompare> TreeType;
23
24 public inline nothrow Iterator Begin()
25 {
26 return tree.Begin();
27 }
28 public inline nothrow ConstIterator Begin() const
29 {
30 return tree.CBegin();
31 }
32 public inline nothrow ConstIterator CBegin() const
33 {
34 return tree.CBegin();
35 }
36 public inline nothrow Iterator End()
37 {
38 return tree.End();
39 }
40 public inline nothrow ConstIterator End() const
41 {
42 return tree.CEnd();
43 }
44 public inline nothrow ConstIterator CEnd() const
45 {
46 return tree.CEnd();
47 }
48 public inline nothrow long Count() const
49 {
50 return tree.Count();
51 }
52 public inline nothrow bool IsEmpty() const
53 {
54 return tree.IsEmpty();
55 }
56 public inline nothrow void Clear()
57 {
58 tree.Clear();
59 }
60 public inline nothrow Iterator Find(const KeyType& key)
61 {
62 return tree.Find(key);
63 }
64 public inline nothrow ConstIterator Find(const KeyType& key) const
65 {
66 return tree.CFind(key);
67 }
68 public inline nothrow ConstIterator CFind(const KeyType& key) const
69 {
70 return tree.CFind(key);
71 }
72 public inline nothrow Iterator LowerBound(const KeyType& key)
73 {
74 return tree.LowerBound(key);
75 }
76 public inline nothrow ConstIterator LowerBound(const KeyType& key) const
77 {
78 return tree.CLowerBound(key);
79 }
80 public inline nothrow ConstIterator CLowerBound(const KeyType& key) const
81 {
82 return tree.CLowerBound(key);
83 }
84 public inline MappedType& operator[](const KeyType& key)
85 {
86 ValueType valueType(key, MappedType());
87 Pair<Iterator, bool> ib = Insert(valueType);
88 Iterator i = ib.first;
89 return i->second;
90 }
91 public inline Pair<Iterator, bool> Insert(const ValueType& value)
92 where ValueType is Copyable
93 {
94 return tree.Insert(value);
95 }
96 public inline nothrow bool Remove(const KeyType& key)
97 {
98 return tree.Remove(key);
99 }
100 public inline nothrow void Remove(Iterator pos)
101 {
102 tree.Remove(pos);
103 }
104 private TreeType tree;
105 }
106
107 public inline nothrow bool operator==<Key, Value, KeyCompare>(const Map<Key, Value, KeyCompare>& left, const Map<Key, Value, KeyCompare>& right)
108 where Key is Regular and Value is Regular and KeyCompare is Relation and KeyCompare.Domain is Key
109 {
110 return left.Count() == right.Count() && Equal(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd(), EqualTo<Pair<Key, Value>>());
111 }
112
113 public inline nothrow bool operator<<Key, Value, KeyCompare>(const Map<Key, Value, KeyCompare>& left, const Map<Key, Value, KeyCompare>& right)
114 where Key is TotallyOrdered and Value is TotallyOrdered and KeyCompare is Relation and KeyCompare.Domain is Key
115 {
116 return LexicographicalCompare(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd(), Less<Pair<Key, Value>>());
117 }
118
119 [system_default="true"]
120 public TextWriter& operator<<<Key, Value, KeyCompare>(TextWriter& writer, const Map<Key, Value, KeyCompare>& map)
121 {
122 writer << "{";
123 bool first = true;
124 for (const Pair<Key, Value>& element : map)
125 {
126 if (first)
127 {
128 first = false;
129 }
130 else
131 {
132 writer << ", ";
133 }
134 writer << element;
135 }
136 writer << "}";
137 return writer;
138 }
139 }