import SBR
import math
import itertools
import random
from itertools import permutations

"""
TripartiteBinarySort.py -- Implementation of the TBS algorithm for sorting bitstrings and permutations,
along with a couple testing/analysis functions
"""

def GDC_TBS(perm):
    """
    Returns the cost to sort perm using TBS as the binary sorting sequence.
    (GenericDivideConquer_TripartiteBinarySort)
    """
    revlist = permutationsort_divideconquer_tbs(perm, 0, len(perm) - 1)
    cost = SBR.compress_reversals(revlist, len(perm)) / 3
    return cost


def tripartite_binary_sort(T, i, j):
    """
    Performs TBS (binary version) on T[i,j] inclusive, returns list of reversals
    """
    if all(T[ind] <= T[ind + 1] for ind in range(i, j)):
        return []
    part1, part2 = (2 * i + j) // 3, (i + 2 * j) // 3
    revlist = []
    revlist += tripartite_binary_sort(T, i, part1)
    flipbits(T, part1 + 1, part2)
    revlist += tripartite_binary_sort(T, part1 + 1, part2)
    flipbits(T, part1 + 1, part2)
    revlist += tripartite_binary_sort(T, part2 + 1, j)
    oneind, zerind = zero_one_indices(T, i, j)
    if oneind < zerind:
        rev = SBR.Reversal(oneind, zerind)
        SBR.reverse(T, rev)
        revlist.append(rev)
    return revlist

def flipbits(T, i, j):
    for index in range(i,j+1):
        T[index] = int(not T[index])


def zero_one_indices(T, i, j):
    """
    returns indices of leftmost 1 and rightmost 0 to reverse the segment across
    the median
    """
    oneind = -1
    zerind = -1
    # Find leftmost 1
    for ind in range(i, j+1):
        if T[ind] == 1:
            oneind = ind
            break
    # Find rightmost 0
    for ind in range(j, i-1, -1):
        if T[ind] == 0:
            zerind = ind
            break
    return oneind, zerind

def perm_to_01(L, i, j):
    """
    TUrns a permutation L[i:j] into a permutation of 0s and 1s, where L[i] is 0 if it is
    less than the median and L[i] is 1 if it is greater than the median
    """
    subseq = L[i:j + 1]
    sorted_subseq = sorted(subseq)
    median = (j - i) // 2
    return L[:i] + [int(sorted_subseq.index(k) > median) for k in subseq] + L[j + 1:]

def permutationsort_divideconquer_tbs(L):
    """Routes the given permutation using reversals. Returns the reversals"""
    j = max(L)
    return permutationsort_divideconquer_tbs(L, 0, j)

def permutationsort_divideconquer_tbs(L, i=None, j=None):
    """
    Sorts the given permutations L from index i to j (inclusive) using a divide and conquer approach. Returns a list of
    reversals used to perform the sort.
    """
    # Set default params
    if i == None:
        i = min(L)
    if j == None:
        j = max(L)

    if i == j:
        return []
    T = perm_to_01(L, i, j)
    revs = tripartite_binary_sort(T, i, j)
    m = (i + j) // 2
    SBR.apply_revs(revs, L)
    return revs + permutationsort_divideconquer_tbs(L, i, m) + permutationsort_divideconquer_tbs(L, m + 1, j)



def all_binary_lists_equal(n):
    """
    generates list of lists, where each list is a binary sequence of length n,
    with equal number of 0s and 1s
    """
    def blep(n, b, ct0s, ct1s, lis):
        if len(b) == n:
            if ct1s == n // 2:
                lis.append(b)
            return
        if ct0s == math.ceil(n / 2):
            lis.append(b + [1] * (n - len(b)))
            return
        if ct1s == n // 2:
            lis.append(b + [0] * (n - len(b)))
            return
        blep(n, b + [0], ct0s + 1, ct1s, lis)
        blep(n, b + [1], ct0s, ct1s + 1, lis)
        return

    lis = []
    blep(n, [], 0, 0, lis)
    return lis

def test_binary_sort():
    """
    Testing correctness of sorting bitstrings with TBS.
    """
    wrong = 0
    for i in range(1000):
      l  = [0]*random.randint(100,200) + [1]*random.randint(100,200)
      random.shuffle(l)
      before = l.copy()
      #print(before)
      tripartite_binary_sort(l, 0 , len(l)-1)
      #print(l, '\n')
      if l != sorted(before):
          print("failed")
    print("passed")

def test_perm_sort():
    """
    Testing correctness of sorting permutations with TBS as
    bitstring sorting subroutine. 
    Returns number
    """
    wrong = 0
    n = 1000
    for ct in range(n):
        L = list(range(1,random.randint(5, 200)))
        random.shuffle(L)
        before = L.copy()
        permutationsort_divideconquer_tbs(L,0,len(L)-1)
        #print(before, '\n', L, '\n')
        if L != sorted(before):
            print("failed")
            return 
    print("passed")