Hash.pm

The package Tree::Prefix::Hash handles the prefix tree in the format of a hash structure.

This is the documentation of all downloads.

Move your mouse over the code area and look at its top right corner where a set of icons for downloading, copy-pasting, etc. will appear.


#!/usr/bin/perl
package Tree::Prefix::Hash;

use strict;
use warnings;

sub new {
	my $classname=shift;
	my $self={};

	# only the empty tree, in order to drop unnecessary (<10) nodes
	# $self->{prefix_tree}->{a}->{b}->{count}=125 means: 125 words are starting with "ab"
	%{$self->{prefix_tree}}=();

	bless($self);
	return $self;
}

# ============ insert word to prefix tree as sequence of letters ============
sub insert_dir {
	my $self=shift;
	my $dir=shift;

	my @letters=split//, $dir;
	my $node=$self->{prefix_tree};

	for my $letter (@letters) {
		#if (++$node->{$letter}->{count}<=10) {
		#}
		$node->{$letter}->{count}++;
		$node->{$letter}->{ls}->{$dir}="";

		$node=$node->{$letter};
	}
}

# ============ changes directory in prefix tree - relative path (prefix) from the root ============
sub change_dir {
	my $self=shift;
	my $dir=shift;

	my @letters=split//, $dir;
	$self->{node}=$self->{prefix_tree};

	for my $letter (@letters) {
		$self->{node}=$self->{node}->{$letter};
	}
}

# ============ lists all the files of a specified node ============
sub list_files {
	my $self=shift;
	my $dir=shift;

	$self->change_dir($dir);
	my @a=sort keys %{$self->{node}->{ls}};

	return \@a;
}

# ============ (recursively) drop small nodes from the tree ============
sub cut_tree {
	my $self=shift;
	my $min_count=shift;
	my $node;

	# on first call use the default node: the root
	if (@_>0) {
		$node=shift;
	} else {
		$node=$self->{prefix_tree};
	}

	for my $letter (keys %$node) {
		if (length $letter > 1) { next; }
		if ($node->{$letter}->{count}<$min_count) {
			# if node is small, drop childs (if length > 1, it's not a child, rather "count" or "list")
			map { delete $node->{$letter}->{$_} } 
				grep { length $_ == 1 } 
				keys %{$node->{$letter}};

			#%{$node->{$letter}}=(
			#	count => $node->{$letter}->{count}
			#);
		} else {
			# if node is big, process deeper
			$self->cut_tree($min_count, $node->{$letter});
		}
	}
}

1;