← Back to branch summary

~peta-power-group/vide/trunk

« back to all changes in this revision

Viewing changes to net.launchpad.vide.flowchart/src/net/launchpad/vide/algorithm/impl/AlgorithmImpl.java

  • Committer: Dražen Lučanin
  • Date: 2011-03-27 00:48:25 UTC
  • Revision ID: kermit666@gmail.com-20110327004825-caw27z7yxh5nlry0
Made tests for basic if and while. The transformation is successful on them (after a couple of fixes).

Show diffs side-by-side

added added

removed removed

Lines of Context:
net.launchpad.vide.flowchart/src/net/launchpad/vide/algorithm/impl/AlgorithmImpl.java
6
6
 */
7
7
package net.launchpad.vide.algorithm.impl;
8
8
 
 
9
import java.util.ArrayList;
9
10
import java.util.Collection;
 
11
import java.util.HashSet;
 
12
import java.util.List;
 
13
import java.util.Set;
 
14
 
10
15
import net.launchpad.vide.algorithm.Algorithm;
 
16
import net.launchpad.vide.algorithm.AlgorithmFactory;
11
17
import net.launchpad.vide.algorithm.AlgorithmPackage;
 
18
import net.launchpad.vide.algorithm.Block;
 
19
import net.launchpad.vide.algorithm.BlockInfo;
 
20
import net.launchpad.vide.algorithm.BlockType;
 
21
import net.launchpad.vide.algorithm.BooleanExpression;
 
22
import net.launchpad.vide.algorithm.Branch;
 
23
import net.launchpad.vide.algorithm.If;
12
24
import net.launchpad.vide.algorithm.Instruction;
 
25
import net.launchpad.vide.algorithm.SingleInstruction;
 
26
import net.launchpad.vide.algorithm.While;
 
27
import net.launchpad.vide.algorithm.WhileLanguageAlgorithm;
 
28
import net.launchpad.vide.algorithm.WhileLanguageBlock;
13
29
import net.launchpad.vide.algorithm.WhileLanguageInstruction;
14
30
 
15
 
import java.util.ArrayList;
16
 
import java.util.HashSet;
17
 
import java.util.List;
18
 
import java.util.Set;
19
 
 
20
 
import net.launchpad.vide.algorithm.*;
21
 
 
22
 
import net.launchpad.vide.algorithm.WhileLanguageAlgorithm;
23
 
 
24
31
import org.eclipse.core.runtime.Assert;
25
 
import org.eclipse.core.runtime.IStatus;
26
32
import org.eclipse.emf.common.notify.NotificationChain;
27
 
 
28
33
import org.eclipse.emf.common.util.EList;
29
 
 
30
34
import org.eclipse.emf.ecore.EClass;
31
35
import org.eclipse.emf.ecore.InternalEObject;
32
 
 
33
36
import org.eclipse.emf.ecore.impl.EObjectImpl;
34
 
 
35
37
import org.eclipse.emf.ecore.util.EObjectContainmentEList;
36
38
import org.eclipse.emf.ecore.util.InternalEList;
37
39
 
144
146
                destination.getInstructions().addAll(source.getInstructions().subList(indexOfIntersection, lengthOfSource));
145
147
                
146
148
                // delete all the instructions after the intersection from source
147
 
                List<WhileLanguageInstruction> toKeep = source.getInstructions().subList(0, indexOfIntersection-1); 
148
 
                source.getInstructions().addAll(toKeep);
 
149
                source.getInstructions().removeAll(source.getInstructions().subList(indexOfIntersection, lengthOfSource));
 
150
//              List<WhileLanguageInstruction> toKeep = source.getInstructions().subList(0, indexOfIntersection);
 
151
//              source.getInstructions().clear();
 
152
//              source.getInstructions().addAll(toKeep);
149
153
                
150
154
        }
151
155
        
152
156
        /**
153
157
         * <!-- begin-user-doc -->
154
 
         * Recursively process blocks to form a while language representation
 
158
         * Recursively process blocks to form a while language equivalent of an algorithm
155
159
         * <!-- end-user-doc -->
156
160
         * @param instruction - first instruction in the main block
157
161
         * @param processedInstructions - a set of processed instructions (so that no instruction gets processed twice)
164
168
                boolean blockHasOneInstruction= false;
165
169
                Instruction nextInstruction = null;
166
170
                
167
 
                //***********************************************************************
168
 
                // preliminary checks - stop processing if reached processed instructions
169
 
                //***********************************************************************
170
 
                if (processedInstructions.contains(instruction)){
171
 
                        // we encountered the curious and ambiguous case of a block pointing to some previous block
172
 
                        // this could mean: end of an if-branch, a loop or a constraint-breech (e.g. an endless loop or something worse)
173
 
                        if (instruction instanceof Branch){
174
 
                                if ((Branch)instruction == currentBlockInfo.getParentBranch() && currentBlockInfo.getType() == BlockType.UNKNOWN_BRANCH){// it's a loop body
175
 
                                        currentBlockInfo.setType(BlockType.LOOP_BODY);
176
 
                                        // we've reached it's body's end so the block is finished
177
 
                                        return currentWhileLanguageBlock;
178
 
                                } else if ((currentBlockInfo.getType() == BlockType.IF_BODY_FALSE)) {// it's a false body of the loop
 
171
                // check to see the block is not empty
 
172
                if (instruction!=null)
 
173
                        blockHasOneInstruction = true;
 
174
                //******************************************
 
175
                // processing instructions further in depth
 
176
                //******************************************
 
177
                while (instruction!=null){
 
178
                        //some special case data...
 
179
                        boolean needsTransferFromIfBranch = false;
 
180
                        Instruction childrenIntersection = null;
 
181
                        
 
182
                        // check to see that we haven't found a backward connection
 
183
                        if (!processedInstructions.contains(instruction)){
 
184
                                // make a note that we're processing this instruction
 
185
                                // (for detection of backward pointers)
 
186
                                processedInstructions.add(instruction);
 
187
                                
 
188
                                //---------------------------
 
189
                                // process single instruction
 
190
                                //---------------------------
 
191
                                if (instruction instanceof Block){// it's just a block, nothing too complicated
 
192
                                        // create equivalent WL instruction
 
193
                                        equivalentWhileLanguageInstruction = AlgorithmFactory.eINSTANCE.createSingleInstruction();
 
194
                                        ((SingleInstruction)equivalentWhileLanguageInstruction).setCommand(((Block)instruction).getCommands());
 
195
                                        // see what instruction we'll process next
 
196
                                        nextInstruction = ((Block) instruction).getNext();
 
197
                                        
 
198
                                } else if (instruction instanceof Branch){
 
199
                                        Branch branch = (Branch)instruction;
 
200
                                        BooleanExpression condition = AlgorithmFactory.eINSTANCE.createBooleanExpression();
 
201
                                        condition.setCommand(branch.getCondtion());
 
202
                                        
 
203
                                        //----------------------
 
204
                                        // process true branch
 
205
                                        // - we don't know if it's an IF or a WHILE
 
206
                                        //----------------------
 
207
                                        //prepare information for the child
 
208
                                        BlockInfo childBlockInfo = AlgorithmFactory.eINSTANCE.createBlockInfo();
 
209
                                        childBlockInfo.setParentBranch(branch);
 
210
                                        childBlockInfo.setDepth(currentBlockInfo.getDepth()+1);
 
211
                                        childBlockInfo.setType(BlockType.UNKNOWN_BRANCH);
 
212
                                        
 
213
                                        WhileLanguageBlock trueBlock = processInstructionBlock(branch.getTrue(), processedInstructions, childBlockInfo);
 
214
                                        if (childBlockInfo.getType() == BlockType.LOOP_BODY){//further child processing told us it is a WHILE
 
215
                                                // it's a loop
 
216
                                                //.............
 
217
                                                equivalentWhileLanguageInstruction = AlgorithmFactory.eINSTANCE.createWhile();
 
218
                                                ((While)equivalentWhileLanguageInstruction).setCondition(condition);
 
219
                                                // the true block is the loop's body (the next command after the loop will be set later like for a normal single instruction)
 
220
                                                ((While)equivalentWhileLanguageInstruction).setBody(trueBlock);
 
221
                                                // we continue the program after the while is not true any more
 
222
                                                nextInstruction=branch.getFalse();
 
223
                                        } else if (childBlockInfo.getType() == BlockType.IF_BODY_TRUE){//further child processing told us it is an IF
 
224
                                                // it's an if-branch
 
225
                                                //..................
 
226
                                                equivalentWhileLanguageInstruction = AlgorithmFactory.eINSTANCE.createIf();
 
227
                                                If whileLanguageIf = (If)equivalentWhileLanguageInstruction;
 
228
                                                whileLanguageIf.setCondition(condition);
 
229
                                                // there has to be a true branch - diagram constraint
 
230
                                                whileLanguageIf.setTrue(trueBlock);
 
231
                                                if (branch.getFalse()!=null){
 
232
                                                        //----------------------
 
233
                                                        // process false branch
 
234
                                                        // - we know it's an IF - the false block needs to be processed to find where the IF ends
 
235
                                                        //----------------------
 
236
                                                        childBlockInfo.setType(BlockType.IF_BODY_FALSE);
 
237
                                                        WhileLanguageBlock falseBlock = processInstructionBlock(branch.getFalse(), processedInstructions, childBlockInfo);
 
238
                                                        whileLanguageIf.setFalse(falseBlock);
 
239
                                                        needsTransferFromIfBranch = true;
 
240
                                                        childrenIntersection = childBlockInfo.getEndOfIF();
 
241
                                                        
 
242
                                                } else {
 
243
                                                        // no else block, which means everything else happens in the (processed) true branch - processing is finished
 
244
                                                        nextInstruction=null;
 
245
                                                }
 
246
                                        }
 
247
                                                
 
248
                                }
 
249
                                
 
250
                                //-------------------------------------------------------
 
251
                                // finalizing the instruction transformation & adding it
 
252
                                //-------------------------------------------------------
 
253
                                // a pointer to know where the new command was created from
 
254
                                equivalentWhileLanguageInstruction.setTransformedFrom(instruction);
 
255
                                // we add the command's while language equivalent to the current block
 
256
                                currentWhileLanguageBlock.getInstructions().add(equivalentWhileLanguageInstruction);
 
257
                                if (needsTransferFromIfBranch){
 
258
                                        transferToDifferentBlockAllAfterIntersection(childrenIntersection, ((If)equivalentWhileLanguageInstruction).getTrue(), currentWhileLanguageBlock);
 
259
                                        nextInstruction = null; // because the true branch already processed all the following instructions
 
260
                                }
 
261
                                
 
262
                                // and we move on to the next instruction
 
263
                                instruction = nextInstruction;
 
264
                                
 
265
                        } else {
 
266
                                //************************************************************************************
 
267
                                // preliminary checks failed - stop processing, because processed instruction reached
 
268
                                //************************************************************************************
 
269
                                // we encountered the curious and ambiguous case of a block pointing to some previous block
 
270
                                // this could mean: end of an if-branch, a loop or a constraint-breech (e.g. an endless loop or something worse)
 
271
                                
 
272
                                //let's first check for an if-branch
 
273
                                if ((currentBlockInfo.getType() == BlockType.IF_BODY_FALSE)) {// it's a false body of the loop
179
274
                                        // we tell our parent what's the intersection of the true and false branches
180
275
                                        currentBlockInfo.setEndOfIF(instruction);
181
276
                                        //TODO: check whether this intersection was processed on the same depth on both sides 
182
277
                                        // and we return the (now processed) false branch
183
278
                                        return currentWhileLanguageBlock;
 
279
                                }
 
280
                                
 
281
                                // ok, then it's gotta be a loop
 
282
                                if (instruction instanceof Branch){
 
283
                                        if ((Branch)instruction == currentBlockInfo.getParentBranch() && currentBlockInfo.getType() == BlockType.UNKNOWN_BRANCH){// it's a loop body
 
284
                                                currentBlockInfo.setType(BlockType.LOOP_BODY);
 
285
                                                // we've reached it's body's end so the block is finished
 
286
                                                return currentWhileLanguageBlock;
 
287
                                        } else {
 
288
                                                //TODO: constraint breach
 
289
                                                System.out.println("Loops can only lead to the last branch on this depth!");
 
290
                                        }
184
291
                                } else {
185
 
                                        throw new UnknownError("this should never occur");
186
 
                                }
187
 
                        } else {
188
 
                                //TODO: constraint breach
189
 
                                System.out.println("Looping back to a processed normal instruction is not allowed!");
190
 
                        }
191
 
                                
192
 
                }
193
 
                
194
 
                while (instruction!=null){
195
 
                        blockHasOneInstruction = true;
196
 
                        
197
 
                        //******************************************
198
 
                        // processing instructions further in depth
199
 
                        //******************************************
200
 
                        if (instruction instanceof Block){// it's just a block, nothing too complicated
201
 
                                // create equivalent WL instruction
202
 
                                equivalentWhileLanguageInstruction = AlgorithmFactory.eINSTANCE.createSingleInstruction();
203
 
                                ((SingleInstruction)equivalentWhileLanguageInstruction).setCommand(((Block)instruction).getCommands());
204
 
                                // see what instruction we'll process next
205
 
                                nextInstruction = ((Block) instruction).getNext();
206
 
                                
207
 
                        } else if (instruction instanceof Branch){
208
 
                                Branch branch = (Branch)instruction;
209
 
                                
210
 
                                //----------------------
211
 
                                // process true branch
212
 
                                // - we don't know if it's an IF or a WHILE
213
 
                                //----------------------
214
 
                                //prepare information for the child
215
 
                                BlockInfo childBlockInfo = AlgorithmFactory.eINSTANCE.createBlockInfo();
216
 
                                childBlockInfo.setParentBranch(branch);
217
 
                                childBlockInfo.setDepth(currentBlockInfo.getDepth()+1);
218
 
                                childBlockInfo.setType(BlockType.UNKNOWN_BRANCH);
219
 
                                
220
 
                                WhileLanguageBlock trueBlock = processInstructionBlock(branch.getTrue(), processedInstructions, childBlockInfo);
221
 
                                if (childBlockInfo.getType() == BlockType.LOOP_BODY){//further child processing told us it is a WHILE
222
 
                                        // it's a loop
223
 
                                        equivalentWhileLanguageInstruction = AlgorithmFactory.eINSTANCE.createWhile();
224
 
                                        // the true block is the loop's body (the next command after the loop will be set later like for a normal single instruction)
225
 
                                        ((While)equivalentWhileLanguageInstruction).setBody(trueBlock);
226
 
                                        // we continue the program after the while is not true any more
227
 
                                        nextInstruction=branch.getFalse();
228
 
                                } else if (childBlockInfo.getType() == BlockType.IF_BODY_TRUE){//further child processing told us it is an IF
229
 
                                        equivalentWhileLanguageInstruction = AlgorithmFactory.eINSTANCE.createIf();
230
 
                                        If whileLanguageIf = (If)equivalentWhileLanguageInstruction;
231
 
                                        // there has to be a true branch - diagram constraint
232
 
                                        whileLanguageIf.setTrue(trueBlock);
233
 
                                        if (branch.getFalse()!=null){
234
 
                                                //----------------------
235
 
                                                // process false branch
236
 
                                                // - we know it's an IF - the false block needs to be processed to find where the IF ends
237
 
                                                //----------------------
238
 
                                                childBlockInfo.setType(BlockType.IF_BODY_FALSE);
239
 
                                                WhileLanguageBlock falseBlock = processInstructionBlock(branch.getFalse(), processedInstructions, childBlockInfo);
240
 
                                                whileLanguageIf.setFalse(falseBlock);
241
 
                                                transferToDifferentBlockAllAfterIntersection(childBlockInfo.getEndOfIF(), trueBlock, currentWhileLanguageBlock);
242
 
                                                
243
 
                                        } else {
244
 
                                                // no else block, which means everything else happens in the (processed) true branch - processing is finished
245
 
                                                nextInstruction=null;
246
 
                                        }
247
 
                                }
248
 
                                        
249
 
                        }
250
 
                        
251
 
                        //***********************************************************************
252
 
                        // finalizing the instruction transformation, before we go to the next one
253
 
                        //***********************************************************************
254
 
                        // we finished processing this instruction
255
 
                        processedInstructions.add(instruction);
256
 
                        // a pointer to know where the new command was created from
257
 
                        equivalentWhileLanguageInstruction.setTransformedFrom(instruction);
258
 
                        // we add the command's while language equivalent to the current block
259
 
                        currentWhileLanguageBlock.getInstructions().add(equivalentWhileLanguageInstruction);
260
 
                        // and we move on to the next instruction
261
 
                        instruction = nextInstruction;
 
292
                                        //TODO: constraint breach
 
293
                                        System.out.println("Looping back to a processed normal instruction is not allowed!");
 
294
                                }
 
295
                        }
262
296
                }
263
297
                
264
298
                //---------------------