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 de55ce1..8e7c791 100644 (file)
--- a/lib/ID3FS/Path.pm
+++ b/lib/ID3FS/Path.pm
@@ -8,11 +8,14 @@ use ID3FS::PathElement::Boolean;
 use ID3FS::PathElement::File;
 use ID3FS::PathElement::Tag;
 use ID3FS::PathElement::Tagval;
+use ID3FS::Path::Node;
 
 our ($STATE_INVALID, $STATE_ROOT, $STATE_TAG, $STATE_TAGVAL,
      $STATE_BOOLEAN, $STATE_ALBUMS, $STATE_TRACKLIST,
      $STATE_FILE)=(0..7);
 
+our %priorities=( "OR" => 0, "AND" => 1, "NOT" => 2 );
+
 sub new
 {
     my $proto=shift;
@@ -294,6 +297,11 @@ sub parse
            $self->state($STATE_INVALID);
        }
     }
+    # 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
@@ -303,4 +311,74 @@ sub state
     return $self->{state};
 }
 
+sub elements_to_tree
+{
+    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 $op=$thing;
+       $right=$self->elements_to_tree($elements);
+       if($op->{name} ne "NOT")
+       {
+           $left=$self->elements_to_tree($elements);
+       }
+       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")
+       {
+#          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)
+           {
+#              print("topop: ", $opstack[$#opstack]->{name},
+#                    ": ", $priorities{$opstack[$#opstack]->{name}}, "\n");
+           }
+           while(@opstack &&
+                 ($priorities{$thing->{name}} <= $priorities{$opstack[$#opstack]->{name}}))
+           {
+#              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";
+       }
+    }
+    while(@opstack)
+    {
+       push(@output, pop(@opstack));
+    }
+#    print "STACK: ", join(', ', map { $_->{name}; } @output), "\n";
+    return @output;
+}
+
 1;