Index: /main/trunk/greenstone2/perllib/classify/List.pm
===================================================================
--- /main/trunk/greenstone2/perllib/classify/List.pm	(revision 36910)
+++ /main/trunk/greenstone2/perllib/classify/List.pm	(revision 36911)
@@ -177,6 +177,11 @@
       { 'name' => "partition_name_length",
 	'desc' => "{List.partition_name_length}",
-	'type' => "string" },
-      
+            '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}",
@@ -224,6 +229,14 @@
       { 'name' => "reverse_sort_leaf_nodes",
 	'desc' => "{List.reverse_sort_leaf_nodes}",
-	'type' => "flag"},
-      
+            '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}",
@@ -347,4 +360,5 @@
 	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
@@ -364,4 +378,5 @@
 	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/^'//;
@@ -479,5 +494,5 @@
 	return unless defined $meta;
 	if ($self->{'filter_regex'} ne "" && $meta !~ /$self->{'filter_regex'}/) {
-	    print STDERR "doc $doc_obj doesn't pass filtering requirement\n" if ($self->{'verbosity'} > 3);
+	    print STDERR "doc $doc_obj doesn't pass filtering requirement. Not classifying.\n" if ($self->{'verbosity'} > 3);
 	    return;
 	}
@@ -530,4 +545,5 @@
 	    $classify_section = 1;
 	    last;
+
 	} 
     }
@@ -680,9 +696,9 @@
 	}
 	elsif ($partition_type_within_level =~ /^approximate_size$/i && 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->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 && 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->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'});
 	}
 	    
@@ -732,7 +748,7 @@
 	# 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, 1);
+	$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" && 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, 1);
+	$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
@@ -748,5 +764,200 @@
 }
 
+
 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 = 10; # 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);
+    
+    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);
+	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 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);
+    
+	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);
+	    $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 = $items_in_partition/$num_splits;
+            # 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, 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 + $items_for_this_md_value > $this_partition_size && $items_done != 0 && ($items_in_partition - ($prev_done+$items_done) >= $tolerance)) {
+		    # 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, $max_partition_name_length, $is_numeric, 1);
+                    $prev_done += $items_done;
+		    $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 > $this_partition_size) {
+                    # if this is the case, we would have already stored what we have done in the previous step.
+		    my $partitionname_for_this_value = $self->generate_partition_start($metadata_value, $last_partition_end, $partition_name_length, $max_partition_name_length, $is_numeric);
+		    # Get the number of partitions needed for this value
+		    my $num_splits = int($items_for_this_md_value / $this_partition_size);
+		    $num_splits++ if ($items_for_this_md_value / $this_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 * $this_partition_size; $d < (($i+1) * $this_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) < $this_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, $max_partition_name_length, $is_numeric);
+		     $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_approximate_size_ORIG
 {
 
@@ -934,4 +1145,5 @@
 }
 
+
 sub split_constant_size
 {
@@ -944,4 +1156,5 @@
     my $metadata_value_to_OIDs_hash_ref = shift(@_);
     my $partition_name_length = shift(@_);
+    my $max_partition_name_length = shift(@_);
     my $is_numeric = shift(@_);
 
@@ -955,5 +1168,5 @@
 	if ($items_in_partition == 0) {
 	    # a new partition, set the name
-	    $partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $is_numeric);
+	    $partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $max_partition_name_length, $is_numeric);
 	}
 	my $numitems_for_this_value = ($bookshelf_type eq "never" ? scalar(@{$metadata_value_to_OIDs_hash_ref->{$metadata_value}}) : 1);
@@ -972,5 +1185,5 @@
 
 	    # now we have filled up the partition
-	    my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $is_numeric);
+	    my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric);
 	    my $partitionname = $partitionstart;
 	    if ($partitionend ne $partitionstart) {
@@ -987,6 +1200,6 @@
 		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, $is_numeric);
-		my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $is_numeric);
+		$partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $max_partition_name_length, $is_numeric);
+		my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric);
 		my $partitionname = $partitionstart;
 		if ($partitionend ne $partitionstart) {
@@ -1002,5 +1215,5 @@
 		$metadata_value_to_OIDs_subhash{$metadata_value} = \@OIDs;
 		$items_in_partition = scalar(@OIDs);
-		$partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $is_numeric);
+		$partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $partition_name_length, $max_partition_name_length, $is_numeric);
 	    }
 		
@@ -1010,5 +1223,5 @@
 	if ($items_in_partition == $partition_size) {
 	    # its the end of a partition
-	    my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $is_numeric);
+	    my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric);
 	    my $partitionname = $partitionstart;
 	    if ($partitionend ne $partitionstart) {
@@ -1025,5 +1238,5 @@
     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, $is_numeric);
+	my $partitionend = $self->generate_partition_end(@sortedmetadata_values[@sortedmetadata_values-1], $partitionstart, $partition_name_length, $max_partition_name_length, $is_numeric);
 	my $partitionname = $partitionstart;
 	if ($partitionend ne $partitionstart) {
@@ -1061,9 +1274,8 @@
     my $lastpartition = $self->generate_partition_name($sortedmetadata_values[0], $numeric_partition_length, $is_numeric);
     foreach my $metadata_value (@sortedmetadata_values) {
-	
 	my $metadata_valuepartition =  $self->generate_partition_name($metadata_value, $numeric_partition_length, $is_numeric);
-
 	# Is this the start of a new partition?
 	if ($metadata_valuepartition ne $lastpartition) {
+	    #print STDERR "new partition, old = $lastpartition, new=$metadata_valuepartition\n";
 	    $self->add_hlist_partition(\@metadata_groups, $classifier_node, $lastpartition, \%metadata_value_to_OIDs_subhash);
 	    %metadata_value_to_OIDs_subhash = ();
@@ -1106,21 +1318,26 @@
     my $lastpartitionend = shift(@_);
     my $partition_name_length = shift(@_);
+    my $max_partition_name_length  = shift(@_);
     my $is_numeric = shift(@_);
-
+    my $is_split = shift(@_);
+    
+#    print STDERR "generate-partitoin start, $metadata_value, $lastpartitionend, $max_partition_name_length\n";
     if ($is_numeric) {
 	return $self->generate_partition_name($metadata_value, $partition_name_length, $is_numeric);
     }
-    
+
+    $is_split = 0 unless defined $is_split;
+ #   print STDERR "is split = $is_split\n";
     if ($partition_name_length) {
+  #      print STDERR "partiton anme lenght = $partition_name_length, just using that length\n";
 	return substr($metadata_value, 0, $partition_name_length);
     }
 
-    my $partitionstart = substr($metadata_value, 0, 1);
-    if ($partitionstart le $lastpartitionend) {
-	$partitionstart = substr($metadata_value, 0, 2);
-	# Give up after three characters
-	if ($partitionstart le $lastpartitionend) {
-	    $partitionstart = substr($metadata_value, 0, 3);
-	}
+    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);
+   # print STDERR "new start = $partitionstart, $variable_partition_name_length\n";
+    while(($partitionstart le $lastpartitionend) && (($variable_partition_name_length += 1) <= $max_partition_name_length)) {
+    #    print STDERR "NEW###### $variable_partition_name_length\n";
+	$partitionstart = substr($metadata_value, 0, $variable_partition_name_length);
     }
 
@@ -1135,6 +1352,7 @@
     my $partitionstart = shift(@_);
     my $partition_name_length = shift(@_);
+    my $max_partition_name_length = shift(@_);
     my $is_numeric = shift(@_);
-
+    #print STDERR "geenrate end, $metadata_value: $partitionstart: $partition_name_length: $max_partition_name_length\n";
     if ($is_numeric) {
 	return $self->generate_partition_name($metadata_value, $partition_name_length, $is_numeric);
@@ -1145,14 +1363,14 @@
 
     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);
-	    }
-	}
-    }
+    #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;
