# Path: kraken/lib/segmentation.py
# def is_in_region(line, region) -> bool:
#     """
#     Tests if a line is inside a region, i.e. if the mid point of the baseline
#     is inside the region.
# 
#     Args:
#         line (geom.LineString): line to test
#         region (geom.Polygon): region to test against
# 
#     Returns:
#         False if line is not inside region, True otherwise.
#     """
#     l_obj = line.interpolate(0.5, normalized=True)
#     return region.contains(l_obj)
# 
# def reading_order(lines: Sequence[Tuple[slice, slice]], text_direction: str = 'lr') -> np.ndarray:
#     """Given the list of lines (a list of 2D slices), computes
#     the partial reading order.  The output is a binary 2D array
#     such that order[i,j] is true if line i comes before line j
#     in reading order."""
# 
#     logger.info('Compute reading order on {} lines in {} direction'.format(len(lines), text_direction))
# 
#     order = np.zeros((len(lines), len(lines)), 'B')
# 
#     def _x_overlaps(u, v):
#         return u[1].start < v[1].stop and u[1].stop > v[1].start
# 
#     def _above(u, v):
#         return u[0].start < v[0].start
# 
#     def _left_of(u, v):
#         return u[1].stop < v[1].start
# 
#     def _separates(w, u, v):
#         if w == u or w == v:
#             return 0
#         if w[0].stop < min(u[0].start, v[0].start):
#             return 0
#         if w[0].start > max(u[0].stop, v[0].stop):
#             return 0
#         if w[1].start < u[1].stop and w[1].stop > v[1].start:
#             return 1
#         return 0
# 
#     if text_direction == 'rl':
#         def horizontal_order(u, v):
#             return not _left_of(u, v)
#     else:
#         horizontal_order = _left_of
# 
#     for i, u in enumerate(lines):
#         for j, v in enumerate(lines):
#             if _x_overlaps(u, v):
#                 if _above(u, v):
#                     order[i, j] = 1
#             else:
#                 if [w for w in lines if _separates(w, u, v)] == []:
#                     if horizontal_order(u, v):
#                         order[i, j] = 1
#     return order
# 
# def topsort(order: np.ndarray) -> List[int]:
#     """Given a binary array defining a partial order (o[i,j]==True means i<j),
#     compute a topological sort.  This is a quick and dirty implementation
#     that works for up to a few thousand elements."""
#     logger.info('Perform topological sort on partially ordered lines')
#     n = len(order)
#     visited = np.zeros(n)
#     L = []
# 
#     def _visit(k):
#         if visited[k]:
#             return
#         visited[k] = 1
#         a, = np.nonzero(np.ravel(order[:, k]))
#         for line in a:
#             _visit(line)
#         L.append(k)
# 
#     for k in range(n):
#         _visit(k)
#     return L


import pytest
import unittest
import shapely.geometry as geom
import numpy as np
from typing import Sequence, Tuple
from kraken.lib.segmentation import is_in_region, reading_order, topsort
        self.assertTrue(np.array_equal(order_rl, expected), "Reading order is not as expected: {}".format(order_rl))

    def test_order_real_in_order(self):
        """
        Real (modified) example: lines are in order.
        The reading order should be the same for left-to-right and right-to-left.
        """
        polygon0 = [[493, 2409], [488, 2374], [1733, 2361], [1741, 2395], [1738, 2409], [493, 2422]]
        polygon1 = [[474, 2712], [466, 2669], [1741, 2655], [1749, 2696], [1746, 2709], [474, 2725]]
        order_lr = reading_order([polygon_slices(line) for line in [polygon0, polygon1]])
        order_rl = reading_order([polygon_slices(line) for line in [polygon0, polygon1]], 'rl')
        # line0 should come before line1, lines do not come before themselves
        expected = np.array([[0, 1], [0, 0]])
        self.assertTrue(np.array_equal(order_lr, expected), "Reading order is not as expected: {}".format(order_lr))
        self.assertTrue(np.array_equal(order_rl, expected), "Reading order is not as expected: {}".format(order_rl))

    def test_topsort_ordered(self):
        """
        Return list for three lines that are already in order.
        """
        partial_sort = np.array([[1, 1, 1], [0, 1, 1], [0, 0, 1]])
        expected = [0, 1, 2]
        self.assertTrue(np.array_equal(topsort(partial_sort), expected))

    def test_topsort_ordered_no_self(self):
        """
        Return list for three lines that are already in order.
        """
        partial_sort = np.array([[0, 1, 1], [0, 0, 1], [0, 0, 0]])
        expected = [0, 1, 2]

# Path: kraken/lib/segmentation.py
# def is_in_region(line, region) -> bool:
#     """
#     Tests if a line is inside a region, i.e. if the mid point of the baseline
#     is inside the region.
# 
#     Args:
#         line (geom.LineString): line to test
#         region (geom.Polygon): region to test against
# 
#     Returns:
#         False if line is not inside region, True otherwise.
#     """
#     l_obj = line.interpolate(0.5, normalized=True)
#     return region.contains(l_obj)
# 
# def reading_order(lines: Sequence[Tuple[slice, slice]], text_direction: str = 'lr') -> np.ndarray:
#     """Given the list of lines (a list of 2D slices), computes
#     the partial reading order.  The output is a binary 2D array
#     such that order[i,j] is true if line i comes before line j
#     in reading order."""
# 
#     logger.info('Compute reading order on {} lines in {} direction'.format(len(lines), text_direction))
# 
#     order = np.zeros((len(lines), len(lines)), 'B')
# 
#     def _x_overlaps(u, v):
#         return u[1].start < v[1].stop and u[1].stop > v[1].start
# 
#     def _above(u, v):
#         return u[0].start < v[0].start
# 
#     def _left_of(u, v):
#         return u[1].stop < v[1].start
# 
#     def _separates(w, u, v):
#         if w == u or w == v:
#             return 0
#         if w[0].stop < min(u[0].start, v[0].start):
#             return 0
#         if w[0].start > max(u[0].stop, v[0].stop):
#             return 0
#         if w[1].start < u[1].stop and w[1].stop > v[1].start:
#             return 1
#         return 0
# 
#     if text_direction == 'rl':
#         def horizontal_order(u, v):
#             return not _left_of(u, v)
#     else:
#         horizontal_order = _left_of
# 
#     for i, u in enumerate(lines):
#         for j, v in enumerate(lines):
#             if _x_overlaps(u, v):
#                 if _above(u, v):
#                     order[i, j] = 1
#             else:
#                 if [w for w in lines if _separates(w, u, v)] == []:
#                     if horizontal_order(u, v):
#                         order[i, j] = 1
#     return order
# 
# def topsort(order: np.ndarray) -> List[int]:
#     """Given a binary array defining a partial order (o[i,j]==True means i<j),
#     compute a topological sort.  This is a quick and dirty implementation
#     that works for up to a few thousand elements."""
#     logger.info('Perform topological sort on partially ordered lines')
#     n = len(order)
#     visited = np.zeros(n)
#     L = []
# 
#     def _visit(k):
#         if visited[k]:
#             return
#         visited[k] = 1
#         a, = np.nonzero(np.ravel(order[:, k]))
#         for line in a:
#             _visit(line)
#         L.append(k)
# 
#     for k in range(n):
#         _visit(k)
#     return L


# Path: tests/test_readingorder.py
import pytest
import unittest
import shapely.geometry as geom
import numpy as np
from typing import Sequence, Tuple
from kraken.lib.segmentation import is_in_region, reading_order, topsort

        self.assertTrue(np.array_equal(order_rl, expected), "Reading order is not as expected: {}".format(order_rl))

    def test_order_real_in_order(self):
        """
        Real (modified) example: lines are in order.
        The reading order should be the same for left-to-right and right-to-left.
        """
        polygon0 = [[493, 2409], [488, 2374], [1733, 2361], [1741, 2395], [1738, 2409], [493, 2422]]
        polygon1 = [[474, 2712], [466, 2669], [1741, 2655], [1749, 2696], [1746, 2709], [474, 2725]]
        order_lr = reading_order([polygon_slices(line) for line in [polygon0, polygon1]])
        order_rl = reading_order([polygon_slices(line) for line in [polygon0, polygon1]], 'rl')
        # line0 should come before line1, lines do not come before themselves
        expected = np.array([[0, 1], [0, 0]])
        self.assertTrue(np.array_equal(order_lr, expected), "Reading order is not as expected: {}".format(order_lr))
        self.assertTrue(np.array_equal(order_rl, expected), "Reading order is not as expected: {}".format(order_rl))

    def test_topsort_ordered(self):
        """
        Return list for three lines that are already in order.
        """
        partial_sort = np.array([[1, 1, 1], [0, 1, 1], [0, 0, 1]])
        expected = [0, 1, 2]
        self.assertTrue(np.array_equal(topsort(partial_sort), expected))

    def test_topsort_ordered_no_self(self):
        """
        Return list for three lines that are already in order.
        """
        partial_sort = np.array([[0, 1, 1], [0, 0, 1], [0, 0, 0]])
        expected = [0, 1, 2]

        self.assertTrue(np.array_equal(topsort(partial_sort), expected))