########################################################################### # # List.pm -- A general and flexible list classifier with most of # the abilities of AZCompactList, and better Unicode, # metadata and sorting capabilities. # # A component of the Greenstone digital library software # from the New Zealand Digital Library Project at the # University of Waikato, New Zealand. # # # Copyright (C) 2005 New Zealand Digital Library Project # # This program is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with this program; if not, write to the Free Software # Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. # # TO DO: - Add an AZCompactList-style hlist option? # ########################################################################### package List; use BaseClassifier; use Sort::NaturallyGS; # for gsort use strict; sub BEGIN { @List::ISA = ('BaseClassifier'); } my $metadata_selection_mode_list = [ { 'name' => "firstvalue", 'desc' => "{List.metadata_selection.firstvalue}"}, { 'name' => "firstvalidmetadata", 'desc' => "{List.metadata_selection.firstvalidmetadata}"}, { 'name' => "allvalues", 'desc' => "{List.metadata_selection.allvalues}"} ]; my $metadata_selection_mode_default = "firstvalidmetadata"; my $valid_metadata_selection_modes = { 'firstvalue' => 1, 'firstvalidmetadata' => 1, 'allvalues' => 1 }; my $metadata_sort_mode_list = [ { 'name' => "unicode", 'desc' => "{List.metadata_sort.unicode}"}, { 'name' => "alphabetic", 'desc' => "{List.metadata_sort.alphabetic}"}, { 'name' => "alphanumeric", 'desc' => "{List.metadata_sort.alphanumeric}"}, { 'name' => "structured", 'desc' => "{List.metadata_sort.structured}"}, { 'name' => "structured_grouped", 'desc' => "{List.metadata_sort.structured_grouped}"} ]; my $metadata_sort_mode_default = "alphanumeric"; my $valid_metadata_sort_modes = { 'unicode' => 1, 'alphabetic' => 1, 'alphanumeric' => 1, 'structured' => 1, 'structured_grouped' => 1 }; my $partition_type_list = [ { 'name' => "per_letter", 'desc' => "{List.level_partition.per_letter}" }, { 'name' => "approximate_size", 'desc' => "{List.level_partition.approximate_size}"}, { 'name' => "constant_size", 'desc' => "{List.level_partition.constant_size}" }, { 'name' => "all_values", 'desc' => "{List.level_partition.all_values}" }, { 'name' => "none", 'desc' => "{List.level_partition.none}" } ]; my $partition_type_default = "per_letter"; my $valid_partition_types = { 'per_letter' => 1, 'constant_size' => 1, 'approximate_size' => 1, 'all_values' => 1, 'none' => 1}; my $partition_size_default = 20; my $numeric_partition_type_list = [ { 'name' => "per_digit", 'desc' => "{List.level_partition.per_digit}" }, { 'name' => "per_number", 'desc' => "{List.level_partition.per_number}" }, { 'name' => "single_partition", 'desc' => "{List.level_partition.single}" }, { 'name' => "approximate_size", 'desc' => "{List.level_partition.approximate_size_numeric}"}, { 'name' => "constant_size", 'desc' => "{List.level_partition.constant_size}" }, { 'name' => "all_values", 'desc' => "{List.level_partition.all_values}" }, { 'name' => "none", 'desc' => "{List.level_partition.none}" } ]; my $numeric_partition_type_default = "single_partition"; my $valid_numeric_partition_types = { 'per_digit' => 1, 'per_number' => 1, 'constant_size' => 1, 'single_partition' => 1, 'approximate_size' => 1, 'all_values' => 1, 'none' =>1 }; my $numeric_partition_size_default = 20; my $numeric_partition_name_length_default = "-1"; # use the full number my $bookshelf_type_list = [ { 'name' => "always", 'desc' => "{List.bookshelf_type.always}" }, { 'name' => "duplicate_only", 'desc' => "{List.bookshelf_type.duplicate_only}" }, { 'name' => "never", 'desc' => "{List.bookshelf_type.never}" } ]; my $bookshelf_type_default = "never"; my $sort_leaf_nodes_using_default = "Title"; my $arguments = [ { 'name' => "metadata", 'desc' => "{List.metadata}", 'type' => "metadata", 'reqd' => "yes" }, { 'name' => "metadata_selection_mode_within_level", 'desc' => "{List.metadata_selection_mode_within_level}", 'type' => "enumstring", # Must be enumstring because multiple values can be specified (separated by '/') 'list' => $metadata_selection_mode_list, 'deft' => $metadata_selection_mode_default }, { 'name' => "metadata_sort_mode_within_level", 'desc' => "{List.metadata_sort_mode_within_level}", 'type' => "enumstring", # Must be enumstring because multiple values can be specified (separated by '/') 'list' => $metadata_sort_mode_list, 'deft' => $metadata_sort_mode_default }, { 'name' => "bookshelf_type", 'desc' => "{List.bookshelf_type}", 'type' => "enum", 'list' => $bookshelf_type_list, 'deft' => $bookshelf_type_default }, { 'name' => "classify_sections", 'desc' => "{List.classify_sections}", 'type' => "flag" }, { 'name' => "partition_type_within_level", 'desc' => "{List.partition_type_within_level}", 'type' => "enumstring", # Must be enumstring because multiple values can be specified (separated by '/') 'list' => $partition_type_list, 'deft' => $partition_type_default }, { 'name' => "partition_size_within_level", 'desc' => "{List.partition_size_within_level}", 'type' => "string", # Must be string because multiple values can be specified (separated by '/') 'deft' => $partition_size_default}, { 'name' => "partition_name_length", 'desc' => "{List.partition_name_length}", 'type' => "string" }, { 'name' => "max_partition_name_length", 'desc' => "{List.max_partition_name_length}", 'type' => "string", 'deft' => "3" }, {'name' => "partition_sort_mode_within_level", 'desc' => "{List.partition_sort_mode_within_level}", 'type' => "enumstring", # Must be enumstring because multiple values can be specified (separated by '/') 'list' => $metadata_sort_mode_list, 'deft' => $metadata_sort_mode_default }, { 'name' => "numeric_partition_type_within_level", 'desc' => "{List.numeric_partition_type_within_level}", 'type' => "enumstring", # Must be enumstring because multiple values can be specified (separated by '/') 'list' => $numeric_partition_type_list, 'deft' => $numeric_partition_type_default }, { 'name' => "numeric_partition_size_within_level", 'desc' => "{List.numeric_partition_size_within_level}", 'type' => "string", # Must be string because multiple values can be specified (separated by '/') 'deft' => $numeric_partition_size_default}, { 'name' => "numeric_partition_name_length_within_level", 'desc' => "{List.numeric_partition_name_length_within_level}", 'type' => "string", 'deft' => $numeric_partition_name_length_default }, {'name' => "numeric_partition_sort_mode_within_level", 'desc' => "{List.numeric_partition_sort_mode_within_level}", 'type' => "enumstring", # Must be enumstring because multiple values can be specified (separated by '/') 'list' => $metadata_sort_mode_list, 'deft' => $metadata_sort_mode_default }, { 'name' => "numbers_first", 'desc' => "{List.numbers_first}", 'type' => 'flag'}, { 'name' => "sort_leaf_nodes_using", 'desc' => "{List.sort_leaf_nodes_using}", 'type' => "metadata", 'deft' => $sort_leaf_nodes_using_default }, { 'name' => "sort_leaf_nodes_sort_mode", 'desc' => "{List.sort_leaf_nodes_sort_mode}", 'type' => "enum", 'list' => $metadata_sort_mode_list, 'deft' => $metadata_sort_mode_default }, { 'name' => "reverse_sort_leaf_nodes", 'desc' => "{List.reverse_sort_leaf_nodes}", 'type' => "flag"}, { 'name' => "sort_leaf_nodes_removeprefix", 'desc' => "{List.sort_leaf_removeprefix}", 'type' => "regexp" }, { 'name' => "sort_leaf_nodes_removesuffix", 'desc' => "{List.sort_leaf_nodes_removesuffix}", 'type' => "regexp" }, { 'name' => "sort_using_unicode_collation", 'desc' => "{List.metadata_sort.unicode} {List.sort_using_unicode_collation}", 'type' => "flag" }, {'name' => "filter_metadata", 'desc' => "{List.filter_metadata}", 'type' => "metadata"}, {'name' => "filter_regex", 'desc' => "{List.filter_regex}", 'type' => "regexp"}, { 'name' => "use_formatted_metadata_for_bookshelf_display", 'desc' => "{List.use_formatted_metadata_for_bookshelf_display}", 'type' => "flag"}, { 'name' => "removeprefix", 'desc' => "{BasClas.removeprefix}", 'type' => "regexp" }, { 'name' => "removesuffix", 'desc' => "{BasClas.removesuffix}", 'type' => "regexp" } ]; my $options = { 'name' => "List", 'desc' => "{List.desc}", 'abstract' => "no", 'inherits' => "yes", 'args' => $arguments }; sub new { my ($class) = shift(@_); my ($classifierslist, $inputargs, $hashArgOptLists) = @_; push(@$classifierslist, $class); push(@{$hashArgOptLists->{"ArgList"}}, @{$arguments}); push(@{$hashArgOptLists->{"OptList"}}, $options); my $self = new BaseClassifier($classifierslist, $inputargs, $hashArgOptLists); bless $self, $class; my $decl = " a A d D "; if ($self->{'info_only'}) { # don't worry about any options etc return $self; } # The metadata elements to use (required) if (!$self->{'metadata'}) { die "Error: No metadata fields specified for List.\n"; } my @metadata_groups = split(/[\/]/, $self->{'metadata'}); $self->{'metadata_groups'} = \@metadata_groups; # The classifier button name (default: the first metadata element specified) if (!$self->{'buttonname'}) { my $first_metadata_group = $metadata_groups[0]; my $first_metadata_element = (split(/[\;|,\/]/, $first_metadata_group))[0]; $self->{'buttonname'} = $self->generate_title_from_metadata($first_metadata_element); } # meta selection mode for each level $self->set_metadata_groups_info_per_level("metadata_selection_mode_within_level", $metadata_selection_mode_default, $valid_metadata_selection_modes); # meta sort mode for each level if ($self->{'sort_using_unicode_collation'}) { print STDERR "WARNING: sort_using_unicode_collation is set, setting metadata_sort_mode_within_level to unicode for all levels, regardless of current setting\n"; $self->{'metadata_sort_mode_within_level'} = "unicode"; $metadata_sort_mode_default = "unicode"; } else { if ($self->{'metadata_sort_mode_within_level'} =~ /unicode/) { $self->{'sort_using_unicode_collation'} = 1; } } $self->set_metadata_groups_info_per_level('metadata_sort_mode_within_level', $metadata_sort_mode_default, $valid_metadata_sort_modes); # Whether to group items into a bookshelf, (must be 'always' for all metadata fields except the last) foreach my $metadata_group (@metadata_groups) { $self->{$metadata_group . ".bookshelf_type"} = "always"; } my $last_metadata_group = $metadata_groups[$#metadata_groups]; # Default: duplicate_only, ie. leave leaf nodes ungrouped (equivalent to AZCompactList -mingroup 2) $self->{$last_metadata_group . ".bookshelf_type"} = $self->{'bookshelf_type'}; # How the items are grouped into partitions (default: by letter) # for each level (metadata group), separated by '/' $self->set_metadata_groups_info_per_level("partition_type_within_level", $partition_type_default, $valid_partition_types); $self->set_metadata_groups_info_per_level("numeric_partition_type_within_level", $numeric_partition_type_default, $valid_numeric_partition_types); # now check whether a level was none - need to set the equivalent level in the other half also to none foreach my $metadata_group (@metadata_groups) { if ($self->{$metadata_group . ".partition_type_within_level"} eq "none" || $self->{$metadata_group . ".numeric_partition_type_within_level"} eq "none") { print STDERR "WARNING: one of -partition_type_within_level or -numeric_partition_type_within_level was set to 'none' for level $metadata_group, overriding current value of both these options to 'none'\n"; $self->{$metadata_group . ".partition_type_within_level"} = "none"; $self->{$metadata_group . ".numeric_partition_type_within_level"} = "none"; } } $self->set_metadata_groups_info_per_level("partition_size_within_level", $partition_size_default); $self->set_metadata_groups_info_per_level("numeric_partition_size_within_level", $numeric_partition_size_default); $self->set_metadata_groups_info_per_level('partition_sort_mode_within_level', $metadata_sort_mode_default, $valid_metadata_sort_modes); $self->set_metadata_groups_info_per_level('numeric_partition_sort_mode_within_level', $metadata_sort_mode_default, $valid_metadata_sort_modes); $self->set_metadata_groups_info_per_level("numeric_partition_name_length_within_level", $numeric_partition_name_length_default); # The removeprefix and removesuffix expressions if ($self->{'removeprefix'}) { # If there are more than one expressions, use '' to quote each experession and '/' to separate my @removeprefix_exprs_within_levellist = split(/'\/'/, $self->{'removeprefix'}); foreach my $metadata_group (@metadata_groups) { my $removeprefix_expr_within_levelelem = shift(@removeprefix_exprs_within_levellist); if (defined($removeprefix_expr_within_levelelem) && $removeprefix_expr_within_levelelem ne "") { # Remove the other ' at the beginning and the end if there is any $removeprefix_expr_within_levelelem =~ s/^'//; $removeprefix_expr_within_levelelem =~ s/'$//; # Remove the extra ^ at the beginning $removeprefix_expr_within_levelelem =~ s/^\^//; $self->{$metadata_group . ".remove_prefix_expr"} = $removeprefix_expr_within_levelelem; } else { $self->{$metadata_group . ".remove_prefix_expr"} = $self->{$metadata_groups[0] . ".remove_prefix_expr"}; } } } if ($self->{'removesuffix'}) { my @removesuffix_exprs_within_levellist = split(/'\/'/, $self->{'removesuffix'}); foreach my $metadata_group (@metadata_groups) { my $removesuffix_expr_within_levelelem = shift(@removesuffix_exprs_within_levellist); if (defined($removesuffix_expr_within_levelelem) && $removesuffix_expr_within_levelelem ne "") { $removesuffix_expr_within_levelelem =~ s/^'//; $removesuffix_expr_within_levelelem =~ s/'$//; # Remove the extra $ at the end $removesuffix_expr_within_levelelem =~ s/\$$//; $self->{$metadata_group . ".remove_suffix_expr"} = $removesuffix_expr_within_levelelem; } else { $self->{$metadata_group . ".remove_suffix_expr"} = $self->{$metadata_groups[0] . ".remove_suffix_expr"}; } } } # The metadata elements to use to sort the leaf nodes (default: Title) my @sort_leaf_nodes_using_metadata_groups = split(/\|/, $self->{'sort_leaf_nodes_using'}); $self->{'sort_leaf_nodes_using_metadata_groups'} = \@sort_leaf_nodes_using_metadata_groups; foreach my $sort_group (@sort_leaf_nodes_using_metadata_groups) { # set metadata_select_type, if not already set - might be already set if the same group was used in -metadata if (!defined $self->{$sort_group . ".metadata_selection_mode_within_level"}) { $self->{$sort_group . ".metadata_selection_mode_within_level"} = $metadata_selection_mode_default; } } my @leaf_nodes_sort_modes = split (/\|/, $self->{'sort_leaf_nodes_sort_mode'}); foreach my $sort_group (@sort_leaf_nodes_using_metadata_groups) { my $leaf_sort_mode = shift(@leaf_nodes_sort_modes); if (!defined $self->{$sort_group . ".metadata_sort_mode_within_level"}) { if (defined $leaf_sort_mode && defined $valid_metadata_sort_modes->{$leaf_sort_mode}) { $self->{$sort_group . ".metadata_sort_mode_within_level"} = $leaf_sort_mode; } else { $self->{$sort_group . ".metadata_sort_mode_within_level"} = $metadata_sort_mode_default; } } } # Create an instance of the Unicode::Collate object if better Unicode sorting is desired if ($self->{'sort_using_unicode_collation'}) { # To use this you first need to download the allkeys.txt file from # http://www.unicode.org/Public/UCA/latest/allkeys.txt and put it in the Perl # Unicode/Collate directory. require Unicode::Collate; $self->{'unicode_collator'} = Unicode::Collate->new(); } # An empty array for the document/section OIDs that we are classifying $self->{'OIDs'} = []; # A hash for all the doc ids that we have seen, so we don't classify something twice $self->{'all_doc_OIDs'} = {}; return $self; } sub init { # Nothing to do... } sub set_metadata_groups_info_per_level { my $self = shift(@_); my $info_name = shift(@_); my $info_default = shift(@_); my $info_valid_types_hash_ref = shift(@_); if (!defined $self->{$info_name}) { print STDERR "List Error: no values were set for option $info_name\n"; } my @info_list = split(/\//, $self->{$info_name}); my $first = 1; foreach my $metadata_group (@{$self->{'metadata_groups'}}) { my $info_elem = shift(@info_list); if (defined ($info_elem) && (!defined $info_valid_types_hash_ref || defined $info_valid_types_hash_ref->{$info_elem})) { $self->{$metadata_group .".$info_name"} = $info_elem; } else { # its empty or an invalid entry my $new_info_elem; if ($first) { $new_info_elem = $info_default; } else { # get the value we had at first $new_info_elem = $self->{@{$self->{'metadata_groups'}}[0] . ".$info_name"}; } $self->{$metadata_group .".$info_name"} = $new_info_elem; if (defined $info_elem) { print STDERR "List Error: $info_elem is not a valid value for $info_name, changing it to $new_info_elem\n"; } } $first = 0; } } # Called for each document in the collection sub classify { my $self = shift(@_); my ($doc_obj) = @_; if (defined $self->{'all_doc_OIDs'}->{$doc_obj->get_OID()}) { print STDERR "Warning, List classifier has already seen document ".$doc_obj->get_OID().", not classifying again\n"; return; } $self->{'all_doc_OIDs'}->{$doc_obj->get_OID()} = 1; # check against filter here if ($self->{'filter_metadata'}) { my $meta = $doc_obj->get_metadata_element($doc_obj->get_top_section(), $self->{'filter_metadata'}); return unless defined $meta; if ($self->{'filter_regex'} ne "" && $meta !~ /$self->{'filter_regex'}/) { print STDERR "doc $doc_obj doesn't pass filtering requirement. Not classifying.\n" if ($self->{'verbosity'} > 3); return; } } # if we get here, we have passed the test for filtering # If "-classify_sections" is set, classify every section of the document if ($self->{'classify_sections'}) { my $section = $doc_obj->get_next_section($doc_obj->get_top_section()); while (defined $section) { $self->classify_section($doc_obj, $doc_obj->get_OID() . ".$section", $section); $section = $doc_obj->get_next_section($section); } } # Otherwise just classify the top document section else { $self->classify_section($doc_obj, $doc_obj->get_OID(), $doc_obj->get_top_section()); } } sub classify_section { my $self = shift(@_); my ($doc_obj,$section_OID,$section) = @_; my @metadata_groups = @{$self->{'metadata_groups'}}; # Only classify the section if it has a value for one of the metadata elements in the first group my $classify_section = 0; my $first_metadata_group = $metadata_groups[0]; my $remove_prefix_expr = $self->{$first_metadata_group . ".remove_prefix_expr"}; my $remove_suffix_expr = $self->{$first_metadata_group . ".remove_suffix_expr"}; foreach my $first_metadata_group_element (split(/\;|,/, $first_metadata_group)) { my $real_first_metadata_group_element = $self->strip_ex_from_metadata($first_metadata_group_element); my $first_metadata_group_element_value = $doc_obj->get_metadata_element($section, $real_first_metadata_group_element); # Remove prefix/suffix if requested if (defined ($first_metadata_group_element_value)) { if (defined $remove_prefix_expr && $remove_prefix_expr ne "") { $first_metadata_group_element_value =~ s/^$remove_prefix_expr//; } if (defined $remove_suffix_expr && $remove_suffix_expr ne "") { $first_metadata_group_element_value =~ s/$remove_suffix_expr$//; } } $first_metadata_group_element_value = &sorttools::format_metadata_for_sorting($first_metadata_group, $first_metadata_group_element_value, $doc_obj, $self); if (defined($first_metadata_group_element_value) && $first_metadata_group_element_value ne "") { # This section must be included in the classifier as we have found a value $classify_section = 1; last; } } # We're not classifying this section because it doesn't have the required metadata return if (!$classify_section); # Otherwise, include this section in the classifier push(@{$self->{'OIDs'}}, $section_OID); # Create a hash for the metadata values of each metadata element we're interested in my %metadata_groups_done = (); foreach my $metadata_group (@metadata_groups, @{$self->{'sort_leaf_nodes_using_metadata_groups'}}) { # Take care not to do a metadata group more than once unless ($metadata_groups_done{$metadata_group}) { my $remove_prefix_expr = $self->{$metadata_group . ".remove_prefix_expr"}; my $remove_suffix_expr = $self->{$metadata_group . ".remove_suffix_expr"}; foreach my $metadata_element (split(/\;|,/, $metadata_group)) { my $real_metadata_element = $self->strip_ex_from_metadata($metadata_element); my @metadata_values = @{$doc_obj->get_metadata($section, $real_metadata_element)}; foreach my $metadata_value (@metadata_values) { # Strip leading and trailing whitespace $metadata_value =~ s/^\s*//; $metadata_value =~ s/\s*$//; # Remove prefix/suffix if requested if (defined $remove_prefix_expr && $remove_prefix_expr ne "") { $metadata_value =~ s/^$remove_prefix_expr//; } if (defined $remove_suffix_expr && $remove_suffix_expr ne "") { $metadata_value =~ s/$remove_suffix_expr$//; } # lowercase metadata both for sorting meta (d/D under D), and to allow CSS to be able to # text-transform the stored lowercase values as capitalize or uppercase (can't CSS # text-transform if stored uppercase). 2 CSS text-transforms have been added to core.css ### no longer do this, as lowercasing is now an option for the user, and is handled by format_metadata_for_sorting my $lc_metadata_value = $metadata_value; #lc($metadata_value); $lc_metadata_value = &sorttools::format_metadata_for_sorting($real_metadata_element, $lc_metadata_value, $doc_obj, $self); # Add the metadata value into the list for this combination of metadata group # and section - if we have some non-whitespace chars # test that we have some non-whitespace chars if ($lc_metadata_value =~ /\S/) { push(@{$self->{$metadata_group . ".list"}->{$section_OID}}, $lc_metadata_value); # add the actual value into the stored values so we can remember the case if (!$self->{'use_formatted_metadata_for_bookshelf_display'}) { if (defined $self->{$metadata_group . ".actualvalues"}->{$lc_metadata_value}->{$metadata_value}) { $self->{$metadata_group . ".actualvalues"}->{$lc_metadata_value}->{$metadata_value}++; } else { $self->{$metadata_group . ".actualvalues"}->{$lc_metadata_value}->{$metadata_value} = 1; } } last if ($self->{$metadata_group . ".metadata_selection_mode_within_level"} eq "firstvalue"); } } # foreach metadatavalue last if ((@metadata_values > 0) && $self->{$metadata_group . ".metadata_selection_mode_within_level"} =~ /^(firstvalue|firstvalidmetadata)$/ ); } # foreach metadata element $metadata_groups_done{$metadata_group} = 1; } } } sub get_classify_info { my $self = shift(@_); # The metadata groups to classify by my @metadata_groups = @{$self->{'metadata_groups'}}; my $first_metadata_group = $metadata_groups[0]; # The OID values of the documents to include in the classifier my @OIDs = @{$self->{'OIDs'}}; # Create the root node of the classification hierarchy my %classifier_node = ( 'thistype' => "Invisible", 'childtype' => "VList", 'Title' => $self->{'buttonname'}, 'contains' => [], 'mdtype' => $first_metadata_group ); # Recursively create the classification hierarchy, one level for each metadata group $self->add_level(\@metadata_groups, \@OIDs, \%classifier_node); return \%classifier_node; } # when using approximate_size or constant_size buckets, if there are less items than partition_size, then we generally don't make a bucket. # However, if the alpha values have partitions and the numerica values don't, then this doesn't display nicely (get documents in an HList) # so if one side has partitions, then we force the other side to have them too. sub will_we_have_partitions { my $self = shift(@_); my $metadata_group = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); my $numeric_metadata_value_to_OIDs_hash_ref = shift(@_); my $partition_type = $self->{$metadata_group . ".partition_type_within_level"}; my $partition_size = $self->{$metadata_group . ".partition_size_within_level"}; my $bookshelf_type = $self->{$metadata_group. ".bookshelf_type"}; my $numeric_partition_type = $self->{$metadata_group . ".numeric_partition_type_within_level"}; my $numeric_partition_size = $self->{$metadata_group . ".numeric_partition_size_within_level"}; if ($partition_type eq "none") { #if this is none, then numeric will also be none, so only need to check one of them. return 0; } # lets count the items to see if either side will be making buckets my $num_alpha = 0; my $num_numeric = 0; if ($bookshelf_type =~ /^(always|duplicate_only)$/) { # each individual value will be a bookshelf or a single item $num_alpha = scalar(keys %$metadata_value_to_OIDs_hash_ref); $num_numeric = scalar(keys %$numeric_metadata_value_to_OIDs_hash_ref); } else { # we have to count actual values to see how many entires there are foreach my $metadata_value (keys %{$metadata_value_to_OIDs_hash_ref}) { $num_alpha += scalar( @{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}); } foreach my $metadata_value (keys %{$numeric_metadata_value_to_OIDs_hash_ref}) { $num_numeric += scalar( @{$numeric_metadata_value_to_OIDs_hash_ref->{$metadata_value}}); } } # if either alpha or numeric has fixed partitions, then we force partitions both sides # but only if there are actually some values - we may have no numeric ones for example if (($partition_type =~ /^(per_letter|all_values)$/ && $num_alpha > 0 )|| ($numeric_partition_type =~ /^(single_partition|per_digit|all_values)/ && $num_numeric > 0)) { return 1; } # we are using approximate/constant size buckets - we need to work out if we actually have enough for buckets my $tolerance = 0; my $numeric_tolerance = 0; if ($partition_type eq "approximate_size") { $tolerance = ($partition_size > 40 ? 10 : int($partition_size/4)); } if ($numeric_partition_type eq "approximate_size" ) { $numeric_tolerance = ($numeric_partition_size > 40 ? 10 : int($numeric_partition_size/4)); } # now, test to see if we have partition on either side - in which case we need to force partitions on the other side if ($num_alpha > $partition_size+$tolerance || $num_numeric > $numeric_partition_size+$numeric_tolerance) { return 1; } return 0; } sub add_level { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my @OIDs = @{shift(@_)}; my $classifier_node = shift(@_); my $metadata_group = $metadata_groups[0]; if (!defined($self->{$metadata_group . ".list"})) { print STDERR "Warning: No metadata values assigned to $metadata_group.\n"; return; } # Create a mapping from metadata value to OID my $OID_to_metadata_values_hash_ref = $self->{$metadata_group . ".list"}; my %metadata_value_to_OIDs_hash = (); my %numeric_metadata_value_to_OIDs_hash = (); foreach my $OID (@OIDs) { if ($OID_to_metadata_values_hash_ref->{$OID}) { my @metadata_values = @{$OID_to_metadata_values_hash_ref->{$OID}}; foreach my $metadata_value (@metadata_values) { if ($metadata_value =~ /^[0-9]/) { push(@{$numeric_metadata_value_to_OIDs_hash{$metadata_value}}, $OID); } else { push(@{$metadata_value_to_OIDs_hash{$metadata_value}}, $OID); } } } } #print STDERR "Number of distinct values: " . scalar(keys %metadata_value_to_OIDs_hash) . "\n"; #print STDERR "Number of distinct numeric values: " . scalar(keys %numeric_metadata_value_to_OIDs_hash) . "\n"; # Partition the values (if necessary) my $partition_type_within_level = $self->{$metadata_group . ".partition_type_within_level"}; my $partition_size_within_level = $self->{$metadata_group . ".partition_size_within_level"}; my $partition_sort_mode_within_level = $self->{$metadata_group . ".partition_sort_mode_within_level"}; my $bookshelf_type_within_level = $self->{$metadata_group. ".bookshelf_type"}; my ($has_partitions) = $self->will_we_have_partitions($metadata_group, \%metadata_value_to_OIDs_hash, \%numeric_metadata_value_to_OIDs_hash); ############################################# ### DO THE NUMBERS IF THEY ARE TO COME FIRST ############################################# if ($self->{'numbers_first'} && keys(%numeric_metadata_value_to_OIDs_hash)) { $self->partition_numeric_values(\@metadata_groups, $classifier_node, \%numeric_metadata_value_to_OIDs_hash, $has_partitions); } ############################################ # DO THE LETTERS ############################################ if (keys(%metadata_value_to_OIDs_hash)){ # make sure we have some values if ($partition_type_within_level =~ /^per_letter$/i) { $self->split_per_letter_or_digit(\@metadata_groups, $classifier_node, $partition_sort_mode_within_level, \%metadata_value_to_OIDs_hash); } elsif ($partition_type_within_level =~ /^approximate_size$/i && $has_partitions) { # scalar(keys %metadata_value_to_OIDs_hash) > $partition_size_within_level) { $self->split_approximate_size(\@metadata_groups, $classifier_node, $partition_size_within_level, $partition_sort_mode_within_level, $bookshelf_type_within_level, \%metadata_value_to_OIDs_hash, $self->{'partition_name_length'}, $self->{'max_partition_name_length'}); } elsif ($partition_type_within_level =~ /^constant_size$/i && $has_partitions) { #scalar(keys %metadata_value_to_OIDs_hash) > $partition_size_within_level) { $self->split_constant_size(\@metadata_groups, $classifier_node, $partition_size_within_level, $partition_sort_mode_within_level, $bookshelf_type_within_level, \%metadata_value_to_OIDs_hash, $self->{'partition_name_length'}, $self->{'max_partition_name_length'}); } # Otherwise just add all the values to a VList else { if ($partition_type_within_level =~ /^all_values$/i) { $classifier_node->{'childtype'} = "HList"; $self->{$metadata_group. ".bookshelf_type"} = "always"; } $self->add_vlist(\@metadata_groups, $classifier_node, \%metadata_value_to_OIDs_hash); } } ########################################### ### DO THE NUMBERS IF THEY ARE TO COME LAST ########################################### if (!$self->{'numbers_first'} && keys(%numeric_metadata_value_to_OIDs_hash)) { $self->partition_numeric_values(\@metadata_groups, $classifier_node, \%numeric_metadata_value_to_OIDs_hash, $has_partitions); } } sub partition_numeric_values { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $numeric_metadata_value_to_OIDs_hash_ref = shift(@_); my $has_partitions = shift(@_); my $metadata_group = $metadata_groups[0]; my $numeric_partition_type_within_level = $self->{$metadata_group . ".numeric_partition_type_within_level"}; my $numeric_partition_size_within_level = $self->{$metadata_group . ".numeric_partition_size_within_level"}; my $numeric_partition_sort_mode_within_level = $self->{$metadata_group . ".numeric_partition_sort_mode_within_level"}; my $numeric_partition_name_length_within_level = $self->{$metadata_group . ".numeric_partition_name_length_within_level"}; my $bookshelf_type_within_level = $self->{$metadata_group. ".bookshelf_type"}; if ($numeric_partition_type_within_level eq "single_partition") { $self->add_hlist_partition(\@metadata_groups, $classifier_node, "0-9", $numeric_metadata_value_to_OIDs_hash_ref); } elsif ($numeric_partition_type_within_level eq "per_digit") { $self->split_per_letter_or_digit(\@metadata_groups, $classifier_node, $numeric_partition_sort_mode_within_level, $numeric_metadata_value_to_OIDs_hash_ref, 1, 1); } elsif ($numeric_partition_type_within_level eq "per_number") { # each different number is a bucket $self->split_per_letter_or_digit(\@metadata_groups, $classifier_node, $numeric_partition_sort_mode_within_level, $numeric_metadata_value_to_OIDs_hash_ref, 1, $numeric_partition_name_length_within_level); } elsif ($numeric_partition_type_within_level eq "constant_size" && $has_partitions) { #scalar(keys %$numeric_metadata_value_to_OIDs_hash_ref) > $numeric_partition_size_within_level) { # Generate hlists of a certain size $self->split_constant_size(\@metadata_groups, $classifier_node, $numeric_partition_size_within_level, $numeric_partition_sort_mode_within_level, $bookshelf_type_within_level, $numeric_metadata_value_to_OIDs_hash_ref, $numeric_partition_name_length_within_level,$numeric_partition_name_length_within_level, 1); } elsif ($numeric_partition_type_within_level eq "approximate_size" && $has_partitions) { #scalar(keys %$numeric_metadata_value_to_OIDs_hash_ref) > $numeric_partition_size_within_level) { $self->split_approximate_size(\@metadata_groups, $classifier_node, $numeric_partition_size_within_level, $numeric_partition_sort_mode_within_level, $bookshelf_type_within_level, $numeric_metadata_value_to_OIDs_hash_ref, $numeric_partition_name_length_within_level, $numeric_partition_name_length_within_level, 1); } # Otherwise just add all the values to a VList else { if ($numeric_partition_type_within_level =~ /^all_values$/i) { $classifier_node->{'childtype'} = "HList"; $self->{$metadata_group. ".bookshelf_type"} = "always"; } $self->add_vlist(\@metadata_groups, $classifier_node, $numeric_metadata_value_to_OIDs_hash_ref); } } sub split_approximate_size { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $partition_size = shift(@_); my $sort_mode = shift(@_); my $bookshelf_type = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); my $partition_name_length = shift(@_); my $max_partition_name_length = shift(@_); my $is_numeric = shift(@_); my $tolerance = ($partition_size > 40 ? 10 : int($partition_size/4)); # should this be an option?? # Generate hlist based on the first letter of the metadata value (like per_letter), or based on # numbers, but also with restriction on the partition size # If a partition has fewer items than specified by the "partition_size_within_level", then group them together if possible # If a partition has more items than specified, split into several hlists. # Depends on the bookshelf_type, one item can be either a document (when bookshelf_type is "never") or a metadata value (otherwise) my @sortedmetadata_values = $self->sort_metadata_values_array($sort_mode, keys(%$metadata_value_to_OIDs_hash_ref)); # Separate values by their first letter, each form a bucket, like the per_letter partition type my $last_partition = $self->generate_partition_name($sortedmetadata_values[0], $partition_name_length, $is_numeric, $sort_mode); my @partition_buckets = (); my @metadata_values_in_bucket = (); my $num_items_in_bucket = 0; foreach my $metadata_value (@sortedmetadata_values) { my $metadata_valuepartition = $self->generate_partition_name($metadata_value, $partition_name_length, $is_numeric, $sort_mode); #****** if ($metadata_valuepartition ne $last_partition) { my @temp_array = @metadata_values_in_bucket; # Cache the values that belong to this bucket, and the number of items in this bucket, not necessary to be the same number as the metadata values my %partition_info = (); $partition_info{'metadata_values'} = \@temp_array; $partition_info{'size'} = $num_items_in_bucket; $partition_info{'name'} = $last_partition; push (@partition_buckets, \%partition_info); @metadata_values_in_bucket = ($metadata_value); $num_items_in_bucket = ($bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : scalar(@metadata_values_in_bucket)); $last_partition = $metadata_valuepartition; } else { $num_items_in_bucket += ($bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : 1); push (@metadata_values_in_bucket, $metadata_value); } } # Last one my %partition_info = (); $partition_info{'metadata_values'} = \@metadata_values_in_bucket; $partition_info{'size'} = $num_items_in_bucket; $partition_info{'name'} = $last_partition; push (@partition_buckets, \%partition_info); # now go through the array of A, B, C buckets, and merge small buckets my @new_partition_buckets = (); for (my $i = 0; $i < scalar(@partition_buckets) - 1; $i++) { my $this_bucket = $partition_buckets[$i]; my $next_bucket = $partition_buckets[$i+1]; my $items_in_partition = $this_bucket->{'size'}; if ($items_in_partition < $partition_size ) { my $items_in_next_partition = $next_bucket->{'size'}; if ($items_in_partition + $items_in_next_partition <= $partition_size+$tolerance ) { # merge this bucket into the next bucket foreach my $metadata_value_to_merge (@{$this_bucket->{'metadata_values'}}) { push(@{$next_bucket->{'metadata_values'}}, $metadata_value_to_merge); } $next_bucket->{'size'} += $items_in_partition; } else { # remember this bucket push (@new_partition_buckets, $this_bucket); } } else { # remember this bucket push (@new_partition_buckets, $this_bucket); } } # add in the last bucket my $last_bucket = $partition_buckets[scalar(@partition_buckets) - 1]; push (@new_partition_buckets, $last_bucket); # Add partitions to the main list, but divide big bucket into several my $last_partition_end = ""; my $partition_start = ""; my $partition_end = ""; my $partition_name = ""; foreach my $partition (@new_partition_buckets) { my @metadata_values = $self->sort_metadata_values_array($sort_mode, @{$partition->{'metadata_values'}}); my $items_in_partition = $partition->{'size'}; $partition_start = $self->generate_partition_start($metadata_values[0], $last_partition_end, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); if ($items_in_partition <= $partition_size+$tolerance) { # we can just add the partition as is my %metadata_values_to_OIDs_subhashes = (); for (my $i = 0; $i < scalar(@metadata_values); $i++) { my $metadata_value = $metadata_values[$i]; $metadata_values_to_OIDs_subhashes{$metadata_value} = $metadata_value_to_OIDs_hash_ref->{$metadata_value}; } my $last_metadata_value = $metadata_values[scalar(@metadata_values)-1]; $partition_end = $self->generate_partition_end($last_metadata_value, $partition_start, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); $partition_name = $partition_start; if ($partition_end ne $partition_start) { $partition_name = $partition_name . "-" . $partition_end; } $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); $last_partition_end = $partition_end; } else { # we have too many items, need to split the partition my $num_splits = int($items_in_partition/$partition_size); $num_splits++ if (($items_in_partition - $partition_size*$num_splits) > $tolerance); my $this_partition_size = int($items_in_partition/$num_splits); if ($this_partition_size < $items_in_partition/$num_splits) { $this_partition_size++ }; # regenerate-the start, noticing that we are a split $partition_start = $self->generate_partition_start($metadata_values[0], $last_partition_end, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode, 1); my $items_done = 0; my $prev_done = 0; my %metadata_values_to_OIDs_subhashes = (); for (my $i = 0; $i < scalar(@metadata_values); $i++) { my $metadata_value = $metadata_values[$i]; # If the bookshelf_type is "never", count the documents, otherwise count the distinct metadata values my $items_for_this_md_value = $bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : 1; if ($items_done >= $this_partition_size) { # what we have stored already is enough for a partition # store this partition $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); $last_partition_end = $partition_end; $partition_start = $self->generate_partition_start($metadata_value, $last_partition_end, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode, 1); $prev_done += $items_done; $items_done = 0; %metadata_values_to_OIDs_subhashes = (); } $partition_end = $self->generate_partition_end($metadata_value, $partition_start, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); $partition_name = $partition_start; if ($partition_end ne $partition_start) { $partition_name = $partition_name . "-" . $partition_end; } if ($items_done + $items_for_this_md_value <= $this_partition_size) { # store all the values for the current metadata to the # current partition $metadata_values_to_OIDs_subhashes{$metadata_value} = $metadata_value_to_OIDs_hash_ref->{$metadata_value}; $items_done += $items_for_this_md_value; } else { # we only want to add some of the values my @OIDs_for_this_value = @{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}; my @OIDs_for_this_partition = (); for (my $j=0; $j< $items_for_this_md_value; $j++) { push (@OIDs_for_this_partition, $OIDs_for_this_value[$j]); $items_done++; if ($items_done >= $this_partition_size ) { # add the partition $metadata_values_to_OIDs_subhashes{$metadata_value} = \@OIDs_for_this_partition; $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); $last_partition_end = $partition_end; $partition_start = $partition_end; # is that right? $self->generate_partition_start($metadata_value, $last_partition_end, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode, 1); $prev_done += $items_done; $items_done = 0; %metadata_values_to_OIDs_subhashes = (); @OIDs_for_this_partition = (); } } # for each OID in the list # at the end, have we got some ids not added to a partition? # add them into the subhash if (scalar(@OIDs_for_this_partition)) { $metadata_values_to_OIDs_subhashes{$metadata_value} = \@OIDs_for_this_partition; } } } # end foreach metadata value # The last partition? if($items_done >0) { $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); } } # end if items in partition > partition size } # end for each partition bucket # The partitions are stored in an HList $classifier_node->{'childtype'} = "HList"; } sub split_approximate_size_ORIG { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $partition_size = shift(@_); my $sort_mode = shift(@_); my $bookshelf_type = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); my $partition_name_length = shift(@_); my $is_numeric = shift(@_); # Generate hlist based on the first letter of the metadata value (like per_letter), or based on # numbers, but also with restriction on the partition size # If a partition has fewer items than specified by the "partition_size_within_level", then group them together if possible # If a partition has more items than specified, split into several hlists. # Depends on the bookshelf_type, one item can be either a document (when bookshelf_type is "never") or a metadata value (otherwise) my @sortedmetadata_values = $self->sort_metadata_values_array($sort_mode, keys(%$metadata_value_to_OIDs_hash_ref)); # Separate values by their first letter, each form a bucket, like the per_letter partition type my $last_partition = $self->generate_partition_name($sortedmetadata_values[0], $partition_name_length, $is_numeric, $sort_mode); my @partition_buckets = (); my @metadata_values_in_bucket = (); my $num_items_in_bucket = 0; foreach my $metadata_value (@sortedmetadata_values) { my $metadata_valuepartition = $self->generate_partition_name($metadata_value, $partition_name_length, $is_numeric, $sort_mode); if ($metadata_valuepartition ne $last_partition) { my @temp_array = @metadata_values_in_bucket; # Cache the values that belong to this bucket, and the number of items in this bucket, not necessary to be the same number as the metadata values my %partition_info = (); $partition_info{'metadata_values'} = \@temp_array; $partition_info{'size'} = $num_items_in_bucket; $partition_info{'name'} = $last_partition; push (@partition_buckets, \%partition_info); @metadata_values_in_bucket = ($metadata_value); $num_items_in_bucket = ($bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : scalar(@metadata_values_in_bucket)); $last_partition = $metadata_valuepartition; } else { $num_items_in_bucket += ($bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : 1); #scalar(@metadata_values_in_bucket); push (@metadata_values_in_bucket, $metadata_value); } } # Last one my %partition_info = (); $partition_info{'metadata_values'} = \@metadata_values_in_bucket; $partition_info{'size'} = $num_items_in_bucket; $partition_info{'name'} = $last_partition; push (@partition_buckets, \%partition_info); # now go through the array of buckets, and merge small buckets my @new_partition_buckets = (); for (my $i = 0; $i < scalar(@partition_buckets) - 1; $i++) { my $this_bucket = $partition_buckets[$i]; my $next_bucket = $partition_buckets[$i+1]; my $items_in_partition = $this_bucket->{'size'}; if ($items_in_partition < $partition_size ) { my $items_in_next_partition = $next_bucket->{'size'}; if ($items_in_partition + $items_in_next_partition <= $partition_size ) { # merge this bucket into the next bucket foreach my $metadata_value_to_merge (@{$this_bucket->{'metadata_values'}}) { push(@{$next_bucket->{'metadata_values'}}, $metadata_value_to_merge); } $next_bucket->{'size'} += $items_in_partition; } else { # remember this bucket push (@new_partition_buckets, $this_bucket); } } else { # remember this bucket push (@new_partition_buckets, $this_bucket); } } # add in the last bucket my $last_bucket = $partition_buckets[scalar(@partition_buckets) - 1]; push (@new_partition_buckets, $last_bucket); # Add partitions to the main list, but divide big bucket into several my $last_partition_end = ""; my $partition_start = ""; my $partition_end = ""; my $partition_name = ""; foreach my $partition (@new_partition_buckets) { my @metadata_values = $self->sort_metadata_values_array($sort_mode, @{$partition->{'metadata_values'}}); my $items_in_partition = $partition->{'size'}; $partition_start = $self->generate_partition_start($metadata_values[0], $last_partition_end, $partition_name_length, $is_numeric, $sort_mode); if ($items_in_partition <= $partition_size) { # we can just add the partition as is my %metadata_values_to_OIDs_subhashes = (); for (my $i = 0; $i < scalar(@metadata_values); $i++) { my $metadata_value = $metadata_values[$i]; $metadata_values_to_OIDs_subhashes{$metadata_value} = $metadata_value_to_OIDs_hash_ref->{$metadata_value}; } my $last_metadata_value = $metadata_values[scalar(@metadata_values)-1]; $partition_end = $self->generate_partition_end($last_metadata_value, $partition_start, $partition_name_length, $is_numeric, $sort_mode); $partition_name = $partition_start; if ($partition_end ne $partition_start) { $partition_name = $partition_name . "-" . $partition_end; } $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); $last_partition_end = $partition_end; } else { # we have too many items, need to split the partition my $items_done = 0; my %metadata_values_to_OIDs_subhashes = (); for (my $i = 0; $i < scalar(@metadata_values); $i++) { my $metadata_value = $metadata_values[$i]; # If the bookshelf_type is "never", count the documents, otherwise count the distinct metadata values my $items_for_this_md_value = $bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : 1; if ($items_done + $items_for_this_md_value > $partition_size && $items_done != 0) { # Save the stored items into a partition $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); $last_partition_end = $partition_end; $partition_start = $self->generate_partition_start($metadata_value, $last_partition_end, $partition_name_length, $is_numeric, $sort_mode); $items_done = 0; %metadata_values_to_OIDs_subhashes = (); } # If bookshelf_type is "never" and the current metadata value holds too many items, need to split into several partitions if ($bookshelf_type eq "never" && $items_for_this_md_value > $partition_size) { my $partitionname_for_this_value = $self->generate_partition_start($metadata_value, $last_partition_end, $partition_name_length, $is_numeric, $sort_mode); # Get the number of partitions needed for this value my $num_splits = int($items_for_this_md_value / $partition_size); $num_splits++ if ($items_for_this_md_value / $partition_size > $num_splits); my @OIDs_for_this_value = @{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}; for (my $i = 0; $i < $num_splits; $i++) { my %OIDs_subhashes_for_this_value = (); my @OIDs_for_this_partition = (); for (my $d = $i * $partition_size; $d < (($i+1) * $partition_size > $items_for_this_md_value ? $items_for_this_md_value : ($i+1) * $partition_size); $d++) { push (@OIDs_for_this_partition, $OIDs_for_this_value[$d]); } # The last bucket might have only a few items and need to be merged with buckets for subsequent metadata values if ($i == $num_splits - 1 && scalar(@OIDs_for_this_partition) < $partition_size) { $partition_start = $partitionname_for_this_value; $partition_name = $partition_start; $metadata_values_to_OIDs_subhashes{$metadata_value} = \@OIDs_for_this_partition; $items_done += scalar(@OIDs_for_this_partition); $last_partition_end = $partitionname_for_this_value } else { # Add an HList for this bucket $OIDs_subhashes_for_this_value{$metadata_value} = \@OIDs_for_this_partition; $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partitionname_for_this_value, \%OIDs_subhashes_for_this_value); $last_partition_end = $partitionname_for_this_value; } } } else { $metadata_values_to_OIDs_subhashes{$metadata_value} = $metadata_value_to_OIDs_hash_ref->{$metadata_value}; $items_done += $bookshelf_type eq "never" ? scalar(@{$metadata_values_to_OIDs_subhashes{$metadata_value}}) : 1; $partition_end = $self->generate_partition_end($metadata_value, $partition_start, $partition_name_length, $is_numeric, $sort_mode); $partition_name = $partition_start; if ($partition_end ne $partition_start) { $partition_name = $partition_name . "-" . $partition_end; } } # The last partition if($i == scalar(@metadata_values) - 1 && $items_done >0) { $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partition_name, \%metadata_values_to_OIDs_subhashes); } } } # end if items in partition > partition size } # The partitions are stored in an HList $classifier_node->{'childtype'} = "HList"; } sub split_constant_size { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $partition_size = shift(@_); my $sort_mode = shift(@_); my $bookshelf_type = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); my $partition_name_length = shift(@_); my $max_partition_name_length = shift(@_); my $is_numeric = shift(@_); my @sortedmetadata_values = $self->sort_metadata_values_array($sort_mode, keys(%$metadata_value_to_OIDs_hash_ref)); my $items_in_partition = 0; my %metadata_value_to_OIDs_subhash = (); my $lastpartitionend = ""; my $partitionstart; foreach my $metadata_value (@sortedmetadata_values) { if ($items_in_partition == 0) { # a new partition, set the name $partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); } my $numitems_for_this_value = ($bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : 1); if ($items_in_partition + $numitems_for_this_value <= $partition_size) { # add all the current values into the temporary list $metadata_value_to_OIDs_subhash{$metadata_value} = $metadata_value_to_OIDs_hash_ref->{$metadata_value}; $items_in_partition += $numitems_for_this_value; } elsif ($items_in_partition < $partition_size) { # only want to add some of the values into temporary list # note, we only get here if bookshelf type is never my @OIDs = @{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}; @OIDs = $self->sort_leaf_items(\@OIDs); my $num_items_needed = $partition_size - $items_in_partition; my @slice = splice(@OIDs, 0, $num_items_needed); $metadata_value_to_OIDs_subhash{$metadata_value} = \@slice; # now we have filled up the partition my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); my $partitionname = $partitionstart; if ($partitionend ne $partitionstart) { $partitionname = $partitionname . "-" . $partitionend; } $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partitionname, \%metadata_value_to_OIDs_subhash); %metadata_value_to_OIDs_subhash = (); $items_in_partition = 0; $lastpartitionend = $partitionend; # can we get more partitions from this metadata value? while (scalar(@OIDs) >= $partition_size) { my @slice = splice(@OIDs, 0, $partition_size); $metadata_value_to_OIDs_subhash{$metadata_value} = \@slice; $partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); my $partitionname = $partitionstart; if ($partitionend ne $partitionstart) { $partitionname = $partitionname . "-" . $partitionend; } $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partitionname, \%metadata_value_to_OIDs_subhash); %metadata_value_to_OIDs_subhash = (); $items_in_partition = 0; $lastpartitionend = $partitionend; } if (scalar(@OIDs) > 0) { $metadata_value_to_OIDs_subhash{$metadata_value} = \@OIDs; $items_in_partition = scalar(@OIDs); $partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); } } if ($items_in_partition == $partition_size) { # its the end of a partition my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); my $partitionname = $partitionstart; if ($partitionend ne $partitionstart) { $partitionname = $partitionname . "-" . $partitionend; } $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partitionname, \%metadata_value_to_OIDs_subhash); %metadata_value_to_OIDs_subhash = (); $items_in_partition = 0; $lastpartitionend = $partitionend; } } # foreach metadata value if ($items_in_partition > 0) { # we have to add the last partition my $partitionend = $self->generate_partition_end(@sortedmetadata_values[@sortedmetadata_values-1], $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric, $sort_mode); my $partitionname = $partitionstart; if ($partitionend ne $partitionstart) { $partitionname = $partitionname . "-" . $partitionend; } $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partitionname, \%metadata_value_to_OIDs_subhash); } # The partitions are stored in an HList $classifier_node->{'childtype'} = "HList"; } sub split_per_letter_or_digit { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $sort_mode = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); my $is_numeric = shift(@_); my $numeric_partition_length = shift(@_); if (not defined $is_numeric) { $is_numeric = 0; } if ($is_numeric && not defined($numeric_partition_length)) { $numeric_partition_length = 1; } # Generate one hlist for each letter my @sortedmetadata_values = $self->sort_metadata_values_array($sort_mode, keys(%$metadata_value_to_OIDs_hash_ref)); #print STDERR "sort the meta values array $sort_mode\n"; #print STDERR map "[$_] ", keys(%$metadata_value_to_OIDs_hash_ref); #print "\n"; #print STDERR map "[$_] ", @sortedmetadata_values; #print "\n"; my %metadata_value_to_OIDs_subhash = (); my $lastpartition = $self->generate_partition_name($sortedmetadata_values[0], $numeric_partition_length, $is_numeric, $sort_mode); foreach my $metadata_value (@sortedmetadata_values) { my $metadata_valuepartition = $self->generate_partition_name($metadata_value, $numeric_partition_length, $is_numeric, $sort_mode); # Is this the start of a new partition? #if ($metadata_valuepartition ne $lastpartition) { if ($self->partition_names_differ($sort_mode,$metadata_valuepartition, $lastpartition)) { $self->add_hlist_partition(\@metadata_groups, $classifier_node, $lastpartition, \%metadata_value_to_OIDs_subhash); %metadata_value_to_OIDs_subhash = (); $lastpartition = $metadata_valuepartition; } $metadata_value_to_OIDs_subhash{$metadata_value} = $metadata_value_to_OIDs_hash_ref->{$metadata_value}; } # Don't forget to add the last partition $self->add_hlist_partition(\@metadata_groups, $classifier_node, $lastpartition, \%metadata_value_to_OIDs_subhash); # The partitions are stored in an HList $classifier_node->{'childtype'} = "HList"; } sub partition_names_differ { my $self = shift(@_); my ($sort_mode) = shift(@_); my ($a, $b) = @_; if ($sort_mode eq "structured") { return &sorttools::structured_cmp($a,$b) != 0; } if ($sort_mode eq "structured_grouped") { return &sorttools::structured_grouped_1_cmp($a,$b) != 0; } return $a ne $b; } sub generate_partition_name { my $self = shift(@_); my $mvalue = shift(@_); my $numeric_partition_length = shift(@_); my $is_numeric = shift(@_); my $sort_mode = shift(@_); if (!$is_numeric || $numeric_partition_length == 1 ) { my $partition = substr($mvalue, 0, 1); if ($sort_mode eq "structured_grouped") { $partition = &sorttools::structured_grouped_normalise($partition); } return $partition; } if ($numeric_partition_length == -1) { my ($all_digits) = $mvalue =~ /^([0-9]+)/; return $all_digits; } my ($some_digits) = $mvalue =~ /^([0-9]{1,$numeric_partition_length})/; return $some_digits; } sub generate_partition_start { my $self = shift(@_); my $metadata_value = shift(@_); my $lastpartitionend = shift(@_); my $partition_name_length = shift(@_); my $max_partition_name_length = shift(@_); my $is_numeric = shift(@_); my $sort_mode = shift(@_); my $is_split = shift(@_); if ($is_numeric) { return $self->generate_partition_name($metadata_value, $partition_name_length, $is_numeric, $sort_mode); } if ($sort_mode eq "structured_grouped") { $metadata_value = &sorttools::structured_grouped_normalise($metadata_value); } $is_split = 0 unless defined $is_split; if ($partition_name_length) { my $partition = substr($metadata_value, 0, $partition_name_length); return $partition; } my $variable_partition_name_length = (1+$is_split <= $max_partition_name_length ? 1+$is_split : $max_partition_name_length); my $partitionstart = substr($metadata_value, 0, $variable_partition_name_length); while(($partitionstart le $lastpartitionend) && (($variable_partition_name_length += 1) <= $max_partition_name_length)) { $partitionstart = substr($metadata_value, 0, $variable_partition_name_length); } return $partitionstart; } sub generate_partition_end { my $self = shift(@_); my $metadata_value = shift(@_); my $partitionstart = shift(@_); my $partition_name_length = shift(@_); my $max_partition_name_length = shift(@_); my $is_numeric = shift(@_); my $sort_mode = shift(@_); if ($is_numeric) { return $self->generate_partition_name($metadata_value, $partition_name_length, $is_numeric, $sort_mode); } if ($sort_mode eq "structured_grouped") { $metadata_value = &sorttools::structured_grouped_normalise($metadata_value); } if ($partition_name_length) { return substr($metadata_value, 0, $partition_name_length); } my $partitionend = substr($metadata_value, 0, length($partitionstart)); #if ($partitionend gt $partitionstart) { # $partitionend = substr($metadata_value, 0, 1); # if ($partitionend le $partitionstart) { # $partitionend = substr($metadata_value, 0, 2); # # Give up after three characters # if ($partitionend le $partitionstart) { # $partitionend = substr($metadata_value, 0, 3); # } # } # } return $partitionend; } sub add_hlist_partition { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $partitionname = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); # Create an hlist partition # Note that we don't need to convert from unicode-aware strings # to utf8 here, as that is handled elsewhere in the code my %child_classifier_node = ( 'Title' => $partitionname, #'Title' => $self->convert_unicode_string_to_utf8_string($partitionname), 'childtype' => "VList", 'contains' => [] ); # Add the children to the hlist partition $self->add_vlist(\@metadata_groups, \%child_classifier_node, $metadata_value_to_OIDs_hash_ref); push(@{$classifier_node->{'contains'}}, \%child_classifier_node); } sub add_vlist { my $self = shift(@_); my @metadata_groups = @{shift(@_)}; my $classifier_node = shift(@_); my $metadata_value_to_OIDs_hash_ref = shift(@_); my $metadata_group = shift(@metadata_groups); $classifier_node->{'mdtype'} = $metadata_group; my $sort_type = $self->{$metadata_group .".metadata_sort_mode_within_level"}; # Create an entry in the vlist for each value foreach my $metadata_value ($self->sort_metadata_values_array($sort_type, keys(%{$metadata_value_to_OIDs_hash_ref}))) { my @OIDs = @{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}; # If there is only one item and 'bookshelf_type' is not always (ie. never or duplicate_only), add the item to the list if (@OIDs == 1 && $self->{$metadata_group . ".bookshelf_type"} ne "always") { my $OID = $OIDs[0]; my $offset = $self->metadata_offset($metadata_group, $OID, $metadata_value); push(@{$classifier_node->{'contains'}}, { 'OID' => $OID, 'offset' => $offset }); } # If 'bookshelf_type' is 'never', list all the items even if there are duplicated values elsif ($self->{$metadata_group . ".bookshelf_type"} eq "never") { @OIDs = $self->sort_leaf_items(\@OIDs); foreach my $OID (@OIDs) { my $offset = $self->metadata_offset($metadata_group, $OID, $metadata_value); push(@{$classifier_node->{'contains'}}, { 'OID' => $OID , 'offset' => $offset }); } } # Otherwise create a sublist (bookshelf) for the metadata value else { my $metadata_value_display = $self->get_metadata_value_display($metadata_group, $metadata_value); my %child_classifier_node = ( 'Title' => $metadata_value_display, 'childtype' => "VList", 'mdtype' => $metadata_group, 'contains' => [] ); # If there are metadata elements remaining, recursively apply the process if (@metadata_groups > 0) { my $next_metadata_group = $metadata_groups[0]; # separate metadata into those that belong in the next/sub-metadata_group # and those that belong at the current level's metadata_group my $OID_to_metadata_values_hash_ref = $self->{$next_metadata_group . ".list"}; my @current_level_OIDs = (); my @next_level_OIDs = (); foreach my $OID (@OIDs) { if ($OID_to_metadata_values_hash_ref->{$OID}) { push(@next_level_OIDs, $OID); } else { push(@current_level_OIDs, $OID); } } # recursively process those docs belonging to the sub-metadata_group $self->add_level(\@metadata_groups, \@next_level_OIDs, \%child_classifier_node); # For those docs that don't belong in the sub/next_metadata_group, but which belong # at this level, just add the documents as children of this list at the current level @current_level_OIDs = $self->sort_leaf_items(\@current_level_OIDs); foreach my $current_level_OID (@current_level_OIDs) { my $offset = $self->metadata_offset($metadata_group, $current_level_OID, $metadata_value); push(@{$child_classifier_node{'contains'}}, { 'OID' => $current_level_OID , 'offset' => $offset }); } } # Otherwise just add the documents as children of this list else { @OIDs = $self->sort_leaf_items(\@OIDs); foreach my $OID (@OIDs) { my $offset = $self->metadata_offset($metadata_group, $OID, $metadata_value); push(@{$child_classifier_node{'contains'}}, { 'OID' => $OID , 'offset' => $offset }); } } # Add the sublist to the list push(@{$classifier_node->{'contains'}}, \%child_classifier_node); } } } sub metadata_offset { my $self = shift(@_); my $metadata_group = shift(@_); my $OID = shift(@_); my $metadata_value = shift(@_); my $OID_to_metadata_values_hash_ref = $self->{$metadata_group . ".list"}; my @metadata_values = @{$OID_to_metadata_values_hash_ref->{$OID}}; for (my $i = 0; $i < scalar(@metadata_values); $i++) { if ($metadata_value eq $metadata_values[$i]) { return $i; } } return 0; } sub sort_leaf_items { my $self = shift(@_); my @OIDs = @{shift(@_)}; # Sort leaf nodes and add to list my @sort_leaf_nodes_using_metadata_groups = @{$self->{'sort_leaf_nodes_using_metadata_groups'}}; foreach my $sort_leaf_nodes_usingmetaelem (reverse @sort_leaf_nodes_using_metadata_groups) { my $OID_to_metadata_values_hash_ref = $self->{$sort_leaf_nodes_usingmetaelem . ".list"}; my $sort_type = $self->{$sort_leaf_nodes_usingmetaelem . ".metadata_sort_mode_within_level"}; # Force a stable sort (Perl 5.6's sort isn't stable) # !! The [0] bits aren't ideal (multiple metadata values) !! @OIDs = @OIDs[ sort { if (defined($OID_to_metadata_values_hash_ref->{$OIDs[$a]}) && defined($OID_to_metadata_values_hash_ref->{$OIDs[$b]})) { if ($sort_type eq "numeric") { $OID_to_metadata_values_hash_ref->{$OIDs[$a]}[0] <=> $OID_to_metadata_values_hash_ref->{$OIDs[$b]}[0]; } elsif ($sort_type eq "alphabetic") { $OID_to_metadata_values_hash_ref->{$OIDs[$a]}[0] cmp $OID_to_metadata_values_hash_ref->{$OIDs[$b]}[0]; } elsif ($sort_type eq "structured") { &sorttools::structured_sort($OID_to_metadata_values_hash_ref->{$OIDs[$a]}[0], $OID_to_metadata_values_hash_ref->{$OIDs[$b]}[0]); } elsif ($sort_type eq "structured_grouped") { &sorttools::structured_grouped_sort($OID_to_metadata_values_hash_ref->{$OIDs[$a]}[0], $OID_to_metadata_values_hash_ref->{$OIDs[$b]}[0]); } else { ncmp($OID_to_metadata_values_hash_ref->{$OIDs[$a]}[0], $OID_to_metadata_values_hash_ref->{$OIDs[$b]}[0]); } } else { $a <=> $b; } } 0..$#OIDs ]; } if ($self->{'reverse_sort_leaf_nodes'}) { return reverse @OIDs; } return @OIDs; } sub sort_metadata_values_array { my $self = shift(@_); my ($sort_mode) = shift(@_); my @metadata_values = @_; if ($sort_mode eq "unicode") { if ($self->{'unicode_collator'}) { return $self->{'unicode_collator'}->sort(@metadata_values); } # the collator wasn't loaded, fall back on default $sort_mode = "alphanumeric"; } if ($sort_mode eq "numeric") { return sort {$a <=> $b} @metadata_values; } if ($sort_mode eq "alphabetic") { return sort {$a cmp $b} @metadata_values; } # debugging # my @tmp =&sorttools::structured_sort(@metadata_values); # print STDERR map "[$_] ", @tmp; # print STDERR "structured grouped sort = \n"; # @tmp = &sorttools::structured_grouped_sort(@metadata_values); # print STDERR map "[$_] ", @tmp; if ($sort_mode eq "structured") { return &sorttools::structured_sort(@metadata_values); } if ($sort_mode eq "structured_grouped") { return &sorttools::structured_grouped_sort(@metadata_values); } # natural sort (greenstone version) return gsort(@metadata_values); } # we are not using this any more. Using gsort instead # $a and $b args automatically passed in and shouldn't be declared sub alpha_numeric_cmp { my $self = shift (@_); my ($aStr, $bStr) = @_; if ($aStr =~ m/^(\d+(\.\d+)?)/) { my $val_a = $1; if ($bStr =~ m/^(\d+(\.\d+)?)/) { my $val_b = $1; if ($val_a != $val_b) { return ($val_a <=> $val_b); } } } return ($aStr cmp $bStr); } sub get_metadata_value_display { my $self = shift(@_); my ($metadata_group, $metadata_value) = @_; return $metadata_value if $self->{'use_formatted_metadata_for_bookshelf_display'}; my $actual_values_hash = $self->{$metadata_group . ".actualvalues"}->{$metadata_value}; my $display_value =""; my $max_count=0; foreach my $v (keys %$actual_values_hash) { if ($actual_values_hash->{$v} > $max_count) { $display_value = $v; $max_count = $actual_values_hash->{$v}; } } return $display_value; } 1;