from collections import namedtuple
import pprint
from enum import Enum


class Direction(Enum):
    NO_SIDE = 0
    LEFT = 1
    RIGHT = 2
    TOP = 3
    BOTTOM = 4
    RIGHT_LEFT = 5
    RIGHT_BOTTOM = 6
    RIGHT_BOTTOM_LEFT = 7
    TOP_RIGHT = 8
    TOP_BOTTOM = 9
    TOP_LEFT = 10
    TOP_RIGHT_BOTTOM = 11
    TOP_RIGHT_LEFT = 12
    TOP_BOTTOM_LEFT = 13
    TOP_RIGHT_BOTTOM_LEFT = 14
    BOTTOM_LEFT = 15


# Track (aka Channel) is a wire that runs from one position to another along X or Y axis
Track = namedtuple('Track', 'direction x_low x_high y_low y_high')


def print_tracks(tracks):
    pprint.pprint(tracks)


def make_tracks(xs, ys, points, grid_width=None, grid_height=None):
    """ Give a list of xs columns and ys rows and points, return a list of
        Track's and connections between the tracks.

        An assert will fail if each point in the point list is not covered by
        a column in xs or a row in ys.

        Connections will be models as indicies into the track list.

        Return:
        [Track], [(index into track list, index into track list)]

    >>> pos = [
    ... (1,1),        (3,1),
    ... (1,2), (2,2), (3,2),
    ... (1,3),        (3,3),
    ... (1,4), (2,4), (3,4),
    ... (1,5),        (3,5),
    ... ]
    >>> xs = [1, 3]
    >>> ys = [2, 4]
    >>> tracks, connections = make_tracks(xs, ys, pos)
    >>> print_tracks(tracks)
    [Track(direction='Y', x_low=1, x_high=1, y_low=1, y_high=5),
     Track(direction='Y', x_low=3, x_high=3, y_low=1, y_high=5),
     Track(direction='X', x_low=1, x_high=3, y_low=2, y_high=2),
     Track(direction='X', x_low=1, x_high=3, y_low=4, y_high=4)]
    >>> print(sorted(connections))
    [(2, 0), (2, 1), (3, 0)]

    >>> pos = [
    ... (68,48), (69,48),
    ... (68,49), (69,49),
    ...          (69,50),
    ...          (69,51),
    ...          (69,52),
    ...          (69,53), (70,53), (71,53), (72,53)]
    >>> xs = [68, 69]
    >>> ys = [53]
    >>> tracks, connections = make_tracks(xs, ys, pos)
    >>> print_tracks(tracks)
    [Track(direction='Y', x_low=68, x_high=68, y_low=48, y_high=53),
     Track(direction='Y', x_low=69, x_high=69, y_low=48, y_high=53),
     Track(direction='X', x_low=68, x_high=72, y_low=53, y_high=53)]
    >>> print(connections)
    [(2, 0), (2, 1)]


    """
    x_set = set(xs)
    y_set = set(ys)

    for x, y in points:
        if x > 0:
            in_x_set = x in x_set or x - 1 in x_set, (x, x_set)
        else:
            in_x_set = x in x_set

        if y > 0:
            in_y_set = y in y_set or y - 1 in y_set, (y, y_set)
        else:
            in_y_set = y in y_set

        assert in_x_set or in_y_set

    all_xs, all_ys = zip(*points)
    x_min = min(all_xs)
    x_max = max(all_xs)
    y_min = min(all_ys)
    y_max = max(all_ys)

    tracks = []
    x_tracks = []
    y_tracks = []
    for x in xs:
        y_low = max(y_min, 1)
        y_high = y_max
        if grid_height is not None:
            y_high = min(y_max, grid_height - 2)

        tracks.append(
            Track(
                direction='Y',
                x_low=x,
                x_high=x,
                y_low=y_low,
                y_high=y_high,
            )
        )
        y_tracks.append(len(tracks) - 1)

    for y in ys:
        x_low = max(x_min, 1)
        x_high = x_max
        if grid_width is not None:
            x_high = min(x_high, grid_width - 2)

        tracks.append(
            Track(
                direction='X',
                x_low=x_low,
                x_high=x_high,
                y_low=y,
                y_high=y,
            )
        )
        x_tracks.append(len(tracks) - 1)

    if len(tracks) == 1:
        return tracks, []

    # If there is more than 1 track, there must be a track in each dimension
    assert len(xs) >= 1 and len(ys) >= 1

    connections = set()

    # Always just connect X tracks to the first Y track, and Y tracks to the
    # first X tracks.
    #
    # To dedup connections, the x channel track will appear first in the
    # connection list.
    for idx, track in enumerate(tracks):
        if track.direction == 'X':
            connections.add((idx, y_tracks[0]))
        else:
            assert track.direction == 'Y'
            connections.add((x_tracks[0], idx))

    return tracks, list(connections)


class Tracks(object):
    """Tracks groups tracks and their connections (AKA Node).
    """

    def __init__(self, tracks, track_connections):
        self.tracks = tracks
        self.track_connections = track_connections

        self.track_cache = {}

    def verify_tracks(self):
        """ Verify that all tracks are connected to all other tracks. """
        track_connections = {}

        for idx, _ in enumerate(self.tracks):
            track_connections[idx] = set((idx, ))

        for conn_a, conn_b in self.track_connections:
            if track_connections[conn_a] is track_connections[conn_b]:
                continue

            assert self.tracks[conn_a].direction != self.tracks[conn_b
                                                                ].direction

            track_connections[conn_a] |= track_connections[conn_b]

            for track_idx in track_connections[conn_a]:
                track_connections[track_idx] = track_connections[conn_a]

        assert len(
            set(id(s) for s in track_connections.values())
        ) == 1, track_connections

    def is_wire_adjacent_to_track(self, idx, coord):
        """returns direction if wire at coord is adjacent to track at index idx
        returns NO_SIDE if not adjacent.
        """
        track = self.tracks[idx]
        wire_x, wire_y = coord

        if track.direction == 'X':
            pin_top = track.y_low == wire_y
            pin_bottom = track.y_low == wire_y - 1
            adjacent_channel = (pin_top or pin_bottom) and (
                track.x_low <= wire_x and wire_x <= track.x_high
            )

            if adjacent_channel:
                if pin_top:
                    return Direction.TOP
                elif pin_bottom:
                    return Direction.BOTTOM
                else:
                    assert False, (coord, track)
            else:
                return Direction.NO_SIDE

        elif track.direction == 'Y':
            pin_right = track.x_low == wire_x
            pin_left = track.x_low == wire_x - 1
            adjacent_channel = (pin_right or pin_left) and (
                track.y_low <= wire_y and wire_y <= track.y_high
            )

            if adjacent_channel:
                if pin_right:
                    return Direction.RIGHT
                elif pin_left:
                    return Direction.LEFT
                else:
                    assert False, (coord, track)
            else:
                return Direction.NO_SIDE
        else:
            assert False, track

    def get_tracks_for_wire_at_coord(self, coord):
        """Returns map of direction to track indicies for valid connections.

        There may be multiple connections to tracks at a particular coordinate,
        this method only returns a possible connection in each direction to
        this track.

        Parameters
        ----------
        coord : (int, int)
            Coordinate to attach to track

        Returns
        -------
        dict(Direction -> int)
            Dictionary of pin direction to track index.

        """

        if coord in self.track_cache:
            return self.track_cache[coord]
        else:
            wire_x, wire_y = coord

            conns = {}
            for idx, track in enumerate(self.tracks):
                pin_dir = self.is_wire_adjacent_to_track(idx, coord)
                if pin_dir != Direction.NO_SIDE:
                    conns[pin_dir] = idx

            self.track_cache[coord] = conns
            return conns


def main():
    import doctest

    print('Doctest begin')
    failure_count, test_count = doctest.testmod(optionflags=doctest.ELLIPSIS)
    assert test_count > 0
    assert failure_count == 0, "Doctests failed!"
    print('Doctest end')


if __name__ == "__main__":
    main()