1 // =================================
  2 // Copyright (c) 2021 Seppo Laakko
  3 // Distributed under the MIT license
  4 // =================================
  5 
  6 using System;
  7 
  8 namespace System.Concepts
  9 {
 10     public concept DefaultConstructible<T>
 11     {
 12         T();
 13         where NonreferenceType<T>;
 14     }
 15 
 16     public concept CopyConstructible<T>
 17     {
 18         T(const T&);
 19         axiom copyIsEqual(T a) { eq(T(a)a); }
 20     }
 21 
 22     public concept MoveConstructible<T>
 23     {
 24         T(T&&);
 25     }
 26 
 27     public concept Destructible<T>
 28     {
 29         ~T();
 30     }
 31 
 32     public concept CopyAssignable<T>
 33     {
 34         void operator=(const T&);
 35     }
 36 
 37     public concept CopyAssignable<TU>
 38     {
 39         void operator=(const U&);
 40     }
 41 
 42     public concept MoveAssignable<T>
 43     {
 44         void operator=(T&&);
 45     }
 46 
 47     public concept Copyable<T>
 48     {
 49         where T is CopyConstructible and T is CopyAssignable;
 50     }
 51 
 52     public concept Movable<T>
 53     {
 54         where T is MoveConstructible and T is MoveAssignable;
 55     }
 56 
 57     public concept Semiregular<T>
 58     {
 59         where T is DefaultConstructible and (T is Movable or T is Copyable) and T is Destructible;
 60     }
 61 
 62     public concept EqualityComparable<T>
 63     {
 64         bool operator==(TT);
 65         axiom equal(T aT b) { a == b <=> eq(ab); }
 66         axiom reflexive(T a) { a == a; }
 67         axiom symmetric(T aT b) { a == b => b == a; }
 68         axiom transitive(T aT bT c) { a == b && b == c => a == c; }
 69         axiom notEqualTo(T aT b) { a != b <=> !(a == b); }
 70     }
 71 
 72     public concept EqualityComparable<TU> : Common<TU>
 73     {
 74         where T is EqualityComparable and U is EqualityComparable and CommonType is EqualityComparable;
 75     }
 76 
 77     public concept LessThanComparable<T>
 78     {
 79         bool operator<(TT);
 80         axiom irreflexive(T a) { !(a < a); }
 81         axiom antisymmetric(T aT b) { a < b => !(b < a); }
 82         axiom transitive(T aT bT c) { a < b && b < c => a < c; }
 83         axiom total(T aT b) { a < b || a == b || a > b; }
 84         axiom greaterThan(T aT b) { a > b <=> b < a; }
 85         axiom greaterThanOrEqualTo(T aT b) { a >= b <=> !(a < b); }
 86         axiom lessThanOrEqualTo(T aT b) { a <= b <=> !(b < a); }
 87     }
 88 
 89     public concept LessThanComparable<TU> : Common<TU>
 90     {
 91         where T is LessThanComparable and U is LessThanComparable and CommonType is LessThanComparable;
 92     }
 93 
 94     public concept Regular<T> : Semiregular<T>
 95     {
 96         where T is EqualityComparable;
 97     }
 98 
 99     public concept TotallyOrdered<T> : Regular<T>
100     {
101         where T is LessThanComparable;
102     }
103 
104     public concept TotallyOrdered<TU> : Common<TU>
105     {
106         where T is TotallyOrdered and U is TotallyOrdered and CommonType is TotallyOrdered;
107     }
108 
109     public concept TrivialIterator<T> where T is Semiregular
110     {
111         typename T.ValueType;
112         where T.ValueType is Semiregular;
113         typename T.ReferenceType;
114         T.ReferenceType operator*();
115         typename T.PointerType;
116         T.PointerType operator->();
117     }
118 
119     public concept OutputIterator<T> : TrivialIterator<T>
120     {
121         T& operator++();
122     }
123 
124     public concept InputIterator<T> : TrivialIterator<T>
125     {
126         T& operator++();
127         where T is Regular;
128     }
129 
130     public concept ForwardIterator<T> : InputIterator<T>
131     {
132         where T is OutputIterator;
133     }
134 
135     public concept BidirectionalIterator<T> : ForwardIterator<T>
136     {
137         T& operator--();
138     }
139 
140     public concept RandomAccessIterator<T> : BidirectionalIterator<T>
141     {
142         T.ReferenceType operator[](long index);
143         T operator+(Tlong);
144         T operator+(longT);
145         T operator-(Tlong);
146         long operator-(TT);
147         where T is LessThanComparable;
148     }
149 
150     public concept UnaryFunction<T> where T is Semiregular
151     {
152         typename T.ArgumentType;
153         typename T.ResultType;
154         where T.ArgumentType is Semiregular;
155         T.ResultType operator()(T.ArgumentType);
156     }
157 
158     public concept BinaryFunction<T> where T is Semiregular
159     {
160         typename T.FirstArgumentType;
161         typename T.SecondArgumentType;
162         typename T.ResultType;
163         where T.FirstArgumentType is Semiregular and T.SecondArgumentType is Semiregular;
164         T.ResultType operator()(T.FirstArgumentTypeT.SecondArgumentType);
165     }
166 
167     public concept UnaryPredicate<T> : UnaryFunction<T>
168     {
169         where T.ResultType is bool;
170     }
171 
172     public concept BinaryPredicate<T> : BinaryFunction<T>
173     {
174         where T.ResultType is bool;
175     }
176 
177     public concept Relation<T> : BinaryPredicate<T>
178     {
179     //  types Domain, FirstArgumentType and SecondArgumentType are all same type:
180         typename T.Domain;
181         where Same<T.DomainT.FirstArgumentType> and Same<T.SecondArgumentTypeT.Domain>;
182     }
183 
184     public concept Relation<TUV> : BinaryPredicate<T>
185     {
186         where T.FirstArgumentType is U and T.SecondArgumentType is V;
187     }
188 
189     public concept UnaryOperation<T> : UnaryFunction<T>
190     {
191         where T.ResultType is T.ArgumentType;
192     }
193 
194     public concept BinaryOperation<T> : BinaryFunction<T>
195     {
196         where T.ResultType is T.FirstArgumentType;
197     }
198 
199     public concept HashFunction<TKey> : UnaryFunction<T>
200     {
201         where T.ArgumentType is Key and T.ResultType is ulong;
202     }
203 
204     public concept KeySelectionFunction<TKeyValue> : UnaryFunction<T>
205     {
206         where T.ArgumentType is Value and T.ResultType is Key;
207     }
208 
209     public concept Container<T> where T is Semiregular
210     {
211         typename T.ValueType;
212         typename T.Iterator;
213         typename T.ConstIterator;
214         where T.Iterator is TrivialIterator and T.ConstIterator is TrivialIterator and T.ValueType is T.Iterator.ValueType;
215         T.Iterator T.Begin();
216         T.ConstIterator T.CBegin();
217         T.Iterator T.End();
218         T.ConstIterator T.CEnd();
219         long T.Count();
220         bool T.IsEmpty();
221     }
222 
223     public concept BackInsertionSequence<T> : Container<T>
224     {
225         void T.Add(T.ValueType);
226     }
227 
228     public concept FrontInsertionSequence<T> : Container<T>
229     {
230         T.Iterator T.InsertFront(T.ValueType);
231     }
232 
233     public concept ForwardContainer<T> : Container<T>
234     {
235         where T.Iterator is ForwardIterator and T.ConstIterator is ForwardIterator;
236     }
237 
238     public concept InsertionSequence<T> : ForwardContainer<T>
239     {
240         T.Iterator T.Insert(T.IteratorT.ValueType);
241     }
242 
243     public concept BidirectionalContainer<T> : ForwardContainer<T>
244     {
245        where T.Iterator is BidirectionalIterator and T.ConstIterator is BidirectionalIterator;
246     }
247 
248     public concept RandomAccessContainer<T> : BidirectionalContainer<T>
249     {
250         where T.Iterator is RandomAccessIterator and T.ConstIterator is RandomAccessIterator;
251     }
252 
253     public concept Integer<I> where I is TotallyOrdered
254     {
255         I operator-(I);
256         I operator~(I);
257         I operator+(II);
258         I operator-(II);
259         I operator*(II);
260         I operator/(II);
261         I operator%(II);
262         I operator<<(II);
263         I operator>>(II);
264         I operator&(II);
265         I operator|(II);
266         I operator^(II);
267     }
268 
269     public concept SignedInteger<I> where I is Integer
270     {
271         I(sbyte);
272     }
273 
274     public concept UnsignedInteger<U> where U is Integer
275     {
276         U(byte);
277     }
278 
279     public concept AdditiveSemigroup<T> where T is Regular
280     {
281         T operator+(TT);
282         axiom additionIsAssociative(T aT bT c) { (a + b) + c == a + (b + c); }
283         axiom additionIsCommutative(T aT b) { a + b == b + a; }
284     }
285 
286     public concept MultiplicativeSemigroup<T> where T is Regular
287     {
288         T operator*(TT);
289         axiom multiplicationIsAssociative(T aT bT c) { (a * b) * c == a * (b * c); }
290     }
291 
292     public concept OrderedAdditiveSemigroup<T> : AdditiveSemigroup<T>
293     {
294         where T is TotallyOrdered;
295         axiom additionPreservesOrder(T aT bT c) { a < b => a + c < b + c; }
296     }
297 
298     public concept OrderedMultiplicativeSemigroup<T> : MultiplicativeSemigroup<T>
299     {
300         where T is TotallyOrdered;
301     }
302     
303     public concept ConversionFromSByte<T>
304     {
305         T(sbyte);
306     }
307 
308     public concept ConversionFromByte<T>
309     {
310         T(byte);
311     }
312 
313     public concept AdditiveMonoid<T> : AdditiveSemigroup<T>
314     {
315         where ConversionFromSByte<T> or ConversionFromByte<T>;
316         axiom zeroIsIdentityElement(T a) { a + 0 == a && 0 + a == a; }
317     }
318 
319     public concept MultiplicativeMonoid<T> : MultiplicativeSemigroup<T>
320     {
321         where ConversionFromSByte<T> or ConversionFromByte<T>;
322         axiom oneIsIdentityElement(T a) { a * 1 == a && 1 * a == a; }
323     }
324 
325     public concept AdditiveGroup<T> : AdditiveMonoid<T>
326     {
327         T operator-(T);
328         T operator-(TT);
329         axiom unaryMinusIsInverseOp(T a) { a + (-a) == 0 && (-a) + a == 0; }
330         axiom subtract(T aT b) { a - b == a + (-b); }
331     }
332 
333     public concept MultiplicativeGroup<T> : MultiplicativeMonoid<T>
334     {
335         T operator/(TT);
336         // 1/a is multiplicative inverse
337         axiom multiplicativeInverseIsInverseOp(T a) { a * (1 / a) == 1 && (1 / a) * a == 1;}
338         axiom division(T aT b) { a / b == a * (1 / b);}
339     }
340 
341     public concept OrderedAdditiveMonoid<T> : OrderedAdditiveSemigroup<T>
342     {
343         where T is AdditiveMonoid;
344     }
345 
346     public concept OrderedAdditiveGroup<T> : OrderedAdditiveMonoid<T>
347     {
348         where T is AdditiveGroup;
349     }
350 
351     public concept Semiring<T> : AdditiveMonoid<T> where T is MultiplicativeMonoid
352     {
353         axiom zeroIsNotOne { 0 != 1; }
354         axiom multiplyingByZeroYieldsZero(T a) { 0 * a == 0 && a * 0 == 0; }
355         axiom distributivity(T aT bT c) { a * (b + c) == a * b + a * c && (b + c) * a == b * a + c * a; }
356     }
357 
358     public concept CommutativeSemiring<T> : Semiring<T>
359     {
360         axiom multiplicationIsCommutative(T aT b) { a * b == b * a; }
361     }
362 
363     public concept EuclideanSemiring<T> : CommutativeSemiring<T>
364     {
365         T operator%(TT);
366         T operator/(TT);
367         axiom quotientAndRemainder(T aT b) { b != 0 => a == a / b * b + a % b; }
368     }
369 }