001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of LearnLib, http://www.learnlib.de/.
003 * 
004 * LearnLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * LearnLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with LearnLib; if not, see
015 * <http://www.gnu.de/documents/lgpl.en.html>.
016 */
017package de.learnlib.cache.dfa;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.List;
022
023import net.automatalib.incremental.dfa.Acceptance;
024import net.automatalib.incremental.dfa.IncrementalDFABuilder;
025import net.automatalib.words.Alphabet;
026import de.learnlib.api.MembershipOracle;
027import de.learnlib.api.MembershipOracle.DFAMembershipOracle;
028import de.learnlib.api.Query;
029
030
031/**
032 * DFA cache. This cache is implemented as a membership oracle: upon construction, it is
033 * provided with a delegate oracle. Queries that can be answered from the cache are answered
034 * directly, others are forwarded to the delegate oracle. When the delegate oracle has finished
035 * processing these remaining queries, the results are incorporated into the cache.
036 * 
037 * @author Malte Isberner <malte.isberner@gmail.com>
038 *
039 * @param <I> input symbol class
040 */
041public class DFACacheOracle<I> implements DFAMembershipOracle<I> {
042        
043        private final IncrementalDFABuilder<I> incDfa;
044        private final MembershipOracle<I,Boolean> delegate;
045
046        /**
047         * Constructor.
048         * @param alphabet the alphabet of the cache
049         * @param delegate the delegate oracle
050         */
051        public DFACacheOracle(Alphabet<I> alphabet, MembershipOracle<I,Boolean> delegate) {
052                this.incDfa = new IncrementalDFABuilder<>(alphabet);
053                this.delegate = delegate;
054        }
055        
056        public int getCacheSize() {
057                return incDfa.size();
058        }
059        
060        /**
061         * Creates an equivalence oracle that checks an hypothesis for consistency with the
062         * contents of this cache. Note that the returned oracle is backed by the cache data structure,
063         * i.e., it is sufficient to call this method once after creation of the cache.
064         * @return the cache consistency test backed by the contents of this cache.
065         */
066        public DFACacheConsistencyTest<I> createCacheConsistencyTest() {
067                return new DFACacheConsistencyTest<>(incDfa);
068        }
069        
070        /*
071         * (non-Javadoc)
072         * @see de.learnlib.api.MembershipOracle#processQueries(java.util.Collection)
073         */
074        @Override
075        public void processQueries(Collection<? extends Query<I, Boolean>> queries) {
076                List<ProxyQuery<I>> unanswered = new ArrayList<>();
077                
078                for(Query<I,Boolean> q : queries) {
079                        Acceptance acc = incDfa.lookup(q.getInput());
080                        if(acc != Acceptance.DONT_KNOW)
081                                q.answer((acc == Acceptance.TRUE) ? true : false);
082                        else
083                                unanswered.add(new ProxyQuery<>(q));
084                }
085                
086                delegate.processQueries(unanswered);
087                
088                for(ProxyQuery<I> q : unanswered)
089                        incDfa.insert(q.getInput(), q.getAnswer());
090        }
091
092}