source: gsdl/trunk/perllib/classify/GenericList.pm@ 17110

Last change on this file since 17110 was 14845, checked in by mdewsnip, 16 years ago

Fixed some efficiency problems with GenericList when collections get large, and renamed a whole bunch of horrible variable names.
  • Property svn:keywords set to Author Date Id Revision
File size: 19.7 KB
Line 
1###########################################################################
2#
3# GenericList.pm -- A general and flexible list classifier with most of
4# the abilities of AZCompactList, and better Unicode,
5# metadata and sorting capabilities.
6#
7# A component of the Greenstone digital library software
8# from the New Zealand Digital Library Project at the
9# University of Waikato, New Zealand.
10#
11# Author: Michael Dewsnip, NZDL Project, University of Waikato, NZ
12#
13# Copyright (C) 2005 New Zealand Digital Library Project
14#
15# This program is free software; you can redistribute it and/or modify
16# it under the terms of the GNU General Public License as published by
17# the Free Software Foundation; either version 2 of the License, or
18# (at your option) any later version.
19#
20# This program is distributed in the hope that it will be useful,
21# but WITHOUT ANY WARRANTY; without even the implied warranty of
22# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23# GNU General Public License for more details.
24#
25# You should have received a copy of the GNU General Public License
26# along with this program; if not, write to the Free Software
27# Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
28#
29# TO DO: - Remove punctuation from metadata values before sorting.
30# - Add an AZCompactList-style hlist option?
31#
32###########################################################################
33
34package GenericList;
35
36
37use BasClas;
38
39use strict;
40
41
42sub BEGIN {
43 @GenericList::ISA = ('BasClas');
44}
45
46
47my $arguments =
48 [ { 'name' => "metadata",
49 'desc' => "{GenericList.metadata}",
50 'type' => "metadata",
51 'reqd' => "yes" },
52
53 # The interesting options
54 { 'name' => "always_bookshelf_last_level",
55 'desc' => "{GenericList.always_bookshelf_last_level}",
56 'type' => "flag" },
57 { 'name' => "classify_sections",
58 'desc' => "{GenericList.classify_sections}",
59 'type' => "flag" },
60 { 'name' => "partition_type_within_level",
61 'desc' => "{GenericList.partition_type_within_level}",
62 'type' => "string",
63 'deft' => "none" },
64 { 'name' => "partition_size_within_level",
65 'desc' => "{GenericList.partition_size_within_level}",
66 'type' => "string" },
67 { 'name' => "partition_name_length",
68 'desc' => "{GenericList.partition_name_length}",
69 'type' => "string" },
70 { 'name' => "sort_leaf_nodes_using",
71 'desc' => "{GenericList.sort_leaf_nodes_using}",
72 'type' => "metadata",
73 'deft' => "Title" },
74 { 'name' => "sort_using_unicode_collation",
75 'desc' => "{GenericList.sort_using_unicode_collation}",
76 'type' => "flag" },
77 { 'name' => "use_hlist_for",
78 'desc' => "{GenericList.use_hlist_for}",
79 'type' => "string" } ];
80
81my $options = { 'name' => "GenericList",
82 'desc' => "{GenericList.desc}",
83 'abstract' => "no",
84 'inherits' => "Yes",
85 'args' => $arguments };
86
87
88sub new
89{
90 my ($class) = shift(@_);
91 my ($classifierslist, $inputargs, $hashArgOptLists) = @_;
92 push(@$classifierslist, $class);
93
94 if (defined $arguments) { push(@{$hashArgOptLists->{"ArgList"}}, @{$arguments}); }
95 if (defined $options) { push(@{$hashArgOptLists->{"OptList"}}, $options); }
96
97 my $self = new BasClas($classifierslist, $inputargs, $hashArgOptLists);
98
99 if ($self->{'info_only'}) {
100 # don't worry about any options etc
101 return bless $self, $class;
102 }
103
104 # The metadata elements to use (required)
105 if (!$self->{'metadata'}) {
106 die "Error: No metadata fields specified for GenericList.\n";
107 }
108 my @metadata_groups = split(/\//, $self->{'metadata'});
109 $self->{'metadata_groups'} = \@metadata_groups;
110
111 # The classifier button name (default: the first metadata element specified)
112 if (!$self->{'buttonname'}) {
113 my $first_metadata_group = $metadata_groups[0];
114 my $first_metadata_element = (split(/\;/, $first_metadata_group))[0];
115 $self->{'buttonname'} = $self->generate_title_from_metadata($first_metadata_element);
116 }
117
118 # Whether to group single items into a bookshelf (must be true for all metadata fields except the last)
119 foreach my $metadata_group (@metadata_groups) {
120 $self->{$metadata_group . ".always_bookshelf"} = "t";
121 }
122 if (!$self->{'always_bookshelf_last_level'}) {
123 # Default: leave leaf nodes ungrouped (equivalent to AZCompactList -mingroup 2)
124 my $last_metadata_group = $metadata_groups[$#metadata_groups];
125 $self->{$last_metadata_group . ".always_bookshelf"} = "f";
126 }
127
128 # Whether to use an hlist or a vlist for each level in the hierarchy (default: vlist)
129 foreach my $metadata_group (@metadata_groups) {
130 $self->{$metadata_group . ".list_type"} = "VList";
131 }
132 foreach my $metadata_group (split(/\,/, $self->{'use_hlist_for'})) {
133 $self->{$metadata_group . ".list_type"} = "HList";
134 }
135
136 # How the items are grouped into partitions (default: no partition)
137 if (!$self->{"partition_type_within_level"}) {
138 $self->{"partition_type_within_level"} = "none";
139 }
140
141 # The number of items in each partition
142 if (!$self->{'partition_size_within_level'}) {
143 # Default: 20
144 foreach my $metadata_group (@metadata_groups) {
145 $self->{$metadata_group . ".partition_size_within_level"} = 20;
146 }
147 }
148 else {
149 my @partition_size_within_levellist = split(/\//, $self->{'partition_size_within_level'});
150
151 # Assign values based on the partition_size_within_level parameter
152 foreach my $metadata_group (@metadata_groups) {
153 my $partition_size_within_levelelem = shift(@partition_size_within_levellist);
154 if (defined($partition_size_within_levelelem)) {
155 $self->{$metadata_group . ".partition_size_within_level"} = $partition_size_within_levelelem;
156 }
157 else {
158 $self->{$metadata_group . ".partition_size_within_level"} = $self->{$metadata_groups[0] . ".partition_size_within_level"};
159 }
160 }
161 }
162
163 # The metadata elements to use to sort the leaf nodes (default: Title)
164 my @sort_leaf_nodes_using_metadata_groups = ( "Title" );
165 if ($self->{'sort_leaf_nodes_using'}) {
166 @sort_leaf_nodes_using_metadata_groups = split(/\|/, $self->{'sort_leaf_nodes_using'});
167 }
168 $self->{'sort_leaf_nodes_using_metadata_groups'} = \@sort_leaf_nodes_using_metadata_groups;
169
170 # Create an instance of the Unicode::Collate object if better Unicode sorting is desired
171 if ($self->{'sort_using_unicode_collation'}) {
172 # To use this you first need to download the allkeys.txt file from
173 # http://www.unicode.org/Public/UCA/latest/allkeys.txt and put it in the Perl
174 # Unicode/Collate directory.
175 require Unicode::Collate;
176 $self->{'unicode_collator'} = Unicode::Collate->new();
177 }
178
179 # An empty array for the document OIDs
180 $self->{'OIDs'} = [];
181
182 return bless $self, $class;
183}
184
185
186sub init
187{
188 # Nothing to do...
189}
190
191
192# Called for each document in the collection
193sub classify
194{
195 my $self = shift(@_);
196 my $doc_obj = shift(@_);
197
198 # If "-classify_sections" is set, classify every section of the document
199 if ($self->{'classify_sections'}) {
200 my $section = $doc_obj->get_next_section($doc_obj->get_top_section());
201 while (defined $section) {
202 $self->classify_section($doc_obj, $doc_obj->get_OID() . ".$section", $section);
203 $section = $doc_obj->get_next_section($section);
204 }
205 }
206 # Otherwise just classify the top document section
207 else {
208 $self->classify_section($doc_obj, $doc_obj->get_OID(), $doc_obj->get_top_section());
209 }
210}
211
212
213sub classify_section
214{
215 my $self = shift(@_);
216 my $doc_obj = shift(@_);
217 my $section_OID = shift(@_);
218 my $section = shift(@_);
219
220 my @metadata_groups = @{$self->{'metadata_groups'}};
221
222 # Only classify the section if it has a value for one of the metadata elements in the first group
223 my $classify_section = 0;
224 my $first_metadata_group = $metadata_groups[0];
225 foreach my $first_metadata_group_element (split(/\;/, $first_metadata_group)) {
226 my $first_metadata_group_element_value = $doc_obj->get_metadata_element($section, $first_metadata_group_element);
227 if (defined($first_metadata_group_element_value) && $first_metadata_group_element_value ne "") {
228 # This section must be included in the classifier
229 $classify_section = 1;
230 last;
231 }
232 }
233
234 # We're not classifying this section because it doesn't have the required metadata
235 return if (!$classify_section);
236
237 # Otherwise, include this section in the classifier
238 push(@{$self->{'OIDs'}}, $section_OID);
239
240 # Create a hash for the metadata values of each metadata element we're interested in
241 my %metadata_groups_done = ();
242 foreach my $metadata_group (@metadata_groups, @{$self->{'sort_leaf_nodes_using_metadata_groups'}}) {
243 # Take care not to do a metadata group more than once
244 unless ($metadata_groups_done{$metadata_group}) {
245 foreach my $metadata_element (split(/\;/, $metadata_group)) {
246 my @metadata_values = @{$doc_obj->get_metadata($section, $metadata_element)};
247 foreach my $metadata_value (@metadata_values) {
248 # Strip leading and trailing whitespace
249 $metadata_value =~ s/^\s*//;
250 $metadata_value =~ s/\s*$//;
251
252 # Convert the metadata value from a UTF-8 string to a Unicode string
253 # This means that length() and substr() work properly
254 # We need to be careful to convert classifier node title values back to UTF-8, however
255 my $metadata_value_unicode_string = $self->convert_utf8_string_to_unicode_string($metadata_value);
256
257 # Add the metadata value into the list for this combination of metadata group and section
258 push(@{$self->{$metadata_group . ".list"}->{$section_OID}}, $metadata_value_unicode_string);
259 }
260 last if (@metadata_values > 0);
261 }
262
263 $metadata_groups_done{$metadata_group} = 1;
264 }
265 }
266}
267
268
269sub get_classify_info
270{
271 my $self = shift(@_);
272
273 # The metadata groups to classify by
274 my @metadata_groups = @{$self->{'metadata_groups'}};
275 my $first_metadata_group = $metadata_groups[0];
276
277 # The OID values of the documents to include in the classifier
278 my @OIDs = @{$self->{'OIDs'}};
279
280 # Create the root node of the classification hierarchy
281 my %classifier_node = ( 'thistype' => "Invisible",
282 'childtype' => $self->{$first_metadata_group . ".list_type"},
283 'Title' => $self->{'buttonname'},
284 'contains' => [],
285 'mdtype' => $first_metadata_group );
286
287 # Recursively create the classification hierarchy, one level for each metadata group
288 $self->add_level(\@metadata_groups, \@OIDs, \%classifier_node);
289 return \%classifier_node;
290}
291
292
293sub add_level
294{
295 my $self = shift(@_);
296 my @metadata_groups = @{shift(@_)};
297 my @OIDs = @{shift(@_)};
298 my $classifier_node = shift(@_);
299 # print STDERR "\nAdding AZ list for " . $classifier_node->{'Title'} . "\n";
300
301 my $metadata_group = $metadata_groups[0];
302 # print STDERR "Processing metadata group: " . $metadata_group . "\n";
303 # print STDERR "Number of OID values: " . @OIDs . "\n";
304
305 if (!defined($self->{$metadata_group . ".list"})) {
306 print STDERR "Warning: No metadata values assigned to $metadata_group.\n";
307 return;
308 }
309
310 # Create a mapping from metadata value to OID
311 my $OID_to_metadata_values_hash_ref = $self->{$metadata_group . ".list"};
312 my %metadata_value_to_OIDs_hash = ();
313 foreach my $OID (@OIDs)
314 {
315 if ($OID_to_metadata_values_hash_ref->{$OID})
316 {
317 my @metadata_values = @{$OID_to_metadata_values_hash_ref->{$OID}};
318 foreach my $metadata_value (@metadata_values)
319 {
320 push(@{$metadata_value_to_OIDs_hash{$metadata_value}}, $OID);
321 }
322 }
323 }
324 # print STDERR "Number of distinct values: " . scalar(keys %metadata_value_to_OIDs_hash) . "\n";
325
326 # Partition the values (if necessary)
327 my $partition_type_within_level = $self->{"partition_type_within_level"};
328 if ($partition_type_within_level =~ /^per_letter$/i) {
329 # Generate one hlist for each letter
330 my @sortedmetadata_values = $self->sort_metadata_values_array(keys(%metadata_value_to_OIDs_hash));
331 my %metadata_value_to_OIDs_subhash = ();
332
333 my $lastpartition = substr($sortedmetadata_values[0], 0, 1);
334 foreach my $metadata_value (@sortedmetadata_values) {
335 my $metadata_valuepartition = substr($metadata_value, 0, 1);
336
337 # Is this the start of a new partition?
338 if ($metadata_valuepartition ne $lastpartition) {
339 $self->add_hlist_partition(\@metadata_groups, $classifier_node, $lastpartition, \%metadata_value_to_OIDs_subhash);
340 %metadata_value_to_OIDs_subhash = ();
341 $lastpartition = $metadata_valuepartition;
342 }
343
344 $metadata_value_to_OIDs_subhash{$metadata_value} = $metadata_value_to_OIDs_hash{$metadata_value};
345 }
346
347 # Don't forget to add the last partition
348 $self->add_hlist_partition(\@metadata_groups, $classifier_node, $lastpartition, \%metadata_value_to_OIDs_subhash);
349
350 # The partitions are stored in an HList
351 $classifier_node->{'childtype'} = "HList";
352 }
353
354 else {
355 # Generate hlists of a certain size
356 my $partition_size_within_level = $self->{$metadata_group . ".partition_size_within_level"};
357 if ($partition_type_within_level =~ /^constant_size$/i && scalar(keys %metadata_value_to_OIDs_hash) > $partition_size_within_level) {
358 my @sortedmetadata_values = $self->sort_metadata_values_array(keys(%metadata_value_to_OIDs_hash));
359 my $itemsdone = 0;
360 my %metadata_value_to_OIDs_subhash = ();
361 my $lastpartitionend = "";
362 my $partitionstart;
363 foreach my $metadata_value (@sortedmetadata_values) {
364 $metadata_value_to_OIDs_subhash{$metadata_value} = $metadata_value_to_OIDs_hash{$metadata_value};
365 $itemsdone++;
366 my $itemsinpartition = scalar(keys %metadata_value_to_OIDs_subhash);
367
368 # Is this the start of a new partition?
369 if ($itemsinpartition == 1) {
370 $partitionstart = $self->generate_partition_start($metadata_value, $lastpartitionend, $self->{"partition_name_length"});
371 }
372
373 # Is this the end of the partition?
374 if ($itemsinpartition == $partition_size_within_level || $itemsdone == @sortedmetadata_values) {
375 my $partitionend = $self->generate_partition_end($metadata_value, $partitionstart, $self->{"partition_name_length"});
376 my $partitionname = $partitionstart;
377 if ($partitionend ne $partitionstart) {
378 $partitionname = $partitionname . "-" . $partitionend;
379 }
380
381 $self->add_hlist_partition(\@metadata_groups, $classifier_node, $partitionname, \%metadata_value_to_OIDs_subhash);
382 %metadata_value_to_OIDs_subhash = ();
383 $lastpartitionend = $partitionend;
384 }
385 }
386
387 # The partitions are stored in an HList
388 $classifier_node->{'childtype'} = "HList";
389 }
390
391 # Otherwise just add all the values to a VList
392 else {
393 $self->add_vlist(\@metadata_groups, $classifier_node, \%metadata_value_to_OIDs_hash);
394 }
395 }
396}
397
398
399sub convert_utf8_string_to_unicode_string
400{
401 my $self = shift(@_);
402 my $utf8_string = shift(@_);
403
404 my $unicode_string = "";
405 foreach my $unicode_value (@{&unicode::utf82unicode($utf8_string)}) {
406 $unicode_string .= chr($unicode_value);
407 }
408 return $unicode_string;
409}
410
411
412sub convert_unicode_string_to_utf8_string
413{
414 my $self = shift(@_);
415 my $unicode_string = shift(@_);
416
417 my @unicode_array;
418 for (my $i = 0; $i < length($unicode_string); $i++) {
419 push(@unicode_array, ord(substr($unicode_string, $i, 1)));
420 }
421 return &unicode::unicode2utf8(\@unicode_array);
422}
423
424
425sub generate_partition_start
426{
427 my $self = shift(@_);
428 my $metadata_value = shift(@_);
429 my $lastpartitionend = shift(@_);
430 my $partition_name_length = shift(@_);
431
432 if ($partition_name_length) {
433 return substr($metadata_value, 0, $partition_name_length);
434 }
435
436 my $partitionstart = substr($metadata_value, 0, 1);
437 if ($partitionstart le $lastpartitionend) {
438 $partitionstart = substr($metadata_value, 0, 2);
439 # Give up after three characters
440 if ($partitionstart le $lastpartitionend) {
441 $partitionstart = substr($metadata_value, 0, 3);
442 }
443 }
444
445 return $partitionstart;
446}
447
448
449sub generate_partition_end
450{
451 my $self = shift(@_);
452 my $metadata_value = shift(@_);
453 my $partitionstart = shift(@_);
454 my $partition_name_length = shift(@_);
455
456 if ($partition_name_length) {
457 return substr($metadata_value, 0, $partition_name_length);
458 }
459
460 my $partitionend = substr($metadata_value, 0, length($partitionstart));
461 if ($partitionend gt $partitionstart) {
462 $partitionend = substr($metadata_value, 0, 1);
463 if ($partitionend le $partitionstart) {
464 $partitionend = substr($metadata_value, 0, 2);
465 # Give up after three characters
466 if ($partitionend le $partitionstart) {
467 $partitionend = substr($metadata_value, 0, 3);
468 }
469 }
470 }
471
472 return $partitionend;
473}
474
475
476sub add_hlist_partition
477{
478 my $self = shift(@_);
479 my @metadata_groups = @{shift(@_)};
480 my $classifier_node = shift(@_);
481 my $partitionname = shift(@_);
482 my $metadata_value_to_OIDs_hash_ref = shift(@_);
483
484 # Create an hlist partition
485 my %child_classifier_node = ( 'Title' => $self->convert_unicode_string_to_utf8_string($partitionname),
486 'childtype' => "VList",
487 'contains' => [] );
488
489 # Add the children to the hlist partition
490 $self->add_vlist(\@metadata_groups, \%child_classifier_node, $metadata_value_to_OIDs_hash_ref);
491 push(@{$classifier_node->{'contains'}}, \%child_classifier_node);
492}
493
494
495sub add_vlist
496{
497 my $self = shift(@_);
498 my @metadata_groups = @{shift(@_)};
499 my $classifier_node = shift(@_);
500 my $metadata_value_to_OIDs_hash_ref = shift(@_);
501
502 my $metadata_group = shift(@metadata_groups);
503 $classifier_node->{'mdtype'} = $metadata_group;
504
505 # Create an entry in the vlist for each value
506 foreach my $metadata_value ($self->sort_metadata_values_array(keys(%{$metadata_value_to_OIDs_hash_ref})))
507 {
508 my @OIDs = @{$metadata_value_to_OIDs_hash_ref->{$metadata_value}};
509
510 # If there is only one item and 'always_bookshelf' is false, add the item to the list
511 if (@OIDs == 1 && $self->{$metadata_group . ".always_bookshelf"} eq "f") {
512 my $OID = $OIDs[0];
513
514 # Find the offset of this metadata value
515 my $offset = 0;
516 my $OID_to_metadata_values_hash_ref = $self->{$metadata_group . ".list"};
517 my @metadata_values = @{$OID_to_metadata_values_hash_ref->{$OID}};
518 for (my $i = 0; $i < scalar(@metadata_values); $i++) {
519 if ($metadata_value eq $metadata_values[$i]) {
520 $offset = $i;
521 last;
522 }
523 }
524 push(@{$classifier_node->{'contains'}}, { 'OID' => $OID, 'offset' => $offset });
525 }
526
527 # Otherwise create a sublist (bookshelf) for the metadata value
528 else {
529 my %child_classifier_node = ( 'Title' => $self->convert_unicode_string_to_utf8_string($metadata_value),
530 'childtype' => "VList",
531 'contains' => [] );
532
533 # If there are metadata elements remaining, recursively apply the process
534 if (@metadata_groups > 0) {
535 my $next_metadata_group = $metadata_groups[0];
536 $child_classifier_node{'childtype'} = $self->{$next_metadata_group . ".list_type"};
537 $self->add_level(\@metadata_groups, \@OIDs, \%child_classifier_node);
538 }
539 # Otherwise just add the documents as children of this list
540 else {
541 # Sort the leaf nodes by the metadata elements specified with -sort_leaf_nodes_using
542 my @sort_leaf_nodes_usingmetadata_groups = @{$self->{'sort_leaf_nodes_using_metadata_groups'}};
543 foreach my $sort_leaf_nodes_usingmetaelem (reverse @sort_leaf_nodes_usingmetadata_groups) {
544 my $OID_to_metadata_values_hash_ref = $self->{$sort_leaf_nodes_usingmetaelem . ".list"};
545 # Force a stable sort (Perl 5.6's sort isn't stable)
546 # !! The [0] bits aren't ideal (multiple metadata values) !!
547 @OIDs = @OIDs[ sort { $OID_to_metadata_values_hash_ref->{$OIDs[$a]}[0] cmp $OID_to_metadata_values_hash_ref->{$OIDs[$b]}[0] || $a <=> $b; } 0..$#OIDs ];
548 }
549
550 foreach my $OID (@OIDs) {
551 push(@{$child_classifier_node{'contains'}}, { 'OID' => $OID });
552 }
553 }
554
555 # Add the sublist to the list
556 push(@{$classifier_node->{'contains'}}, \%child_classifier_node);
557 }
558 }
559}
560
561
562sub sort_metadata_values_array
563{
564 my $self = shift(@_);
565 my @metadata_values = @_;
566
567 if ($self->{'unicode_collator'}) {
568 return $self->{'unicode_collator'}->sort(@metadata_values);
569 }
570 else {
571 return sort(@metadata_values);
572 }
573}
574
575
5761;
Note: See TracBrowser for help on using the repository browser.