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 Iterator Begin()
25 {
26 return tree.Begin();
27 }
28 public inline ConstIterator Begin() const
29 {
30 return tree.CBegin();
31 }
32 public inline ConstIterator CBegin() const
33 {
34 return tree.CBegin();
35 }
36 public inline Iterator End()
37 {
38 return tree.End();
39 }
40 public inline ConstIterator End() const
41 {
42 return tree.CEnd();
43 }
44 public inline ConstIterator CEnd() const
45 {
46 return tree.CEnd();
47 }
48 public inline long Count() const
49 {
50 return tree.Count();
51 }
52 public inline bool IsEmpty() const
53 {
54 return tree.IsEmpty();
55 }
56 public inline void Clear()
57 {
58 tree.Clear();
59 }
60 public inline Iterator Find(const KeyType& key)
61 {
62 return tree.Find(key);
63 }
64 public inline ConstIterator Find(const KeyType& key) const
65 {
66 return tree.CFind(key);
67 }
68 public inline ConstIterator CFind(const KeyType& key) const
69 {
70 return tree.CFind(key);
71 }
72 public inline Iterator LowerBound(const KeyType& key)
73 {
74 return tree.LowerBound(key);
75 }
76 public inline ConstIterator LowerBound(const KeyType& key) const
77 {
78 return tree.CLowerBound(key);
79 }
80 public inline ConstIterator CLowerBound(const KeyType& key) const
81 {
82 return tree.CLowerBound(key);
83 }
84 public MappedType& operator[](const KeyType& key)
85 {
86 KeyType keyType(key);
87 ValueType valueType(Rvalue(keyType), Rvalue(MappedType()));
88 Pair<Iterator, bool> ib = Insert(Rvalue(valueType));
89 Iterator i = ib.first;
90 return i->second;
91 }
92 public MappedType& operator[](KeyType&& key)
93 {
94 ValueType valueType(Rvalue(key), Rvalue(MappedType()));
95 Pair<Iterator, bool> ib = Insert(Rvalue(valueType));
96 Iterator i = ib.first;
97 return i->second;
98 }
99 public inline Pair<Iterator, bool> Insert(const ValueType& value)
100 where ValueType is Copyable and MappedType is Copyable
101 {
102 return tree.Insert(value);
103 }
104 public inline Pair<Iterator, bool> Insert(ValueType&& value)
105 where ValueType is Movable and MappedType is Movable
106 {
107 return tree.Insert(Rvalue(value));
108 }
109 public inline bool Remove(const KeyType& key)
110 {
111 return tree.Remove(key);
112 }
113 public inline void Remove(Iterator pos)
114 {
115 tree.Remove(pos);
116 }
117 private TreeType tree;
118 }
119
120 public bool operator==<Key, Value, KeyCompare>(const Map<Key, Value, KeyCompare>& left, const Map<Key, Value, KeyCompare>& right)
121 where Key is Regular and Value is Regular and KeyCompare is Relation and KeyCompare.Domain is Key
122 {
123 return left.Count() == right.Count() && Equal(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd(), EqualTo<Pair<Key, Value>>());
124 }
125
126 public bool operator<<Key, Value, KeyCompare>(const Map<Key, Value, KeyCompare>& left, const Map<Key, Value, KeyCompare>& right)
127 where Key is TotallyOrdered and Value is TotallyOrdered and KeyCompare is Relation and KeyCompare.Domain is Key
128 {
129 return LexicographicalCompare(left.CBegin(), left.CEnd(), right.CBegin(), right.CEnd(), Less<Pair<Key, Value>>());
130 }
131
132 [system_default]
133 public TextWriter& operator<<<Key, Value, KeyCompare>(TextWriter& writer, const Map<Key, Value, KeyCompare>& map)
134 {
135 if (writer.Error()) return writer;
136 writer << "{";
137 bool first = true;
138 for (const Pair<Key, Value>& element : map)
139 {
140 if (first)
141 {
142 first = false;
143 }
144 else
145 {
146 writer << ", ";
147 }
148 writer << element;
149 }
150 writer << "}";
151 return writer;
152 }