a4/tcp/tester/learner/ObservationTree.java

   1 package learner;
   2
   3 import java.util.HashMap;
   4 import java.util.LinkedList;
   5 import java.util.List;
   6 import java.util.Map;
   7
   8 import net.automatalib.words.Word;
   9
  10 /**
  11  * @author Ramon Janssen
  12  *
  13  * @param <I> the input type of the observations
  14  * @param <O> the output type of the observations
  15  */
  16 public class ObservationTree<I,O> {
  17         private final ObservationTree<I,O> parent;
  18         private final I parentInput;
  19         private final O parentOutput;
  20         private final Map<I, ObservationTree<I,O>> children;
  21         private final Map<I, O> outputs;
  22
  23         public ObservationTree() {
  24                 this(null, null, null);
  25         }
  26
  27         private ObservationTree(ObservationTree<I,O> parent, I parentInput, O parentOutput) {
  28                 this.children = new HashMap<>();
  29                 this.outputs = new HashMap<>();
  30                 this.parent = parent;
  31                 this.parentInput = parentInput;
  32                 this.parentOutput = parentOutput;
  33         }
  34
  35         /**
  36          * @return The outputs observed from the root of the tree until this node
  37          */
  38         private List<O> getOutputChain() {
  39                 if (this.parent == null) {
  40                         return new LinkedList<O>();
  41                 } else {
  42                         List<O> parentChain = this.parent.getOutputChain();
  43                         parentChain.add(parentOutput);
  44                         return parentChain;
  45                 }
  46         }
  47
  48         private List<I> getInputChain() {
  49                 if (this.parent == null) {
  50                         return new LinkedList<I>();
  51                 } else {
  52                         List<I> parentChain = this.parent.getInputChain();
  53                         parentChain.add(this.parentInput);
  54                         return parentChain;
  55                 }
  56         }
  57
  58         /**
  59          * Add one input and output symbol and traverse the tree to the next node
  60          * @param input
  61          * @param output
  62          * @return the next node
  63          * @throws InconsistencyException
  64          */
  65         public ObservationTree<I,O> addObservation(I input, O output) throws CacheInconsistencyException {
  66                 O previousOutput = this.outputs.get(input);
  67                 boolean createNewBranch = previousOutput == null;
  68                 if (createNewBranch) {
  69                         // input hasn't been queried before, make a new branch for it and traverse
  70                         this.outputs.put(input, output);
  71                         ObservationTree<I,O> child = new ObservationTree<I,O>(this, input, output);
  72                         this.children.put(input, child);
  73                         return child;
  74                 } else if (!previousOutput.equals(output)) {
  75                         // input is inconsistent with previous observations, throw exception
  76                         List<O> oldOutputChain = this.children.get(input).getOutputChain();
  77                         List<O> newOutputChain = this.getOutputChain();
  78                         List<I> inputChain = this.getInputChain();
  79                         newOutputChain.add(output);
  80                         throw new CacheInconsistencyException(toWord(inputChain), toWord(oldOutputChain), toWord(newOutputChain));
  81                 } else {
  82                         // input is consistent with previous observations, just traverse
  83                         return this.children.get(input);
  84                 }
  85         }
  86
  87         /**
  88          * Add Observation to the tree
  89          * @param inputs
  90          * @param outputs
  91          * @throws CacheInconsistencyException Inconsistency between new and stored observations
  92          */
  93         public void addObservation(Word<I> inputs, Word<O> outputs) throws CacheInconsistencyException {
  94                 addObservation(inputs.asList(), outputs.asList());
  95         }
  96
  97
  98         public void addObservation(List<I> inputs, List<O> outputs) throws CacheInconsistencyException {
  99                 if (inputs.isEmpty() && outputs.isEmpty()) {
 100                         return;
 101                 } else if (inputs.isEmpty() || outputs.isEmpty()) {
 102                         throw new RuntimeException("Input and output words should have the same length:\n" + inputs + "\n" + outputs);
 103                 } else {
 104                         I firstInput = inputs.get(0);
 105                         O firstOutput = outputs.get(0);
 106                         try {
 107                                 this.addObservation(firstInput, firstOutput)
 108                                         .addObservation(inputs.subList(1, inputs.size()), outputs.subList(1, outputs.size()));
 109                         } catch (CacheInconsistencyException e) {
 110                                 throw new CacheInconsistencyException(toWord(inputs), e.getOldOutput(), toWord(outputs));
 111                         }
 112                 }
 113         }
 114
 115         public static<T> Word<T> toWord(List<T> symbolList) {
 116                 return Word.fromList(symbolList);
 117         }
 118 }