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.ArrayList;
029import java.util.Collection;
030import java.util.Collections;
031import java.util.Comparator;
032import java.util.HashSet;
033import java.util.Iterator;
034import java.util.Set;
035
036import com.google.common.base.Function;
037import com.google.common.collect.Iterators;
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.Concept;
044import conexp.fx.core.context.ConceptLattice;
045import conexp.fx.core.context.MatrixContext;
046import conexp.fx.gui.task.TimeTask;
047
048public final class NextConcept<G, M> implements Iterable<Concept<G, M>> {
049
050  public static final <G, M> TimeTask<Void> concepts(final ConceptLattice<G, M> lattice) {
051    return new TimeTask<Void>("NextConcept") {
052
053      private final Comparator<Concept<G, M>> intentSizeComparator = new Comparator<Concept<G, M>>() {
054
055        public final int compare(final Concept<G, M> c1, final Concept<G, M> c2) {
056          return (int) Math.signum(c1.intent().size() - c2.intent().size());
057        }
058      };
059
060      protected final Void call() {
061        updateProgress(0d, 1d);
062        if (isCancelled())
063          return null;
064        updateMessage("Computing Formal Concepts...");
065        lattice.dispose();
066        updateProgress(0.05d, 1d);
067        double currentConceptNumber = 0;
068        final double maximalConceptNumber =
069            Math.pow(2d, (double) Math.min(lattice.context.rowHeads().size(), lattice.context.colHeads().size()));
070        final HashSet<Concept<G, M>> hashSet = new HashSet<Concept<G, M>>();
071        updateProgress(0.1d, 1d);
072        final Iterator<Concept<G, M>> iterator = new NextConcept<G, M>(lattice.context).iterator();
073        updateProgress(0.2d, 1d);
074        while (iterator.hasNext()) {
075          Concept<G, M> concept = iterator.next();
076          hashSet.add(concept);
077          currentConceptNumber++;
078          updateProgress(0.2d + 0.5d * (currentConceptNumber / maximalConceptNumber), 1d);
079          updateMessage("computing concepts: " + currentConceptNumber + "...");
080        }
081        updateProgress(0.7d, 1d);
082        final ArrayList<Concept<G, M>> concepts = new ArrayList<Concept<G, M>>(hashSet);
083        updateProgress(0.75d, 1d);
084        updateMessage("sorting " + currentConceptNumber + " concepts...");
085        Collections.sort(concepts, intentSizeComparator);
086        updateProgress(0.9d, 1d);
087        lattice.rowHeads().addAll(concepts);
088        updateMessage("Pushing Changes...");
089//        lattice.pushAllChangedEvent();
090        updateProgress(1d, 1d);
091        return null;
092      }
093    };
094  }
095
096  private final MatrixContext<G, M> context;
097
098  public NextConcept(final MatrixContext<G, M> context) {
099    super();
100    this.context = context;
101  }
102
103  private interface HullOperator<M> {
104
105    public Collection<Integer> closure(final Iterable<M> iterable);
106  }
107
108  public final Iterator<Concept<G, M>> iterator() {
109    final MatrixContext<G, M> selection = context.selection;
110//    selection.pushAllChangedEvent();
111    // maybe drop this for huge contexts
112    // or encapsulate in own class or blocking task
113//    final MatrixContext<Set<Integer>, Set<Integer>> reduced;
114//    switch (MatrixContext.AutomaticMode.fromSize(selection.rowHeads().size(), selection.colHeads().size())){
115//      case REDUCE:
116//              reduced = selection._reduced.clone();
117//              break;
118//      case CLEAN:
119//      case NONE:
120//      default:
121//    reduced = selection._cleaned.clone();
122//                      break;
123//    }
124    final MatrixContext<Set<Integer>, Set<Integer>> reduced = selection._reduced.clone();
125    final HullOperator<Integer> hullOp = new HullOperator<Integer>() {
126
127      public Collection<Integer> closure(Iterable<Integer> set) {
128        return reduced._extent(set);
129      }
130    };
131    return Iterators.transform(new UnmodifiableIterator<BitSetFX>() {
132
133      private final int rows = reduced.rowHeads().size();
134      private BitSetFX _A = new BitSetFX(reduced._colAnd(SetLists.integers(reduced.colHeads().size())));
135
136      public final boolean hasNext() {
137        return _A != null;
138      }
139
140      public final BitSetFX next() {
141        final BitSetFX _nextExtent = _A;
142        _APlus();
143        return _nextExtent;
144      }
145
146      private final void _APlus() {
147        BitSetFX _APlus;
148        for (int _g = rows - 1; _g > -1; --_g)
149          if (!_A.contains(_g)) {
150            _APlus = _APlusG(_g);
151            if (_AisLexicSmallerG(_APlus, _g)) {
152              _A = _APlus;
153              return;
154            }
155          }
156        _A = null;
157      }
158
159      private final BitSetFX _APlusG(final int _g) {
160        return new BitSetFX(
161            hullOp.closure(
162                Collections3.iterable(
163                    Iterators.concat(
164                        Iterators.filter(_A.iterator(), Collections3.isSmaller(_g)),
165                        Iterators.singletonIterator(_g)))));
166      }
167
168      private final boolean _AisLexicSmallerG(final BitSetFX _B, final int _g) {
169        for (int _h : _B)
170          if (_h == _g)
171            break;
172          else if (!_A.contains(_h))
173            return false;
174        return true;
175      }
176    }, new Function<BitSetFX, Concept<G, M>>() {
177
178      public final Concept<G, M> apply(final BitSetFX _extent) {
179        return new Concept<G, M>(
180            selection.rowHeads().getAll(
181                selection._colAnd(
182                    Collections3.iterable(
183                        Iterators.concat(
184                            Iterators.transform(
185                                reduced.colHeads().getAll(reduced._rowAnd(_extent), true).iterator(),
186                                Collections3.<Integer> setToIterator())))),
187                true),
188            selection.colHeads().getAll(
189                selection._rowAnd(
190                    Collections3.iterable(
191                        Iterators.concat(
192                            Iterators.transform(
193                                reduced.rowHeads().getAll(_extent, true).iterator(),
194                                Collections3.<Integer> setToIterator())))),
195                true));
196      }
197    });
198  }
199}