use Tree::DAG_Node;
use Data::Dumper;
use Net::IP;
# compares two Tree::DAG Nodes and returns positive if right (second) argument is bigger
sub compare_nodes {
	my ($compare_node, $leaf_node) = @_;
	my $source_OK = compare_subnet($compare_node->{'attributes'}{'source'},$leaf_node->{'attributes'}{'source'});
	my $destination_OK = compare_subnet($compare_node->{'attributes'}{'destination'},$leaf_node->{'attributes'}{'destination'});
	print "$compare_node->{'attributes'}{'original'} is a daughter of $leaf_node->{'attributes'}{'original'}\n\n" if ($source_OK && $destination_OK);
	return 1 if ($source_OK && $destination_OK);
	return undef;
}

# create nodes for tree construction later on
my $root = Tree::DAG_Node->new;
$root->attributes ({
		original => 'permit ip any any',
		source => ['0.0.0.0/0'], 
		destination => ['0.0.0.0/0']
	});

my $leaf_1 = Tree::DAG_Node->new;
$leaf_1->attributes ({
		original => 'permit ip 10.0.0.0/8 172.16.0.0/16',
		source => ['10.0.0.0/8'], 
		destination => ['172.16.0.0/16']
	});

my $leaf_2 = Tree::DAG_Node->new;
$leaf_2->attributes ({
		original => 'permit ip 10.0.0.0/16 172.16.0.0/24',
		source => ['10.0.0.0/16'], 
		destination => ['172.16.0.0/24']
	});

my $leaf_3 = Tree::DAG_Node->new;
$leaf_3->attributes ({
		original => 'permit ip 192.168.0.0/16 12.16.0.0/24',
		source => ['192.168.0.0/16'], 
		destination => ['12.16.0.0/24']
	});

my @node_list;
push @node_list, $leaf_1, $leaf_2, $leaf_3 ;

# Subnet comparison
# returns true if $x is a subset of $y
sub compare_subnet {
    my ($x, $y) = @_;
    a_in_b ($_, @$y) or return '' foreach @$x;		#Check if each element of 
    return 1;
};


# check one ip address against array of ip addresses
# first argument is single address, second one is array
sub a_in_b  {
  my $node1 = shift(@_);
  my @ip_list = @_;
  for my $node2 (@ip_list) {
    my $ip1 = new Net::IP ($node1) || die (Net::IP::Error());
    my $ip2 = new Net::IP ($node2) || die (Net::IP::Error());
    if (($ip1->overlaps($ip2) == $IP_A_IN_B_OVERLAP) || ($ip1->overlaps($ip2) ==  $IP_IDENTICAL))  {
      return 1;
    }
    
  }
  return '';
}

#build the tree
foreach my $node (@node_list){
	my $location;
	$root->walk_down({
			callback => sub {
				my $this_node = shift;
				if (compare_nodes($node,$this_node)){
					$location = $this_node->address;
					1;
				}
				else{
					0;
				}
			}

		});
	$root->address($location)->add_daughter($node) if defined $root->address($location);
}

# print the tree
$root->walk_down({
    callback => sub {
        my $node = shift;
            print "  " x $_[0]->{_depth};
            print $node->{'attributes'}{'original'}, "\n";
        },
    _depth => 0,
});

$root->delete_tree();

##</code><code>##

permit ip any any
  permit ip 10.0.0.0/8 172.16.0.0/16
    permit ip 10.0.0.0/16 172.16.0.0/24
  permit ip 192.168.0.0/16 12.16.0.0/24

##</code><code>##

root > A > B > C

##</code><code>##

[A,C,B]
##</code><code>##

root
 A
  C
  B

##</code><code>##

root
 A
  B
   C