+# inserts string into trie and updates count for each character
+sub update_trie {
+ my ($trie, $string) = @_;
+ foreach (split //, $string) {
+ $trie = $trie->{$_} ||= {COUNT => 0};
+ $trie->{COUNT}++;
+ }
+}
+
+# returns an array of tuples (prefix, remainder)
+sub find_unique_prefixes {
+ my @stuff = @_;
+ my @return = ();
+
+ # any single prefix exceeding the soft limit is omitted
+ # if any prefix exceeds the hard limit all are omitted
+ # 0 indicates no limit
+ my $soft_limit = 0;
+ my $hard_limit = 3;
+
+ # build a trie modelling all possible options
+ my %trie;
+ foreach my $print (@stuff) {
+ if ((ref $print) eq 'ARRAY') {
+ $print = $print->[0];
+ }
+ elsif ((ref $print) eq 'HASH') {
+ $print = $print->{VALUE};
+ }
+ update_trie(\%trie, $print);
+ push @return, $print;
+ }
+
+ # use the trie to find the unique prefixes
+ for (my $i = 0; $i < @return; $i++) {
+ my $ret = $return[$i];
+ my @letters = split //, $ret;
+ my %search = %trie;
+ my ($prefix, $remainder);
+ my $j;
+ for ($j = 0; $j < @letters; $j++) {
+ my $letter = $letters[$j];
+ if ($search{$letter}{COUNT} == 1) {
+ $prefix = substr $ret, 0, $j + 1;
+ $remainder = substr $ret, $j + 1;
+ last;
+ }
+ else {
+ my $prefix = substr $ret, 0, $j;
+ return ()
+ if ($hard_limit && $j + 1 > $hard_limit);
+ }
+ %search = %{$search{$letter}};
+ }
+ if ($soft_limit && $j + 1 > $soft_limit) {
+ $prefix = undef;
+ $remainder = $ret;
+ }
+ $return[$i] = [$prefix, $remainder];
+ }
+ return @return;
+}
+
+# filters out prefixes which have special meaning to list_and_choose()
+sub is_valid_prefix {
+ my $prefix = shift;
+ return (defined $prefix) &&
+ !($prefix =~ /[\s,]/) && # separators
+ !($prefix =~ /^-/) && # deselection
+ !($prefix =~ /^\d+/) && # selection
+ ($prefix ne '*') && # "all" wildcard
+ ($prefix ne '?'); # prompt help
+}
+
+# given a prefix/remainder tuple return a string with the prefix highlighted
+# for now use square brackets; later might use ANSI colors (underline, bold)
+sub highlight_prefix {
+ my $prefix = shift;
+ my $remainder = shift;
+
+ if (!defined $prefix) {
+ return $remainder;
+ }
+
+ if (!is_valid_prefix($prefix)) {
+ return "$prefix$remainder";
+ }
+
+ if (!$menu_use_color) {
+ return "[$prefix]$remainder";
+ }
+
+ return "$prompt_color$prefix$normal_color$remainder";
+}
+