#!/usr/bin/perl

# manhattan_intersection( @lines )
#   Find the intersections of strictly horizontal and vertical lines.
#   Requires basic_tree_add(), basic_tree_del(), and basic_tree_find(),
#   all defined in Chapter 3, Advanced Data Structures.
#
sub manhattan_intersection {
    my @op; # The coordinates are transformed here as operations.

    while (@_) {
        my @line = splice @_, 0, 4;

        if ($line[1] == $line[3]) {     # Horizontal.
            push @op, [ @line, \&range_check_tree ];
        } else {                        # Vertical.
            # Swap if upside down.
            @line = @line[0, 3, 2, 1] if $line[1] > $line[3];

            push @op, [ @line[0, 1, 2, 1], \&basic_tree_add ];
            push @op, [ @line[0, 3, 2, 3], \&basic_tree_del ];
        }
    }

    my $x_tree; # The range check tree.
    # The x coordinate comparison routine.
    my $compare_x = sub { $_[0]->[0] <=> $_[1]->[0] };
    my @intersect; # The intersections.

    foreach my $op (sort { $a->[1] <=> $b->[1] ||
                           $a->[4] == \&range_check_tree ||
                           $a->[0] <=> $b->[0] }
                           @op) {
        if ($op->[4] == \&range_check_tree) {
            push @intersect, $op->[4]->( \$x_tree, $op, $compare_x );
        } else { # Add or delete.
            $op->[4]->( \$x_tree, $op, $compare_x );
        }
    }

    return @intersect;
}

# range_check_tree( $tree_link, $horizontal, $compare )
#    Returns the list of tree nodes that are within the limits
#    $horizontal->[0] and $horizontal->[1].  Depends on the binary
#    trees of Chapter 3, Advanced Data Structures.
#
sub range_check_tree {
    my ( $tree, $horizontal, $compare ) = @_;

    my @range          = ( );   # The return value.
    my $node           = $$tree;
    my $vertical_x     = $node->{val};
    my $horizontal_lo  = [ $horizontal->[ 0 ] ];
    my $horizontal_hi  = [ $horizontal->[ 1 ] ];

    return unless defined $$tree;

    push @range, range_check_tree( \$node->{left}, $horizontal, $compare )
        if defined $node->{left};

    push @range, $vertical_x->[ 0 ], $horizontal->[ 1 ]
        if $compare->( $horizontal_lo, $horizontal ) <= 0 &&
           $compare->( $horizontal_hi, $horizontal ) >= 0;

    push @range, range_check_tree( \$node->{right}, $horizontal,
                                   $compare )
        if defined $node->{right};

    return @range;
}

@lines = ( 1, 6,  1, 3,  1, 2,  3, 2,  1, 1,  4, 1,
           2, 4,  7, 4,  3, 0,  3, 6,  4, 3,  4, 7,
           5, 7,  5, 4,  5, 2,  7, 2 );

print join(" ", manhattan_intersection(@lines)), "\n";

# Usage:
# ($link, $node) = basic_tree_find( \$tree, $target, $cmp )
#
# Search the tree \$tree for $target.  The optional $cmp
# argument specifies an alternative comparison routine
# (called as $cmp->( $item1, $item2 ) to be used instead
# of the default numeric comparison.  It should return a
# value consistent with the <=> or cmp operators.
#
# Return two items:
#
#    1. a reference to the link that points to the node
#       (if it was found) or to the place where it should
#       go (if it was not found)
#
#    2. the node itself (or undef if it doesn't exist)

sub basic_tree_find {
    my ($tree_link, $target, $cmp) = @_;
    my $node;

    # $tree_link is the next pointer to be followed.
    # It will be undef if we reach the bottom of the tree.
    while ( $node = $$tree_link ) {
        local $^W = 0;      # no warnings, we expect undef values

        my $relation = ( defined $cmp
                    ? $cmp->( $target, $node->{val} )
                    : $target <=> $node->{val} );

        # If we found it, return the answer.
        return ($tree_link, $node) if $relation == 0;

        # Nope - prepare to descend further - decide which way we go.
        $tree_link = $relation > 0 ? \$node->{left} : \$node->{right};
    }

    # We fell off the bottom, so the element isn't there, but we
    # tell caller where to create a new element (if desired).
    return ($tree_link, undef);
}

# $node = basic_tree_add( \$tree, $target, $cmp );
#
# If there is not already a node in the tree \$tree that
# has the value $target, create one.  Return the new or
# previously existing node.  The third argument is an
# optional comparison routine and is simply passed on to
# basic_tree_find.

sub basic_tree_add {
    my ($tree_link, $target, $cmp) = @_;
    my $found;

    ($tree_link, $found) = basic_tree_find( $tree_link, $target, $cmp );

    unless ($found) {
        $found = {
            left  => undef,
            right => undef,
            val   => $target
        };
        $$tree_link = $found;
    }

    return $found;
}

# $val = basic_tree_del( \$tree, $target[, $cmp ] );
#
# Find the element of \$tree that has the value $val
# and remove it from the tree.  Return the value, or
# return undef if there was no appropriate element
# on the tree.

sub basic_tree_del {
    my ($tree_link, $target, $cmp) = @_;
    my $found;

    ($tree_link, $found) = basic_tree_find ( $tree_link, $target, $cmp );

    return undef unless $found;

    # tree_link has to be made to point to any children of $found:
    #  if there are no children, make it null
    #  if there is only one child, it can just take the place
    #    of $found
    #  But, if there are two children, they have to be merged somehow
    #    to fit in the one reference.
    #
    if ( ! defined $found->{left} ) {
        $$tree_link = $found->{right};
    } elsif ( ! defined $found->{right} ) {
        $$tree_link = $found->{left};
    } else {
        MERGE_SOMEHOW( $tree_link, $found );
    }

    return $found->{val};
}

# MERGE_SOMEHOW
#
# Make $tree_link point to both $found->{left} and $found->{right}.

# Attach $found->{left} to the leftmost child of $found->{right}
# and then attach $found->{right} to $$tree_link.
sub MERGE_SOMEHOW {
    my ($tree_link, $found) = @_;
    my $left_of_right = $found->{right};
    my $next_left;

    $left_of_right = $next_left
        while $next_left = $left_of_right->{left};

    $left_of_right->{left} = $found->{left};

    $$tree_link = $found->{right};
}

# traverse( $tree, $func )
#
# Traverse $tree in order, calling $func() for each element.
#    in turn

sub traverse {
    my $tree = shift or return;   # skip undef pointers
    my $func = shift;

    traverse( $tree->{left}, $func );
    &$func( $tree );
    traverse( $tree->{right}, $func );
}