001/*
002 * @author Francesco.Kriegel@gmx.de
003 */
004package conexp.fx.core.algorithm.nextclosure;
005
006/*
007 * #%L
008 * Concept Explorer FX
009 * %%
010 * Copyright (C) 2010 - 2023 Francesco Kriegel
011 * %%
012 * This program is free software: you can redistribute it and/or modify
013 * it under the terms of the GNU General Public License as
014 * published by the Free Software Foundation, either version 3 of the
015 * License, or (at your option) any later version.
016 * 
017 * This program is distributed in the hope that it will be useful,
018 * but WITHOUT ANY WARRANTY; without even the implied warranty of
019 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
020 * GNU General Public License for more details.
021 * 
022 * You should have received a copy of the GNU General Public
023 * License along with this program.  If not, see
024 * <http://www.gnu.org/licenses/gpl-3.0.html>.
025 * #L%
026 */
027
028import java.util.Collection;
029import java.util.HashSet;
030import java.util.Iterator;
031import java.util.List;
032import java.util.Set;
033
034import com.google.common.base.Function;
035import com.google.common.collect.Collections2;
036import com.google.common.collect.Iterators;
037import com.google.common.collect.Sets;
038import com.google.common.collect.UnmodifiableIterator;
039
040import conexp.fx.core.collections.BitSetFX;
041import conexp.fx.core.collections.Collections3;
042import conexp.fx.core.collections.setlist.SetLists;
043import conexp.fx.core.context.MatrixContext;
044import conexp.fx.gui.task.TimeTask;
045import de.tudresden.inf.tcs.fcalib.Implication;
046import javafx.application.Platform;
047
048public final class NextImplication<G, M> implements Iterable<Implication<M>> {
049
050  public static final <G, M> TimeTask<Void>
051      implications(final MatrixContext<G, M> context, final List<Implication<M>> implications) {
052    return new TimeTask<Void>("NextImplication") {
053
054      protected final Void call() {
055        updateProgress(0d, 1d);
056        if (isCancelled())
057          return null;
058        updateMessage("Computing Formal Implications...");
059        updateProgress(0.05d, 1d);
060        double currentImplicationNumber = 0;
061        // final double maximalImplicationNumber = 1;
062        updateProgress(0.1d, 1d);
063        final Iterator<Implication<M>> iterator = new NextImplication<G, M>(context).iterator();
064        updateProgress(0.2d, 1d);
065        // final boolean observable = implications instanceof
066        // ObservableList;
067        while (iterator.hasNext()) {
068          final Implication<M> next = iterator.next();
069          if (Platform.isFxApplicationThread()) {
070            implications.add(next);
071          } else {
072            Platform.runLater(new Runnable() {
073
074              public void run() {
075                implications.add(next);
076              }
077            });
078          }
079//            if (!next.getPremise().equals(next.getConclusion())) {
080//              final HashSet<M> premise = new HashSet<M>();
081//              premise.addAll(next.getPremise());
082//              final HashSet<M> conclusion = new HashSet<M>();
083//              conclusion.addAll(next.getConclusion());
084//              conclusion.removeAll(next.getPremise());
085//              // if (observable)
086//              // Platform.runLater(new Runnable() {
087//              //
088//              // @Override
089//              // public void run() {
090//              // implications.add(new Implication<M>(premise,
091//              // conclusion));
092//              // }
093//              // });
094//              // else
095//              implications.add(new Implication<M>(premise, conclusion));
096//            }
097          currentImplicationNumber++;
098          // updateProgress(0.2d + 0.7d * (currentImplicationNumber /
099          // maximalImplicationNumber), 1d);
100          updateMessage("computing implications: " + currentImplicationNumber + "...");
101        }
102        updateProgress(1d, 1d);
103        return null;
104      }
105    };
106
107  }
108
109  private final MatrixContext<G, M> context;
110
111  public NextImplication(final MatrixContext<G, M> context) {
112    super();
113    this.context = context;
114  }
115
116  private interface HullOperator<M> {
117
118    public Collection<Integer> closure(final Collection<M> iterable);
119  }
120
121  private final static class BitImplication {
122
123    private final BitSetFX premise;
124    private final BitSetFX conclusion;
125
126    private BitImplication(BitSetFX premise, BitSetFX conclusion) {
127      super();
128      this.premise = premise;
129      this.conclusion = conclusion;
130    }
131
132  }
133
134  public final Iterator<Implication<M>> iterator() {
135    final MatrixContext<Set<Integer>, Set<Integer>> cleaned = context.selection._cleaned.clone();
136    final UnmodifiableIterator<BitImplication> it = new UnmodifiableIterator<BitImplication>() {
137
138      private final int                   cols   = cleaned.colHeads().size();
139      private BitSetFX                    _P     = new BitSetFX(cleaned._colAnd(SetLists.integers(cols)));
140      private final Set<BitImplication>   impls  = new HashSet<BitImplication>();
141      private final HullOperator<Integer> hullOp = new HullOperator<Integer>() {
142
143                                                   public final Collection<Integer>
144                                                       closure(final Collection<Integer> set) {
145                                                     for (BitImplication impl : impls)
146                                                       if (set.containsAll(impl.premise))
147                                                         set.addAll(impl.conclusion);
148                                                     return set;
149                                                   }
150                                                 };
151
152      public final boolean hasNext() {
153        return _P != null;
154      }
155
156      public final BitImplication next() {
157        BitSetFX _nextPseudoIntent;
158        BitImplication bitImplication;
159        do {
160          _nextPseudoIntent = _P;
161          bitImplication = toBitImplication(_nextPseudoIntent);
162          _PPlus();
163        } while (_P != null && bitImplication.conclusion.isEmpty());
164        impls.add(bitImplication);
165        return bitImplication;
166      }
167
168      private final BitImplication toBitImplication(final BitSetFX pseudoIntent) {
169        final BitSetFX conclusion = new BitSetFX(cleaned._intent(pseudoIntent));
170        conclusion.removeAll(pseudoIntent);
171        return new BitImplication(pseudoIntent, conclusion);
172      }
173
174      private final void _PPlus() {
175        BitSetFX _PPlus;
176        for (int _m = cols - 1; _m > -1; --_m)
177          if (!_P.contains(_m)) {
178            _PPlus = _PPlusM(_m);
179            if (_PisLexicSmallerM(_PPlus, _m)) {
180              _P = _PPlus;
181              return;
182            }
183          }
184        _P = null;
185      }
186
187      private final BitSetFX _PPlusM(final int _m) {
188        return new BitSetFX(
189            hullOp.closure(
190                Sets.newHashSet(
191                    Collections3.iterable(
192                        Iterators.concat(
193                            Iterators.filter(_P.iterator(), Collections3.isSmaller(_m)),
194                            Iterators.singletonIterator(_m))))));
195      }
196
197      private final boolean _PisLexicSmallerM(final BitSetFX _B, final int _m) {
198        for (int _n : _B)
199          if (_n == _m)
200            break;
201          else if (!_P.contains(_n))
202            return false;
203        return true;
204      }
205    };
206    final Function<BitImplication, Implication<M>> f = new Function<BitImplication, Implication<M>>() {
207
208      public final Implication<M> apply(final BitImplication _implication) {
209        final Collection<M> p = context.selection.colHeads().getAll(
210            Collections3
211                .union(Collections2.transform(_implication.premise, new Function<Integer, Collection<Integer>>() {
212
213                  @Override
214                  public final Collection<Integer> apply(final Integer index) {
215                    return cleaned.colHeads().get(index);
216                  }
217                })),
218            false);
219        final Collection<M> c = context.selection.colHeads().getAll(
220            Collections3
221                .union(Collections2.transform(_implication.conclusion, new Function<Integer, Collection<Integer>>() {
222
223                  @Override
224                  public final Collection<Integer> apply(final Integer index) {
225                    return cleaned.colHeads().get(index);
226                  }
227                })),
228            false);
229        return new Implication<M>(Sets.newHashSet(p), Sets.newHashSet(c));
230      }
231    };
232    return Iterators.transform(it, f);
233  }
234}