Source code

001package conexp.fx.core.collections.relation;
002
003/*
004 * #%L
005 * Concept Explorer FX
006 * %%
007 * Copyright (C) 2010 - 2023 Francesco Kriegel
008 * %%
009 * This program is free software: you can redistribute it and/or modify
010 * it under the terms of the GNU General Public License as
011 * published by the Free Software Foundation, either version 3 of the
012 * License, or (at your option) any later version.
013 * 
014 * This program is distributed in the hope that it will be useful,
015 * but WITHOUT ANY WARRANTY; without even the implied warranty of
016 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
017 * GNU General Public License for more details.
018 * 
019 * You should have received a copy of the GNU General Public
020 * License along with this program.  If not, see
021 * <http://www.gnu.org/licenses/gpl-3.0.html>.
022 * #L%
023 */
024
025import java.util.Arrays;
026import java.util.Collection;
027import java.util.HashSet;
028import java.util.Iterator;
029import java.util.ListIterator;
030import java.util.NoSuchElementException;
031import java.util.Set;
032import java.util.function.BiPredicate;
033
034import com.google.common.base.Predicate;
035import com.google.common.collect.Iterators;
036import com.google.common.collect.Sets;
037
038import conexp.fx.core.collections.Collections3;
039import conexp.fx.core.collections.ListIterators;
040import conexp.fx.core.collections.Pair;
041import conexp.fx.core.collections.SimpleListIterator;
042import conexp.fx.core.collections.setlist.AbstractSetList;
043import conexp.fx.core.collections.setlist.SetList;
044import conexp.fx.core.collections.setlist.SetLists;
045
046public abstract class AbstractRelation<R, C> implements Relation<R, C> {
047
048  public static <R, C> AbstractRelation<R, C>
049      fromPredicate(final SetList<R> rowHeads, final SetList<C> colHeads, final BiPredicate<R, C> predicate) {
050    return new AbstractRelation<R, C>(rowHeads, colHeads, false) {
051
052      @Override
053      public final boolean contains(final Object o1, final Object o2) {
054        try {
055          return predicate.test((R) o1, (C) o2);
056        } catch (ClassCastException e) {
057          return false;
058        }
059      }
060
061    };
062  }
063
064  public static <R> AbstractRelation<R, R> fromPredicate(final SetList<R> heads, final BiPredicate<R, R> predicate) {
065    return new AbstractRelation<R, R>(heads, heads, true) {
066
067      @Override
068      public final boolean contains(final Object o1, final Object o2) {
069        try {
070          return predicate.test((R) o1, (R) o2);
071        } catch (ClassCastException e) {
072          return false;
073        }
074      }
075
076    };
077  }
078
079  protected final boolean homogen;
080  protected SetList<R>    rowHeads;
081  protected SetList<C>    colHeads;
082
083  @SuppressWarnings("unchecked")
084  protected AbstractRelation(final SetList<R> rowHeads, final SetList<C> colHeads, final boolean homogen) {
085    this(homogen);
086    if (homogen) {
087      if (!rowHeads.equals(colHeads))
088        throw new NoHomogenRelationException();
089      this.rowHeads = rowHeads;
090      this.colHeads = (SetList<C>) this.rowHeads;
091    } else {
092      this.rowHeads = rowHeads;
093      this.colHeads = colHeads;
094    }
095  }
096
097  protected AbstractRelation(final boolean homogen) {
098    super();
099    this.homogen = homogen;
100  }
101
102  public SetList<R> rowHeads() {
103    return rowHeads;
104  }
105
106  public SetList<C> colHeads() {
107    return colHeads;
108  }
109
110  public abstract boolean contains(Object o1, Object o2);
111
112  public boolean containsAll(final Relation<?, ?> r) {
113    for (Pair<?, ?> p : r)
114      if (!contains(p.x(), p.y()))
115        return false;
116    return true;
117  }
118
119  public Set<C> row(final Object o) {
120    return rowAnd(o);
121  }
122
123  public Set<R> col(final Object o) {
124    return colAnd(o);
125  }
126
127  public final Set<C> rowAnd(final Object... rows) {
128    return rowAnd(Arrays.asList(rows));
129  }
130
131  public final Set<R> colAnd(final Object... cols) {
132    return colAnd(Arrays.asList(cols));
133  }
134
135  public Set<C> rowAnd(final Collection<?> rows) {
136    return Sets.filter(colHeads(), new Predicate<C>() {
137
138      public final boolean apply(C col) {
139        for (Object row : rows)
140          if (!AbstractRelation.this.contains(row, col))
141            return false;
142        return true;
143      }
144    });
145  }
146
147  public Set<R> colAnd(final Collection<?> cols) {
148    return Sets.filter(rowHeads(), new Predicate<R>() {
149
150      public final boolean apply(final R row) {
151        for (Object col : cols)
152          if (!AbstractRelation.this.contains(row, col))
153            return false;
154        return true;
155      }
156    });
157  }
158
159  public Relation<R, C> subRelation(final Collection<?> rows, final Collection<?> cols) {
160    return new AbstractRelation<R, C>(
161        SetLists.intersection(rowHeads, rows),
162        SetLists.intersection(colHeads, cols),
163        false) {
164
165      public final boolean contains(final Object o1, final Object o2) {
166        return rowHeads().contains(o1) && colHeads().contains(o2) && AbstractRelation.this.contains(o1, o2);
167      }
168    };
169  }
170
171  public Relation<R, C> filter(
172      final Predicate<? super R> rowPredicate,
173      final Predicate<? super C> colPredicate,
174      final Predicate<Pair<R, C>> relationPredicate) {
175    return new AbstractRelation<R, C>(rowHeads.filter(rowPredicate), colHeads.filter(colPredicate), false) {
176
177      @SuppressWarnings("unchecked")
178      public final boolean contains(final Object o1, final Object o2) {
179        return rowHeads().contains(o1) && colHeads().contains(o2) && AbstractRelation.this.contains(o1, o2)
180            && relationPredicate.apply(new Pair<R, C>((R) o1, (C) o2));
181      }
182    };
183  }
184
185  public boolean equals(final Object o) {
186    return this == o
187        || (o instanceof Relation && size() == ((Relation<?, ?>) o).size() && containsAll((Relation<?, ?>) o));
188  }
189
190  public final boolean smallerEq(final Relation<R, C> r) {
191    return r.containsAll(this);
192  }
193
194  public final boolean smaller(final Relation<R, C> r) {
195    return size() < r.size() && smallerEq(r);
196  }
197
198  public final boolean greaterEq(final Relation<R, C> r) {
199    return r.smallerEq(this);
200  }
201
202  public final boolean greater(final Relation<R, C> r) {
203    return r.smaller(this);
204  }
205
206  public final boolean uncomparable(final Relation<R, C> r) {
207    return !smallerEq(r) && !greaterEq(r);
208  }
209
210  public final int compareTo(final Relation<R, C> r) {
211    if (equals(r))
212      return 0;
213    if (smallerEq(r))
214      return -1;
215    if (greaterEq(r))
216      return 1;
217    return Integer.MAX_VALUE;
218  }
219
220  public Iterator<Pair<R, C>> iterator() {
221    return Iterators
222        .filter(
223            ListIterators.<R, C> cartesianProduct(rowHeads().listIterator(), colHeads().listIterator(), 0),
224            new Predicate<Pair<R, C>>() {
225
226              public final boolean apply(final Pair<R, C> p) {
227                return contains(p.x(), p.y());
228              }
229            });
230  }
231
232  public int size() {
233    int size = 0;
234    for (R row : rowHeads())
235      for (C col : colHeads())
236        if (contains(row, col))
237          size++;
238    return size;
239  }
240
241  public boolean isFull() {
242    for (R row : rowHeads())
243      for (C col : colHeads())
244        if (!contains(row, col))
245          return false;
246    return true;
247  }
248
249  public boolean isEmpty() {
250    for (R row : rowHeads())
251      for (C col : colHeads())
252        if (contains(row, col))
253          return false;
254    return true;
255  }
256
257  public MatrixRelation<R, C> clone() {
258    final MatrixRelation<R, C> clone = new MatrixRelation<R, C>(rowHeads(), colHeads(), homogen);
259    clone.addAllFast(this);
260    return clone;
261  }
262
263  public boolean[][] toArray() {
264    final boolean[][] a = new boolean[rowHeads().size()][colHeads().size()];
265    for (int i = 0; i < rowHeads().size(); i++)
266      for (int j = 0; j < colHeads().size(); j++)
267        a[i][j] = contains(rowHeads().get(i), colHeads().get(j));
268    return a;
269  }
270
271  private static final int colspan = 8;
272
273  public String toString() {
274    final StringBuilder s = new StringBuilder();
275    s.append(getClass().getName() + "@" + hashCode() + "\r\n");
276    s.append(rowHeads().size() + " domain elements: " + rowHeads() + "\r\n");
277    s.append(colHeads().size() + " codomain elements. " + colHeads() + "\r\n");
278    String spaces = "";
279    while (spaces.length() < colspan)
280      spaces += " ";
281    s.append(spaces);
282    spaces = spaces.substring(1);
283    String c;
284    for (C col : colHeads()) {
285      c = col.toString().substring(0, Math.min(colspan, col.toString().length()));
286      while (c.length() < colspan)
287        c += " ";
288      s.append("\t" + c);
289    }
290    s.append("\r\n");
291    String r;
292    for (R row : rowHeads()) {
293      r = row.toString().substring(0, Math.min(colspan, row.toString().length()));
294      while (r.length() < colspan)
295        r += " ";
296      s.append(r);
297      for (C col : colHeads())
298        if (contains(row, col))
299          s.append("\tX" + spaces);
300        else
301          s.append("\t." + spaces);
302      s.append("\r\n");
303    }
304    return s.toString();
305  }
306
307  public void empty() {
308    throw new UnsupportedOperationException();
309  }
310
311  public void fill() {
312    throw new UnsupportedOperationException();
313  }
314
315  public void dispose() {
316    throw new UnsupportedOperationException();
317  }
318
319  public boolean add(final R row, final C col) {
320    throw new UnsupportedOperationException();
321  }
322
323  public boolean addFast(final Object o1, final Object o2) {
324    throw new UnsupportedOperationException();
325  }
326
327  public boolean addAll(final Relation<? extends R, ? extends C> r) {
328    throw new UnsupportedOperationException();
329  }
330
331  public boolean addAllFast(final Relation<?, ?> r) {
332    throw new UnsupportedOperationException();
333  }
334
335  public boolean remove(final Object o1, final Object o2) {
336    throw new UnsupportedOperationException();
337  }
338
339  public boolean removeAll(final Relation<?, ?> r) {
340    throw new UnsupportedOperationException();
341  }
342
343  public boolean retainAll(final Relation<?, ?> r) {
344    throw new UnsupportedOperationException();
345  }
346
347  @Override
348  public boolean isHomogen() {
349    return homogen;
350  }
351
352  protected final void checkHomogen() throws NoHomogenRelationException {
353    if (!isHomogen())
354      throw new NoHomogenRelationException();
355  }
356
357  public MatrixRelation<R, R> neighborhood() {
358    checkHomogen();
359    return clone().neighborhood();
360  }
361
362  public MatrixRelation<R, R> order() {
363    checkHomogen();
364    return clone().order();
365  }
366
367  public SetList<Set<R>> equivalenceClasses() {
368    checkHomogen();
369    return new AbstractSetList<Set<R>>() {
370
371      @Override
372      public final ListIterator<Set<R>> listIterator(final int i) {
373        return new SimpleListIterator<Set<R>>(true) {
374
375          private final HashSet<R> available = new HashSet<R>(rowHeads());
376
377          {
378            createFirst(i);
379          }
380
381          @Override
382          protected final Set<R> createNext() {
383            try {
384              final R head = Collections3.firstElement(available);
385              final Set<R> eq = new HashSet<R>(col(head));
386              available.removeAll(eq);
387              return eq;
388            } catch (NoSuchElementException e) {
389              return null;
390            }
391          }
392
393          @Override
394          protected final Set<R> createPrevious() {
395            // TODO Auto-generated method stub
396            return null;
397          }
398        };
399      }
400    };
401  }
402}