File perl-Algorithm-Tree-NCA.spec of Package perl-Algorithm-Tree-NCA

Overview Repositories Revisions Requests Users Attributes Meta

File perl-Algorithm-Tree-NCA.spec of Package perl-Algorithm-Tree-NCA (Revision 4ef72d8ddb14b7a5f507b259c17664b5)

Currently displaying revision 4ef72d8ddb14b7a5f507b259c17664b5 , Show latest

#
# spec file for package perl-Algorithm-Tree-NCA
#
# Copyright (c) 2015 SUSE LINUX GmbH, Nuernberg, Germany.
#
# All modifications and additions to the file contributed by third parties
# remain the property of their copyright owners, unless otherwise agreed
# upon. The license for this file, and modifications and additions to the
# file, is the same license as for the pristine package itself (unless the
# license for the pristine package is not an Open Source License, in which
# case the license is the MIT License). An "Open Source License" is a
# license that conforms to the Open Source Definition (Version 1.9)
# published by the Open Source Initiative.

# Please submit bugfixes or comments via http://bugs.opensuse.org/
#

Name:           perl-Algorithm-Tree-NCA
Version:        0.02
Release:        0
%define cpan_name Algorithm-Tree-NCA
Summary:        Constant time retrieval of I<Nearest Common Ancestor>
License:        CHECK(GPL-1.0+ or Artistic-1.0)
Group:          Development/Libraries/Perl
Url:            http://search.cpan.org/dist/Algorithm-Tree-NCA/
Source0:        http://www.cpan.org/authors/id/M/MA/MATKIN/%{cpan_name}-%{version}.tar.gz
BuildArch:      noarch
BuildRoot:      %{_tmppath}/%{name}-%{version}-build
BuildRequires:  perl
BuildRequires:  perl-macros
%{perl_requires}

%description
This package provides constant-time retrieval of the Nearest Common
Ancestor (NCA) of nodes in a tree. The implementation is based on the
algorithm by Harel and which can, after linear-time preprocessing, retrieve
the nearest common ancestor of two nodes in constant time.

To implement the algorithm it is necessary to store some data for each node
in the tree.

* -
  A _node number_ assigned to the node in a pre-order fashion

* -
  A number to identify the _run_ of the node (the "ALGORITHM" manpage)

* -
  The _leader_ for each run, which should be retrievable through its
  node number

* -
  A _magic_ number (the "ALGORITHM" manpage)

* -
  The _parent_ node for each node

* -
  The _maximum_ number assigned to a any node in the subtree

All data above, with the exception of the node number, is stored in an
array inside the 'Algorithm::Tree::NCA' object.

The node number has to be stored in the actual tree node in some manner
(alternative solutions would be to slow to give constant-time retrieval),
which requires a _set method_ and a _get method_ for the nodes. Since the
most common case is using hashes to represent nodes, there are default
implementations of the set and get methods.

The default set method is:

sub _set_method {
      my($node,$value) = @_;

$node->{'_nca_number'} = $value;
  }

and the default get method is:

sub _get_method {
      my($node) = @_;

return $node->{'_nca_number'};
  }

If have chosen another representation of your nodes, you can provide
alternative set and get methods by using the *-set* and *-get* options when
creating the 'Algorithm::Tree::NCA' object.

%prep
%setup -q -n %{cpan_name}-%{version}
find . -type f -print0 | xargs -0 chmod 644

%build
%{__perl} Makefile.PL INSTALLDIRS=vendor
%{__make} %{?_smp_mflags}

%check
%{__make} test

%install
%perl_make_install
%perl_process_packlist
%perl_gen_filelist

%files -f %{name}.files
%defattr(-,root,root,755)
%doc Changes README Release

%changelog

Places

File perl-Algorithm-Tree-NCA.spec of Package perl-Algorithm-Tree-NCA (Revision 4ef72d8ddb14b7a5f507b259c17664b5)

Places