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 Iterator Begin()
24 {
25 return tree.Begin();
26 }
27 public inline ConstIterator Begin() const
28 {
29 return tree.CBegin();
30 }
31 public inline ConstIterator CBegin() const
32 {
33 return tree.CBegin();
34 }
35 public inline Iterator End()
36 {
37 return tree.End();
38 }
39 public inline ConstIterator End() const
40 {
41 return tree.CEnd();
42 }
43 public inline ConstIterator CEnd() const
44 {
45 return tree.CEnd();
46 }
47 public inline long Count() const
48 {
49 return tree.Count();
50 }
51 public inline bool IsEmpty() const
52 {
53 return tree.IsEmpty();
54 }
55 public void Clear()
56 {
57 tree.Clear();
58 }
59 public inline Iterator Find(const KeyType& key)
60 {
61 return tree.Find(key);
62 }
63 public inline ConstIterator Find(const KeyType& key) const
64 {
65 return tree.CFind(key);
66 }
67 public inline ConstIterator CFind(const KeyType& key) const
68 {
69 return tree.CFind(key);
70 }
71 public inline Iterator LowerBound(const KeyType& key)
72 {
73 return tree.LowerBound(key);
74 }
75 public inline ConstIterator LowerBound(const KeyType& key) const
76 {
77 return tree.CLowerBound(key);
78 }
79 public inline 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 bool Remove(const KeyType& key)
89 {
90 return tree.Remove(key);
91 }
92 public inline void Remove(Iterator pos)
93 {
94 tree.Remove(pos);
95 }
96 private TreeType tree;
97 }
98
99 public 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 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]
112 public TextWriter& operator<<<T, C>(TextWriter& writer, const Set<T, C>& set)
113 {
114 if (writer.Error()) return writer;
115 writer << "{";
116 bool first = true;
117 for (const T& element : set)
118 {
119 if (first)
120 {
121 first = false;
122 }
123 else
124 {
125 writer << ", ";
126 }
127 writer << element;
128 }
129 writer << "}";
130 return writer;
131 }