algovi_ppbs_orig

package pivot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PivotPartitioningByScanning {

    // m1 - 1       elements in list are less than pivot
    // m2 - m1      elements are equal to pivot
    // n - m2 + 1   elements greater than pivot (where n = list.size()-1)
    int m1;
    int m2;

    // before and after each iteration:
    // 1.   1 <= i1 <= m1 <= i2 <= m2 <= i3 <= n+1
    // 2.   S[j] < pivot for j in (1, ..., i1-1),  if i1 < m1: S[i1] >= pivot
    // 3.   S[j] = pivot for j in (m1, ..., i2-1), if i2 < m2: S[i2] != pivot
    // 4.   S[j] > pivot for j in (m2, ..., i3-1), if i3 <= n: S[i3] <= pivot
    int i1;
    int i2;
    int i3;

    public static void main(String[] args) {
        PivotPartitioningByScanning scanner = new PivotPartitioningByScanning();

        List<Integer> ints = new ArrayList<>();
        String list = "27 20 24 22 30 25 12 17 15 17 22 23 15 22 18 29 20 23 29 20";
        list = "11 20 19 21 13 15 26 16 29 30 17 11 27 24 18 24 27 24 28 11";
        list = "11 20 19 21 13 19 15";

        String[] splits = list.split(" ");
        for(String num : splits) {
            ints.add(Integer.parseInt(num));
        }

        System.out.println("length = " + ints.size());
        for(Integer i : ints) {
            System.out.print(i + ", ");
        }
        System.out.println();

        scanner.ppbs(ints, 19);
        for(Integer i : ints) {
            System.out.print(i + ", ");
        }
    }


    // variant: at least one of i1, i2, i3 is increased by at least 1, none of them is decreased
    // break condition: i1 == m1 && i2 == m2 && i3 == n + 1
    private void ppbs(List<Integer> list, int pivot) {
        init(list, pivot);

        int iter = 0;
        while(i1 != m1 || i2 != m2 || i3 != list.size()) {
            System.out.print(iter++ + ": ");
            for(Integer i : list) {
                System.out.print(i + ", ");
            }
            System.out.println();
            // note: for nabla: i1+1, i2+1, i3+1 !!!
            System.out.println("i1 = " + i1);
            System.out.println("i2 = " + i2);
            System.out.println("i3 = " + i3);
            System.out.println();
            System.out.println();

            if(i1 < m1) {
                // TODO
                if(list.get(i1) == pivot) {
                    swap(list, i1, i2);

                    do {
                        i2++;
                    } while(i2 != m2 && list.get(i2) == pivot);
                }
                // S[i1] > p
                else {
                    swap(list, i1, i3);

                    do {
                        i3++;
                    } while(i3 != list.size() && list.get(i3) > pivot);
                }

                while(i1 < m1 && list.get(i1) < pivot) {
                    i1++;
                }
            }
            // i1 == m1
            else {
                swap(list, i2, i3);

                do {
                    i2++;
                } while(i2 != m2 && list.get(i2) == pivot);

                do {
                    i3++;
                } while(i3 != list.size() && list.get(i3) > pivot);
            }
        } // while()

        System.out.print(iter++ + ": ");
        for(Integer i : list) {
            System.out.print(i + ", ");
        }
        System.out.println();
        // note: for nabla: i1+1, i2+1, i3+1 !!!
        System.out.println("i1 = " + i1);
        System.out.println("i2 = " + i2);
        System.out.println("i3 = " + i3);
        System.out.println();
        System.out.println();
    } // ppbs()


    private void init(List<Integer> list, int pivot) {
        m1 = 0;
        for(int j=0; j < list.size(); ++j) {
            if(list.get(j) < pivot) {
                m1++;
            }
        }

        m2 = m1;
        for(int j=0; j < list.size(); ++j) {
            if(list.get(j) == pivot) {
                m2++;
            }
        }

        i1 = 0;
        i2 = m1;
        i3 = m2;

        while(i1 < m1 && list.get(i1) < pivot) {
            i1++;
        }

        while(i2 < m2 && list.get(i2) == pivot) {
            i2++;
        }

        while(i3 < list.size() && list.get(i3) > pivot) {
            i3++;
        }
    } // init()


    private void swap(List<Integer> list, int idx1, int idx2) {
        Integer temp = list.get(idx1);
        list.set(idx1, list.get(idx2));
        list.set(idx2, temp);
    }
}