Commits

Toby Inkster committed ef8377f

initial version

Comments (0)

Files changed (17)

+use inc::Module::Package 'RDF:tobyink 0.009';
+

examples/benchmarking-output.txt

+# Word count: 50000
+ok 1
+ok 2
+ok 3
+1..3
+# Benchmarking rnkeytopsort for top 5
+
+#         Rate naive    pp    xs
+# naive 1.03/s    --  -59%  -87%
+# pp    2.48/s  142%    --  -68%
+# xs    7.76/s  657%  213%    --
+# 
+
+# Benchmarking rnkeytopsort for top 50
+
+#         Rate naive    pp    xs
+# naive 1.03/s    --  -54%  -86%
+# pp    2.23/s  115%    --  -69%
+# xs    7.23/s  599%  224%    --
+# 
+
+# Benchmarking rnkeytopsort for top 500
+
+#         Rate naive    pp    xs
+# naive 1.03/s    --  -45%  -87%
+# pp    1.88/s   82%    --  -76%
+# xs    7.75/s  651%  313%    --
+# 
+

examples/benchmarking.pl

+use v5.10;
+use strict;
+use warnings;
+use Test::More;
+use Benchmark qw(cmpthese);
+
+use Sort::Key::Top 'rnkeytopsort';
+use Sort::Key::Top::PP 'rnkeytopsort' => { -as => 'rnkeytopsort_pp' };
+
+# Naive pure Perl implementation of rnkeytopsort
+sub rnkeytopsort_naive (&$@) {
+	my ($code, $n, @list) = @_;
+	my @sorted =
+		map  { $_->[1] }
+		sort { $b->[0] <=> $a->[0] }
+		map  { [ $code->($_), $_ ] } @_;
+	return @sorted[ 0 .. $n-1 ];
+}
+
+my @list;
+open my $fh, '<', '/usr/share/dict/words';
+while (<$fh>) {
+	chomp;
+	push @list, $_;
+	last if @list >= 50_000;
+}
+say "# Word count: @{[ scalar @list ]}";
+
+my @xs    = rnkeytopsort       { length($_) } 50 => @list;
+my @pp    = rnkeytopsort_pp    { length($_) } 50 => @list;
+my @naive = rnkeytopsort_naive { length($_) } 50 => @list;
+
+is_deeply(\@xs, \@naive);
+is_deeply(\@pp, \@naive);
+is_deeply(\@pp, \@xs);
+done_testing;
+
+# Make Benchmark output into TAP comments...
+use IO::Callback; SELECT: {
+	select(
+		IO::Callback->new('>', sub {
+			my $in = shift;
+			$in =~ s/^/# /m;
+			print STDOUT $in;
+		})
+	);
+};
+
+for my $N (qw< 5 50 500 >)
+{
+	say "Benchmarking rnkeytopsort for top $N";
+	cmpthese(50, {
+		xs    => sub { rnkeytopsort       { length($_) } $N, @list },
+		pp    => sub { rnkeytopsort_pp    { length($_) } $N, @list },
+		naive => sub { rnkeytopsort_naive { length($_) } $N, @list },
+	});
+	say q();
+}

lib/Sort/Key/Top/PP.pm

+package Sort::Key::Top::PP;
+
+use 5.008;
+use strict;
+use warnings;
+no warnings qw( once );
+
+use Exporter::Everything;
+
+BEGIN {
+	$Sort::Key::Top::PP::AUTHORITY = 'cpan:TOBYINK';
+	$Sort::Key::Top::PP::VERSION   = '0.001';
+}
+
+sub _tail_numeric {
+	my ($list, $top_n) = @_;
+	my @top;
+	my $cur;
+	for my $i (@$list) {
+		next if @top==$top_n && $i->[0] < $top[0][0];
+		((@top = $i), next) unless @top;
+		my ($low, $high) = (0, scalar @top);
+		(
+			($cur = ($low + $high) >> 1),
+			($i->[0] - $top[$cur][0] > 0)
+				? ($low = $cur + 1)
+				: ($high = $cur),
+		) while $low < $high;
+		splice(@top, $low, 0, $i);
+		shift @top if @top > $top_n;
+	}
+	return reverse @top;
+}
+
+sub _head_numeric {
+	my ($list, $top_n) = @_;
+	my @top;
+	my $cur;
+	for my $i (@$list) {
+		next if @top==$top_n && $i->[0] > $top[0][0];
+		((@top = $i), next) unless @top;
+		my ($low, $high) = (0, scalar @top);
+		(
+			($cur = ($low + $high) >> 1),
+			($top[$cur][0] - $i->[0] > 0)
+				? ($low = $cur + 1)
+				: ($high = $cur),
+		) while $low < $high;
+		splice(@top, $low, 0, $i);
+		shift @top if @top > $top_n;
+	}
+	return reverse @top;
+}
+
+sub _head_stringy {
+	my ($list, $top_n) = @_;
+	my @top;
+	my $cur;
+	for my $i (@$list) {
+		next if @top==$top_n && $i->[0] gt $top[0][0];
+		((@top = $i), next) unless @top;
+		my ($low, $high) = (0, scalar @top);
+		(
+			($cur = ($low + $high) >> 1),
+			(($top[$cur][0] cmp $i->[0]) > 0)
+				? ($low = $cur + 1)
+				: ($high = $cur),
+		) while $low < $high;
+		splice(@top, $low, 0, $i);
+		shift @top if @top > $top_n;
+	}
+	return reverse @top;
+}
+
+sub _tail_stringy {
+	my ($list, $top_n) = @_;
+	my @top;
+	my $cur;
+	for my $i (@$list) {
+		next if @top==$top_n && $i->[0] lt $top[0][0];
+		((@top = $i), next) unless @top;
+		my ($low, $high) = (0, scalar @top);
+		(
+			($cur = ($low + $high) >> 1),
+			(($top[$cur][0] cmp $i->[0]) < 0)
+				? ($low = $cur + 1)
+				: ($high = $cur),
+		) while $low < $high;
+		splice(@top, $low, 0, $i);
+		shift @top if @top > $top_n;
+	}
+	return reverse @top;
+}
+
+sub _preprocess {
+	my $code  = shift;
+	my $count = 0;
+	$code
+		? [ map [ $code->($_), $_, $count++ ], @_ ]
+		: [ map [ $_         , $_, $count++ ], @_ ];
+}
+
+sub _postprocess {
+	my $n = shift;
+	wantarray
+		? map($_->[1], @_)
+		: ( @_ >= $n ? $_[-1][1] : undef )
+}
+
+sub _restore_order;
+if (eval { require Sort::Key }) {
+	*_restore_order = sub { &Sort::Key::ikeysort(sub { $_->[2] }, @_) };
+}
+else {
+	*_restore_order = sub { sort { $a->[2] <=> $b->[2] } @_ };
+}
+
+sub top {
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_head_stringy(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub topsort {
+	my $n = shift;
+	_postprocess $n,
+	_head_stringy(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub keytop (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_head_stringy(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub keytopsort (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_head_stringy(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub ntop {
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_head_numeric(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub ntopsort {
+	my $n = shift;
+	_postprocess $n,
+	_head_numeric(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub nkeytop (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_head_numeric(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub nkeytopsort (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_head_numeric(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub rtop {
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_tail_stringy(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub rtopsort {
+	my $n = shift;
+	_postprocess $n,
+	_tail_stringy(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub rkeytop (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_tail_stringy(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub rkeytopsort (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_tail_stringy(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub rntop {
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_tail_numeric(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub rntopsort {
+	my $n = shift;
+	_postprocess $n,
+	_tail_numeric(
+		_preprocess(undef, @_),
+		$n
+	);
+}
+
+sub rnkeytop (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_restore_order
+	_tail_numeric(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub rnkeytopsort (&$@) {
+	my $k = shift;
+	my $n = shift;
+	_postprocess $n,
+	_tail_numeric(
+		_preprocess($k, @_),
+		$n
+	);
+}
+
+sub head {
+	unshift @_, 1;
+	scalar &topsort;
+}
+
+sub nhead {
+	unshift @_, 1;
+	scalar &ntopsort;
+}
+
+sub keyhead (&@) {
+	splice(@_, 1, 0, 1);
+	scalar &keytopsort;
+}
+
+sub nkeyhead (&@) {
+	splice(@_, 1, 0, 1);
+	scalar &nkeytopsort;
+}
+
+sub tail {
+	unshift @_, 1;
+	scalar &rtopsort;
+}
+
+sub ntail {
+	unshift @_, 1;
+	scalar &rntopsort;
+}
+
+sub keytail (&@) {
+	splice(@_, 1, 0, 1);
+	scalar &rkeytopsort;
+}
+
+sub nkeytail (&@) {
+	splice(@_, 1, 0, 1);
+	scalar &rnkeytopsort;
+}
+
+1;
+
+__END__
+
+=encoding utf-8
+
+=head1 NAME
+
+Sort::Key::Top::PP - pure Perl implementation of parts of Sort::Key::Top
+
+=head1 SYNOPSIS
+
+	use Sort::Key::Top::PP 'top';
+	my @top5 = top 5 => @biglist;
+
+=head1 DESCRIPTION
+
+Sort::Key::Top::PP is set of functions for finding the top "n" items in an
+array by some criteria. It's not as fast as L<Sort::Key::Top>, but it is
+generally quite a bit faster than sorting the entire array and taking the
+first "n" items.
+
+This module implements pure Perl equivalents of the following functions as
+descibed in L<Sort::Key::Top>.
+
+=over
+
+=item *
+
+C<top>
+
+=item *
+
+C<topsort>
+
+=item *
+
+C<keytop>
+
+=item *
+
+C<keytopsort>
+
+=item *
+
+C<ntop>
+
+=item *
+
+C<ntopsort>
+
+=item *
+
+C<nkeytop>
+
+=item *
+
+C<nkeytopsort>
+
+=item *
+
+C<rtop>
+
+=item *
+
+C<rtopsort>
+
+=item *
+
+C<rkeytop>
+
+=item *
+
+C<rkeytopsort>
+
+=item *
+
+C<rntop>
+
+=item *
+
+C<rntopsort>
+
+=item *
+
+C<rnkeytop>
+
+=item *
+
+C<rnkeytopsort>
+
+=item *
+
+C<head>
+
+=item *
+
+C<nhead>
+
+=item *
+
+C<keyhead>
+
+=item *
+
+C<nkeyhead>
+
+=item *
+
+C<tail>
+
+=item *
+
+C<ntail>
+
+=item *
+
+C<keytail>
+
+=item *
+
+C<nkeytail>
+
+=back
+
+=head1 BUGS
+
+Please report any bugs to
+L<http://rt.cpan.org/Dist/Display.html?Queue=Sort-Key-Top-PP>.
+
+=head1 SEE ALSO
+
+L<Sort::Key::Top>,
+L<http://blogs.perl.org/users/stas/2012/12/tmtowtdi-plus-benchmarking.html#comments>.
+
+=head1 AUTHOR
+
+Toby Inkster E<lt>tobyink@cpan.orgE<gt>.
+
+Key parts of the top n selection algorithm (and much egging on) by Stanislaw
+Pusep (cpan:SYP).
+
+API inspired by L<Sort::Key::Top> by Salvador Fandiño García (cpan:SALVA).
+
+=head1 COPYRIGHT AND LICENCE
+
+This software is copyright (c) 2012 by Toby Inkster.
+
+This is free software; you can redistribute it and/or modify it under
+the same terms as the Perl 5 programming language system itself.
+
+=head1 DISCLAIMER OF WARRANTIES
+
+THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
+WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+

meta/changes.pret

+# This file acts as the project's changelog.
+
+`Sort-Key-Top-PP 0.001 cpan:TOBYINK`
+	issued  2012-12-11;
+	label   "Initial release".
+
+# This file contains general metadata about the project.
+
+@prefix : <http://usefulinc.com/ns/doap#>.
+
+`Sort-Key-Top-PP`
+	:programming-language "Perl" ;
+	:shortdesc            "pure Perl implementation of parts of Sort::Key::Top";
+	:homepage             <https://metacpan.org/release/Sort-Key-Top-PP>;
+	:download-page        <https://metacpan.org/release/Sort-Key-Top-PP>;
+	:bug-database         <http://rt.cpan.org/Dist/Display.html?Queue=Sort-Key-Top-PP>;
+	:repository           <https://bitbucket.org/tobyink/p5-sort-key-top-pp>;
+	:created              2012-12-11;
+	:license              <http://dev.perl.org/licenses/>;
+	:maintainer           cpan:TOBYINK;
+	:developer            cpan:TOBYINK.
+
+<http://dev.perl.org/licenses/>
+	dc:title  "the same terms as the perl 5 programming language system itself".
+

meta/makefile.pret

+# This file provides instructions for packaging.
+
+`Sort-Key-Top-PP`
+	perl_version_from m`Sort::Key::Top::PP`;
+	version_from      m`Sort::Key::Top::PP`;
+	readme_from       m`Sort::Key::Top::PP`;
+	test_requires     p`Test::More 0.61` ;
+	.
+
+# This file contains data about the project developers.
+
+@prefix : <http://xmlns.com/foaf/0.1/>.
+
+cpan:TOBYINK
+	:name  "Toby Inkster";
+	:mbox  <mailto:tobyink@cpan.org>.
+
+use Test::More tests => 1;
+BEGIN { use_ok('Sort::Key::Top::PP') };
+
+=head1 PURPOSE
+
+Just to check the module actually compiles.
+
+=head1 AUTHOR
+
+Toby Inkster E<lt>tobyink@cpan.orgE<gt>.
+
+=head1 COPYRIGHT AND LICENCE
+
+This software is copyright (c) 2012 by Toby Inkster.
+
+This is free software; you can redistribute it and/or modify it under
+the same terms as the Perl 5 programming language system itself.
+use strict;
+use warnings;
+use Test::More;
+
+use Sort::Key::Top::PP qw(nkeytop top rnkeytop topsort
+                      nkeytopsort rnkeytopsort
+                      nhead nkeyhead tail nkeytail
+                     );
+
+
+my @top;
+
+@top = nkeytop { abs $_ } 5 => 1, 2, 7, 5, 5, 1, 78, 0, -2, -8, 2;
+is_deeply(\@top, [1, 2, 1, 0, -2], "nkeytop 1");
+
+
+my @a = qw(cat fish bird leon penguin horse rat elephant squirrel dog);
+
+is_deeply([top 5 => @a], [qw(cat fish bird elephant dog)], "top 1");
+
+is_deeply([top 30 => @a], [@a], "top 1.1");
+
+is_deeply([rnkeytop { length $_ } 3 => qw(a ab aa aac b t uu g h)], [qw(ab aa aac)], "rnkeytop 1");
+
+is_deeply([top 5 => qw(a b ab t uu g h aa aac)], [qw(a b ab aa aac)], "top 2");
+
+is_deeply([topsort 5 => qw(a b ab t uu g h aa aac)], [qw(a aa aac ab b)], "topsort 1");
+
+is_deeply([rnkeytopsort { length $_ } 3 => qw(a ab aa aac b t uu g h)], [qw(aac ab aa)], "rnkeytopsort 1");
+
+is(scalar(top 5 => @a), q(dog), "scalar top 1");
+
+is(scalar(top 30 => @a), undef, "top 1.1");
+
+is(scalar(rnkeytop { length $_ } 3 => qw(a ab aa aac b t uu g h)), q(aac), "scalar rnkeytop 1");
+
+is(scalar(top 5 => qw(a b ab t uu g h aa aac)), q(aac), "scalar top 2");
+
+is(scalar(topsort 5 => qw(a b ab t uu g h aa aac)), q(b), "scalar topsort 1");
+
+is(scalar(rnkeytopsort { length $_ } 3 => qw(a ab aa aac b t uu g h)), q(aa), "scalar rnkeytopsort 1");
+
+#is_deeply([nkeypartref { $_ * $_ } 1 => (760, 617, -836)], [[617], [760, -836]], "nkeypartref");
+
+my @data = map { join ('', map { ('a'..'f')[rand 6] } 0..(3 + rand  6)) } 0..1000;
+
+if (0){my$n=0;
+#for my $n (0, 1, 2, 3, 4, 10, 16, 20, 50, 100, 200, 500, 900, 990,
+#           996, 997, 998, 999, 1000, 1001, 1002, 1003, 1010, 1020, 2000, 4000,
+#           100000, 2000000, -1, -2, -3, -4, -10, -16, -20, -50, -100, -200, -500,
+#           -900, -990, -996, -997, -998, -999, -1000, -1001, -1002, -1003, -1010,
+#           -1020, -2000, -4000, -100000, -2000000 ) {
+
+  my ($min, $max);
+
+
+
+  if ($n >= 0) {
+    $max = @data > $n ? $n - 1 : $#data;
+    $min = 0;
+  }
+  else {
+    if (@data > -$n) {
+      $min = @data + $n;
+      $max = $#data;
+    }
+    else {
+      $min = 0;
+      $max = $#data;
+    }
+  }
+
+
+  # on 5.6.x perls, sort is not stable, so we have to stabilize it ourselves:
+  my @ixs = sort { length($data[$a]) <=> length($data[$b]) or $a <=> $b } 0 .. $#data;
+  my @sorted = @data[@ixs];
+
+  my @rixs = sort { length($data[$b]) <=> length($data[$a]) or $a <=> $b } 0 .. $#data;
+  my @rsorted = @data[@rixs];
+
+
+  is_deeply([topsort $n => @data], [(sort @data)[$min..$max]], "topsort ($n)")
+      or diag ("data: @data, min: $min, max: $max");
+
+  is_deeply([nkeytopsort { length $_ } $n => @data],
+            [ (@sorted)[$min..$max]], "nkeytopsort ($n)");
+  is_deeply([rnkeytopsort { length $_ } $n => @data],
+            [ (@rsorted)[$min..$max]], "rnkeytopsort ($n)");
+#  is_deeply([ikeytopsort { length $_ } $n => @data],
+#            [ (@sorted)[$min..$max]], "ikeytopsort ($n)");
+#  is_deeply([rikeytopsort { length $_ } $n => @data],
+#            [ (@rsorted)[$min..$max]], "rikeytopsort ($n)");
+#  is_deeply([ukeytopsort { length $_ } $n => @data],
+#            [ (@sorted)[$min..$max]], "ukeytopsort ($n)");
+#  is_deeply([rukeytopsort { length $_ } $n => @data],
+#            [ (@rsorted)[$min..$max]], "rukeytopsort ($n)");
+
+  my $n1 = $n > 0 ? $n - 1 : $n < 0 ? $n : @data + 10;
+
+  my $vn = (!$n || abs($n) > @data) ? undef : $sorted[$n > 0 ? $n - 1 : $n];
+  my $rvn = (!$n || abs($n) > @data) ? undef : $rsorted[$n > 0 ? $n - 1 : $n];
+    
+
+  is(scalar(topsort $n => @data), (sort @data)[$n1], "scalar topsort ($n)");
+
+  is(scalar(nkeytopsort { length $_ } $n => @data),
+     $vn, "scalar nkeytopsort ($n)");
+
+  is(scalar(rnkeytopsort { length $_ } $n => @data),
+     $rvn, "scalar rnkeytopsort ($n)");
+
+#  is(scalar(ikeytopsort { length $_ } $n => @data),
+#     $vn, "scalar ikeytopsort ($n)");
+#
+#  is(scalar(rikeytopsort { length $_ } $n => @data),
+#     $rvn, "scalar rikeytopsort ($n)");
+#
+#  is(scalar(ukeytopsort { length $_ } $n => @data),
+#     $vn, "scalar ukeytopsort ($n)");
+#
+#  is(scalar(rukeytopsort { length $_ } $n => @data),
+#     $rvn, "scalar rukeytopsort ($n)");
+}
+
+is(nhead(6, 7, 3, 8, 9, 9), 3, "nhead");
+is((nkeyhead { length $_ } qw(a ab aa aac b t uu uiyii)), 'a', 'nkeyhead');
+is(tail(qw(a ab aa aac b t uu uiyii)), 'uu', 'tail');
+is((nkeytail { length $_ } qw(a ab aa aac b t uu uiyii)), 'uiyii', 'nkeytail');
+#is(atpos(3, qw(a ab aa aac b t uu uiyii)), 'ab', 'atpos');
+#is((rnkeyatpos { abs $_ } 2 => -0.3, 1.1, 4, 0.1, 0.9, -2), 1.1, 'rnkeyatpos');
+#is((rnkeyatpos { abs $_ } -2 => -0.3, 1.1, 4, 0.1, 0.9, -2), -0.3, 'rnkeyatpos neg');
+
+done_testing;
+
+=encoding utf-8
+
+=head1 PURPOSE
+
+Test L<Sort::Key::Top::PP> against test cases from L<Sort::Key::Top>.
+
+=head1 AUTHOR
+
+This is a slightly modified version of a test file by Salvador Fandiño García.
+
+=head1 COPYRIGHT AND LICENCE
+
+This software is copyright (c) 2006-2008, 2011 by Salvador Fandiño García.
+
+This is free software; you can redistribute it and/or modify it under
+the same terms as the Perl 5 programming language system itself.
+use Test::More;
+eval "use Test::Pod 1.00";
+plan skip_all => "Test::Pod 1.00 required for testing POD" if $@;
+all_pod_files_ok();
+

xt/02pod_coverage.t

+use XT::Util;
+use Test::More;
+use Test::Pod::Coverage;
+
+plan skip_all => __CONFIG__->{skip_all}
+	if __CONFIG__->{skip_all};
+
+if ( __CONFIG__->{modules} )
+{
+	my @modules = @{ __CONFIG__->{modules} };
+	pod_coverage_ok($_, "$_ is covered") for @modules;
+	done_testing(scalar @modules);
+}
+else
+{
+	all_pod_coverage_ok();
+}
+

xt/03meta_uptodate.config

+{"package":"Sort-Key-Top-PP"}
+

xt/03meta_uptodate.t

+use XT::Util;
+use Test::More tests => 1;
+use Test::RDF::DOAP::Version;
+doap_version_ok(__CONFIG__->{package}, __CONFIG__->{version_from});
+
+use Test::EOL;
+all_perl_files_ok();
+use Test::Tabs;
+all_perl_files_ok();
+use XT::Util;
+use Test::More;
+use Test::HasVersion;
+
+plan skip_all => __CONFIG__->{skip_all}
+	if __CONFIG__->{skip_all};
+
+if ( __CONFIG__->{modules} )
+{
+	my @modules = @{ __CONFIG__->{modules} };
+	pm_version_ok($_, "$_ is covered") for @modules;
+	done_testing(scalar @modules);
+}
+else
+{
+	all_pm_version_ok();
+}
+