|
1 package ro.infoiasi.donald.compiler.simple;
2
3 import java.util.*;
4
5 class RelationNotInternal extends RuntimeException  {}
6 class IncompatibleRelations extends RuntimeException {};
7
8 public class Relation {
9 public class IntPair implements Comparable {
10 private int first;
11 private int second;
12 public IntPair(int i, int j) {
13 first = i;
14 second = j;
15 }
16
17 public int getFirst() {
18 return first;
19 }
20
21 public int getSecond() {
22 return second;
23 }
24
25 public void setFirst(int i) {
26 first = i;
27 }
28
29 public void setSecond(int j) {
30 second = j;
31 }
32
33 public boolean equals(Object o) {
34 return (o instanceof IntPair)
35 && first == ((IntPair)o).first
36 && second == ((IntPair)o).second;
37 }
38
39 public int hashCode() {
40 int result = 17;
41 result = 37*result + first;
42 result = 37*result + second;
43 return result;
44 }
45
46 public int compareTo(Object o) {
47 IntPair ip = (IntPair)o;
48 if (first < ip.first) {
49 return -1;
50 } else if (first > ip.first) {
51 return +1;
52 } else if (second < ip.second) {
53 return -1;
54 } else if (second > ip.second) {
55 return +1;
56 } else {
57 return 0;
58 }
59 }
60
61 public String toString() {
62 return "("+first+","+second+")";
63 }
64 }
65
66 private Set s = newSet();
68 private int n = 0;
69 private int m = 0;
70
71 private static Set newSet() {
72 return new LinkedHashSet();
73 }
74
75 public Relation(int n) {
76 this(n, n);
77 }
78
79 public Relation(int n, int m) {
80 this.n = n;
81 this.m = m;
82 }
83
84 public Relation(int n, boolean[][] a) {
85 this(n, n, a);
86 }
87
88 public Relation(int n, int m, boolean[][] a) {
89 this(n, m);
90 for (int i = 0; i<n; i++) {
91 for (int j = 0; j<m; j++) {
92 if (a[i][j]) {
93 add(i, j);
94 }
95 }
96 }
97 }
98
99 public Relation(Relation r) {
100 this(r.m, r.m);
101 s = newSet();
102 s.addAll(r.s);
103 }
104
105 private void checkPair(int i, int j)
106 throws IndexOutOfBoundsException {
107 if (i<0 || i>=n || j<0 || j>=m) {
108 throw new IndexOutOfBoundsException ();
109 }
110 }
111
112 private void checkInternal()
113 throws RelationNotInternal {
114 if (n != m) {
115 throw new RelationNotInternal();
116 }
117 }
118
119 public boolean contains(int i, int j) {
120 checkPair(i, j);
121 return s.contains(new IntPair(i, j));
122 }
123
124 public boolean add(int i, int j) {
125 checkPair(i, j);
126 return s.add(new IntPair(i, j));
127 }
128
129 public boolean remove(int i, int j) {
130 checkPair(i, j);
131 return s.remove(new IntPair(i, j));
132 }
133
134 public Iterator iterator() {
135 return s.iterator();
136 }
137
138 public boolean isReflexive() {
139 checkInternal();
140 for (int i = 0; i<n; i++) {
141 if (!contains(i, i)) {
142 return false;
143 }
144 }
145 return true;
146 }
147
148 public boolean isIreflexive() {
149 checkInternal();
150 for (int i = 0; i<n; i++) {
151 if (contains(i, i)) {
152 return false;
153 }
154 }
155 return true;
156 }
157
158 public Relation reflexiveClosure() {
159 checkInternal();
160 Relation r = new Relation(this);
161 for (int i = 0; i<n; i++) {
162 r.add(i, i);
163 }
164 return r;
165 }
166
167 public boolean isTransitive() {
168 checkInternal();
169 for (int k = 0; k<n; k++) {
170 for (int i = 0; i<n; i++) {
171 if (contains(i, k)) {
172 for (int j = 0; j<n; j++) {
173 if (contains(k, j) && !contains(i,j)) {
174 return false;
175 }
176 }
177 }
178 }
179 }
180 return true;
181 }
182
183 public Relation transitiveClosure() {
184 checkInternal();
185 Relation r = new Relation(this);
186 for (int k = 0; k<n; k++) {
188 for (int i = 0; i<n; i++) {
189 if (r.contains(i, k)) {
190 for (int j = 0; j<n; j++) {
191 if (r.contains(k, j)) {
192 r.add(i, j);
193 }
194 }
195 }
196 }
197 }
198 return r;
199 }
200
201 public boolean isSymmetrical() {
202 checkInternal();
203 Iterator it = s.iterator();
204 while (it.hasNext()) {
205 IntPair ip = (IntPair)it.next();
206 if (!contains(ip.getSecond(), ip.getFirst())) {
207 return false;
208 }
209 }
210 return true;
211 }
212
213 public boolean isAsymmetrical() {
214 checkInternal();
215 Iterator it = s.iterator();
216 while (it.hasNext()) {
217 IntPair ip = (IntPair)it.next();
218 if (contains(ip.getSecond(), ip.getFirst())) {
219 return false;
220 }
221 }
222 return true;
223 }
224
225 public boolean isAntisymmetrical() {
226 checkInternal();
227 Iterator it = s.iterator();
228 while (it.hasNext()) {
229 IntPair ip = (IntPair)it.next();
230 if (contains(ip.getSecond(), ip.getFirst())
231 && ip.getFirst() != ip.getSecond()) {
232 return false;
233 }
234 }
235 return true;
236 }
237
238 public Relation symmetricalClosure() {
239 checkInternal();
240 Relation r = new Relation(this);
241 Iterator it = s.iterator();
242 while (it.hasNext()) {
243 IntPair ip = (IntPair)it.next();
244 r.add(ip.getSecond(), ip.getFirst());
245 }
246 return r;
247 }
248
249 public Relation reflexiveTransitiveClosure() {
250 return reflexiveClosure().transitiveClosure();
251 }
252
253 public boolean isEquivalence() {
254 return (isReflexive() && isSymmetrical() && isTransitive());
255 }
256
257 public Relation equivalenceClosure() {
258 return reflexiveClosure().transitiveClosure().symmetricalClosure();
259 }
260
261 public boolean isPartialOrdering() {
262 return (isReflexive() && isAntisymmetrical() && isTransitive());
263 }
264
265 public boolean isTotalOrdering() {
266 return (isPartialOrdering() && isConex());
267 }
268
269 public boolean isConex() {
270 checkInternal();
271 for (int i = 0; i<n; i++) {
272 for (int j = i+1; j<n; j++) {
273 if (!contains(i,j) && !contains(j,i)) {
274 return false;
275 }
276 }
277 }
278 return true;
279 }
280
281 public Relation inverse() {
282 Relation r = new Relation(m, n);
283 Iterator it = s.iterator();
284 while (it.hasNext()) {
285 IntPair ip = (IntPair)it.next();
286 r.add(ip.getSecond(), ip.getFirst());
287 }
288 return r;
289 }
290
291 public static Relation product(Relation r1, Relation r2) {
292 if (r1.m != r2.n) {
293 throw new IncompatibleRelations();
294 }
295 Relation r = new Relation(r1.n, r2.m);
296 Iterator it = r1.s.iterator();
297 while (it.hasNext()) {
298 IntPair ip1 = (IntPair)it.next();
299 for (int i = 0; i<r2.m; i++) {
300 if (r2.contains(ip1.getSecond(), i)) {
301 r.add(ip1.getFirst(), i);
302 }
303 }
304 }
305 return r;
306 }
307
308 public boolean[][] toArray() {
309 boolean[][] a = new boolean[n][];
310 for (int i = 0; i<n; i++) {
311 a[i] = new boolean[m];
312 for (int j = 0; j<m; j++) {
313 if (s.contains(new IntPair(i, j))) {
314 a[i][j] = true;
315 } else {
316 a[i][j] = false;
317 }
318 }
319 }
320 return a;
321 }
322
323 public String toString() {
324 StringBuffer sb = new StringBuffer ();
325 sb.append("{");
326 Iterator it = s.iterator();
327 while (it.hasNext()) {
328 IntPair ip = (IntPair)it.next();
329 sb.append(ip.toString());
330 }
331 sb.append("}");
332 return sb.toString();
333 }
334
335 private static void printBoolMatrix(boolean[][] a) {
336 for (int i = 0; i<a.length; i++) {
337 for (int j = 0; j<a[i].length; j++) {
338 if (a[i][j]) {
339 System.out.print("1");
340 } else {
341 System.out.print("0");
342 }
343 }
344 System.out.println();
345 }
346 }
348
349 public static void main(String [] args) throws RelationNotInternal {
350 boolean[][] a = { {false, true, false, false},
351 {false, false, true, false},
352 {false, false, false, true},
353 {false, true, false, true}};
354
355 boolean[][] c = { {true, false, false, false, false},
356 {false, true, false, false, false},
357 {false, true, false, false, false},
358 {false, true, false, false, true}};
359
360 Relation rho = new Relation(4, a);
361 Relation sigma = new Relation(4, 5, c);
362 printBoolMatrix(rho.toArray());
363 printBoolMatrix(sigma.toArray());
364 printBoolMatrix(product(rho, sigma).toArray());
365
366 System.out.println(rho);
367 System.out.println(rho.reflexiveClosure()+" "+rho.isReflexive()+" "+rho.reflexiveClosure().isReflexive());
368 System.out.println(rho.transitiveClosure()+" "+rho.isTransitive()+" "+rho.transitiveClosure().isTransitive());
369 System.out.println(rho.symmetricalClosure()+" "+rho.isSymmetrical()+" "+rho.symmetricalClosure().isSymmetrical());
370 }
371 }
372 |
Popular Tags |
Java API By Example, From Geeks To Geeks.