From 0ec7164718e571df6fbeb0abfbaa1fe16af20575 Mon Sep 17 00:00:00 2001 From: Ian Beckwith Date: Wed, 6 Oct 2010 05:57:28 +0100 Subject: [PATCH] assemble tag expression into binary tree, respecting precedence --- lib/ID3FS/DB.pm | 20 +++++----- lib/ID3FS/Path.pm | 99 +++++++++++++++++++++++++++++++------------------- lib/ID3FS/Path/Node.pm | 6 +-- 3 files changed, 74 insertions(+), 51 deletions(-) diff --git a/lib/ID3FS/DB.pm b/lib/ID3FS/DB.pm index bbb1be5..e986f36 100644 --- a/lib/ID3FS/DB.pm +++ b/lib/ID3FS/DB.pm @@ -225,7 +225,7 @@ sub tags $sql .= join("\n\tAND ", @andclauses) . "\n"; } $sql .= "GROUP BY t2.name;"; - print "SQL: $sql\n"; +# print "SQL: $sql\n"; my $result=$self->cmd_rows($sql); my @tagnames=map { $_->[0]; } @$result; print "SUBNAMES: ", join(', ', @tagnames), "\n"; @@ -259,7 +259,7 @@ sub artists "INNER JOIN files ON subselect.files_id=files.id\n" . "INNER JOIN artists ON files.artists_id=artists.id\n" . "GROUP BY artists.name;"); - print "SQL: $sql\n"; +# print "SQL: $sql\n"; my $result=$self->cmd_rows($sql); my @tagnames=map { $_->[0]; } @$result; print "ARTISTS: ", join(', ', @tagnames), "\n"; @@ -299,7 +299,7 @@ sub artist_albums "INNER JOIN artists ON artists.id=files.artists_id\n\t" . "WHERE artists.id=? and albums.name <> ''\n\t" . "GROUP BY albums.name\n"); - print "ARTIST_ALBUMS SQL: $sql\n"; +# print "ARTIST_ALBUMS SQL: $sql\n"; my $result=$self->cmd_rows($sql, $artist_id); my @albums=map { $_->[0]; } @$result; print "ALBUMS: ", join(', ', @albums), "\n"; @@ -317,7 +317,7 @@ sub artist_tracks "INNER JOIN albums ON albums.id=files.albums_id\n\t" . "WHERE artists.id=? AND albums.name=''\n\t" . "GROUP BY files.name\n"); - print "ARTIST_TRACKS SQL: $sql\n"; +# print "ARTIST_TRACKS SQL: $sql\n"; my $result=$self->cmd_rows($sql, $artist_id); my @names=map { $_->[0]; } @$result; print "ARTISTTRACKS: ", join(', ', @names), "\n"; @@ -332,7 +332,7 @@ sub album_tracks "INNER JOIN artists ON artists.id=files.artists_id\n\t" . "WHERE artists.id=? AND albums.id=?\n\t" . "GROUP BY files.name\n"); - print "ALBUM_TRACKS SQL($artist_id, $album_id): $sql\n"; +# print "ALBUM_TRACKS SQL($artist_id, $album_id): $sql\n"; my $result=$self->cmd_rows($sql, $artist_id, $album_id); my @names=map { $_->[0]; } @$result; print "TRACKS: ", join(', ', @names), "\n"; @@ -365,7 +365,7 @@ sub tracks "\t) AS subselect\n" . "INNER JOIN files ON files.id=subselect.files_id\n" . "GROUP BY files.name;"); - print "SQL: $sql\n"; +# print "SQL: $sql\n"; my $result=$self->cmd_rows($sql); my @names=map { $_->[0]; } @$result; print "TRACKS: ", join(', ', @names), "\n"; @@ -382,7 +382,7 @@ sub filename "INNER JOIN paths ON files.paths_id=paths.id\n" . "WHERE files.id=?\n" . "GROUP BY paths.name, files.name"); - print "FILENAME SQL: $sql\n"; +# print "FILENAME SQL: $sql\n"; my ($path, $name)=$self->cmd_onerow($sql, $id); my $id3fs_path=join('/', map { $_->{name}; } @constraints); return($self->relativise($path, $name, $mountpoint, $id3fs_path)); @@ -403,8 +403,8 @@ sub tags_subselect my @andclauses=(); if(@tags) { - push(@andclauses, "( t1.parents_id=" . (defined($parent) ? $parent : "''") . " )"); - push(@andclauses, "( t1.id IN ( " . join(', ', @tags) ." ) )"); + push(@orclauses, "( t1.parents_id=" . (defined($parent) ? $parent : "''") . " )"); + push(@orclauses, "( t1.id IN ( " . join(', ', @tags) ." ) )"); } for my $pair (@tags_vals) { @@ -703,7 +703,7 @@ sub prune_paths return unless(@ids); my $sql=("DELETE FROM files WHERE paths_id IN (\n\t" . join(', ', map { "\"$_\""; } @ids). "\n\t)"); - print "SQL: \n", $sql, "\n"; +# print "SQL: \n", $sql, "\n"; $self->cmd($sql); } diff --git a/lib/ID3FS/Path.pm b/lib/ID3FS/Path.pm index 0ca6711..d4fec73 100644 --- 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 "\nINPUT: ", 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"; + } + else + { +# 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; diff --git a/lib/ID3FS/Path/Node.pm b/lib/ID3FS/Path/Node.pm index 08c2088..b692750 100644 --- a/lib/ID3FS/Path/Node.pm +++ b/lib/ID3FS/Path/Node.pm @@ -37,9 +37,9 @@ sub print my $op=$self->op(); my $left=$self->left(); my $right=$self->right(); - return undef unless($left || $right); + return "" unless($left || $right); my $str .= $self->print_node($left); - $str .= " $op " if($op); + $str .= (" " . $op->{name} . " ") if($op); $str .= $self->print_node($right); if($op || ($left && $right)) { @@ -53,7 +53,7 @@ sub print_node my($self, $node)=@_; return "" unless(defined($node)); return $node->print() if(ref($node) eq "ID3FS::Path::Node"); - return $node; + return $node->{name}; } 1; -- 2.11.0