API tools faq
paste
bekovski

ppbs_generator

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