Recipe 11.16 Program: Outlines

Outlines are a simple (and thus popular) way of structuring data. The hierarchy of detail implied by an outline maps naturally to our top-down way of thinking about the world. The only problem is that it's not obvious how to represent outlined data as a Perl data structure.

Take, for example, this simple outline of some musical genres:

Alternative .Punk ..Emo ..Folk Punk .Goth ..Goth Rock ..Glam Goth Country .Old Time .Bluegrass .Big Hats Rock .80s ..Big Hair ..New Wave .60s ..British ..American

Here we use a period to indicate a subgroup. There are many different formats in which that outline could be output. For example, you might write the genres out in full:

Alternative Alternative - Punk Alternative - Punk - Emo Alternative - Punk - Folk Punk Alternative - Goth ...

You might number the sections:

1 Alternative 1.1 Punk 1.1.1 Emo 1.1.2 Folk Punk 1.2 Goth ...

or alphabetize:

Alternative Alternative - Goth Alternative - Goth - Glam Goth Alternative - Goth - Goth Rock Alternative - Punk Alternative - Punk - Emo ...

or show inheritance:

Alternative Punk - Alternative Emo - Punk - Alternative Folk Punk - Punk - Alternative Goth - Alternative Goth Rock - Goth - Alternative ...

These transformations are all much easier than it might seem. The trick is to represent the levels of the hierarchy as elements in an array. For example, you'd represent the third entry in the sample outline as:

@array = ("Alternative", "Goth", "Glam Goth");

Now reformatting the entry is trivial. There's an elegant way to parse the input file to get this array representation:

while (<FH>) {   chomp;   $tag[$in = s/\G\.//g] = $_;   # do something with @tag[0..$in] }

The substitution deletes leading periods from the current entry, returning how many it deleted. This number indicates the indentation level of the current entry.

Alphabetizing is now simple using the Unix sort program:

$ISA = "-"; open(STDOUT, "|sort -b -t'$ISA' -df"); while (<DATA>) {     chomp;     $tag[$in = s/\G\.//g] = $_;     print join(" $ISA ", @tag[0 .. $in]); } close STDOUT; _ _END_ _ Alternative .Punk ..Emo ..Folk Punk .Goth

Numbering the outline is equally simple:

while (<DATA>) {     chomp;     $count[$in = s/\G\.//g]++;     delete @count[($in+1) .. $#count];     print join(".", @count), " $_"; }  _ _END_ _ Alternative .Punk ..Emo ..Folk Punk .Goth ..Goth Rock

Notice that renumbering is our only application where we've deleted elements from the array. This is because we're not keeping names of hierarchy levels in the array; now we're keeping counts. When we go up a level (e.g., from three levels down to a new second-level heading), we reset the counter on the old level.