# Principled Programming / Tim Teitelbaum / Chapter 9.
def reverse(A: list[int], L: int, R: int) -> None:
   """
   Given int array A[0..n-1], reverse(A,L,R) reverses the order of the
   subsequence A[L..R] in situ without affecting the rest of A.
   """
   while L < R:
       # Swap A[L] and A[R].
           temp: int = A[L]; A[L] = A[R]; A[R] = temp
       #
           L += 1; R -= 1

def  e9_1_1() -> None:
   """Test reverse. """
   A: list[int] = [1,2,3,4,5,6,7,8]

   print(A, "reversed is:")
   reverse(A, 0, len(A) - 1)
   print(A)

def left_shift_k(A: list[int], n: int, k: int) -> None:
   """
   Given array A[0..n-1], and 0≤k, Left_shift(A,n,k) shifts elements of A
    left k places. Values shifted off the left end of A are lost. Values not
    overwritten remain as they were originally.
    """
   if k > 0:
      for j in range(n-k): A[j] = A[j+k]

def e9_2_1() -> None:
    """Test left_shift_k."""
    A: list[int] = [1, 2, 3, 4, 5, 6, 7, 8]
    k: int = 3

    print(A, "left shifted by", k, "is")
    left_shift_k(A, len(A), k)
    print(A)

def e9_2_2() -> None:
    """Test left_shift_k.Boundary case of k=length of array."""
    A: list[int] = [1, 2, 3, 4, 5, 6, 7, 8]
    k: int = len(A)

    print(A, "left shifted by", k, "is")
    left_shift_k(A, len(A), k)
    print(A)

def left_rotate_one(A: list[int], n: int) -> None:
   """
   Given int array A[0..n-1], left_rotate_one(A,n) shifts A[1..n-1] 1 place
    left, with the value originally in A[0] reentering at right in A[n-1].
   """
   temp: int = A[0]
   left_shift_k(A, n, 1)
   A[n-1] = temp

def e9_3_1() -> None:
   """Test left_rotate_one."""
   A: list[int] = [1,2,3,4,5,6,7,8]

   print(A, "left rotated by 1 is")
   left_rotate_one(A, len(A))
   print(A)

# 4 approaches to left_rotate_k.
#   (1) left_rotate_1 k times.
#   (2) k-ary generalization of swap.
#   (3) Three reverses.
#   (4) Juggling in strides of k.
def  e9_4_1() -> None:
    """
    Given int array A[0..n-1], and integer k, 0≤k<n, left shift A[k..n-1]
    k places, with values originally in A[0..k-1] reentering at right
    Do so by: (1) left_rotate_1 k times.
    """
    A: list[int] = [1,2,3,4,5,6,7,8]
    n: int = len(A)
    k: int = 3

    print(A, "left rotated by", k, "is")
    for j in range(k): left_rotate_one(A, n);
    print(A)

def e9_4_2() -> None:
    """
    Given int array A[0..n-1], and integer k, 0≤k<n, left shift A[k..n-1]
    k places, with values originally in A[0..k-1] reentering at right
    Do so by: (2) k-ary generalization of swap.
    """
    A: list[int] = [1, 2, 3, 4, 5, 6, 7, 8]
    n: int = len(A)
    k: int = 3

    #
    print(A, "left rotated by", k, "is")

    temp: list[int] = [0] * k
    for j in range(0, k): temp[j] = A[j]
    left_shift_k(A, n, k)
    for j in range(0, k): A[n - k + j] = temp[j]

    print(A)

def e9_4_3() -> None:
   """
   Given int array A[0..n-1], and integer k, 0≤k<n, left shift A[k..n-1]
    k places, with values originally in A[0..k-1] reentering at right
    Do so by: (3) Three reverses.
   """
   A: list[int] = [1, 2, 3, 4, 5, 6, 7, 8]
   n: int = len(A)
   k: int = 3

   print(A, "left rotated by", k, "is")
   reverse(A, 0, k - 1)
   reverse(A, k, n - 1)
   reverse(A, 0, n - 1)
   print(A)

def e9_4_4() -> None:
    """
    Given int array A[0..n-1], and integer k, 0≤k<n, left shift A[k..n-1]
    k places, with values originally in A[0..k-1] reentering at right
    Do so by: (4) Juggling in strides of k
    """

    A: list[int] = [1, 2, 3, 4, 5, 6, 7, 8]
    n: int = len(A)
    k: int = 4

    print(A, "left rotated by", k, "is")

    g: int = gcd(n,k)
    for j in range(g):
        p: int = j                     # Start at A[j]
        temp: int = A[p]               #   and make a hole there.
        while ((p + k) % n) != j:      # Stop if p is about to be j again.
            A[p] = A[(p+k) % n]        # Fill the hole, making a new hole.
            p = (p+k) % n              # Advance to the new hole.
        A[p] = temp                    # Fill the last hole from temp.

    print(A)

def  e9_5_1() -> None:
        """
        Dutch National Flag Problem:
        Given array A[0..n-1] consisting of only three values (red, white,
        and blue), rearrange A into all red, then white, then blue.
        """
        R: int = -1; W: int = 0; B: int = +1
        A: list[int] = [B, R, W, B, R, W, B, R]
        n: int = len(A)

        print(A, "rearranged according to the Dutch National Flag Problem is")

    # INVARIANT: A[0..w-1] red, A[w..k-1] white, A[b..n-1] blue, for 0≤w≤k≤b≤n.
    # VARIANT: b-k
        k : int = 0; w: int = 0; b: int = n
    # Repeatedly reduce the size of the region of unknown color (?) until it’s empty.
        while k != b:
            if A[k] == B:
                # Swap A[b-1] and A[k].
                    temp = A[b - 1];  A[b - 1] = A[k];  A[k] = temp
                # Update the ? and Blue region boundaries.
                    b -= 1
            elif A[k] == R:
                # Swap A[w] and A[k].
                    temp = A[k];  A[k] = A[w];  A[w] = temp
                # Update the Red and White region boundaries.
                    w += 1;  k += 1
            else: # A[k] == W
                # Update the White and ? region boundaries.
                    k += 1

        print(A)

# Partitioning.
def partition(A: list[int], L: int, R: int, p: int) -> None:
        """
        Given A[L..R-1] and pivot value p, partition(A,L,R,p) rearranges A[L..R-1] into
        all <p, then all ==p, then all >p.
        """

    # INVARIANT: A[L..w-1]<p, A[w..k-1]==p, A[b..R-1]>p, for L≤w≤k≤b≤R.
    # VARIANT: b-k
        w: int = L; k: int = L;  b: int = R
    # Repeatedly reduce the size of the region of unknown value (?) until it’s empty.
        temp: int
        while k != b:
            if A[k]>p:
                # Swap A[b-1] and A[k].
                    temp = A[b-1];  A[b-1] = A[k];  A[k] = temp
                # Update the ? and >p region boundaries.
                    b -= 1
            elif A[k] < p:
                # Swap A[w] and A[k]. */
                    temp = A[k];  A[k] = A[w];  A[w] = temp
                # Update the <p> and ==p region boundaries.
                    k += 1;  w += 1
            else: # A[k]== p
                # Update the ==p and ? region boundaries.
                    k += 1

def  e9_6_1() -> None:
   """Test partitioning. """
   A: list[int] = [10, 20, 15, 25, 5, 3, 22, 1 ]
   n: int = len(A)
   p: int = 15    # The pivot.

   print(A, "partitioned according to the pivot", p, "is")
   partition(A, 0, n, p)
   print(A)

def  e9_7_1() -> None:
        """
        Given ordered arrays A and B of lengths na and nb, create ordered
        array C of length na+nb consisting of those values.
        """
        A: list[int] = [10, 10, 12, 12, 20, 21, 21]; na: int = len(A)
        B: list[int] = [5, 15, 15, 21, 23];          nb: int = len(B)

        C: list[int] = [0]* (na+nb)  # C[0..kc-1] is to be collation of
                                    # A[0..ka-1] and B[0..kb-1].

        ka:int = 0; kb: int = 0; kc: int = 0   # Indices in A, B, and C.

        print(A, "collated with")
        print(B, "is")

    # Copy values from A or B into C until one array is exhausted.
        while ka < na and kb < nb:
            if A[ka] < B[kb]: C[kc] = A[ka]; ka += 1; kc += 1
            else:             C[kc] = B[kb]; kb += 1; kc += 1
    # Copy remaining values into C from the unexhausted array.
        while ka < na: C[kc] = A[ka]; ka += 1; kc += 1
        while kb < nb: C[kc] = B[kb]; kb += 1; kc += 1

    # Display result.
        print(C)

# Utility.
def gcd(x: int, y: int) -> int:
   while x != y:
      if x < y: y = y - x
      else: x = x - y
   return x

# Uncomment out to run.
#e9_1_1()
#e9_2_1()
#e9_2_2()
#e9_3_1()
#e9_4_1()
#e9_4_2()
#e9_4_3()
#e9_4_4()
#e9_5_1()
#e9_6_1()
#e9_7_1()