Changeset 15683 for trunk/ippScripts/scripts/magic_tree.pl

Timestamp:

Nov 21, 2007, 5:11:47 PM (18 years ago)

Author:

Paul Price

Message:

Updating to use up to 4 branches per node.

File:

• trunk/ippScripts/scripts/magic_tree.pl (modified) (4 diffs)

trunk/ippScripts/scripts/magic_tree.pl

@@ -189 +189 @@
     contents => \@fields,       # Contents of node
     position => 'root',         # Position in tree
+    children => {},             # Children of node
 };
 my @tasks = ( $root );
@@ -242 +243 @@
 }
 
-# Divide a node into upper and lower nodes
+# Divide a list into two, returning the lower and upper parts
+sub divide_list
+{
+    my $list = shift;           # List to divide
+    my $index = shift;          # Name of index for sorting
+
+    my @sorted = sort { $$a{$index} <=> $$b{$index} } @$list; # Sorted list
+    my $median = int(scalar @sorted / 2); # Median point of list
+    my @upper = splice(@sorted, $median); # Upper part of the sorted list
+
+    return (\@sorted, \@upper);
+}
+
+# Create a new node, add it to the parent, and add it to the task list if required
+sub new_node
+{
+    my $parent = shift;         # The parent node
+    my $contents = shift;       # Contents of the new node
+    my $position = shift;       # Position description
+    my $tasks = shift;          # Tasks to do
+
+    my $node = {
+        contents => $contents,
+        position => $parent->{position} . '_' . $position,
+        children => {},
+    };
+
+    $parent->{children}->{$position} = $node;
+
+    push @$tasks, $node if scalar @$contents > 4;
+
+    return $node;
+}
+
+# Divide a node
 sub divide_node
 {
@@ -251 +286 @@
 
     my $contents = $node->{contents} or die "Can't find contents of node."; # Contents of node
-    my $index = (not defined $node->{index} or $node->{index} eq 'xi') ? 'eta' : 'xi'; # Property to sort
-    my @sorted = sort { $$a{$index} <=> $$b{$index} } @$contents; # Sorted list
-    my $median = int(scalar @sorted / 2); # Median point of list
-    my @top = splice(@sorted, $median); # Top of the sorted list
-
-    my $upper = {               # Upper node
-        contents => \@top,
-        index => $index,
-        position => $node->{position} . 'U',
-    };
-    my $lower = {               # Lower node
-        contents => \@sorted,
-        index => $index,
-        position => $node->{position} . 'L',
-    };
-
-    $node->{upper} = $upper;
-    $node->{lower} = $lower;
+
+    my ($lower, $upper) = divide_list($contents, 'xi');
+
+    if (scalar @$lower > 4) {
+        my ($ll, $lr) = divide_list($lower, 'eta');
+        new_node($node, $ll, 'll', $tasks);
+        new_node($node, $lr, 'lr', $tasks);
+    } else {
+        new_node($node, $lower, 'L', $tasks);
+    }
+
+    if (scalar @$upper > 4) {
+        my ($ul, $ur) = divide_list($upper, 'eta');
+        new_node($node, $ul, 'ul', $tasks);
+        new_node($node, $ur, 'ur', $tasks);
+    } else {
+        new_node($node, $upper, 'U', $tasks);
+    }
+
     $node->{contents} = undef;
-
-    push @$tasks, $upper if scalar @top > MAX_FIELDS;
-    push @$tasks, $lower if scalar @sorted > MAX_FIELDS;
 
     return $node;
@@ -293 +326 @@
         }
     } else {
-        $output .= "$position\t\tSTR\t${position}L\n";
-        $output .= "$position\t\tSTR\t${position}U\n";
-        $output .= print_node($node->{lower});
-        $output .= print_node($node->{upper});
+        foreach my $div ( keys %{$node->{children}} ) {
+            $output .= "$position\t\tSTR\t${position}_$div\n";
+            $output .= print_node($node->{children}->{$div});
+        }
     }