| 1 | # | ||||||||||
| 2 | # Copyright (c) 2021 Christian Jaeger, copying@christianjaeger.ch | ||||||||||
| 3 | # | ||||||||||
| 4 | # This is free software, offered under either the same terms as perl 5 | ||||||||||
| 5 | # or the terms of the Artistic License version 2 or the terms of the | ||||||||||
| 6 | # MIT License (Expat version). See the file COPYING.md that came | ||||||||||
| 7 | # bundled with this file. | ||||||||||
| 8 | # | ||||||||||
| 9 | |||||||||||
| 10 | =head1 NAME | ||||||||||
| 11 | |||||||||||
| 12 | FP::SortedPureArray | ||||||||||
| 13 | |||||||||||
| 14 | =head1 SYNOPSIS | ||||||||||
| 15 | |||||||||||
| 16 | use FP::PureArray; | ||||||||||
| 17 | use FP::SortedPureArray; | ||||||||||
| 18 | use FP::Equal qw(is_equal); | ||||||||||
| 19 | use FP::Ops qw(real_cmp); | ||||||||||
| 20 | |||||||||||
| 21 | my $a1 = purearray(10, 40, 50, 50, 60); | ||||||||||
| 22 | |||||||||||
| 23 | # This re-blesses $a1, too ($a1 and $s1 are the same object), so | ||||||||||
| 24 | # it's not a functional operation, but then it shouldn't be | ||||||||||
| 25 | # damaging either, or so one hopes...: | ||||||||||
| 26 | my $s1 = $a1->as_sorted_by(\&real_cmp); | ||||||||||
| 27 | |||||||||||
| 28 | is_equal [ $s1->perhaps_binsearch(40) ], [40]; | ||||||||||
| 29 | is_equal [ $s1->perhaps_binsearch(41) ], []; | ||||||||||
| 30 | ok $s1->checks_ok; | ||||||||||
| 31 | |||||||||||
| 32 | *real_sortedpurearray = sortedpurearray_by(\&real_cmp); | ||||||||||
| 33 | my $vs = real_sortedpurearray(10, 40, 50, 50, 60); | ||||||||||
| 34 | |||||||||||
| 35 | is_equal [ $vs->perhaps_binsearch(40) ], [40]; | ||||||||||
| 36 | is_equal [ $vs->perhaps_binsearch(41) ], []; | ||||||||||
| 37 | ok $vs->checks_ok; | ||||||||||
| 38 | |||||||||||
| 39 | # For performance reasons, the constructor does *not* sort the | ||||||||||
| 40 | # values or check whether the values are actually sorted. | ||||||||||
| 41 | my $bad = real_sortedpurearray(10, 50, 40, 60); | ||||||||||
| 42 | |||||||||||
| 43 | # But that check can be run explicitly: | ||||||||||
| 44 | ok not $bad->checks_ok; | ||||||||||
| 45 | |||||||||||
| 46 | ok real_sortedpurearray(10, 50, 50, 60)->checks_ok; | ||||||||||
| 47 | |||||||||||
| 48 | is sortedpurearray_by(\&real_cmp)->(10,10)->checks_ok, 1; | ||||||||||
| 49 | is sortedpurearray_by(\&real_cmp)->(20,10)->checks_ok, ''; | ||||||||||
| 50 | is sortedpurearray_by(\&real_cmp)->(3,10)->checks_ok, 1; | ||||||||||
| 51 | |||||||||||
| 52 | =head1 DESCRIPTION | ||||||||||
| 53 | |||||||||||
| 54 | A sorted L<FP::PureArray>. Has all the methods of the latter, plus | ||||||||||
| 55 | currently just `perhaps_binsearch`. | ||||||||||
| 56 | |||||||||||
| 57 | So, this is very much unfinished and deserves more methods and | ||||||||||
| 58 | constructors, as well as possibly a protocol (FP::Abstract::*). | ||||||||||
| 59 | |||||||||||
| 60 | =head1 SEE ALSO | ||||||||||
| 61 | |||||||||||
| 62 | L<FP::PureArray>, that this inherits from. | ||||||||||
| 63 | |||||||||||
| 64 | =head1 NOTE | ||||||||||
| 65 | |||||||||||
| 66 | This is alpha software! Read the status section in the package README | ||||||||||
| 67 | or on the L<website|http://functional-perl.org/>. | ||||||||||
| 68 | |||||||||||
| 69 | =cut | ||||||||||
| 70 | |||||||||||
| 71 | package FP::SortedPureArray; | ||||||||||
| 72 | 1 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 73 | 1 | ▶ | use utf8; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 74 | 1 | ▶ | use warnings; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 75 | 1 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 76 | 1 | ▶ | use experimental 'signatures'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 77 | 1 | ▶ | use Exporter "import"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 78 | |||||||||||
| 79 | our @EXPORT = qw(sortedpurearray_by); | ||||||||||
| 80 | our @EXPORT_OK = qw(); | ||||||||||
| 81 | our %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]); | ||||||||||
| 82 | |||||||||||
| 83 | 1 | ▶ | use FP::PureArray; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 84 | 1 | ▶ | use FP::Carp; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 85 | |||||||||||
| 86 | 0 | ▶ | sub sortedpurearray_by { | ||||||||
|
Subroutine
sortedpurearray_by: not called CC=2 SCAR=17.9
| |||||||||||
| 87 | 0 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 88 | 0 | my ($cmp) = @_; | |||||||||
| 89 | 0 | ▶ | sub { | ||||||||
|
Subroutine
__ANON__: not called CC=1 SCAR=6.9
| |||||||||||
| 90 | 0 | purearray(@_)->as_sorted_by($cmp) | |||||||||
| 91 | } | ||||||||||
| 92 | 0 | } | |||||||||
| 93 | |||||||||||
| 94 | package FP::_::SortedPureArray { | ||||||||||
| 95 | our @ISA = qw(FP::_::PureArray); | ||||||||||
| 96 | |||||||||||
| 97 | 0 | ▶ | use List::BinarySearch qw(binsearch); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=2.6
| |||||||||||
| 98 | use FP::Carp; | ||||||||||
| 99 | use FP::Array qw(array_map); | ||||||||||
| 100 | use FP::Docstring; | ||||||||||
| 101 | |||||||||||
| 102 | # Implement the additional field via external hashtable, so that | ||||||||||
| 103 | # array accesses and super class methods all work without | ||||||||||
| 104 | # indirection. I expect this to be the right trade off. | ||||||||||
| 105 | |||||||||||
| 106 | my %sorted_by_cmp; # pointer => subroutine | ||||||||||
| 107 | |||||||||||
| 108 | sub new_from_purearray { | ||||||||||
| 109 | @_ == 3 or fp_croak_arity 3; | ||||||||||
| 110 | my ($class, $a, $sorted_by_cmp) = @_; | ||||||||||
| 111 | |||||||||||
| 112 | # Not so read-only after all... evil? | ||||||||||
| 113 | Internals::SvREADONLY @$a, 0; | ||||||||||
| 114 | bless $a, $class; | ||||||||||
| 115 | Internals::SvREADONLY @$a, 1; | ||||||||||
| 116 | $sorted_by_cmp{ $a +0 } = $sorted_by_cmp; | ||||||||||
| 117 | $a | ||||||||||
| 118 | } | ||||||||||
| 119 | |||||||||||
| 120 | sub checks_ok { | ||||||||||
| 121 | @_ == 1 or fp_croak_arity 1; | ||||||||||
| 122 | __ 'Verifies if the array *is* sorted as it is claimed to be, | ||||||||||
| 123 | returns true iff it is.'; | ||||||||||
| 124 | my ($self) = @_; | ||||||||||
| 125 | my $len = @$self; | ||||||||||
| 126 | return 1 if $len == 0; | ||||||||||
| 127 | my $cmp = $sorted_by_cmp{ $self +0 }; | ||||||||||
| 128 | my $v = $self->[0]; | ||||||||||
| 129 | |||||||||||
| 130 | for (1 .. $len - 1) { | ||||||||||
| 131 | my $v2 = $self->[$_]; | ||||||||||
| 132 | my $c = $cmp->($v, $v2); | ||||||||||
| 133 | return '' unless $c <= 0; | ||||||||||
| 134 | $v = $v2; | ||||||||||
| 135 | } | ||||||||||
| 136 | 1 | ||||||||||
| 137 | } | ||||||||||
| 138 | |||||||||||
| 139 | sub DESTROY { | ||||||||||
| 140 | my $self = shift; | ||||||||||
| 141 | delete $sorted_by_cmp{ $self +0 }; | ||||||||||
| 142 | } | ||||||||||
| 143 | |||||||||||
| 144 | sub FP_Show_show { | ||||||||||
| 145 | my ($self, $show) = @_; | ||||||||||
| 146 | "sortedpurearray_by(" | ||||||||||
| 147 | . $show->($sorted_by_cmp{ $self +0 }) . ")->(" | ||||||||||
| 148 | . join(", ", @{ array_map($show, $self) }) . ")" | ||||||||||
| 149 | } | ||||||||||
| 150 | |||||||||||
| 151 | sub perhaps_binsearch { | ||||||||||
| 152 | @_ == 2 or fp_croak_arity 2; | ||||||||||
| 153 | __ '$self->perhaps_binsearch($element): searches using the | ||||||||||
| 154 | comparator stored with $self'; | ||||||||||
| 155 | my ($self, $element) = @_; | ||||||||||
| 156 | |||||||||||
| 157 | if ( | ||||||||||
| 158 | defined( | ||||||||||
| 159 | my $index | ||||||||||
| 160 | = binsearch { $sorted_by_cmp{ $self +0 }->($a, $b) } | ||||||||||
| 161 | $element, @$self | ||||||||||
| 162 | ) | ||||||||||
| 163 | ) | ||||||||||
| 164 | { | ||||||||||
| 165 | $self->[$index] | ||||||||||
| 166 | } else { | ||||||||||
| 167 | () | ||||||||||
| 168 | } | ||||||||||
| 169 | } | ||||||||||
| 170 | } | ||||||||||
| 171 | |||||||||||
| 172 | 1 | ||||||||||