utils/lib/rr_graph/points.py

#!/usr/bin/env python3
"""
Functions for dealing with groups of points.
"""

import math
import string
import sys

import enum
from collections import defaultdict
from collections import namedtuple

from ..asserts import assert_eq
from ..asserts import assert_type

from ..rr_graph import Position, P

_NamedPosition = namedtuple("NamedPosition", ["pos", "names"])


class NamedPosition(_NamedPosition):
    """Class to store a position and a set of names associated with it."""

    def __new__(cls, pos, names):
        assert_type(pos, Position)
        assert_type(names, list)
        for n in names:
            assert_type(n, str)
        return _NamedPosition.__new__(cls, pos, names)

    @property
    def x(self):
        return self.pos.x

    @property
    def y(self):
        return self.pos.y

    @property
    def first(self):
        assert len(self.names) > 0, self.names
        return self.names[0]

    def __str__(self):
        return "NP({},{},{})".format(
            self.pos.x,
            self.pos.y,
            ",".join(repr(n) for n in self.names),
        )

    def __repr__(self):
        return self.__str__()


def NP(x, y, *n):
    """Syntactic sugar for NamedPosition."""
    n = list(n)
    if not n:
        n = ["{}+{}".format(string.ascii_letters[x], string.ascii_letters[y])]
    return NamedPosition(P(x, y), n)


class StraightSegment(list):
    class Type(enum.Enum):
        """Category of straight segment

        Vertical - all points have same x value
        Horizontal - all point have same y value
        Stub - single point, no direction yet.
        """

        V = '|'
        V__doc__ = 'Vertical'

        H = '-'
        H__doc__ = 'Horizontal'

        S = 'o'
        S__doc__ = 'Stub'

        def __repr__(self):
            return 'StraightSegment.Type.' + self.name

    def __init__(self, direction, positions):
        list.__init__(self, positions)
        assert_type(direction, StraightSegment.Type)
        assert_type(positions, list)
        if direction == StraightSegment.Type.S:
            assert len(positions) == 1, (
                "Stubs must only have one position not {}".format(positions)
            )
        else:
            for p in positions:
                assert_type(p, (Position, NamedPosition))
                if direction == StraightSegment.Type.V:
                    assert_eq(p[0].x, p.x)
                elif direction == StraightSegment.Type.H:
                    assert_eq(p[0].y, p.y)
                else:
                    assert False, "Unknown direction {}".format(direction)
        self.direction = direction

    @property
    def d(self):
        return self.direction

    def __str__(self):
        return "{} {}".format(self.direction.value, list.__repr__(self))

    def __repr__(self):
        return "{}({}, {})".format(
            self.__class__.__name__,
            self.direction,
            list.__repr__(self),
        )

    def y_range(self):
        y_pos = [p.y for p in self]
        return min(y_pos), max(y_pos)

    def x_range(self):
        x_pos = [p.x for p in self]
        return min(x_pos), max(x_pos)

    def along(self, pos):
        """Return if position lies along segment"""
        assert len(self) > 0
        assert_type(pos, (NamedPosition, Position))

        if len(self) == 1:
            assert self.d == StraightSegment.Type.S, (self, pos)
            return (pos.x == self[0].x) or (pos.y == self[0].y)
        elif self.d == StraightSegment.Type.V:
            return pos.x == self[0].x
        elif self.d == StraightSegment.Type.H:
            return pos.y == self[0].y
        else:
            assert False, "Weird segment %s" % self

    def get_at(self, pos):
        for p in self:
            if p.x == pos.x and p.y == pos.y:
                return p
        raise ValueError("Nothing found at {} {}".format(pos, self))

    def has_at(self, pos):
        try:
            self.get_at(pos)
            return True
        except ValueError:
            return False

    def replace(self, pos):
        """Replace point at same x and y. Essentially updating the names.
        If no match is found, list remains unmodified and the function returns False.
        """
        for i, p in enumerate(self):
            if pos.x != p.x or pos.y != p.y:
                continue
            self[i] = pos
            return True
        return False

    def append(self, pos):
        """Add new position. Update direction if needed"""
        if len(self) > 0:
            if pos.x == self[0].x:
                direction = StraightSegment.Type.V
            elif pos.y == self[0].y:
                direction = StraightSegment.Type.H
        else:
            direction = self.direction

        if self.direction == StraightSegment.Type.S:
            assert len(self) <= 1, "Stub must have at most single point"
            self.direction = direction
        assert direction == self.direction, "Can't append in different direction {} {}".format(
            self.direction, direction
        )
        list.append(self, pos)

    def extend_to(self, pos):
        """Return point starting at Segment first position and extend for connection to pos"""
        pclass = self[0].pos.__class__
        if self.d == StraightSegment.Type.H:
            return pclass(pos.x, self[0].y)
        elif self.d == StraightSegment.Type.V:
            return pclass(self[0].x, pos.y)
        elif self.d == StraightSegment.Type.S:
            return pclass(self[0].x, pos.y)
            # assert pos.x == self[0].x or pos.y == self[0].y, (pos, self)
            # return pclass(*pos)
        assert self.d != StraightSegment.Type.S, self
        assert False, self

    @property
    def names(self):
        """Return list of all names of points along segment"""
        names = []
        for npos in self:
            names.extend(n for n in npos.names)
        return list(set(names))


def straight_longest(positions):
    """Get the largest straight section from a group of positions.

    Arguments:
        positions : [(Position, [str, ...]), ...]

    Returns:
        (StraightSegment([Position|NamedPosition, ...]), [Position|NamedPosition, ...])

    >>> s, r = straight_longest([P(1,0),])
    >>> print(str(s))
    o [P(x=1, y=0)]

    >>> s, r = straight_longest([
    ...         P(1,0),
    ... P(0,1), P(1,1), P(2, 1), P(3, 1),
    ... P(0,2), P(1,2), P(2, 2), P(3, 2),
    ...         P(1,3),
    ... ])
    >>> print(str(s))
    - [P(x=0, y=2), P(x=1, y=2), P(x=2, y=2), P(x=3, y=2)]
    >>> s, r = straight_longest(r)
    >>> print(str(s))
    - [P(x=0, y=1), P(x=1, y=1), P(x=2, y=1), P(x=3, y=1)]
    >>> s, r = straight_longest(r)
    >>> print(str(s))
    | [P(x=1, y=0), P(x=1, y=3)]
    >>> r
    []

    >>> s, r = straight_longest([
    ...         P(1,0),
    ... P(0,1), P(1,1), P(2, 1),
    ...         P(1,2),
    ... ])
    >>> print(str(s))
    - [P(x=0, y=1), P(x=1, y=1), P(x=2, y=1)]
    >>> s, r = straight_longest(r)
    >>> print(str(s))
    | [P(x=1, y=0), P(x=1, y=2)]
    >>> r
    []

    >>> s, r = straight_longest([
    ...         P(1,0),
    ... P(0,1),         P(10, 1),
    ...         P(1,5),
    ... ])
    >>> print(str(s))
    - [P(x=0, y=1), P(x=10, y=1)]
    >>> s, r = straight_longest(r)
    >>> print(str(s))
    | [P(x=1, y=0), P(x=1, y=5)]
    >>> r
    []

    >>> s, r = straight_longest([
    ... P(0,0), P(1,0),
    ... P(0,1),         P(2, 1),
    ... P(0,2), P(1,2),
    ... P(0,3), P(1,3), P(2, 3),
    ... P(0,4), P(1,4),
    ... P(0,5),         P(2, 5),
    ... P(0,6), P(1,6),
    ... ])
    >>> print(str(s))
    | [P(x=0, y=0), P(x=0, y=1), P(x=0, y=2), P(x=0, y=3), P(x=0, y=4), P(x=0, y=5), P(x=0, y=6)]
    >>> s, r = straight_longest(r)
    >>> print(str(s))
    | [P(x=1, y=0), P(x=1, y=2), P(x=1, y=3), P(x=1, y=4), P(x=1, y=6)]
    >>> s, r = straight_longest(r)
    >>> print(str(s))
    | [P(x=2, y=1), P(x=2, y=3), P(x=2, y=5)]
    >>> r
    []

    """
    assert_type(positions, list)

    # Count how frequently each x and y coordinate is found.
    coordinate_count = {
        'x': defaultdict(int),
        'y': defaultdict(int),
    }
    for pos in positions:
        assert_type(pos, (Position, NamedPosition))
        coordinate_count['x'][pos.x] += 1
        coordinate_count['y'][pos.y] += 1

    # If out the most common x and v coordinates
    x_val = list(sorted((c, x) for x, c in coordinate_count['x'].items()))
    y_val = list(sorted((c, y) for y, c in coordinate_count['y'].items()))

    # Work out the direction this segment will run
    if x_val[-1][0] > y_val[-1][0]:
        direction = StraightSegment.Type.V
    else:
        direction = StraightSegment.Type.H

    # Work out which positions are on this segment
    segment = StraightSegment(direction, [])
    not_in_segment = []
    if direction == StraightSegment.Type.V:
        x_pos = x_val[-1][1]
        for pos in positions:
            if pos.x != x_pos:
                not_in_segment.append(pos)
                continue
            segment.append(pos)
    elif direction == StraightSegment.Type.H:
        direction = "-"
        y_pos = y_val[-1][1]
        for pos in positions:
            if pos.y != y_pos:
                not_in_segment.append(pos)
                continue
            segment.append(pos)

    # Single length segments are "stubs"
    if len(segment) == 1:
        segment.direction = StraightSegment.Type.S

    return segment, not_in_segment


def print_segments(segs):
    for s in segs:
        print(s)


def print_conns(conns):
    for p, joins in sorted(conns.items()):
        for (aname, bname) in joins:
            print("{}x{} {}<->{}".format(p.x, p.y, aname, bname))


def decompose_into_straight_lines(positions):
    """
    Takes a network and converts it to a list of straight segments.


    Arguments:
        positions : [(Position, [str, ...]), ...]

    >>> # Single element
    >>> pos = [NP(1,0),]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> for s in segs:
    ...     print(s)
    o [NP(1,0,'b+a')]

    >>> # Single horizontal line
    >>> pos = [NP(1,0), NP(2,0)]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> for s in segs:
    ...     print(s)
    - [NP(1,0,'b+a'), NP(2,0,'c+a')]

    >>> # Single vertical line
    >>> pos = [NP(1,2), NP(1,3)]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> for s in segs:
    ...     print(s)
    | [NP(1,2,'b+c'), NP(1,3,'b+d')]

    >>> # Cross shape
    >>> pos = [
    ...           NP(1,0),
    ...  NP(0,1), NP(1,1), NP(2, 1),
    ...           NP(1,2),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,1,'a+b'), NP(1,1,'b+b'), NP(2,1,'c+b')]
    | [NP(1,0,'b+a'), NP(1,1,'b+b_x'), NP(1,2,'b+c')]
    >>> print_conns(conns)
    1x1 b+b<->b+b_x

    >>> # Cross with two horizontal bars
    >>> pos = [
    ...           NP(1,0),
    ...  NP(0,1), NP(1,1), NP(2, 1), NP(3, 1),
    ...  NP(0,2), NP(1,2), NP(2, 2), NP(3, 2),
    ...           NP(1,3),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,1,'a+b'), NP(1,1,'b+b'), NP(2,1,'c+b'), NP(3,1,'d+b')]
    - [NP(0,2,'a+c'), NP(1,2,'b+c'), NP(2,2,'c+c'), NP(3,2,'d+c')]
    | [NP(1,0,'b+a'), NP(1,1,'b+b_x'), NP(1,2,'b+c_x'), NP(1,3,'b+d')]
    >>> print_conns(conns)
    1x1 b+b<->b+b_x
    1x2 b+c<->b+c_x

    >>> # Cross with unequal horizontal bars
    >>> pos = [
    ...           NP(1,0),
    ...  NP(0,1), NP(1,1), NP(2, 1), NP(3, 1),
    ...  NP(0,2), NP(1,2), NP(2, 2),
    ...           NP(1,3),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,1,'a+b'), NP(1,1,'b+b'), NP(2,1,'c+b'), NP(3,1,'d+b')]
    - [NP(0,2,'a+c'), NP(1,2,'b+c'), NP(2,2,'c+c')]
    | [NP(1,0,'b+a'), NP(1,1,'b+b_x'), NP(1,2,'b+c_x'), NP(1,3,'b+d')]
    >>> print_conns(conns)
    1x1 b+b<->b+b_x
    1x2 b+c<->b+c_x

    >>> # FIXME: Cross with missing middle
    >>> pos = [
    ...           NP(1,0),
    ...  NP(0,1),          NP(10, 1),
    ...           NP(1,5),
    ... ]
    >>> try:
    ...     conns, segs = decompose_into_straight_lines(pos)
    ... except AssertionError:
    ...     pass

    >>> # 3 straight lines
    >>> pos = [
    ...  NP(0,0), NP(1,0),
    ...  NP(0,1),          NP(2,1),
    ...  NP(0,2), NP(1,2),
    ...  NP(0,3), NP(1,3), NP(2,3),
    ...  NP(0,4), NP(1,4),
    ...  NP(0,5),          NP(2,5),
    ...  NP(0,6), NP(1,6),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    | [NP(0,0,'a+a'), NP(0,1,'a+b'), NP(0,2,'a+c'), NP(0,3,'a+d'), NP(0,4,'a+e'), NP(0,5,'a+f'), NP(0,6,'a+g')]
    - [NP(0,3,'a+d_x'), NP(1,3,'b+d_x'), NP(2,3,'c+d_x')]
    | [NP(1,0,'b+a'), NP(1,2,'b+c'), NP(1,3,'b+d'), NP(1,4,'b+e'), NP(1,6,'b+g')]
    | [NP(2,1,'c+b'), NP(2,3,'c+d'), NP(2,5,'c+f')]
    >>> print_conns(conns)
    0x3 a+d<->a+d_x
    1x3 b+d<->b+d_x
    2x3 c+d<->c+d_x

    >>> # H shaped
    >>> pos = [
    ...  NP(0,0),          NP(2,0),
    ...  NP(0,1),          NP(2,1),
    ...  NP(0,2),          NP(2,2),
    ...  NP(0,3), NP(1,3), NP(2,3),
    ...  NP(0,4),          NP(2,4),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    | [NP(0,0,'a+a'), NP(0,1,'a+b'), NP(0,2,'a+c'), NP(0,3,'a+d'), NP(0,4,'a+e')]
    - [NP(0,3,'a+d_x'), NP(1,3,'b+d'), NP(2,3,'c+d_x')]
    | [NP(2,0,'c+a'), NP(2,1,'c+b'), NP(2,2,'c+c'), NP(2,3,'c+d'), NP(2,4,'c+e')]
    >>> print_conns(conns)
    0x3 a+d<->a+d_x
    2x3 c+d<->c+d_x

    >>> # Corner shape
    >>> pos = [
    ...  NP(0,1,'io_0/D_IN_0'), NP(1,1,'neigh_op_lft_0','neigh_op_lft_4'),
    ...                         NP(1,2,'neigh_op_bnl_0','neigh_op_bnl_4'),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,1,'io_0/D_IN_0'), NP(1,1,'neigh_op_lft_0','neigh_op_lft_4')]
    | [NP(1,1,'neigh_op_lft_0_x'), NP(1,2,'neigh_op_bnl_0','neigh_op_bnl_4')]
    >>> print_conns(conns)
    1x1 neigh_op_lft_0<->neigh_op_lft_0_x

    >>> # Going around corners
    >>> pos = [
    ...                            NP(1,0,'span4_horz_r_4'), NP(2,0,'span4_horz_r_8'), NP(3,0,'span4_horz_r_12'), NP(4,0,'span4_horz_l_12'),
    ...  NP(0,1,'span4_vert_b_0'),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,0,'span4_horz_r_4_to_span4_vert_b_0'), NP(1,0,'span4_horz_r_4'), NP(2,0,'span4_horz_r_8'), NP(3,0,'span4_horz_r_12'), NP(4,0,'span4_horz_l_12')]
    | [NP(0,0,'span4_horz_r_4_to_span4_vert_b_0_x'), NP(0,1,'span4_vert_b_0')]
    >>> print_conns(conns)
    0x0 span4_horz_r_4_to_span4_vert_b_0<->span4_horz_r_4_to_span4_vert_b_0_x

    >>> pos = [
    ...                            NP(1,0,'span4_horz_r_4'), NP(2,0,'span4_horz_r_8'), NP(3,0,'span4_horz_r_12'),
    ...  NP(0,1,'span4_vert_b_0'),
    ...  NP(0,2,'span4_vert_b_0'),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,0,'span4_horz_r_4_to_span4_vert_b_0'), NP(1,0,'span4_horz_r_4'), NP(2,0,'span4_horz_r_8'), NP(3,0,'span4_horz_r_12')]
    | [NP(0,0,'span4_horz_r_4_to_span4_vert_b_0_x'), NP(0,1,'span4_vert_b_0'), NP(0,2,'span4_vert_b_0')]
    >>> print_conns(conns)
    0x0 span4_horz_r_4_to_span4_vert_b_0<->span4_horz_r_4_to_span4_vert_b_0_x

    >>> pos = [
    ...  NP(10,0,'span4_horz_r_4'), NP(12,0,'span4_horz_r_8'), NP(13,0,'span4_horz_r_12'),
    ...                                                                                    NP(14,1,'span4_vert_b_0'),
    ...                                                                                    NP(14,2,'span4_vert_b_0'),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(10,0,'span4_horz_r_4'), NP(12,0,'span4_horz_r_8'), NP(13,0,'span4_horz_r_12'), NP(14,0,'span4_horz_r_12_to_span4_vert_b_0')]
    | [NP(14,0,'span4_horz_r_12_to_span4_vert_b_0_x'), NP(14,1,'span4_vert_b_0'), NP(14,2,'span4_vert_b_0')]
    >>> print_conns(conns)
    14x0 span4_horz_r_12_to_span4_vert_b_0<->span4_horz_r_12_to_span4_vert_b_0_x

    >>> # FIXME: This is a bit weird
    >>> # Make sure NP(1,2) isn't in the output...
    >>> pos = [
    ... NP(0,0),          NP(2,0),
    ... NP(0,1), NP(1,1), NP(2,1),
    ... NP(0,2),          NP(2,2),
    ... NP(0,3), NP(1,3), NP(2,3),
    ... NP(0,4),          NP(2,4),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    | [NP(0,0,'a+a'), NP(0,1,'a+b'), NP(0,2,'a+c'), NP(0,3,'a+d'), NP(0,4,'a+e')]
    - [NP(0,3,'a+d_x'), NP(1,3,'b+d_x'), NP(2,3,'c+d_x')]
    | [NP(1,1,'b+b'), NP(1,3,'b+d')]
    | [NP(2,0,'c+a'), NP(2,1,'c+b'), NP(2,2,'c+c'), NP(2,3,'c+d'), NP(2,4,'c+e')]
    >>> print_conns(conns)
    0x3 a+d<->a+d_x
    1x3 b+d<->b+d_x
    2x3 c+d<->c+d_x

    >>> # FIXME: This is weird?
    >>> pos = [
    ...  NP(0,16,'span4_vert_t_12'),
    ...                              NP(1,17,'span4_horz_l_12'),
    ... ]
    >>> conns, segs = decompose_into_straight_lines(pos)
    >>> print_segments(segs)
    - [NP(0,16,'span4_vert_t_12'), NP(1,16,'span4_horz_l_12_to_span4_vert_t_12_x')]
    | [NP(1,16,'span4_horz_l_12_to_span4_vert_t_12'), NP(1,17,'span4_horz_l_12')]
    >>> print_conns(conns)
    1x16 span4_horz_l_12_to_span4_vert_t_12<->span4_horz_l_12_to_span4_vert_t_12_x

    """ # noqa: 501
    assert len(positions) > 0, positions
    for pos in positions:
        assert_type(pos, NamedPosition)

    npclass = positions[0].__class__
    pclass = positions[0].pos.__class__

    # position_used_by[position] = (NamedPosition, StraightSegment)
    position_used_by = {}
    segments = {
        '|': [],
        '-': [],
        'o': [],
        'ALL': [],
    }
    # connections[position] = (namea, nameb)
    connections = defaultdict(list)

    def add_segment(s, is_spine=False):
        assert len(s) > 0, (s, is_spine)
        assert_type(s, StraightSegment)
        for np in s:
            assert_type(np, NamedPosition)
            if not is_spine:
                assert np.pos not in position_used_by, (
                    np.pos, s, position_used_by[np.pos]
                )
                position_used_by[np.pos] = (np, s)

        for p, (other_p, other_s) in position_used_by.items():
            assert p.x == other_p.x, (p, other_p)
            assert p.y == other_p.y, (p, other_p)
            if s is other_s:
                continue

            if not s.along(p):
                continue

            assert p not in connections, (p, connections)

            current_name = other_p.names[0]
            new_name = current_name + '_x'

            connection_p = npclass(p, [new_name])
            if is_spine:
                s.replace(connection_p)
            else:
                s.append(connection_p)
            connections[p].append((current_name, new_name))
        s.sort()
        # print(s)
        segments['ALL'].append(s)
        segments[s.d.value].append(s)

    # Convert the positions into straight lines.
    remaining = list(positions)
    while len(remaining) > 0:
        assert_type(remaining, list)
        straight_segment, remaining = straight_longest(remaining)
        add_segment(straight_segment)

    if len(segments['ALL']) == 1:
        assert len(connections) == 0, (segments, connections)
        return connections, segments['ALL']

    # FIXME: Hack for dealing with the corner case
    if len(segments['ALL']) == 2 and len(connections) == 0:
        longest = segments['ALL'][0]
        other = []
        for seg in segments['ALL'][1:]:
            if len(longest) < len(seg):
                longest, seg = seg, longest
            other.append(seg)

        # assert len(other) == 1, (longest, other)
        # assert len(longest) > 1, (longest, other)
        pointa, pointb = straight_closet(longest, other[0])
        corner_point = longest.extend_to(pointb)
        corner_name = "{}_to_{}".format(pointa.names[0], pointb.names[0])
        longest.append(npclass(corner_point, [corner_name]))
        longest.sort()
        other[0].append(npclass(corner_point, [corner_name + "_x"]))
        other[0].sort()
        connections[corner_point].append((corner_name, corner_name + "_x"))
    """
    # FIXME: Check all the segments are connected together
    for_checking = list(segments['ALL'])
    connected = [for_checking.pop(0)]
    while len(for_checking) > 0:
        point = None
        for seg1 in for_checking:
            for seg2 in connected:
                test_point = common_point(seg1, seg2)
                if test_point is not None:
                    point = test_point
                    connected.append(seg2)
                    break
        if point is not None:
            for_checking.remove(connected[-1])
        else:
            assert False, (for_checking, connected)
    """

    # Check connections
    # If they are all vertical or horizontal, we need to create a spine.
    if len(connections) == 0 and len(segments['-']) > 0:
        assert len(segments['|']) == 0
        for seg in segments['o']:
            seg.direction = StraightSegment.Type.H
            segments['-'].append(seg)

        x_pos = defaultdict(int)
        for seg in segments['-']:
            assert len(seg) > 0, seg
            for p in seg:
                x_pos[p.x] += 1

        x = list(sorted((m, x) for x, m in x_pos.items()))[-1][-1]

        spine = StraightSegment(StraightSegment.Type.V, [])
        for seg in segments['-']:
            p = pclass(x, seg.y_range()[0])
            spine.append(npclass(p, names=[seg.get_at(p).first]))
        add_segment(spine, True)

    elif len(connections) == 0 and len(segments['|']) > 0:
        assert len(segments['-']) == 0
        for seg in segments['o']:
            seg.direction = StraightSegment.Type.V
            segments['|'].append(seg)

        y_pos = defaultdict(int)
        for seg in segments['|']:
            assert len(seg) > 0, seg
            for p in seg:
                y_pos[p.y] += 1

        y = list(sorted((m, y) for y, m in y_pos.items()))[-1][-1]

        spine = StraightSegment(StraightSegment.Type.H, [])
        for seg in segments['|']:
            assert len(seg) > 0, seg
            p = pclass(seg.x_range()[0], y)
            spine.append(npclass(p, names=[seg.get_at(p).first]))
        add_segment(spine, True)

    segments['ALL'].sort()
    return connections, segments['ALL']


def straight_ends(positions):
    """Get the ends of a straight line.

    >>> straight_ends([P(0,1), P(1,1)])
    (P(x=0, y=1), P(x=1, y=1))

    >>> straight_ends([P(0,1), P(1,1), P(2,1)])
    (P(x=0, y=1), P(x=2, y=1))

    >>> straight_ends([P(1,0), P(1,1), P(1,2)])
    (P(x=1, y=0), P(x=1, y=2))

    >>> straight_ends([P(1,1), P(1,1)])
    (P(x=1, y=1), P(x=1, y=1))

    >>> # FIXME: Is this the correct behaviour?
    >>> straight_ends([P(1,1), P(1,4)])
    (P(x=1, y=1), P(x=1, y=4))

    >>> straight_ends([P(0,0), P(1,1)])
    Traceback (most recent call last):
      ...
    TypeError: Not straight x:{0, 1} y:{0, 1}
    >>> straight_ends([P(0,0), P(1,1), P(0,2)])
    Traceback (most recent call last):
      ...
    TypeError: Not straight x:{0, 1} y:{0, 1, 2}

    """
    pclass = positions[0].__class__

    x_pos = set(p.x for p in positions)
    y_pos = set(p.y for p in positions)

    if len(x_pos) > 1:
        if len(y_pos) != 1:
            raise TypeError("Not straight x:{} y:{}".format(x_pos, y_pos))
    if len(y_pos) > 1:
        if len(x_pos) != 1:
            raise TypeError("Not straight x:{} y:{}".format(x_pos, y_pos))

    start = pclass(min(x_pos), min(y_pos))
    end = pclass(max(x_pos), max(y_pos))

    assert start.x == end.x or start.y == end.y, "{} {}".format(start, end)

    return start, end


def distance(p1, p2):
    return math.sqrt((p2.x - p1.x)**2 + (p2.y - p1.y)**2)


def straight_closet(line1, line2):
    """

    # >>> straight_intersection((P(0, 0), P(0, 10)), (P(0, 0), P(10, 0)))
    # P(x=0, y=0)
    # >>> straight_intersection((P(10, 0), P(10, 10)), (P(0, 0), P(10, 0)))
    # P(x=10, y=0)
    # >>> straight_intersection((P(5, 0), P(5, 10)), (P(0, 0), P(10, 0)))
    # P(x=5, y=0)
    # >>> straight_intersection((P(0, 5), P(10, 5)), (P(5, 0), P(5, 10)))
    # P(x=5, y=5)

    """
    min_d = sys.maxsize
    pa, pb = None, None

    for p1 in line1:
        for p2 in line2:
            d = distance(p1, p2)
            if d < min_d:
                pa, pb = p1, p2
                min_d = d

    assert pa is not None, "{} {}".format(line1, line2)
    assert pb is not None, "{} {}".format(line1, line2)
    return pa, pb


class Point(object):
    def __init__(self, coord):
        self.x, self.y = coord
        self.tracks = 0

    def __repr__(self):
        return 'Point(coord=({},{}),tracks={})'.format(
            self.x, self.y, repr(self.tracks)
        )


class Track(object):
    def __init__(self, dim, tracks=None, other_tracks=None, points=[]):
        self.dim = dim

        self.points = []
        self.tracks = tracks
        self.other_tracks = other_tracks
        for p in points:
            self.add_point(p)

    def add_point(self, p):
        self.points.append(p)
        p.tracks += 1

    def __repr__(self):
        return 'Track(dim={},points={})'.format(
            repr(self.dim), repr(self.points)
        )


def decompose_points_into_tracks(
        points, grid_width=None, grid_height=None, right_only=False
):
    """ This function takes a bag of points and returns a set of x lines and
        y lines that cover all points, and all lines touch each other.

    This is the first step to forming VPR tracks from points.  VPR tracks have
    limited length, whereas this function returns lines of infinite length.

    Args:
        points: List of (x, y) tuples that are points to be connected into the
            the track
        grid_width (int): Optional maximum x dimension
        grid_height (int): Optional maximum y dimension
        right_only (bool): Assume that points are only available via pins on
            the right.  Some arches restrict pins to the right side only.

    >>> # Single element
    >>> pos = [(1,0)]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = []
    y = [0]

    >>> # Single horizontal line
    >>> pos = [(1,0), (2,0)]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = []
    y = [0]

    >>> # Single vertical line
    >>> pos = [(1,2), (1,3)]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [1]
    y = []

    >>> # Cross shape
    >>> pos = [
    ...         (2,1),
    ...  (1,2), (2,2), (3, 2),
    ...         (2,3),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [2]
    y = [2]

    >>> # Cross shape at edge
    >>> pos = [
    ...         (1,0),
    ...  (0,1), (1,1), (2, 1),
    ...         (1,2),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0]

    >>> # Cross with two horizontal bars
    >>> pos = [
    ...         (1,0),
    ...  (0,1), (1,1), (2, 1), (3, 1),
    ...  (0,2), (1,2), (2, 2), (3, 2),
    ...         (1,3),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0, 1]

    >>> # Cross with unequal horizontal bars
    >>> pos = [
    ...         (1,0),
    ...  (0,1), (1,1), (2, 1), (3, 1),
    ...  (0,2), (1,2), (2, 2),
    ...         (1,3),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0, 1]

    >>> pos = [
    ...           (1,0),
    ...  (0,1),          (10, 1),
    ...           (1,5),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0]

    >>> # 3 straight lines
    >>> pos = [
    ...         (1,0),
    ...  (0,1),          (2,1),
    ...  (0,2), (1,2),
    ...  (0,3), (1,3),   (2,3),
    ...  (0,4), (1,4),
    ...  (0,5),          (2,5),
    ...  (0,6), (1,6),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0, 3, 5]

    >>> # H shaped
    >>> pos = [
    ...                (2,0),
    ...  (0,1),        (2,1),
    ...  (0,2),        (2,2),
    ...  (0,3), (1,3), (2,3),
    ...  (0,4),        (2,4),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0, 2, 3]

    >>> # H shaped
    >>> pos = [
    ...  (1,1),        (3,1),
    ...  (1,2),        (3,2),
    ...  (1,3),        (3,3),
    ...  (1,4), (2,4), (3,4),
    ...  (1,5),        (3,5),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [1, 2]
    y = [4]

    >>> # Corner shape
    >>> pos = [
    ...  (0,1), (1,1),
    ...                         (1,2)
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = []

    >>> # Going around corners
    >>> pos = [
    ...         (1,0), (2,0), (3,0), (4,0),
    ...  (0,1),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0]

    >>> pos = [
    ...                            (1,0), (2,0), (3,0),
    ...  (0,1),
    ...  (0,2),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0]

    >>> pos = [
    ...  (10,0), (12,0), (13,0),
    ...                          (14,1),
    ...                          (14,2),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [14]
    y = [0]

    >>> # Make sure (1,2) isn't in the output...
    >>> pos = [
    ...               (2,0),
    ... (0,1), (1,1), (2,1),
    ... (0,2),        (2,2),
    ... (0,3), (1,3), (2,3),
    ... (0,4),        (2,4),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = [0, 2, 3]

    >>> pos = [
    ...  (0,16),
    ...          (1,17),
    ... ]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [0]
    y = []

    >>> pos = [
    ... (68,48), (69,48),
    ... (68,49), (69,49),
    ...          (69,50),
    ...          (69,51),
    ...          (69,52),
    ...          (69,53), (70,53), (71,53), (72,53)]
    >>> ret = decompose_points_into_tracks(pos)
    >>> print_tracks(ret)
    x = [68]
    y = [52]

    """

    xs, ys = zip(*points)

    x_min = max(0, min(xs) - 1)
    x_max = max(xs)
    if grid_width is not None:
        x_max = min(x_max, grid_width - 2)

    y_min = max(0, min(ys) - 1)
    y_max = max(ys)
    if grid_height is not None:
        y_max = min(y_max, grid_height - 2)

    points = [Point(p) for p in points]
    x_tracks = {}
    y_tracks = {}

    for x in range(x_min, x_max + 1):
        x_tracks[x] = Track(dim=x, tracks=x_tracks, other_tracks=y_tracks)
    for y in range(y_min, y_max + 1):
        y_tracks[y] = Track(dim=y, tracks=y_tracks, other_tracks=x_tracks)

    def on_x_track(p):
        # x tracks extend from 1 to grid_height - 1
        if p.y <= 0:
            return False

        if grid_height is not None and p.y >= grid_height - 2:
            return False

        return True

    def on_y_track(p):
        # y tracks extend from 1 to grid_width - 1
        if p.x <= 0:
            return False

        if grid_width is not None and p.x >= grid_width - 2:
            return False

        return True

    def is_corner_point(p):
        if p.x == 0 and p.y == 0:
            return True

        if grid_width is not None:
            assert grid_height is not None
            if p.x == grid_width - 1 and p.y == 0:
                return True

            if p.x == 0 and p.y == grid_height - 1:
                return True

            if p.x == grid_width - 1 and p.y == grid_height - 1:
                return True

        return False

    for p in points:
        # No points in corner
        assert not is_corner_point(p), p

        if on_x_track(p) and p.x in x_tracks:
            # The x-1 connection is for left pins.
            if p.x > 0 and not right_only:
                x_tracks[p.x - 1].add_point(p)
            x_tracks[p.x].add_point(p)

        # If all pins are on the right, then the y_tracks are used for cross
        # bar only, and points are not connected.
        if on_y_track(p) and not right_only and p.y in y_tracks:
            if p.y > 0:
                y_tracks[p.y - 1].add_point(p)
            y_tracks[p.y].add_point(p)

    def try_remove_track(track):
        assert track.dim in track.tracks

        for point in track.tracks[track.dim].points:
            if point.tracks <= 1:
                return False

        # If there is more than 1 other track, cannot have zero of this track.
        if len(track.tracks) <= 1 and len(track.other_tracks) > 1:
            return False

        for point in track.tracks[track.dim].points:
            point.tracks -= 1

        del track.tracks[track.dim]

        return True

    # Attempt to remove tracks, starting with the track with the smallest
    # number of connections.
    while len(x_tracks) > 0 and len(y_tracks) > 0:
        x_track = min(x_tracks.values(), key=lambda key: len(key.points))
        y_track = min(y_tracks.values(), key=lambda key: len(key.points))

        if len(x_track.points) < len(y_track.points):
            if not try_remove_track(x_track):
                if not try_remove_track(y_track):
                    break
        else:
            if not try_remove_track(y_track):
                if not try_remove_track(x_track):
                    break

    # Walk each dimension, attempting to removing excess lines from the line
    # with the smallest number of points.
    while len(x_tracks) > 0:
        x_track = min(x_tracks.values(), key=lambda key: len(key.points))
        if not try_remove_track(x_track):
            break

    while len(y_tracks) > 0:
        y_track = min(y_tracks.values(), key=lambda key: len(key.points))
        if not try_remove_track(y_track):
            break

    # Walk each dimension, attempting to removing excess lines from any line,
    # starting with the smallest.
    while True:
        for x_track in sorted(x_tracks.values(),
                              key=lambda key: len(key.points)):
            if try_remove_track(x_track):
                continue
        for y_track in sorted(y_tracks.values(),
                              key=lambda key: len(key.points)):
            if try_remove_track(y_track):
                continue
        break

    # Sanity check results
    for p in points:
        on_a_track = False
        if on_x_track(p):
            if p.x > 0:
                on_a_track = on_a_track or p.x - 1 in x_tracks

            on_a_track = on_a_track or p.x in x_tracks

        if on_y_track(p):
            if p.y > 0:
                on_a_track = on_a_track or p.y - 1 in y_tracks

            on_a_track = on_a_track or p.y in y_tracks

        assert on_a_track, p

    return list(x_tracks.keys()), list(y_tracks.keys())


def print_tracks(ret):
    x_tracks, y_tracks = ret

    print('x = {}'.format(x_tracks))
    print('y = {}'.format(y_tracks))