# Path: dppy/exotic_dpps_core.py
# def RSK(sequence):
#     """Apply Robinson-Schensted-Knuth correspondence on a sequence of reals, e.g. a permutation, and return the corresponding insertion and recording tableaux.
# 
#     :param sequence:
#         Sequence of real numbers
#     :type sequence:
#         array_like
# 
#     :return:
#         :math:`P, Q` insertion and recording tableaux
#     :rtype:
#         list
# 
#     .. seealso::
# 
#         `RSK Wikipedia <https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted%E2%80%93Knuth_correspondence>`_
#     """
# 
#     P, Q = [], []  # Insertion/Recording tableau
# 
#     for it, x in enumerate(sequence, start=1):
# 
#         # Iterate along the rows of the tableau P to find a place for the bouncing x and record the position where it is inserted
#         for row_P, row_Q in zip(P, Q):
# 
#             # If x finds a place at the end of a row of P
#             if x >= row_P[-1]:
#                 row_P.append(x)  # add the element at the end of the row of P
#                 row_Q.append(it)  # record its position in the row of Q
#                 break
#             else:
#                 # find place for x in the row of P to keep the row ordered
#                 ind_insert = bisect_right(row_P, x)
#                 # Swap x with the value in place
#                 x, row_P[ind_insert] = row_P[ind_insert], x
# 
#         # If no room for x at the end of any row of P create a new row
#         else:
#             P.append([x])
#             Q.append([it])
# 
#     return P, Q


import unittest
import sys
from dppy.exotic_dpps_core import RSK
sys.path.append('..')



class TestRSKCorrespondence(unittest.TestCase):
    """ Test Robinson-Schensted-Knuth correspondence

    Examples come from `Connor Ahlbach's paper <https://pdfs.semanticscholar.org/613e/6105bd02c4f6442d9f255534294230253aa3.pdf>`_ see
    Definition 1.6 and Proposition 2.2
    """

    sequences = [list(range(1, 7)),
                 list(range(6, 0, -1)),
                 [3, 6, 1, 4, 5, 2],
                 [6, 2, 3, 5, 1, 4],
                 [5, 2, 6, 1, 4, 3],
                 [4, 2, 6, 5, 1, 3]]

    PQ_tableaux = [
        ([[1, 2, 3, 4, 5, 6]], [[1, 2, 3, 4, 5, 6]]),
        ([[1], [2], [3], [4], [5], [6]], [[1], [2], [3], [4], [5], [6]]),
        ([[1, 2, 5], [3, 4], [6]], [[1, 2, 5], [3, 4], [6]]),
        ([[1, 3, 4], [2, 5], [6]], [[1, 3, 4], [2, 6], [5]]),
        ([[1, 3], [2, 4], [5, 6]], [[1, 3], [2, 5], [4, 6]]),
        ([[1, 3], [2, 5], [4, 6]], [[1, 3], [2, 4], [5, 6]])]

    def test_RSK_output(self):

        for i, (seq, tab) in enumerate(zip(self.sequences, self.PQ_tableaux)):
            with self.subTest(index=i, seq=seq):

# Path: dppy/exotic_dpps_core.py
# def RSK(sequence):
#     """Apply Robinson-Schensted-Knuth correspondence on a sequence of reals, e.g. a permutation, and return the corresponding insertion and recording tableaux.
# 
#     :param sequence:
#         Sequence of real numbers
#     :type sequence:
#         array_like
# 
#     :return:
#         :math:`P, Q` insertion and recording tableaux
#     :rtype:
#         list
# 
#     .. seealso::
# 
#         `RSK Wikipedia <https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted%E2%80%93Knuth_correspondence>`_
#     """
# 
#     P, Q = [], []  # Insertion/Recording tableau
# 
#     for it, x in enumerate(sequence, start=1):
# 
#         # Iterate along the rows of the tableau P to find a place for the bouncing x and record the position where it is inserted
#         for row_P, row_Q in zip(P, Q):
# 
#             # If x finds a place at the end of a row of P
#             if x >= row_P[-1]:
#                 row_P.append(x)  # add the element at the end of the row of P
#                 row_Q.append(it)  # record its position in the row of Q
#                 break
#             else:
#                 # find place for x in the row of P to keep the row ordered
#                 ind_insert = bisect_right(row_P, x)
#                 # Swap x with the value in place
#                 x, row_P[ind_insert] = row_P[ind_insert], x
# 
#         # If no room for x at the end of any row of P create a new row
#         else:
#             P.append([x])
#             Q.append([it])
# 
#     return P, Q


# Path: tests/test_RSK.py
import unittest
import sys
from dppy.exotic_dpps_core import RSK

sys.path.append('..')



class TestRSKCorrespondence(unittest.TestCase):
    """ Test Robinson-Schensted-Knuth correspondence

    Examples come from `Connor Ahlbach's paper <https://pdfs.semanticscholar.org/613e/6105bd02c4f6442d9f255534294230253aa3.pdf>`_ see
    Definition 1.6 and Proposition 2.2
    """

    sequences = [list(range(1, 7)),
                 list(range(6, 0, -1)),
                 [3, 6, 1, 4, 5, 2],
                 [6, 2, 3, 5, 1, 4],
                 [5, 2, 6, 1, 4, 3],
                 [4, 2, 6, 5, 1, 3]]

    PQ_tableaux = [
        ([[1, 2, 3, 4, 5, 6]], [[1, 2, 3, 4, 5, 6]]),
        ([[1], [2], [3], [4], [5], [6]], [[1], [2], [3], [4], [5], [6]]),
        ([[1, 2, 5], [3, 4], [6]], [[1, 2, 5], [3, 4], [6]]),
        ([[1, 3, 4], [2, 5], [6]], [[1, 3, 4], [2, 6], [5]]),
        ([[1, 3], [2, 4], [5, 6]], [[1, 3], [2, 5], [4, 6]]),
        ([[1, 3], [2, 5], [4, 6]], [[1, 3], [2, 4], [5, 6]])]

    def test_RSK_output(self):

        for i, (seq, tab) in enumerate(zip(self.sequences, self.PQ_tableaux)):
            with self.subTest(index=i, seq=seq):

                self.assertTrue(RSK(seq) == tab)