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