1 #if !defined HAVE_EQUIVCLASSES_H__
2 #define HAVE_EQUIVCLASSES_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010, 2012 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8 #include "fxttypes.h"
9
10
11 template <typename Type>
equivalence_classes(const Type * s,ulong n,bool (* equiv_q)(Type,Type),ulong * q)12 void equivalence_classes(const Type *s, ulong n, bool (*equiv_q)(Type, Type), ulong *q)
13 // Given an equivalence relation '==' (as function equiv_q())
14 // and a set s[] with n elements,
15 // write to q[k] the index j of the first element s[j] such that s[k]==s[j].
16 // For the complexity C: n<=C<=n*n
17 // C=n*n if each element is in its own class
18 // C=n if all elements are in the same class
19 {
20 for (ulong k=0; k<n; ++k) q[k] = k; // each in own class
21 for (ulong k=1; k<n; ++k)
22 {
23 #if 1
24 ulong j = 0;
25 while ( ! equiv_q(s[j], s[k]) ) ++j;
26 q[k] = q[j];
27 #else
28 ulong j = k;
29 while ( j-- )
30 {
31 if ( equiv_q(s[j], s[k]) )
32 {
33 q[k] = q[j];
34 break;
35 }
36 }
37 #endif
38 }
39 }
40 // -------------------------
41
42
43 #endif // !defined HAVE_EQUIVCLASSES_H__
44