001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib 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 * AutomataLib 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 AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.util.minimizer;
018
019import java.util.Collection;
020
021import net.automatalib.commons.util.mappings.Mapping;
022
023
024
025/**
026 * The result structure of a minimization process. The result of a minimization
027 * process is a partition on the original set of states. This is represented
028 * by a collection of {@link Block}s containing states that are equivalent
029 * and thus can be merged.
030 * <p>
031 * Since all states in a block are equivalent (and thus especially have the
032 * same set of outgoing edge labels), a minimized automaton can be created
033 * from this partition by instantiating a state for each block. The edges
034 * between those states are created in the following way: For each state/block,
035 * an original state is chosen arbitrarily from this block. The edges are
036 * created according to the edges of this state, only that they point to
037 * the states representing the blocks the respective target states belong to
038 * (using {@link #getBlockForState(Object)}).
039 * <p>
040 * The blocks in the result partition are guaranteed to have contiguous IDs
041 * (see {@link Block#getId()}), starting at 0. This allows an efficient
042 * construction of the resulting automaton.
043 * <p>
044 * A more convenient way to obtain a representation of the resulting, minimized
045 * automaton is using a {@link BlockAutomaton}.
046 * 
047 * @author Malte Isberner <malte.isberner@gmail.com>
048 *
049 * @param <S> state class.
050 * @param <L> transition label class.
051 */
052public final class MinimizationResult<S, L> {
053        // the state storage, used for retrieving the State records
054        // for an original state
055        private final Mapping<S,State<S,L>> stateStorage;
056        // the blocks in the final partition
057        private final Collection<Block<S,L>> blocks;
058        
059        /**
060         * Constructor.
061         * @param stateStorage the state storage,
062         * @param blocks the final partition.
063         */
064        MinimizationResult(Mapping<S,State<S,L>> stateStorage,
065                        Collection<Block<S,L>> blocks) {
066                this.stateStorage = stateStorage;
067                this.blocks = blocks;
068        }
069        
070        /**
071         * Retrieves the number of blocks in the final partition.
072         * @return the number of blocks.
073         */
074        public int getNumBlocks() {
075                return blocks.size();
076        }
077        
078        /**
079         * Retrieves all blocks in the final partition.
080         * @return the final partition.
081         */
082        public Collection<Block<S,L>> getBlocks() {
083                return blocks;
084        }
085        
086        
087        /**
088         * Retrieves all (original) states in a block.
089         * @param block the block.
090         * @return a collection containing all original states in this
091         * block.
092         */
093        public static <S,L> Collection<S> getStatesInBlock(Block<S,L> block) {
094                return new OriginalStateCollection<S>(block.getStates());
095        }
096        
097        /**
098         * Chooses a representative (i.e., an arbitrary element of the
099         * set of states) from a block.
100         * @param block the block.
101         * @return an arbitrary element of the state set of the given block.
102         */
103        public S getRepresentative(Block<S,L> block) {
104                return block.getStates().choose().getOriginalState();
105        }
106        
107        /**
108         * Retrieves the block to which a given original state belongs.
109         * @param origState the original state.
110         * @return the corresponding block.
111         */
112        public Block<S,L> getBlockForState(S origState) {
113                State<S,L> state = stateStorage.get(origState);
114                return state.getBlock();
115        }
116        
117        /**
118         * Creates a {@link BlockAutomaton} using this results structure.
119         * @return the block automaton.
120         */
121        public BlockAutomaton<S,L> asBlockAutomaton() {
122                return new BlockAutomaton<S, L>(this);
123        }
124}