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}