API tools faq
paste
Advertisement
bekovski

ppbs_generator2

bekovski
Aug 8th, 2018
80
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 22.95 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  * PPBSGenerator.java
  3.  * Bekir Özkara, 2018 for the Animal project at TU Darmstadt.
  4.  * Copying this file for educational purposes is permitted without further authorization.
  5.  */
  6. //package generators.sorting;
  7. package pivot;
  8.  
  9. import java.awt.Color;
  10. import java.util.Hashtable;
  11. import java.util.Locale;
  12.  
  13. import algoanim.animalscript.AnimalScript;
  14. import algoanim.counter.model.TwoValueCounter;
  15. import algoanim.counter.view.TwoValueView;
  16. import algoanim.primitives.ArrayMarker;
  17. import algoanim.primitives.IntArray;
  18. import algoanim.primitives.SourceCode;
  19. import algoanim.primitives.generators.Language;
  20. import algoanim.properties.AnimationPropertiesKeys;
  21. import algoanim.properties.ArrayMarkerProperties;
  22. import algoanim.properties.ArrayProperties;
  23. import algoanim.properties.CounterProperties;
  24. import algoanim.properties.RectProperties;
  25. import algoanim.properties.SourceCodeProperties;
  26. import algoanim.properties.TextProperties;
  27. import algoanim.util.Coordinates;
  28. import algoanim.util.TicksTiming;
  29. import algoanim.util.Timing;
  30. import animal.main.Animal;
  31. import generators.framework.Generator;
  32. import generators.framework.GeneratorType;
  33. import generators.framework.properties.AnimationPropertiesContainer;
  34. import pivotHelper.Manager;
  35.  
  36. public class PPBSGenerator implements Generator {
  37.     private Language lang;
  38.    
  39.     // algorithm related
  40.     private int pivot;
  41.     private int[] intArray;
  42.    
  43.     Timing timing = new TicksTiming(15);
  44.     SourceCode scInit;
  45.     SourceCode scPartition;
  46.    
  47.     // m1 - 1       elements in list are less than pivot
  48.     // m2 - m1      elements are equal to pivot
  49.     // n - m2 + 1   elements greater than pivot (where n = list.size()-1)
  50.     private ArrayMarker m1;
  51.     private ArrayMarker m2;
  52.    
  53.     // before and after each iteration:
  54.     // 1.   1 <= i1 <= m1 <= i2 <= m2 <= i3 <= n+1
  55.     // 2.   S[j] < pivot for j in (1, ..., i1-1),  if i1 < m1: S[i1] >= pivot
  56.     // 3.   S[j] = pivot for j in (m1, ..., i2-1), if i2 < m2: S[i2] != pivot
  57.     // 4.   S[j] > pivot for j in (m2, ..., i3-1), if i3 <= n: S[i3] <= pivot
  58.     private ArrayMarker i1;
  59.     private ArrayMarker i2;
  60.     private ArrayMarker i3;
  61.    
  62.     // j is used in the for loops for setting m1, m2
  63.     private ArrayMarker j;
  64.    
  65.    
  66.    
  67.     // array marker props
  68.     private ArrayMarkerProperties m1MarkerProps;
  69.     private ArrayMarkerProperties m2MarkerProps;
  70.     private ArrayMarkerProperties i1MarkerProps;
  71.     private ArrayMarkerProperties i2MarkerProps;
  72.     private ArrayMarkerProperties i3MarkerProps;
  73.     private ArrayMarkerProperties jMarkerProps;
  74.     // array props
  75.     private ArrayProperties arrayProps;
  76.     // text props (general)
  77.     private TextProperties textProps;
  78.     // source code props
  79.     private SourceCodeProperties sourceCodeProps;
  80.     // box props with text
  81.     private RectProperties boxProps;
  82.     private TextProperties textBoxProps;
  83.     // pivot and result text props
  84.     private TextProperties pivotTextProps;
  85.     private TextProperties resultTextProps;
  86.     // # iterations text
  87.     private TextProperties iterationTextProps;
  88.     // counter props
  89.     private CounterProperties counterProps;
  90.    
  91.     // own values
  92.         private Color i1Color;
  93.         private Color i2Color;
  94.         private Color i3Color;
  95.        
  96.         TwoValueCounter counter;
  97.         TwoValueView view;
  98.    
  99.  
  100.     public void init(){
  101.         lang = new AnimalScript("Pivot Partitioning By Scanning", "Bekir Özkara", 640, 480);
  102.         lang.setStepMode(true);
  103.        
  104.         Manager.lang = lang;
  105.     }
  106.    
  107.     public static void main(String[] args) {
  108.         Generator generator = new PPBSGenerator();
  109.         Animal.startGeneratorWindow(generator);
  110.     }
  111.  
  112.     public String generate(AnimationPropertiesContainer props,Hashtable<String, Object> primitives) {
  113.        
  114.         pivot = (Integer)primitives.get("pivot");
  115.         intArray = (int[])primitives.get("intArray");
  116.        
  117.         m1MarkerProps = (ArrayMarkerProperties)props.getPropertiesByName("m1MarkerProps");
  118.         m2MarkerProps = (ArrayMarkerProperties)props.getPropertiesByName("m2MarkerProps");
  119.         i1MarkerProps = (ArrayMarkerProperties)props.getPropertiesByName("i1MarkerProps");
  120.         i2MarkerProps = (ArrayMarkerProperties)props.getPropertiesByName("i2MarkerProps");
  121.         i3MarkerProps = (ArrayMarkerProperties)props.getPropertiesByName("i3MarkerProps");
  122.         jMarkerProps = (ArrayMarkerProperties)props.getPropertiesByName("jMarkerProps");
  123.         arrayProps = (ArrayProperties)props.getPropertiesByName("arrayProps");
  124.         textProps = (TextProperties)props.getPropertiesByName("textProps");
  125.         sourceCodeProps = (SourceCodeProperties)props.getPropertiesByName("sourceCodeProps");
  126.         boxProps = (RectProperties)props.getPropertiesByName("boxProps");
  127.         textBoxProps = (TextProperties)props.getPropertiesByName("textBoxProps");
  128.         pivotTextProps = (TextProperties)props.getPropertiesByName("pivotTextProps");
  129.         resultTextProps = (TextProperties)props.getPropertiesByName("resultTextProps");
  130.        
  131.         // end auto
  132.         counterProps = new CounterProperties();
  133.         counterProps.set(AnimationPropertiesKeys.FILL_PROPERTY, Color.BLUE);
  134.         counterProps.set(AnimationPropertiesKeys.FILLED_PROPERTY, true);
  135.        
  136.         iterationTextProps = pivotTextProps;
  137.        
  138.         i1Color = (Color)i1MarkerProps.get(AnimationPropertiesKeys.COLOR_PROPERTY);
  139.         i2Color = (Color)i2MarkerProps.get(AnimationPropertiesKeys.COLOR_PROPERTY);
  140.         i3Color = (Color)i3MarkerProps.get(AnimationPropertiesKeys.COLOR_PROPERTY);
  141.        
  142.         // main()
  143.         Manager.makeTitle();
  144.        
  145.         showIntroText();
  146.        
  147. //      int[] arr = new int[] {11, 20, 19, 21, 13, 19, 15};
  148. //      int pivot = 19;
  149. //      pivot = 13;
  150.        
  151.         ppbs(intArray, pivot);  // use Animal-provided values instead
  152.        
  153.         Manager.hideArrayMarker(i1);
  154.         Manager.hideArrayMarker(i2);
  155.         Manager.hideArrayMarker(i3);
  156.         lang.nextStep();
  157.        
  158.         Manager.clear();
  159.         showOutroText();
  160.        
  161.         return lang.toString();
  162.     }
  163.  
  164.     private void showIntroText() {
  165.         Manager.showIntroText(textProps);
  166.         lang.nextStep("Introduction");
  167.         Manager.clear();
  168.     }
  169.    
  170.     private void showOutroText() {
  171.         Manager.showOutroText(textProps);
  172.         lang.nextStep("Outro");
  173.     }
  174.    
  175.    
  176.     // variant: at least one of i1, i2, i3 is increased by at least 1, none of them is decreased
  177.     // break condition: i1 == m1 && i2 == m2 && i3 == n + 1
  178.     private void ppbs(int[] arr, int pivot) {
  179.         IntArray array = lang.newIntArray(new Coordinates(400, 250), arr, "array", null, arrayProps);
  180.         Manager.addToClearList(array);
  181.        
  182.         counter = lang.newCounter(array);
  183.         view = lang.newCounterView(counter, new Coordinates(400, 100), counterProps, true, true);
  184.        
  185.         int pivotX = 600;
  186.         int pivotY = 350;
  187.         Manager.makePivotText(pivot, pivotX, pivotY, pivotTextProps);
  188.        
  189.         // this dummy array is needed to make i3 point one past the last element at the end (it will not be shown though)
  190.         int[] dummyArr = new int[arr.length+1];
  191.         for(int i=0; i < arr.length; ++i) {
  192.             dummyArr[i] = arr[i];
  193.         }
  194.         IntArray dummyArray = lang.newIntArray(new Coordinates(400, 250), dummyArr, "dummyArray", null, arrayProps);
  195.         dummyArray.hide();
  196.        
  197.         Manager.makeBox(400, 350, 550, 450, boxProps);
  198.        
  199.         // init
  200.         showSourceCodeInit();
  201.        
  202.         scInit.highlight(0);
  203.         lang.nextStep("Init");
  204.        
  205.         m1 = lang.newArrayMarker(array, 0, "m1", null, m1MarkerProps);
  206.         scInit.toggleHighlight(0, 1);
  207.         Manager.addToClearList(m1);
  208.         Manager.makeM1Text(m1.getPosition(), textBoxProps);
  209.         lang.nextStep();
  210.         scInit.unhighlight(1);
  211.  
  212.         j = lang.newArrayMarker(array, 0, "j", null, jMarkerProps);
  213.         for(; j.getPosition() < array.getLength(); j.increment(null, timing)) {
  214.             scInit.highlight(2);
  215.             lang.nextStep();
  216.            
  217.             scInit.toggleHighlight(2, 3);
  218.             if(array.getData(j.getPosition()) < pivot) {
  219.                 lang.nextStep();
  220.                 scInit.highlight(3, 0, true);
  221.                 m1.increment(null, timing);
  222.                 scInit.highlight(4);
  223.                 Manager.makeM1Text(m1.getPosition(), textBoxProps);
  224.             }
  225.            
  226.             // unhighlight if-case
  227.             lang.nextStep();
  228.             scInit.unhighlight(3);
  229.             scInit.unhighlight(4);
  230.         }
  231.         j.hide();
  232.        
  233.         m2 = lang.newArrayMarker(array, m1.getPosition(), "m2", null, m2MarkerProps);
  234.         scInit.highlight(5);
  235.         Manager.addToClearList(m2);
  236.         Manager.makeM2Text(m2.getPosition(), textBoxProps);
  237.         lang.nextStep();
  238.         scInit.unhighlight(5);
  239.  
  240.        
  241.         j = lang.newArrayMarker(array, 0, "j", null, jMarkerProps);
  242.         for(; j.getPosition() < array.getLength(); j.increment(null, timing)) {
  243.             scInit.highlight(6);
  244.             lang.nextStep();
  245.            
  246.             scInit.toggleHighlight(6, 7);
  247.             if(array.getData(j.getPosition()) == pivot) {
  248.                 lang.nextStep();
  249.                 scInit.highlight(7, 0, true);
  250.                 m2.increment(null, timing);
  251.                 scInit.highlight(8);
  252.                 Manager.makeM2Text(m2.getPosition(), textBoxProps);
  253.             }
  254.            
  255.             // unhighlight if-case
  256.             lang.nextStep();
  257.             scInit.unhighlight(7);
  258.             scInit.unhighlight(8);
  259.         }
  260.         j.hide();
  261.        
  262.         i1 = lang.newArrayMarker(array, 0, "i1", null, i1MarkerProps);
  263.         scInit.highlight(9);
  264.         Manager.addToClearList(i1);
  265.         Manager.makeI1Text(i1.getPosition(), textBoxProps);
  266.         lang.nextStep();
  267.        
  268.         i2 = lang.newArrayMarker(array, m1.getPosition(), "i2", null, i2MarkerProps);
  269.         scInit.toggleHighlight(9, 10);
  270.         Manager.addToClearList(i2);
  271.         Manager.makeI2Text(i2.getPosition(), textBoxProps);
  272.         lang.nextStep();
  273.        
  274.         i3 = lang.newArrayMarker(dummyArray, m2.getPosition(), "i3", null, i3MarkerProps);          // TODO: is dummyArray ok?
  275.         scInit.toggleHighlight(10, 11);
  276.         Manager.addToClearList(i3);
  277.         Manager.makeI3Text(i3.getPosition(), textBoxProps);
  278.         lang.nextStep();
  279.        
  280.         scInit.toggleHighlight(11, 12);
  281.         lang.nextStep();
  282.         while(i1.getPosition() < m1.getPosition() && array.getData(i1.getPosition()) < pivot) {
  283.             Manager.highlightCell(array, i1.getPosition(), i1Color);
  284.             i1.increment(null, timing);
  285.             scInit.toggleHighlight(12, 13);
  286.             Manager.makeI1Text(i1.getPosition(), textBoxProps);
  287.             lang.nextStep();
  288.            
  289.             scInit.toggleHighlight(13, 12);
  290.             lang.nextStep();
  291.         }
  292.         scInit.unhighlight(12);
  293.        
  294.         scInit.highlight(14);
  295.         lang.nextStep();
  296.         while(i2.getPosition() < m2.getPosition() && array.getData(i2.getPosition()) == pivot) {
  297.             Manager.highlightCell(array, i2.getPosition(), i2Color);
  298.             i2.increment(null, timing);
  299.             scInit.toggleHighlight(14, 15);
  300.             Manager.makeI2Text(i2.getPosition(), textBoxProps);
  301.             lang.nextStep();
  302.            
  303.             scInit.toggleHighlight(15, 14);
  304.             lang.nextStep();
  305.         }
  306.         scInit.unhighlight(14);
  307.        
  308.         scInit.highlight(16);
  309.         lang.nextStep();
  310.         while(i3.getPosition() < array.getLength() && array.getData(i3.getPosition()) > pivot) {
  311.             Manager.highlightCell(array, i3.getPosition(), i3Color);
  312.             i3.increment(null, timing);
  313.             scInit.toggleHighlight(16, 17);
  314.             Manager.makeI3Text(i3.getPosition(), textBoxProps);
  315.             lang.nextStep();
  316.            
  317.             scInit.toggleHighlight(17, 16);
  318.             lang.nextStep();
  319.         }
  320.         scInit.unhighlight(16);
  321.         // endinit
  322.        
  323.         scInit.hide();
  324.            
  325.         // partitioning
  326.         showSourceCodePartition();
  327.        
  328.         scPartition.highlight(0);
  329.         lang.nextStep("Partition");
  330.        
  331.         scPartition.toggleHighlight(0, 1);
  332.         lang.nextStep();
  333.         int iter = 0;
  334.         while(i1.getPosition() != m1.getPosition() || i2.getPosition() != m2.getPosition() || i3.getPosition() != array.getLength()) {
  335.             Manager.makeIterationText(iter++, pivotX, pivotY + 25, iterationTextProps);
  336.            
  337.             scPartition.toggleHighlight(1, 2);
  338.             lang.nextStep();
  339.            
  340.             if(i1.getPosition() < m1.getPosition()) {
  341.                 // highlight if first
  342.                 scPartition.highlight(2, 0, true);
  343.                 scPartition.highlight(3);
  344.                 lang.nextStep();
  345.                 if(array.getData(i1.getPosition()) == pivot) {
  346. //                      scPartition.unhighlight(2);
  347.                     scPartition.highlight(3, 0, true);
  348.                     scPartition.highlight(4);
  349.                     array.swap(i1.getPosition(), i2.getPosition(), null, timing);   // nextStep before or after swap ???
  350.                     lang.nextStep();
  351.                    
  352.                     scPartition.toggleHighlight(4, 5);
  353.                     while(i2.getPosition() < m2.getPosition() && array.getData(i2.getPosition()) == pivot) {
  354.                         lang.nextStep();
  355.                        
  356.                         Manager.highlightCell(array, i2.getPosition(), i2Color);
  357.                         i2.increment(null, timing);
  358.                         scPartition.toggleHighlight(5, 6);
  359.                         Manager.makeI2Text(i2.getPosition(), textBoxProps);
  360.                        
  361.                         lang.nextStep();
  362.                         scPartition.toggleHighlight(6, 5);
  363.                     }
  364.                     lang.nextStep();
  365.                     scPartition.unhighlight(5); // while()
  366.                     scPartition.unhighlight(3); // if(array[i1] == pivot)
  367.                 }
  368.                 // S[i1] > p
  369.                 else {
  370.                     // unhighlight if and highlight else
  371.                     scPartition.toggleHighlight(3, 8);
  372.                     lang.nextStep();
  373.                    
  374.                     scPartition.highlight(8, 0, true);
  375.                     scPartition.highlight(9);
  376.                     array.swap(i1.getPosition(), i3.getPosition(), null, timing);
  377.                     lang.nextStep();
  378.                    
  379.                     scPartition.toggleHighlight(9, 10);
  380.                     while(i3.getPosition() < array.getLength() && array.getData(i3.getPosition()) > pivot) {
  381.                         lang.nextStep();
  382.                        
  383.                         Manager.highlightCell(array, i3.getPosition(), i3Color);
  384.                         i3.increment(null, timing);
  385.                         scPartition.toggleHighlight(10, 11);
  386.                         Manager.makeI3Text(i3.getPosition(), textBoxProps);
  387.                        
  388.                         lang.nextStep();
  389.                         scPartition.toggleHighlight(11, 10);
  390.                     }
  391.                     lang.nextStep();
  392.                     scPartition.unhighlight(10);    // while()
  393.                     scPartition.unhighlight(8);     // else
  394.                 }
  395.                
  396.                 scPartition.highlight(12);
  397.                 while(i1.getPosition() < m1.getPosition() && array.getData(i1.getPosition()) < pivot) {
  398.                     lang.nextStep();
  399.                    
  400.                     Manager.highlightCell(array, i1.getPosition(), i1Color);
  401.                     i1.increment(null, timing);
  402.                     scPartition.toggleHighlight(12, 13);
  403.                     Manager.makeI1Text(i1.getPosition(), textBoxProps);
  404.                    
  405.                     lang.nextStep();
  406.                     scPartition.toggleHighlight(13, 12);
  407.                 }
  408.                 lang.nextStep();               
  409.                 scPartition.unhighlight(12);    // while()
  410. //                  scPartition.unhighlight(2);     // if(i1 < m1) needed?
  411.             }
  412.             // i1 == m1
  413.             else {
  414.                 // first else case
  415.                 scPartition.toggleHighlight(2, 15);
  416.                 lang.nextStep();
  417.                
  418.                 scPartition.highlight(15, 0, true);
  419.                 scPartition.highlight(16);
  420.                 array.swap(i2.getPosition(), i3.getPosition(), null, timing);
  421.                 lang.nextStep();
  422.                
  423.                 scPartition.toggleHighlight(16, 17);
  424.                 while(i2.getPosition() < m2.getPosition() && array.getData(i2.getPosition()) == pivot) {
  425.                     lang.nextStep();
  426.                    
  427.                     Manager.highlightCell(array, i2.getPosition(), i2Color);
  428.                     i2.increment(null, timing);
  429.                     scPartition.toggleHighlight(17, 18);
  430.                     Manager.makeI2Text(i2.getPosition(), textBoxProps);
  431.                    
  432.                     lang.nextStep();
  433.                     scPartition.toggleHighlight(18, 17);
  434.                 }
  435.                 lang.nextStep();
  436.                
  437.                 scPartition.toggleHighlight(17, 19);
  438.                 while(i3.getPosition() < array.getLength() && array.getData(i3.getPosition()) > pivot) {
  439.                     lang.nextStep();
  440.                    
  441.                     Manager.highlightCell(array, i3.getPosition(), i3Color);
  442.                     i3.increment(null, timing);
  443.                     scPartition.toggleHighlight(19, 20);
  444.                     Manager.makeI3Text(i3.getPosition(), textBoxProps);
  445.                    
  446.                     lang.nextStep();
  447.                     scPartition.toggleHighlight(20, 19);
  448.                 }
  449.                 lang.nextStep();
  450.                 scPartition.unhighlight(19);    // while()
  451.                 scPartition.unhighlight(15);    // else (context)
  452.             }
  453.         } // while()
  454.         Manager.makeIterationText(iter++, pivotX, pivotY + 25, iterationTextProps);
  455.        
  456.         lang.nextStep();
  457.         scPartition.highlight(21);
  458.         Manager.makeResultText(new int[] { m1.getPosition(),  m2.getPosition() }, pivotX, pivotY + 50,  resultTextProps);
  459.     } // ppbs()
  460.    
  461.    
  462.     // ===========================================================================
  463.     // ===========================================================================
  464.     // ===========================================================================
  465.     // ===========================================================================
  466.     // ===========================================================================
  467.     // ===========================================================================
  468.    
  469.     private void showSourceCodeInit() {
  470.         scInit = lang.newSourceCode(new Coordinates(20, 150), "sourceCode", null, sourceCodeProps);
  471.         Manager.addToClearList(scInit);
  472.        
  473.         scInit.addCodeLine("init(A, pivot, m1, m2, i1, i2, i3)", null, 0, null);    // 1
  474.         scInit.addCodeLine("m1 = 0", null, 1, null);                                // 2
  475.         scInit.addCodeLine("for j=0 to A.length-1", null, 1, null);                 // 3
  476.         scInit.addCodeLine("if A[j] < pivot", null, 2, null);                       // 4
  477.         scInit.addCodeLine("m1++", null, 3, null);                                  // 5
  478.         scInit.addCodeLine("m2 = m1", null, 1, null);                               // 6
  479.         scInit.addCodeLine("for j=0 to A.length-1", null, 1, null);                 // 7
  480.         scInit.addCodeLine("if A[j] == pivot", null, 2, null);                      // 8
  481.         scInit.addCodeLine("m2++", null, 3, null);                                  // 9
  482.         scInit.addCodeLine("i1 = 0", null, 1, null);                                // 10
  483.         scInit.addCodeLine("i2 = m1", null, 1, null);                               // 11
  484.         scInit.addCodeLine("i3 = m2", null, 1, null);                               // 12
  485.         scInit.addCodeLine("while i1 < m1 and A[i1] < pivot", null, 1, null);       // 13
  486.         scInit.addCodeLine("i1++", null, 2, null);                                  // 14
  487.         scInit.addCodeLine("while i2 < m2 and A[i2] == pivot", null, 1, null);      // 15
  488.         scInit.addCodeLine("i2++", null, 2, null);                                  // 16
  489.         scInit.addCodeLine("while i3 < A.length and A[i3] > pivot", null, 1, null); // 17
  490.         scInit.addCodeLine("i3++", null, 2, null);                                  // 18
  491.     }
  492.    
  493.     private void showSourceCodePartition() {
  494.         scPartition = lang.newSourceCode(new Coordinates(20, 150), "sourceCode", null, sourceCodeProps);
  495.         Manager.addToClearList(scPartition);
  496.        
  497.         scPartition.addCodeLine("partition(A, pivot, m1, m2, i1, i2, i3)", null, 0, null);      // 1
  498.         scPartition.addCodeLine("while i1 != m1 or i2 != m2 or i3 != A.length", null, 1, null); // 2
  499.         scPartition.addCodeLine("if i1 < m1", null, 2, null);                                   // 3
  500.         scPartition.addCodeLine("if A[i1] == pivot", null, 3, null);                            // 4
  501.         scPartition.addCodeLine("swap A[i1] with A[i2]", null, 4, null);                        // 5
  502.         scPartition.addCodeLine("while i2 < m2 and A[i2] == pivot", null, 4, null);             // 6
  503.         scPartition.addCodeLine("i2++", null, 5, null);                                         // 7
  504.         scPartition.addCodeLine("// A[i1] > pivot", null, 3, null);                             // 8
  505.         scPartition.addCodeLine("else", null, 3, null);                                         // 9
  506.         scPartition.addCodeLine("swap A[i1] with A[i3]", null, 4, null);                        // 10
  507.         scPartition.addCodeLine("while i3 < A.length and A[i3] > pivot", null, 4, null);        // 11
  508.         scPartition.addCodeLine("i3++", null, 5, null);                                         // 12
  509.         scPartition.addCodeLine("while i1 < m1 and A[i1] < pivot", null, 3, null);              // 13
  510.         scPartition.addCodeLine("i1++", null, 4, null);                                         // 14
  511.        
  512.         scPartition.addCodeLine("// i1 == m1", null, 2, null);                                  // 15
  513.         scPartition.addCodeLine("else", null, 2, null);                                         // 16
  514.         scPartition.addCodeLine("swap A[i2] with A[i3]", null, 3, null);                        // 17
  515.         scPartition.addCodeLine("while i2 < m2 and A[i2] == pivot", null, 3, null);             // 18
  516.         scPartition.addCodeLine("i2++", null, 4, null);                                         // 19
  517.         scPartition.addCodeLine("while i3 < A.length and A[i3] > pivot", null, 3, null);        // 20
  518.         scPartition.addCodeLine("i3++", null, 4, null);                                         // 21
  519.        
  520.         // optional:
  521.         scPartition.addCodeLine("return [m1, m2]", null, 1, null);
  522.     }
  523.    
  524.    
  525.    
  526.     // ===========================================================================
  527.     // ===========================================================================
  528.     // ===========================================================================
  529.     // ===========================================================================
  530.     // ===========================================================================
  531.     // ===========================================================================
  532.    
  533.    
  534.     public String getName() {
  535.         return "Pivot Partitioning By Scanning";
  536.     }
  537.  
  538.     public String getAlgorithmName() {
  539.         return "Partitioning";
  540.     }
  541.  
  542.     public String getAnimationAuthor() {
  543.         return "Bekir Özkara";
  544.     }
  545.  
  546.     public String getDescription(){
  547.         return "Pivot Partitioning by Scanning (PPbS) rearranges the elements in an array A around a given "
  548.  +"\n"
  549.  +"pivot element in place, much like the partitioning procedure used in the Quicksort algorithm, "
  550.  +"\n"
  551.  +"e.g. the one shown in the famous CLRS book.                                "
  552.  +"\n"
  553.  +"There are some differences though: whereas the algorithm from CLRS partitions the array into two parts"
  554.  +"\n"
  555.  +"(elements <= pivot and elements > pivot), given a pivot element which always is the last element in "
  556.  +"\n"
  557.  +"the array, PPbS partitions the array into three parts (<, ==, and > than the pivot) with a freely chosable "
  558.  +"\n"
  559.  +"pivot. PPbS, however, suffers from nested loops, so its time complexity is worse.                                         "
  560.  +"\n"
  561.  +"                                                                                                                                                    "
  562.  +"\n"
  563.  +"PPbS returns two pointers, m1 and m2, that satisfy the following conditions:                                                                     "
  564.  +"\n"
  565.  +"   1. There are m1 many elements that have a value < pivot                                                                                   "
  566.  +"\n"
  567.  +"   2. There are (m2 - m1) many elements that have a value == pivot                                                                               "
  568.  +"\n"
  569.  +"   3. There are (n - m2) many elements that have a value > pivot, where n == A.length.                                                         ";
  570.     }
  571.  
  572.     public String getCodeExample(){
  573.         return "// here: pseudo-code"
  574.  +"\n"
  575.  +"init(Array A, Pivot p)"
  576.  +"\n"
  577.  +"  m1 = 0"
  578.  +"\n"
  579.  +"  foreach(elem in A): if elem < p then m1++"
  580.  +"\n"
  581.  +"  m2 = m1"
  582.  +"\n"
  583.  +"  foreach(elem in A): if elem == p then m2++"
  584.  +"\n"
  585.  +"  i1 = 0"
  586.  +"\n"
  587.  +"  i2 = m1"
  588.  +"\n"
  589.  +"  i3 = m2"
  590.  +"\n"
  591.  +"  while(i1 < m1 and A[i1] < p) i1++"
  592.  +"\n"
  593.  +"  while(i2 < m2 and A[i1] == p) i2++"
  594.  +"\n"
  595.  +"  while(i3 < A.length and A[i3] > p) i3++"
  596.  +"\n"
  597.  +"\n"
  598.  +"\n"
  599.  +"partition(Array A, Pivot p)"
  600.  +"\n"
  601.  +"  until(i1 == m1 and i2 == m2 and i3 == A.length) do:"
  602.  +"\n"
  603.  +"      if i1 < m1"
  604.  +"\n"
  605.  +"          if A[i1] == p"
  606.  +"\n"
  607.  +"              swap A[i1] with A[i2]"
  608.  +"\n"
  609.  +"              while(i2 < m2 and A[i2] == p) i2++"
  610.  +"\n"
  611.  +"          else"
  612.  +"\n"
  613.  +"              swap A[i1] with A[i3]"
  614.  +"\n"
  615.  +"              while(i3 < A.length and A[i3] > p) i3++"
  616.  +"\n"
  617.  +"          while(i1 < m1 and A[i1] < p) i1++"
  618.  +"\n"
  619.  +"      else "
  620.  +"\n"
  621.  +"          swap A[i2] with A[i3]"
  622.  +"\n"
  623.  +"          while(i2 < m2 and A[i2] == p) i2++"
  624.  +"\n"
  625.  +"          while(i3 < A.length and A[i3] > p) i3++"
  626.  +"\n"
  627.  +"  return m1 and m2"
  628.  +"\n"
  629.  +"  ";
  630.     }
  631.  
  632.     public String getFileExtension(){
  633.         return "asu";
  634.     }
  635.  
  636.     public Locale getContentLocale() {
  637.         return Locale.ENGLISH;
  638.     }
  639.  
  640.     public GeneratorType getGeneratorType() {
  641.         return new GeneratorType(GeneratorType.GENERATOR_TYPE_SORT);
  642.     }
  643.  
  644.     public String getOutputLanguage() {
  645.         return Generator.JAVA_OUTPUT;
  646.     }
  647.  
  648. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!