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 */
017/**
018 * 
019 */
020package net.automatalib.util.minimizer;
021
022import java.util.ArrayList;
023import java.util.List;
024
025import net.automatalib.commons.smartcollections.BasicLinkedListEntry;
026import net.automatalib.commons.smartcollections.ElementReference;
027import net.automatalib.commons.smartcollections.IntrusiveLinkedList;
028import net.automatalib.commons.smartcollections.UnorderedCollection;
029
030
031
032/**
033 * A block in the partition calculated during minimization.
034 * <p>
035 * At the end of the minimization process, all states in the same block may
036 * be identified.
037 * 
038 * @author Malte Isberner <malte.isberner@gmail.com>
039 *
040 * @param <S> state class.
041 * @param <L> transition label class.
042 */
043public final class Block<S,L> extends BasicLinkedListEntry<Block<S,L>,Block<S,L>> {
044        // The states contained in this block
045        private final UnorderedCollection<State<S,L>> states;
046        
047        // The references for both the partition and splitter collection.
048        private ElementReference partitionReference,
049                splitterQueueReference;
050
051        // The bucket of this block, used for initially arranging the
052        // states ordered by their respective blocks during the weak sort.
053        private IntrusiveLinkedList<State<S,L>> bucket
054                = new IntrusiveLinkedList<State<S,L>>();
055        
056        // The sub blocks, i.e., the new blocks that result from
057        // splitting this block.
058        private List<UnorderedCollection<State<S,L>>>
059                subBlocks = new ArrayList<UnorderedCollection<State<S,L>>>();
060        
061        // The total number of elements in all sub blocks, this is used
062        // to detect whether an actual split has to be performed.
063        private int elementsInSubBlocks;
064        
065        // The sub block currently being created.
066        private UnorderedCollection<State<S,L>> currSubBlock;
067        
068        private final int id;
069        
070        /**
071         * Constructor.
072         */
073        Block(int id) {
074                this.id = id;
075                this.states = new UnorderedCollection<State<S,L>>();
076        }
077        
078        /**
079         * Constructor.
080         * @param states creates a block for the given collection of states.
081         * Ownership of this collection is assumed.
082         */
083        Block(int id, UnorderedCollection<State<S,L>> states) {
084                this.id = id;
085                this.states = states;
086                for(State<S,L> state : states)
087                        state.setBlock(this);
088        }
089        
090        /**
091         * Adds a state to this block.
092         * @param state the state to add.
093         */
094        void addState(State<S,L> state) {
095                ElementReference ref = states.referencedAdd(state);
096                state.setBlockReference(ref);
097                state.setBlock(this);
098        }
099        
100        /**
101         * Retrieves the collection of states in this block. 
102         * @return the states in this block.
103         */
104        UnorderedCollection<State<S,L>> getStates() {
105                return states;
106        }
107        
108        /**
109         * Retrieves the bucket of this block.
110         * @return this blocks bucket.
111         */
112        IntrusiveLinkedList<State<S,L>> getBucket() {
113                return bucket;
114        }
115        
116        /**
117         * Adds a state to this blocks bucket.
118         * @param state the state to add.
119         * @return <code>true</code> iff this was the first state to be added
120         * to the bucket, <code>false</code> otherwise.
121         */
122        boolean addToBucket(State<S,L> state) {
123                boolean first = bucket.isEmpty();
124                bucket.pushBack(state);
125                return first;
126        }
127        
128        /**
129         * Initializes a new sub block.
130         */
131        void createSubBlock() {
132                currSubBlock = new UnorderedCollection<State<S,L>>();
133                subBlocks.add(currSubBlock);
134        }
135        
136        /**
137         * Adds a state to the current sub block.
138         * @param state the state to be added.
139         */
140        void addToSubBlock(State<S,L> state) {
141                currSubBlock.referencedAdd(state);
142                elementsInSubBlocks++;
143        }
144        
145        
146        /**
147         * Retrieves the size of this block, i.e., the number of states it
148         * contains.
149         * @return the size of this block.
150         */
151        public int size() {
152                return states.size();
153        }
154        
155        /**
156         * Retrieves the number of elements contained in sub blocks.
157         * @return the number of elements in sub blocks.
158         */
159        int getElementsInSubBlocks() {
160                return elementsInSubBlocks;
161        }
162
163        /**
164         * Retrieves the {@link ElementReference} that references this block
165         * in the partition collection, for efficient removal.
166         * @return the reference.
167         */
168        ElementReference getPartitionReference() {
169                return partitionReference;
170        }
171
172        /**
173         * Sets the partition reference.
174         * @param partitionReference the reference.
175         */
176        void setPartitionReference(
177                        ElementReference partitionReference) {
178                this.partitionReference = partitionReference;
179        }
180
181        /**
182         * Retrieves the {@link ElementReference} referencing this block in the
183         * splitter collection, for efficient removal. If this block is no
184         * potential splitter, <code>null</code> is returned.
185         * @return the reference or <code>null</code>.
186         */
187        ElementReference getSplitterQueueReference() {
188                return splitterQueueReference;
189        }
190
191        /**
192         * Sets the splitter queue reference.
193         * @param splitterQueueReference the reference
194         */
195        void setSplitterQueueReference(
196                        ElementReference splitterQueueReference) {
197                this.splitterQueueReference = splitterQueueReference;
198        }
199        
200        /**
201         * Removes a state from this block.
202         * @param ref the reference for this state.
203         */
204        void removeState(ElementReference ref) {
205                states.remove(ref);
206        }
207
208        /**
209         * Retrieves the list of sub blocks, if any.
210         * @return the sub blocks.
211         */
212        List<UnorderedCollection<State<S,L>>> getSubBlocks() {
213                return subBlocks;
214        }
215        
216        /**
217         * Resets all sub block information.
218         */
219        void clearSubBlocks() {
220                subBlocks.clear();
221                elementsInSubBlocks = 0;
222        }
223
224        /**
225         * Checks whether or not this block is empty, i.e., contains no states.
226         * @return <code>true</code> iff the block is empty, <code>false</code>
227         * otherwise.
228         */
229        public boolean isEmpty() {
230                return states.isEmpty();
231        }
232        
233        /**
234         * Checks whether or not this block is a singleton, i.e., contains only
235         * a single state.
236         * @return <code>true</code> iff this block is a singleton,
237         * <code>false</code> otherwise.
238         */
239        public boolean isSingleton() {
240                return (states.size() == 1);
241        }
242        
243        
244        /**
245         * Retrieves the ID of this block.
246         * @return the id of this block.
247         */
248        public int getId() {
249                return id;
250        }
251
252        /*
253         * (non-Javadoc)
254         * @see de.ls5.smartcollections.LinkedListEntry#getElement()
255         */
256        @Override
257        public Block<S, L> getElement() {
258                return this;
259        }
260}