1

To make it simple, I am trying to get this heap to print in a tree like format. It's close but I know I am missing stuff, but I just can't wrap my head around this module. I know there is tree::simple and I think just Tree? But I can't really find any tutorials on how to actually use with a list or a array. The heap sort is right, cause it's sorting the list after the tree has been posted but I can't figure how to draw the tree correctly, then again outputting has never been my strong suit on any language. I think it's not grabbing the data from the file? least that is my idea but i'm not confident enough to be sure. here is my code so far.

#!/usr/bin/perl

use 5.006;
use strict;
use warnings;
use Tree::DAG_Node;

process_data(read_file('data.txt'));
process_data((3,1,4,1,5,9,2,6,5,3,6));

sub read_file{
    my($filename)=@_;
    my @data=();
    my @words;
    open(my $fh, "<", $filename)
        or die "Could not open file: $!\n";
    while(<$fh>){
        chomp;
        @words = split(' ');
        foreach my $word(@words) {
            push @data, $word;
        }
    }
    close $fh;
    return @data;
}


sub heap_sort {
    my ($a) = @_;
    my $n = @$a;
    for (my $i = ($n - 2) / 2; $i >= 0; $i--) {
        down_heap($a, $n, $i);
    }
    for (my $i = 0; $i < $n; $i++) {
        my $t = $a->[$n - $i - 1];
        $a->[$n - $i - 1] = $a->[0];
        $a->[0] = $t;
        down_heap($a, $n - $i - 1, 0);
    }
}

sub down_heap {
    my ($a, $n, $i) = @_;
    while (1) {
        my $j = max($a, $n, $i, 2 * $i + 1, 2 * $i + 2);
        last if $j == $i;
        my $t = $a->[$i];
        $a->[$i] = $a->[$j];
        $a->[$j] = $t;
        $i = $j;
    }

    sub max {
        my ($a, $n, $i, $j, $k) = @_;
        my $m = $i;
        $m = $j if $j < $n && $a->[$j] > $a->[$m];
        $m = $k if $k < $n && $a->[$k] > $a->[$m];
        return $m;
    }
}

sub draw_tree{
    my(@data)=@_;
    my $root = Tree::DAG_Node->new;
    $root->name($_[0]);
    $root->new_daughter->name($_) for ('1'..'10');
    my @names = @data;
    my $count =0;
    for my $n ($root->daughters) {
        for (split //, $names[$count++]) {
            $n->new_daughter->name($_)
        }
    }
    print map "$_\n", @{$root->draw_ascii_tree};
}

sub process_data{
    my(@data)=@_;
    my @a = @data;
    print "@a\n";
    print "\n";
    heap_sort(\@a);
    print "\n";
    print "@a\n";
    print "\n";
    draw_tree(@a);
} 

and here is the output I am getting so far.

10,4,5,2,1,7

Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
Use of uninitialized value in split at HEAPSORTtree.pl line 77.
                                                       |

                                                 <10,4,5,2,1,7>

                                     /---------------------------------------+--
-+---+---+---+---+---+---+---\
                                     |                                       |
 |   |   |   |   |   |   |   |
                                    <1>                                     <2>
<3> <4> <5> <6> <7> <8> <9> <10>
 /-----------------+-----------------+---+---+---+---+---+---+---+---+---\

 |                 |                 |   |   |   |   |   |   |   |   |   |

<1> <Tree::DAG_Node=HASH(0x4b32dc)> <,> <4> <,> <5> <,> <2> <,> <1> <,> <7>


10,4,5,2,1,7

3 1 4 1 5 9 2 6 5 3 6

                   |
                  <1>
 /---+---+---+---+---+---+---+---+---\
 |   |   |   |   |   |   |   |   |   |
<1> <2> <3> <4> <5> <6> <7> <8> <9> <10>
 |   |   |   |   |   |   |   |   |   |
<1> <1> <2> <3> <3> <4> <5> <5> <6> <9>

1 1 2 3 3 4 5 5 6 9 6

Press any key to continue . . .

the output I want is similar to this

|               
            <root>             
     /-------+-------+-------\ 
     |       |       |       | 
    <1>     <d>     <e>     <f>
 /---+---\           |         
 |   |   |          <3>        
<a> <b> <c>      /---+---\     
                 |   |   |     
                <g> <h> <i>   
Håkon Hægland
  • 39,012
  • 21
  • 81
  • 174
Dom
  • 21
  • 2
  • What is the content of `data.txt`? – Håkon Hægland Apr 30 '18 at 12:29
  • 1
    The content of the data.txt is 10,4,5,2,1,7 – Dom Apr 30 '18 at 12:40
  • Note that the nested sub `max()` is not private to `down_heap()`, see [Nested subroutines and Scoping in Perl](https://stackoverflow.com/q/10192228/2173773) for more information. However, lexical subroutines are available beginning from Perl version 5.18, see [`perdoc perlsub`](https://perldoc.perl.org/perlsub.html#Lexical-Subroutines). – Håkon Hægland Apr 30 '18 at 13:24
  • oh! Oh my gosh, Sorry max() wasn't suppose to be that far indented like that, I just looked at it vs the code I had. – Dom Apr 30 '18 at 16:15
  • And I was wrong about the content of the data.txt. it's 10 4 5 2 1 7 – Dom Apr 30 '18 at 16:29
  • And should I nest it? The heap sort works(as it's sorting just about everything I throw at it) but I'm not getting the correct output with this module. – Dom Apr 30 '18 at 16:36
  • Hello @Dom. No need to nest the `max()` sub routine. I wonder what is the purpose of this line: `$root->new_daughter->name($_) for ('1'..'10')` ? Why are you adding 10 daughter nodes? – Håkon Hægland Apr 30 '18 at 17:58
  • Hey @HåkonHægland. I put that in as filler when I was writing as when I tried to reference anything else, it wouldn't accept it as something to display. – Dom Apr 30 '18 at 20:41
  • @HåkonHægland I've been messing around with this module some more, and managed to get it to display certain numbers depending on their potion in the list. I think I just need to code a way to compare to nodes and also swap them while also comparing new inserts with stuff already in the tree. – Dom May 01 '18 at 00:16

0 Answers0