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}