sort_elements: ignore everything except tags and booleans

[id3fs.git] / lib / ID3FS / Path.pm

diff --git a/lib/ID3FS/Path.pm b/lib/ID3FS/Path.pm
index 0ca6711..8e7c791 100644 (file)
--- a/lib/ID3FS/Path.pm
+++ b/lib/ID3FS/Path.pm
@@ -297,7 +297,11 @@ sub parse
            $self->state($STATE_INVALID);
        }
     }
-    $self->{tagtree}=$self->elements_to_tree(@{$self->{elements}});
+    # sort elements by precedence
+    @{$self->{elements}}=$self->sort_elements(@{$self->{elements}});
+    my $thing=$self->elements_to_tree([ @{$self->{elements}} ]);
+    $self->{tagtree}=$self->elements_to_tree([ @{$self->{elements}} ]);
+#    print($self->{tagtree}->print(), "\n") if $self->{tagtree};
 }
 
 sub state
@@ -309,53 +313,72 @@ sub state
 
 sub elements_to_tree
 {
-    my($self, @elements)=@_;
-    my $op=undef;
-    my $top=undef;
-    my $node=undef;
-    my $lastop=undef;
-    use Data::Dumper;
-    while(my $element=shift @elements)
+    my($self, $elements)=@_;
+    return undef unless(@$elements);
+    my ($left, $right, $op)=(undef, undef, undef);
+    my $thing=pop @$elements;
+    if(ref($thing) eq "ID3FS::PathElement::Boolean")
     {
-       my $tag;
-       if(ref($element) eq "ID3FS::PathElement::Boolean")
+       my $op=$thing;
+       $right=$self->elements_to_tree($elements);
+       if($op->{name} ne "NOT")
        {
-           $lastop=$op;
-           $op=$element->{name};
-#          print "BOOL: $op\n";
+           $left=$self->elements_to_tree($elements);
        }
-       if(ref($element) eq "ID3FS::PathElement::Tag")
+       return ID3FS::Path::Node->new($left, $op, $right);
+    }
+    else
+    {
+       return ID3FS::Path::Node->new($thing);
+    }
+}
+
+# Dijkstra's shunting-yard algorithm
+sub sort_elements
+{
+    my ($self, @input)=@_;
+    my @opstack=();
+    my @output=();
+#    print "INPUT: ", join(', ', map { $_->{name}; } @input), "\n";
+    while(my $thing = shift @input)
+    {
+       if(ref($thing) eq "ID3FS::PathElement::Tag")
        {
-           $tag=$element->{name};
-           while(@elements && ref($elements[0]) eq "ID3FS::PathElement::Tag")
-           {
-               $tag .= "/" . (shift @elements)->{name};
-           }
-#          print "TAG: $tag\n";
-           my $node=ID3FS::Path::Node->new($tag);
-           if(!$top)
-           {
-               $top=$node;
-           }
-           elsif($op)
+#          print "Pushing $thing->{name} to output\n";
+           push(@output, $thing);
+#          print "OPSTACK: ", join(', ', map { $_->{name}; } @opstack), "\n";
+#          print "OUTPUT: ", join(', ', map { $_->{name}; } @output), "\n";
+       }
+       elsif(ref($thing) eq "ID3FS::PathElement::Boolean")
+       {
+#          print "BOOL: $thing->{name}\n";
+           # bool
+#          print "thing: $thing->{name}: $priorities{$thing->{name}} ";
+           if(@opstack)
            {
-               my $nextop=undef;
-               if(!defined($lastop) || ($priorities{$lastop} >= $priorities{$op}))
-               {
-                   $top=ID3FS::Path::Node->new($node, $op, $top);
-               }
-               else
-               {
-                   $top=ID3FS::Path::Node->new($top, $op, $node);
-               }
+#              print("topop: ", $opstack[$#opstack]->{name},
+#                    ": ", $priorities{$opstack[$#opstack]->{name}}, "\n");
            }
-           else
+           while(@opstack &&
+                 ($priorities{$thing->{name}} <= $priorities{$opstack[$#opstack]->{name}}))
            {
-               die ("FAIL - SHOULD NOT HAPPEN\n");
+#              print "Pushing ", $opstack[$#opstack]->{name}, " from opstack to output\n";
+               push(@output, pop(@opstack));
+#              print "OPSTACK: ", join(', ', map { $_->{name}; } @opstack), "\n";
+#              print "OUTPUT: ", join(', ', map { $_->{name}; } @output), "\n";
            }
+#          print "Pushing $thing->{name} to opstack\n";
+           push(@opstack, $thing);
+#          print "OPSTACK: ", join(', ', map { $_->{name}; } @opstack), "\n";
+#          print "OUTPUT: ", join(', ', map { $_->{name}; } @output), "\n";
        }
     }
-    print($top->print(), "\n") if $top;
+    while(@opstack)
+    {
+       push(@output, pop(@opstack));
+    }
+#    print "STACK: ", join(', ', map { $_->{name}; } @output), "\n";
+    return @output;
 }
 
 1;