001/**
002 * @author Francesco.Kriegel@gmx.de
003 */
004package conexp.fx.core.algorithm.lattice;
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.HashMap;
030import java.util.Iterator;
031import java.util.List;
032import java.util.Map;
033import java.util.Set;
034import java.util.function.Consumer;
035import java.util.function.Supplier;
036import java.util.stream.Collectors;
037
038import com.google.common.base.Function;
039import com.google.common.collect.Lists;
040import com.google.common.util.concurrent.AtomicDouble;
041
042import conexp.fx.core.collections.BitSetFX;
043import conexp.fx.core.collections.Collections3;
044import conexp.fx.core.context.Concept;
045import conexp.fx.core.context.ConceptLattice;
046import conexp.fx.core.context.MatrixContext;
047import conexp.fx.gui.dataset.FCADataset;
048import conexp.fx.gui.task.TimeTask;
049
050public final class IPred<G, M> {
051
052  public static final <G, M> TimeTask<Void> neighborhood(final String id, final ConceptLattice<G, M> lattice) {
053    return new TimeTask<Void>(id + " - iPred") {
054
055      protected final Void call() {
056        updateProgress(0d, 1d);
057        if (isCancelled())
058          return null;
059        updateMessage("Computing Concept Neighborhood...");
060        lattice.empty();
061        final int bits = lattice.context.colHeads().size();
062        final List<BitSetFX> intents =
063            new ArrayList<BitSetFX>(Lists.transform(lattice.rowHeads(), new Function<Concept<G, M>, BitSetFX>() {
064
065          public final BitSetFX apply(final Concept<G, M> concept) {
066            return lattice.context.colHeads().subBitSet(concept.intent());
067          }
068        }));
069        updateProgress(0.2d, 1d);
070        final Iterator<BitSetFX> intentIterator = intents.iterator();
071        final List<BitSetFX> borderIntents = new ArrayList<BitSetFX>(intents.size());
072        final Map<BitSetFX, BitSetFX> faceAccumulation = new HashMap<BitSetFX, BitSetFX>(intents.size(), 1f);
073        for (BitSetFX intent : intents)
074          faceAccumulation.put(intent, new BitSetFX(bits));
075        if (intentIterator.hasNext())
076          borderIntents.add(intentIterator.next());
077        final double total = intents.size();
078        double actual = 0d;
079        while (intentIterator.hasNext()) {
080          actual++;
081          updateProgress(0.3d + 0.7d * (actual / total), 1d);
082          updateMessage("Computing Neighborhood: " + (int) actual + " of " + (int) total + " Concepts...");
083          final BitSetFX intent = intentIterator.next();
084          final List<BitSetFX> candidateIntents = new ArrayList<BitSetFX>(borderIntents.size());
085          for (BitSetFX borderIntent : borderIntents) {
086            final BitSetFX candidateIntent = ((BitSetFX) intent.clone());
087            candidateIntent.and(borderIntent);
088            candidateIntents.add(candidateIntent);
089          }
090          for (BitSetFX candidateIntent : candidateIntents) {
091            final BitSetFX candidateFace = faceAccumulation.get(candidateIntent);
092            final BitSetFX intentFace = ((BitSetFX) intent.clone());
093            try {
094              intentFace.and(candidateFace);
095            } catch (Exception e) {
096              System.err.println("intentFace: " + intentFace);
097              System.err.println("candidateFace: " + candidateFace);
098              e.printStackTrace();
099            }
100            if (intentFace.isEmpty()) {
101              lattice._add((int) actual, intents.indexOf(candidateIntent));
102              final BitSetFX face = ((BitSetFX) intent.clone());
103              face.andNot(candidateIntent);
104              candidateFace.or(face);
105              borderIntents.remove(candidateIntent);
106            }
107          }
108          borderIntents.add(intent);
109        }
110//        updateMessage(
111//            "Pushing Changes...");
112//        lattice.pushAllChangedEvent();
113        updateProgress(1d, 1d);
114        return null;
115      }
116    };
117  }
118
119  public static final <G, M> ConceptLattice<G, M>
120      getConceptLattice(final MatrixContext<G, M> cxt, final Set<Concept<G, M>> concepts) {
121    final ConceptLattice<G, M> lattice = new ConceptLattice<G, M>(cxt);
122    lattice.rowHeads().addAll(
123        concepts
124            .parallelStream()
125            .sorted((c1, c2) -> (int) Math.signum(c1.extent().size() - c2.extent().size()))
126            .collect(Collectors.toList()));
127    populateConceptLattice(lattice, __ -> {} , __ -> {} , () -> false);
128    return lattice;
129  }
130
131  public static final <G, M> void populateConceptLattice(
132      final ConceptLattice<G, M> lattice,
133      final Consumer<String> messageConsumer,
134      final Consumer<Double> statusConsumer,
135      final Supplier<Boolean> isCancelled) {
136    statusConsumer.accept(0d);
137    if (isCancelled.get())
138      return;
139    messageConsumer.accept("Computing Concept Neighborhood...");
140    lattice.empty();
141    final int bits = lattice.context.colHeads().size();
142    final List<BitSetFX> intents = lattice
143        .rowHeads()
144        .parallelStream()
145        .map(concept -> lattice.context.colHeads().subBitSet(concept.intent()))
146        .collect(Collectors.toList());
147    statusConsumer.accept(0.2d);
148    final Iterator<BitSetFX> intentIterator = intents.iterator();
149    final List<BitSetFX> borderIntents = new ArrayList<BitSetFX>(intents.size());
150    final Map<BitSetFX, BitSetFX> faceAccumulation =
151        intents.parallelStream().collect(Collectors.toMap(intent -> intent, intent -> new BitSetFX(bits)));
152    if (intentIterator.hasNext())
153      borderIntents.add(intentIterator.next());
154    final double total = intents.size();
155    final AtomicDouble actual = new AtomicDouble(0d);
156    while (intentIterator.hasNext()) {
157      if (isCancelled.get())
158        break;
159      actual.set(actual.get() + 1d);
160      statusConsumer.accept(0.3d + 0.7d * (actual.get() / total));
161      messageConsumer.accept("Computing Neighborhood: " + (int) actual.get() + " of " + (int) total + " Concepts...");
162      final BitSetFX intent = intentIterator.next();
163      Set<BitSetFX> toBeRemoved = Collections3.newConcurrentHashSet();
164      borderIntents.parallelStream().map(borderIntent -> {
165        final BitSetFX candidateIntent = ((BitSetFX) intent.clone());
166        candidateIntent.and(borderIntent);
167        return candidateIntent;
168      }).forEach(candidateIntent -> {
169        final BitSetFX candidateFace = faceAccumulation.get(candidateIntent);
170        final BitSetFX intentFace = ((BitSetFX) intent.clone());
171        intentFace.and(candidateFace);
172        if (intentFace.isEmpty()) {
173          final int index = intents.indexOf(candidateIntent);
174          synchronized (lattice) {
175            lattice._add((int) actual.get(), index);
176          }
177          final BitSetFX face = ((BitSetFX) intent.clone());
178          face.andNot(candidateIntent);
179          candidateFace.or(face);
180          toBeRemoved.add(candidateIntent);
181        }
182      });
183      borderIntents.removeAll(toBeRemoved);
184      borderIntents.add(intent);
185    }
186//    messageConsumer.accept(
187//        "Pushing Changes...");
188//    lattice.pushAllChangedEvent();
189    statusConsumer.accept(1d);
190  }
191
192  public static final <G, M> TimeTask<Void> neighborhoodP(final FCADataset<G, M> dataset) {
193    return new TimeTask<Void>(dataset, "iPred (parallel)") {
194
195      protected final Void call() {
196        populateConceptLattice(dataset.lattice, m -> updateMessage(m), p -> updateProgress(p, 1d), this::isCancelled);
197        return null;
198//        updateProgress(0d, 1d);
199//        if (isCancelled())
200//          return null;
201//        updateMessage("Computing Concept Neighborhood...");
202//        dataset.lattice.empty();
203//        final int bits = dataset.lattice.context.colHeads().size();
204//        final List<BitSet> intents = dataset.lattice
205//            .rowHeads()
206//            .parallelStream()
207//            .map(concept -> dataset.lattice.context.colHeads().subBitSet(concept.intent()))
208//            .collect(Collectors.toList());
209//        updateProgress(0.2d, 1d);
210//        final Iterator<BitSet> intentIterator = intents.iterator();
211//        final List<BitSet> borderIntents = new ArrayList<BitSet>(intents.size());
212//        final Map<BitSet, BitSet> faceAccumulation =
213//            intents.parallelStream().collect(Collectors.toMap(intent -> intent, intent -> new BitSet(bits)));
214//        if (intentIterator.hasNext())
215//          borderIntents.add(intentIterator.next());
216//        final double total = intents.size();
217//        final AtomicDouble actual = new AtomicDouble(0d);
218//        while (intentIterator.hasNext()) {
219//          if (this.isCancelled())
220//            break;
221//          actual.set(actual.get() + 1d);
222//          updateProgress(0.3d + 0.7d * (actual.get() / total), 1d);
223//          updateMessage("Computing Neighborhood: " + (int) actual.get() + " of " + (int) total + " Concepts...");
224//          final BitSet intent = intentIterator.next();
225//          Set<BitSet> toBeRemoved = Collections3.newConcurrentHashSet();
226//          borderIntents.parallelStream().map(borderIntent -> {
227//            final BitSet candidateIntent = ((BitSet) intent.clone());
228//            candidateIntent.and(borderIntent);
229//            return candidateIntent;
230//          }).forEach(candidateIntent -> {
231//            final BitSet candidateFace = faceAccumulation.get(candidateIntent);
232//            final BitSet intentFace = ((BitSet) intent.clone());
233//            intentFace.and(candidateFace);
234//            if (intentFace.isEmpty()) {
235//              final int index = intents.indexOf(candidateIntent);
236//              synchronized (dataset.lattice) {
237//                dataset.lattice._add((int) actual.get(), index);
238//              }
239//              final BitSet face = ((BitSet) intent.clone());
240//              face.andNot(candidateIntent);
241//              candidateFace.or(face);
242//              toBeRemoved.add(candidateIntent);
243//            }
244//          });
245//          borderIntents.removeAll(toBeRemoved);
246//          borderIntents.add(intent);
247//        }
248////        updateMessage(
249////            "Pushing Changes...");
250////        lattice.pushAllChangedEvent();
251//        updateProgress(1d, 1d);
252//        return null;
253      }
254    };
255  }
256}