Source code

001package conexp.fx.core.collections.relation;
002
003/*
004 * #%L
005 * Concept Explorer FX
006 * %%
007 * Copyright (C) 2010 - 2019 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.filter(
222        ListIterators.<R, C> cartesianProduct(rowHeads().listIterator(), colHeads().listIterator(), 0),
223        new Predicate<Pair<R, C>>() {
224
225          public final boolean apply(final Pair<R, C> p) {
226            return contains(p.x(), p.y());
227          }
228        });
229  }
230
231  public int size() {
232    int size = 0;
233    for (R row : rowHeads())
234      for (C col : colHeads())
235        if (contains(row, col))
236          size++;
237    return size;
238  }
239
240  public boolean isFull() {
241    for (R row : rowHeads())
242      for (C col : colHeads())
243        if (!contains(row, col))
244          return false;
245    return true;
246  }
247
248  public boolean isEmpty() {
249    for (R row : rowHeads())
250      for (C col : colHeads())
251        if (contains(row, col))
252          return false;
253    return true;
254  }
255
256  public MatrixRelation<R, C> clone() {
257    final MatrixRelation<R, C> clone = new MatrixRelation<R, C>(rowHeads(), colHeads(), homogen);
258    clone.addAllFast(this);
259    return clone;
260  }
261
262  public boolean[][] toArray() {
263    final boolean[][] a = new boolean[rowHeads().size()][colHeads().size()];
264    for (int i = 0; i < rowHeads().size(); i++)
265      for (int j = 0; j < colHeads().size(); j++)
266        a[i][j] = contains(rowHeads().get(i), colHeads().get(j));
267    return a;
268  }
269
270  private static final int colspan = 5;
271
272  public String toString() {
273    final StringBuilder s = new StringBuilder();
274    s.append(getClass().getName() + "@" + hashCode() + "\r\n");
275    s.append(rowHeads().size() + " domain elements.\r\n");
276    s.append(colHeads().size() + " codomain elements.\r\n");
277    String spaces = "";
278    while (spaces.length() < colspan)
279      spaces += " ";
280    s.append(spaces);
281    spaces = spaces.substring(1);
282    String c;
283    for (C col : colHeads()) {
284      c = col.toString().substring(0, Math.min(colspan, col.toString().length()));
285      while (c.length() < colspan)
286        c += " ";
287      s.append("\t" + c);
288    }
289    s.append("\r\n");
290    String r;
291    for (R row : rowHeads()) {
292      r = row.toString().substring(0, Math.min(colspan, row.toString().length()));
293      while (r.length() < colspan)
294        r += " ";
295      s.append(r);
296      for (C col : colHeads())
297        if (contains(row, col))
298          s.append("\tX" + spaces);
299        else
300          s.append("\t." + spaces);
301      s.append("\r\n");
302    }
303    return s.toString();
304  }
305
306  public void empty() {
307    throw new UnsupportedOperationException();
308  }
309
310  public void fill() {
311    throw new UnsupportedOperationException();
312  }
313
314  public void dispose() {
315    throw new UnsupportedOperationException();
316  }
317
318  public boolean add(final R row, final C col) {
319    throw new UnsupportedOperationException();
320  }
321
322  public boolean addFast(final Object o1, final Object o2) {
323    throw new UnsupportedOperationException();
324  }
325
326  public boolean addAll(final Relation<? extends R, ? extends C> r) {
327    throw new UnsupportedOperationException();
328  }
329
330  public boolean addAllFast(final Relation<?, ?> r) {
331    throw new UnsupportedOperationException();
332  }
333
334  public boolean remove(final Object o1, final Object o2) {
335    throw new UnsupportedOperationException();
336  }
337
338  public boolean removeAll(final Relation<?, ?> r) {
339    throw new UnsupportedOperationException();
340  }
341
342  public boolean retainAll(final Relation<?, ?> r) {
343    throw new UnsupportedOperationException();
344  }
345
346  @Override
347  public boolean isHomogen() {
348    return homogen;
349  }
350
351  protected final void checkHomogen() throws NoHomogenRelationException {
352    if (!isHomogen())
353      throw new NoHomogenRelationException();
354  }
355
356  public MatrixRelation<R, R> neighborhood() {
357    checkHomogen();
358    return clone().neighborhood();
359  }
360
361  public MatrixRelation<R, R> order() {
362    checkHomogen();
363    return clone().order();
364  }
365
366  public SetList<Set<R>> equivalenceClasses() {
367    checkHomogen();
368    return new AbstractSetList<Set<R>>() {
369
370      @Override
371      public final ListIterator<Set<R>> listIterator(final int i) {
372        return new SimpleListIterator<Set<R>>(true) {
373
374          private final HashSet<R> available = new HashSet<R>(rowHeads());
375
376          {
377            createFirst(i);
378          }
379
380          @Override
381          protected final Set<R> createNext() {
382            try {
383              final R head = Collections3.firstElement(available);
384              final Set<R> eq = new HashSet<R>(col(head));
385              available.removeAll(eq);
386              return eq;
387            } catch (NoSuchElementException e) {
388              return null;
389            }
390          }
391
392          @Override
393          protected final Set<R> createPrevious() {
394            // TODO Auto-generated method stub
395            return null;
396          }
397        };
398      }
399    };
400  }
401}