recursive sort 
Author Message
 recursive sort

Greetings,

I have an array of strings representing directory entries, as such:

size:depth:name

For example:

300:0:/
100:1:usr/
50:2:local/
200:1:var/
100:2:spool/

Would represent

/
  usr/
    local/
  var/
    spool/

'depth' is how far into the filesystem the directory in question is. The
size field is recursive, so a parent's size will never be larger than a
child.

Anyhow, the problem is this. I want to sort this tree by size, so that the
largest directory is at the top, while maintianing a valid representation of
the directory structure. I imagine this will require a rather tricky
recursive function.

Perhaps a better approach would be an array of references to arrays. I'm
avoiding re-traversal of the tree though... ack!

TiA,

sh



Mon, 17 May 2004 21:09:06 GMT  
 recursive sort

Quote:
> Greetings,

> I have an array of strings representing directory entries, as such:

> size:depth:name

(snip)

Quote:
> Anyhow, the problem is this. I want to sort this tree by size, so that the
> largest directory is at the top, while maintianing a valid representation
of
> the directory structure. I imagine this will require a rather tricky
> recursive function.

(snip)

Somebody will probably post a one-liner... :)

But here is a recursive solution-

Steve

#!/usr/bin/perl

use strict;
use warnings;

my $indent = "  ";

while (<DATA>) {
    chomp;
    my ($size,$depth,$name) = split /:/   or next;

    my $node = {
            name  => $name,
            size  => $size,
            depth => $depth,
            kids  => []
    };


    $refs[$depth] = $node;

Quote:
}

sub recprint {
    while (my $node = shift) {
        printf "%6d %s $node->{name}\n",
            $node->{size}, $indent x $node->{depth};

        recprint(

        );
    }

Quote:
}

recprint($refs[0]);

__END__
380:0:/
100:1:usr/
50:2:local/
280:1:var/
100:2:spool/



Mon, 17 May 2004 22:03:34 GMT  
 recursive sort
[Posted and mailed]



Quote:
> Greetings,

> I have an array of strings representing directory entries, as such:

> size:depth:name

> For example:

> 300:0:/
> 100:1:usr/
> 50:2:local/
> 200:1:var/
> 100:2:spool/

> Would represent

> /
>   usr/
>     local/
>   var/
>     spool/

> 'depth' is how far into the filesystem the directory in question is. The
> size field is recursive, so a parent's size will never be larger than a
> child.

That didn't make any sense to me.   How do I know that spool is a child
of var, for example?  What if I have these pathnames on my system:

        /var/spool/mail
        /var/spool/blah
        /usr/spool/printers
        /etc/spool/config

Would I get:

0:/
1:var/
2:spool/
3:mail/
3:blah/
1:usr/
2:spool/
3:printers/
1:etc/
2:spool/
3:config/

(without sizes..)

Is that the structure you have here?

Quote:
> Anyhow, the problem is this. I want to sort this tree by size, so that the
> largest directory is at the top, while maintianing a valid representation of
> the directory structure. I imagine this will require a rather tricky
> recursive function.

If this is the case, it's not tricky at all.  Simply:

        * map each line into it's full representation:

                X:0:/
                X:1:/spool/
                X:2:/spool/mail/
                X:3:/spool/blah/
                X:1:/usr/
                X:2:/usr/spool/
                X:3:/usr/spool/printers/
                etc...

        * Sort this:

                alphabetically by pathname (slashes and all...)
                then
                numerically by size (shown as X's)

        * Then take the resulting array and s/.*([^/]+\/)/$1/g
          each element

The implementation is left as an exercise for the reader.

--
    Clinton A. Pierce            Teach Yourself Perl in 24 Hours  *and*

"If you rush a Miracle Man,     for details, see http://geeksalad.org    
        you get rotten Miracles." --Miracle Max, The Princess Bride



Mon, 17 May 2004 22:48:01 GMT  
 recursive sort

Quote:
> That didn't make any sense to me.   How do I know that spool is a child
> of var, for example?  What if I have these pathnames on my system:

> /var/spool/mail
> /var/spool/blah
>         /usr/spool/printers
>         /etc/spool/config

> Would I get:

> 0:/
> 1:var/
> 2:spool/
> 3:mail/
> 3:blah/
> 1:usr/
> 2:spool/
> 3:printers/
> 1:etc/
> 2:spool/
> 3:config/

> (without sizes..)

> Is that the structure you have here?

Yes, that's exactly it.

- Show quoted text -

Quote:
> If this is the case, it's not tricky at all.  Simply:

> * map each line into it's full representation:

> X:0:/
> X:1:/spool/
> X:2:/spool/mail/
> X:3:/spool/blah/
> X:1:/usr/
> X:2:/usr/spool/
> X:3:/usr/spool/printers/
> etc...

> * Sort this:

> alphabetically by pathname (slashes and all...)
> then
> numerically by size (shown as X's)

> * Then take the resulting array and s/.*([^/]+\/)/$1/g
>   each element

> The implementation is left as an exercise for the reader.

The problem is that each item is dependent on its parent, which is always
above it. Simply reordering all the items would break everything.

sh



Mon, 17 May 2004 22:54:55 GMT  
 recursive sort

(snipped)

Quote:
> I have an array of strings representing directory entries, as such:
> size:depth:name
> For example:
> 300:0:/
> 100:1:usr/
> 50:2:local/
> 200:1:var/
> 100:2:spool/
> Anyhow, the problem is this. I want to sort this tree by size, so that the
> largest directory is at the top, while maintianing a valid representation of
> the directory structure. I imagine this will require a rather tricky
> recursive function.

Your article is poorly written. Your parameters are unclear.
I personally cannot, with any certainty, be sure of what is
being asked by you. This format you display, is very vague.
You provide no explanation for your second field. You have
failed to indicate if you are working with total number of
files or the total of all file sizes. Only thing which is
moderately clear, is you want to maintain full paths.

Appears to me you are asking:

 "How do I sort directories by number of files contained in each
  directory and, maintain my full paths to each directory, sorted
  in descending directory size order by total number of files?"

Do work at writing clear, concise and coherent articles. Use of
Plain English works well as does reading your article several
times and asking yourself, "How will others interpret this?"

Vagueness is reserved for prose, poetry and music lyrics along
with dragon riddles.

I've tossed together a test script which will perform what I believe
you to be asking. It performs deep recursion, tallies a total file
count for each directory, then performs a descending sort based on
number of files per directory. My sorting is based on a presumption
you wish your first "field" to contain a total number of files.
Numerically named directories could pose a problem. Keep this in
mind for a sort. Additionally, my test script does not count a
child directory as a file; my counter ignores sub-directories.

This test script also eliminates this problem of identifying parallel
child directories, a problem you don't appear to have addressed; this
is not in your unclear and limited parameters.

If this is not what you want, perhaps some snippets will prove
useful to you.

Again, please work at writing clear, concise and coherent articles.
Doing so is a display of courtesy towards the reader.

This is where you plug in your starting directory:

$internal_path = "c:/apache/users/{*filter*}";

Give this a whirl and discover if my script approximates what you want.
Be sure to exhaustively test this script; I wrote this based on a lot
of presumptions due to your poorly written article.

Godzilla!
--

TEST SCRIPT:
____________

#!perl

print "Content-type: text/plain\n\n";

$internal_path = "c:/apache/users/{*filter*}";

chdir($internal_path);


 {

  opendir(DIR, $directory) || next;
  while (defined($child = readdir(DIR)))
   {
    if (-d "$directory/$child" && $child ne "." && $child ne "..")

    if (-f "$directory/$child")
     { $counter++; }
   }

  closedir(DIR);
  $counter = 0;
 }

$" = "\n";


$" = " ";

exit;



Tue, 18 May 2004 00:56:23 GMT  
 recursive sort

(snipped)

Quote:
> > I have an array of strings representing directory entries, as such:
> > size:depth:name
> > For example:
> > 300:0:/
> You provide no explanation for your second field.

I have given some thought to what you mean by "depth" in
your article. My current presumption is you mean how "deep"
is a child directory, relative to the ultimate upward parent
directory, or "c:/" in my code. I have no clue on how you
personally count depth; there are no rules on this.

Some consider  c:/  as zero and some consider  c:/  as one.

Find this:

    if (-f "$directory/$child")
     { $counter++; }
   }

Change those lines to this:

    if (-f "$directory/$child")
     {
      $counter++;
      $depth = "$directory/$child";
      $depth = ($depth =~ tr/\/// - 1);
     }
   }

I've subtracted one from my depth count to reflect my personal
definition of depth. You may change my arithmetic to reflect
your own personal choice for depth.

A pretty print could be had by padding numbers with a zero
or zeroes as needed. Another personal choice on this. I like
the trailing slash on my prints but this too could be changed.
Removing those trailing slashes will change your depth count.

Labels for each field is something I would add for a crisp
clean looking print accessorized with zero padded numbers;
looks better when all is lined up and nice, gives it a
professional look.

Godzilla!
--
   "Do not pay any attention to what Godzilla says. It is a troll, and
    has no decent working knowledge of Perl or programming in general.
    Search groups.google.com to see a history of its posts and replies
    to these posts."

          - The CLPM Troll aka a myriad fake names.



Tue, 18 May 2004 03:01:29 GMT  
 recursive sort
[Posted and mailed]



Quote:

>> * Sort this:

>> alphabetically by pathname (slashes and all...)
>> then
>> numerically by size (shown as X's)

>> * Then take the resulting array and s/.*([^/]+\/)/$1/g
>>   each element

>> The implementation is left as an exercise for the reader.

> The problem is that each item is dependent on its parent, which is always
> above it. Simply reordering all the items would break everything.

Yes, but the beauty is that the reordering _as_I've_described_it will
preserve that structure for you.  Takes some grokking, but I've done this
trick and it works.  :)  Good luck.

--
    Clinton A. Pierce            Teach Yourself Perl in 24 Hours  *and*

"If you rush a Miracle Man,     for details, see http://geeksalad.org    
        you get rotten Miracles." --Miracle Max, The Princess Bride



Tue, 18 May 2004 03:56:22 GMT  
 recursive sort

Quote:

> Greetings,

> I have an array of strings representing directory entries, as such:

> size:depth:name

> For example:

> 300:0:/
> 100:1:usr/
> 50:2:local/
> 200:1:var/
> 100:2:spool/

> Would represent

> /
>   usr/
>     local/
>   var/
>     spool/

> 'depth' is how far into the filesystem the directory in question is.
> The size field is recursive, so a parent's size will never be larger
> than a child.

> Anyhow, the problem is this. I want to sort this tree by size, so that
> the largest directory is at the top, while maintianing a valid
> representation of the directory structure. I imagine this will require
> a rather tricky recursive function.

> Perhaps a better approach would be an array of references to arrays.
> I'm avoiding re-traversal of the tree though... ack!


while( <DATA> ) {
   chomp;
   my ($size, $depth, $name) = split /:/;




   $tree{$node}{size} = $size;
   $tree{$node}{depth} = $depth;
   $tree{$node}{name} = $name;

Quote:
}

sort_print("/");

sub sort_print {
   my $path = shift;
   my $item = $tree{$path};
   my $depth = $$item{depth} + 1;

   sort_print $_
       foreach
       sort {$tree{$a}{size} <=> $tree{$b}{size}}

Quote:
}

It's recursive, yes, but not especially "tricky"

--
Klein bottle for rent - inquire within.



Fri, 21 May 2004 10:57:34 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Recursive sorting

2. Recursive Sort

3. Newbie: Recursive data structure with recursive subroutine.

4. Recursive subroutine output to recursive subroutine problem

5. re-sorting a sorted list (and sorting by date)

6. YAPSQ (Perl Style Question): sorting and maintaining sorted order

7. Perl sort different from unix sort

8. SORT sort hash with alpha-numeric keys

9. Sorting a hash by value and sub sorting the keys

10. PROPOSAL: Sort::Topological: general topological sorting of acyclic directed graphs

11. PERLFUNC: sort - sort a list of values

12. PERLFUNC: sort - sort a list of values

 

 
Powered by phpBB® Forum Software