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.algorithms.lstargeneric.closing;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import net.automatalib.commons.util.comparison.CmpUtil;
023import net.automatalib.words.Alphabet;
024
025import de.learnlib.algorithms.lstargeneric.table.ObservationTable;
026import de.learnlib.algorithms.lstargeneric.table.Row;
027import de.learnlib.api.MembershipOracle;
028
029/**
030 * Collection of predefined observation table closing strategies.
031 * 
032 * @see ClosingStrategy
033 * 
034 * @author Malte Isberner <malte.isberner@gmail.com>
035 *
036 */
037public class ClosingStrategies {
038        
039        /**
040         * Closing strategy that randomly selects one representative row to close from each equivalence
041         * class.
042         */
043        public static final ClosingStrategy<Object,Object> CLOSE_RANDOM
044                = new CloseRandomStrategy();
045        
046        /**
047         * Closing strategy that selects the first row from each equivalence class as representative.
048         */
049        public static final ClosingStrategy<Object,Object> CLOSE_FIRST
050                = new ClosingStrategy<Object,Object>() {
051                        @Override
052                        public <RI, RO> List<Row<RI>> selectClosingRows(
053                                        List<List<Row<RI>>> unclosedClasses,
054                                        ObservationTable<RI, RO> table,
055                                        MembershipOracle<RI, RO> oracle) {
056                                List<Row<RI>> result = new ArrayList<Row<RI>>(unclosedClasses.size());
057                                for(List<Row<RI>> clazz : unclosedClasses)
058                                        result.add(clazz.get(0));
059                                return result;
060                        }
061        };
062        
063        /**
064         * Closing strategy that selects the shortest row of each equivalence class (more precisely:
065         * a row which's prefix has minimal length in the respective class) as representative. 
066         */
067        public static final ClosingStrategy<Object,Object> CLOSE_SHORTEST
068                = new ClosingStrategy<Object,Object>() {
069                        @Override
070                        public <RI, RO> List<Row<RI>> selectClosingRows(
071                                        List<List<Row<RI>>> unclosedClasses,
072                                        ObservationTable<RI, RO> table,
073                                        MembershipOracle<RI, RO> oracle) {
074                                
075                                List<Row<RI>> result = new ArrayList<Row<RI>>();
076                                for(List<Row<RI>> clazz : unclosedClasses) {
077                                        Row<RI> shortest = null;
078                                        int shortestLen = Integer.MAX_VALUE;
079                                        for(Row<RI> row : clazz) {
080                                                int prefixLen = row.getPrefix().length();
081                                                if(shortest == null || prefixLen < shortestLen) {
082                                                        shortest = row;
083                                                        shortestLen = prefixLen;
084                                                }
085                                        }
086                                        result.add(shortest);
087                                }
088                                return result;
089                        }
090        };
091        
092        /**
093         * Closing strategy that selects the lexicographically minimal row (wrt. its prefix)
094         * of each equivalence class as representative.
095         */
096        public static final ClosingStrategy<Object,Object> CLOSE_LEX_MIN
097                = new ClosingStrategy<Object,Object>() {
098                        @Override
099                        public <RI, RO> List<Row<RI>> selectClosingRows(
100                                        List<List<Row<RI>>> unclosedClasses,
101                                        ObservationTable<RI, RO> table,
102                                        MembershipOracle<RI, RO> oracle) {
103                                List<Row<RI>> result = new ArrayList<Row<RI>>(unclosedClasses.size());
104                                Alphabet<RI> alphabet = table.getInputAlphabet();
105                                for(List<Row<RI>> clazz : unclosedClasses) {
106                                        Row<RI> lexMin = null;
107                                        for(Row<RI> row : clazz) {
108                                                if(lexMin == null)
109                                                        lexMin = row;
110                                                else if(CmpUtil.lexCompare(row.getPrefix(), lexMin.getPrefix(), alphabet) < 0)
111                                                        lexMin = row;
112                                        }
113                                        result.add(lexMin);
114                                }
115                                return result;
116                        }
117        };
118
119}