#!/usr/bin/perl -w
#

use strict;
my $Debug = 5;

package Entity;

use Carp;

sub new {
    my $class = shift;
    my $self = {};
    $self->{ID} = shift;
    $self->{TXT} = shift;
    $self->{PRINTED} = 0;
    bless ($self, $class);

    if ($Debug & 2) {
	carp "Initing $self id " . $self->{ID};
    }

    return $self;
}

sub id {
    my $self = shift;
    return $self->{ID};
}

sub add_txt {
    my $self = shift;
    $self->{TXT} .= shift;
}

sub get_txt {
    my $self = shift;
    return $self->{TXT};
}

sub get_txt_first {
    my $self = shift;
    my @a = split(/\n/, $self->{TXT});
    return shift(@a) . "\n";
}

sub get_txt_rest {
    my $self = shift;
    my @a = split(/\n/, $self->{TXT});
    shift @a;
    return join("\n", @a) . "\n";
}

sub get_value {
    my ($self, $key) = @_;
    my $re = "<tag\\s+k=['\"]${key}['\"]\\s+v=['\"]([^'\"]*)['\"]";
    if ($self->{TXT} =~ /$re/) {
	return $1;
    } else {
	print STDERR "Not found: " . $self->{TXT} . "\n";
	return undef;
    }
}

sub is_printed {
    my $self = shift;
    return $self->{PRINTED};
}

sub set_printed {
    my $self = shift;
    $self->{PRINTED} = 1;
}

package Node;
@Node::ISA = ("Entity");

sub new {
    my $class = shift;
    my $self = $class->SUPER::new(@_);
    $self->{WAYS} = [];
    bless ($self, $class);
    return $self;
}

sub add_to_way {
    my ($self, $way, $offset) = @_;
    push @{ $self->{WAYS} }, { way => $way, offset => $offset };
}

sub del_from_way {
    my ($self, $way, $offset) = @_;
    for (my $i=0; $i<$#{$self->{WAYS}}; $i++) {
	my $entry = ${$self->{WAYS}}[$i];
	if (defined($entry) && 
	    ${$entry}{way} == $way && 
	    ${$entry}{offset} == $offset) {
	    delete ${$self->{WAYS}}[$i];
	    last;
	}
    }
}

sub list_ways {
    my $self = shift;
    my $s = '';
    foreach my $w (@{$self->{WAYS}}) {
	if (defined(${$w}{way})) {
	    $s .= ${$w}{way}->id() . ':' . ${$w}{offset} . ' ';
	}
    }
    return $s;
}

sub get_ways {
    my $self = shift;
    return $self->{WAYS};
}



package Way;
@Way::ISA = ("Entity");

use Carp;

sub new {
    my $class = shift;
    my $self = $class->SUPER::new(@_);
    $self->{NODES} = [];
    $self->{RELS} = [];
    bless ($self, $class);
    return $self;
}

sub add_node {
    my ($self, $node) = @_;
    push @{$self->{NODES}}, $node;
    $node->add_to_way($self, $#{$self->{NODES}});
}

sub add_to_rel {
    my ($self, $rel, $role) = @_;
    push @{ $self->{RELS} }, { rel => $rel, role => $role };
}

sub del_from_rel {
    my ($self, $rel, $role) = @_;
    for (my $i=0; $i<$#{$self->{RELS}}; $i++) {
	my $entry = ${$self->{RELS}}[$i];
	if (defined($entry) && 
	    ${$entry}{rel} == $rel &&
	    ${$entry}{role} eq $role) {
	    delete ${$self->{RELS}}[$i];
	    last;
	}
    }
}

sub list_nodes {
    my $self = shift;
    my $s = '';
    foreach my $n (@{$self->{NODES}}) {
	$s .= $n->id() . ' ';
    }
    return $s;
}

sub list_rels {
    my $self = shift;
    my $s = '';
    foreach my $r (@{$self->{RELS}}) {
	$s .= ${$r}{rel}->id() . ':' . ${$r}{role} . ' ';
    }
    return $s;
}

sub get_txt {
    my $self = shift;
    my $id = $self->id();
    my $s = $self->get_txt_first();
    foreach my $n (@{$self->{NODES}}) {
	$s .= "    <nd ref='" . $n->id() . "' />\n" if defined($n);
    }
    $s .= $self->get_txt_rest();
    $s =~ s/^(.*way id=['"])[^'"]*(['"].*)$/$1$id$2/s;

    return $s;
}

sub get_node {
    my ($self, $offset) = @_;
    if ($offset < 0 || $offset > $#{$self->{NODES}}) {
	return undef;
    } else {
	return ${$self->{NODES}}[$offset];
    }
}

sub get_rels {
    my $self = shift;
    return $self->{RELS};
}

sub get_nodes {
    my $self = shift;
    return $self->{NODES};
}

sub del_node {
    my ($self, $offset) = @_;
    if ($offset >= 0 && $offset <= $#{$self->{NODES}}) {
	if ($Debug) {
	    print STDERR "Deleting offset: $offset\n";
	}
	${$self->{NODES}}[$offset]->del_from_way($self, $offset);
	delete ${$self->{NODES}}[$offset];
    }
    if ($self->node_count() < 1) {
    }
}

sub node_count {
    my $self = shift;
    return $#{$self->{NODES}}+1;
}

sub del {
    my $self = shift;
    foreach my $r (@{$self->{RELS}}) {
	${$r}{rel}->del_way($self, ${$r}{role});
    }
}



package Relation;
@Relation::ISA = ("Entity");

sub new {
    my $class = shift;
    my $self = $class->SUPER::new(@_);
    $self->{WAYS} = [];
    bless ($self, $class);
    return $self;
}

sub add_way {
    my ($self, $way, $role) = @_;
    push @{ $self->{WAYS} }, { way => $way, role => $role };
    $way->add_to_rel($self, $role);
}

sub del_way {
    my ($self, $way, $role) = @_;
    for (my $i=0; $i<$#{$self->{WAYS}}; $i++) {
	my $entry = ${$self->{WAYS}}[$i];
	if (defined($entry) && 
	    ${$entry}{way} == $way &&
	    ${$entry}{role} eq $role) {
	    $way->del_from_rel($self, $role);
	    delete ${$self->{WAYS}}[$i];
	    last;
	}
    }
}

sub get_txt {
    my $self = shift;
    my $s = $self->get_txt_first();
    foreach my $w (@{$self->{WAYS}}) {
	$s .= "    <member type='way' ref='" . ${$w}{way}->id() . "' visible='true' role='" . ${$w}{role} . "' />\n" if defined($w) && defined(${$w}{way});
    }
    $s .= $self->get_txt_rest();
}

sub get_ways {
    my $self = shift;
    return $self->{WAYS};
}














package main;

my %nodes = ();
my %ways = ();
my %rels = ();
my $min_id = -1;

sub read_osm {
    my $in_node = 0;
    my $in_way = 0;
    my $in_rel = 0;
    my $id;

    while (<>) {
	if (!$in_node && /<node .*id=['"]([^'"]*)['"]/) {
	    $id = $1;
	    $min_id = $id - 1 if $id <= $min_id;
	    $nodes{$id} = Node->new($id, $_);
	    $in_node = 1 unless /\/>\W*$/;
	} elsif ($in_node) {
	    $nodes{$id}->add_txt($_);
	    $in_node = 0 if /<\/node>/;
	} elsif (!$in_way && /<way .*id=['"]([^'"]*)['"]/) {
	    $id = $1;
	    $min_id = $id - 1 if $id <= $min_id;
	    $ways{$id} = Way->new($id, $_);
	    $in_way = 1;
	} elsif ($in_way) {
	    if (/<nd .*ref=['"]([^'"]*)['"]/) {
		$ways{$id}->add_node($nodes{$1});
	    } else {
		$ways{$id}->add_txt($_);
		$in_way = 0 if (/<\/way>/);
	    }
	} elsif (!$in_rel && /<relation .*id=['"]([^'"]*)['"]/) {
	    $id = $1;
	    $min_id = $id - 1 if $id <= $min_id;
            $rels{$id} = Relation->new($id, $_);
            $in_rel = 1;
	} elsif ($in_rel) {
	    if (/<member .*type=['"]way['"] .*ref=['"]([^'"]*)['"] .*role=['"]([^'"]*)['"]/) {
		$rels{$id}->add_way($ways{$1}, $2);
	    } else {
		$rels{$id}->add_txt($_);
		$in_rel = 0 if (/<\/relation>/);
	    }
	}
    }
}

# Copy all relations incl. role from src -> tgt
sub copy_relations {
    my ($tgt, $src) = @_;
    my $rels = $src->get_rels();

    foreach my $r (@{$rels}) {
	${$r}{rel}->add_way($tgt, ${$r}{role});
    }
}

sub move_nodes {
    my ($id, $src, $start) = @_;

    if ($Debug) {
	print STDERR "Moving " . $src->id() . "($start) -> $id\n";
    }
    # Initialise new way with same text
    $ways{$id} = Way->new($id, $src->get_txt_first());
    $ways{$id}->add_txt($src->get_txt_rest());
    copy_relations($ways{$id}, $src);

    for (my $i=$start; defined(my $node = $src->get_node($i)); $i++) {
	# Add all nodes to new way
	$ways{$id}->add_node($node);
	# Remove all intermediate nodes from w1
	$src->del_node($i);
    }
}

sub resolve_duplicate {
    my ($w1, $w1_low, $w1_high, $w2, $w2_low, $w2_high) = @_;
    my $id = $min_id--;
    my $w1_max = $w1->node_count()-1;
    my $w2_max = $w2->node_count()-1;

    if ($Debug) {
	print STDERR "Resolving " . $w1->id() . "($w1_low, $w1_high, $w1_max) " . $w2->id() . "($w2_low, $w2_high, $w2_max) -> $id\n";
    }
    # no if
    {
        # Initialise new way with same text
	$ways{$id} = Way->new($id, $w1->get_txt_first());
        $ways{$id}->add_txt($w1->get_txt_rest());
	# Copy relation membership
        copy_relations($ways{$id}, $w1);
	copy_relations($ways{$id}, $w2);

        for (my $i=$w1_low; $i<=$w1_high; $i++) {
	    # Add all nodes to new way
	    $ways{$id}->add_node($w1->get_node($i));
	    # Remove all intermediate nodes from w1
	    $w1->del_node($i) if ($i == 0 || $i == $w1_max || ($i > $w1_low && $i < $w1_high));
	}
	# Remove all intermediate nodes from w2
	for (my $i=$w2_low; $i<=$w2_high; $i++) {
	    $w2->del_node($i) if ($i == 0 || $i == $w2_max || ($i > $w2_low && $i < $w2_high));
	}

        # Move remaining part to new ways
        move_nodes($min_id--, $w1, $w1_high) if ($w1_high < $w1_max);
        move_nodes($min_id--, $w2, $w2_high) if ($w2_high < $w2_max);
    }
}

sub find_duplicate_ways {
    my $node = shift;
    my $found = 1;
    my $first = 1;

    # loop over all unique combinations of ways containing the node
  while ($found) {
    $found = 0;
    my $ways = $node->get_ways();
    print STDERR "Number of ways in node ".$node->id().": ".($#{$ways}+1)."\n";
    for (my $i1=0; $i1<$#{$ways}; $i1++) {
	my $w1 = ${$ways}[$i1];
	next if !defined($w1);
	for (my $i2=$i1+1; $i2<=$#{$ways}; $i2++) {
	    my $w2 = ${$ways}[$i2];
	    next if !defined($w2);
	    my $w1_low = my $w1_high = ${$w1}{offset};
	    my $w2_low = my $w2_high = ${$w2}{offset};

	    # find the longest match from this node on
	    while (defined(my $n1 = ${$w1}{way}->get_node($w1_low-1)) && 
		   defined(my $n2 = ${$w2}{way}->get_node($w2_low-1))) {
		last if ($n1 != $n2);
		$w1_low--; $w2_low--;
	    }
	    while (defined(my $n1 = ${$w1}{way}->get_node($w1_high+1)) &&
	           defined(my $n2 = ${$w2}{way}->get_node($w2_high+1))) {
		last if ($n1 != $n2);
		$w1_high++; $w2_high++;
	    }
	    if ($w1_low == $w1_high) {
		while (defined(my $n1 = ${$w1}{way}->get_node($w1_low-1)) && 
		       defined(my $n2 = ${$w2}{way}->get_node($w2_high+1))) {
		    last if ($n1 != $n2);
		    $w1_low--; $w2_high++;
		}
		while (defined(my $n1 = ${$w1}{way}->get_node($w1_high+1)) &&
		       defined(my $n2 = ${$w2}{way}->get_node($w2_low-1))) {
		    last if ($n1 != $n2);
		    $w1_high++; $w2_low--;
		}
	    }

	    # And remove the duplicate
	    if ($w1_low < $w1_high) {
		print STDERR "Search started at: " . ${$w1}{way}->id() . ", " . ${$w1}{offset} . "\n";
		resolve_duplicate(${$w1}{way}, $w1_low, $w1_high, ${$w2}{way}, $w2_low, $w2_high);
		$found = 1;
		last;
	    }
	}
	last if $found;
    }
  }
}

sub find_duplicate_rels {
    my @rel_keys = keys(%rels);
    for (my $i1=0; $i1<$#rel_keys; $i1++) {
	my $r1 = $rels{$rel_keys[$i1]};
	next unless defined($r1);
	for (my $i2=$i1+1; $i2<=$#rel_keys; $i2++) {
	    my $r2 = $rels{$rel_keys[$i2]};
	    next unless defined($r2);

	    if ($r1->get_value('maaamet:KOOD') eq $r2->get_value('maaamet:KOOD')) {
		print STDERR "Found duplicate relations: " . $rel_keys[$i1] . ", " . $rel_keys[$i2] . "\n";
		my $ways = $r2->get_ways();
		foreach my $w (@{$ways}) {
		    print STDERR "Moving way " . ${$w}{way}->id() . "\n";
		    $r1->add_way(${$w}{way}, ${$w}{role});
		    $r2->del_way(${$w}{way}, ${$w}{role});
		}
		delete $rels{$rel_keys[$i2]};
	    }
	}
    }
}

sub print_osm {
    print "<osm version='0.6' generator='shp2osm.pl'>\n";
    foreach my $r (keys %rels) {
	foreach my $w (@{$rels{$r}->get_ways()}) {
	    if (defined($w) && $w && defined(${$w}{way}) && !${$w}{way}->is_printed()) {
		foreach my $n (@{${$w}{way}->get_nodes()}) {
		    if (defined($n) && $n && !$n->is_printed()) {
			print $n->get_txt();
			$n->set_printed();
		    }
		}
		print ${$w}{way}->get_txt();
		${$w}{way}->set_printed();
	    }
	}
        print $rels{$r}->get_txt();
    }
    foreach my $w (keys %ways) {
	if (!$ways{$w}->is_printed()) {
	    foreach my $n (@{$ways{$w}->get_nodes()}) {
		if (defined($n) && $n && !$n->is_printed()) {
		    print $n->get_txt();
		    $n->set_printed();
		}
	    }
	    print $ways{$w}->get_txt();
	}
    }
    foreach my $n (sort { $b <=> $a } keys %nodes) {
	if (!$nodes{$n}->is_printed()) {
	    print $nodes{$n}->get_txt();
	}
    }
    print "</osm>";
}

# main
read_osm();

#foreach my $k (keys %ways) {
#    print "\nWay Id: $k == " . $ways{$k}->id() . "\n";
#    print "1: " . $ways{$k}->get_txt_first();
#    print "Nodes: " . $ways{$k}->list_nodes() . "\n";
#    print "Txt: " . $ways{$k}->get_txt() . "\n";
#    print "Rels: " . $ways{$k}->list_rels() . "\n";
#}

find_duplicate_rels();

foreach my $k (keys %nodes) {
    find_duplicate_ways($nodes{$k});
}

foreach my $k (keys %ways) {
    my $count = $ways{$k}->node_count();
    print STDERR "Way: " . $ways{$k}->id() . ", Nodes: $count\n";
    if ($count < 1) {
	$ways{$k}->del();
	delete $ways{$k};
    }
    while ($count > 1000) {
	my $id = $min_id--;
        move_nodes($id, $ways{$k}, $count-601);
	# Fix the connection of ways -- yes, that q&d
	$ways{$k}->add_node($ways{$id}->get_node(0));
	$count -= 600;
    }
}

print_osm();