The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.
 / 
Array-Ordered-0.01
River stage zero No dependents
/ Array::Ordered

NAME

Array::Ordered - Methods for handling ordered arrays

VERSION

Version 0.01

SYNOPSIS

    use Array::Ordered;
    
    # Export
    $array  = order [],       \&my_comparison;
    $array  = order \@array,  \&my_comparison;
    $array  = order $array,   \&other_comparison;
    
    # Utility
    $size   = $array->size;
    @items  = $array->clear;  # $array->size == 0
    
    # Strictly Ordered:
    $elem   = $array->find            $match;
              $array->insert          $item;
    $elem   = $array->find_or_insert  $match;
    $item   = $array->remove          $match;
    $pos    = $array->position        $match;
    unless(   $array->is_reduced  ) {
              $array->reduce;
    }
    
    # Unstrictly Ordered:
    $elem   = $array->first           $match;
    $elem   = $array->last            $match;
              $array->unshift         @items;
              $array->push            @items;
    $item   = $array->shift           $match;
    $item   = $array->pop             $match;
    $pos    = $array->first_position  $match;
    $pos    = $array->last_position   $match;
    $count  = $array->occurrences     $match;
    unless(   $array->is_sorted  ) {
              $array->sort;
    }
    
    # Multi-element:
    @elems  = $array->find_all        $match;
    @elems  = $array->heads;
    @elems  = $array->tails;
    @items  = $array->remove_all      $match;
    @items  = $array->shift_heads;
    @items  = $array->pop_tails;

DESCRIPTION

The purpose of the Array::Ordered module is to provide functionality to Perl with methods for accessing and modifying arrays while keeping them sorted.

At the heart of this module are two symmetrical binary search algorithms:

  1. The first returns the index of the first element equal to or greater than a matching argument. (possibly the array's size)

  2. The second returns the index of the last element equal to or less than a matching argument. (possibly -1)

Elements are inserted and deleted from the ordered array using 'splice'. Because of allocation overhead, this module's methods are intended for relatively small arrays. See "TODO".

TERMINOLOGY

Comparison Subroutine

A comparison subroutine takes two arguments - each a scalar or a reference - and returns a numeric scalar:

  • Negative if the first argument should preceed the second (less than)

  • Zero if they are equivalent (equal to)

  • Positive if the first argument should follow the second (greater than)

Equivalency Sequence

Consider an array A = <X0, X1, X2, Y0, Z0, Z1> sorted by the rule C such that:

  • C (X*, X*) = 0, C (X*, Y*) < 0, C (X*, Z*) < 0,
  • C (Y*, X*) > 0, C (Y*, Y*) = 0, C (Y*, Z*) < 0,
  • C (Z*, X*) > 0, C (Z*, Y*) > 0, C (Z*, Z*) = 0

The array A has three equivalency sequences: AX = <X0, X1, X2>, AY = <Y0>, and AZ = <Z0, Z1>.

The length of every equivalency sequence in a strictly ordered array is 1. Only an unstrictly ordered array can have equivalency sequences of length greater than 1.

METHODS

For the purposes of clarity, I have used the following convention for naming variables:

  • A variable is named $item or @items if it refers to data introduced into or removed from the ordered array.

  • A variable is named $elem or @elems if it refers to data accessed and remaining in the ordered array.

  • An argument is named $match when it is used to fish out one or more equivalent elements from the array.

Export

order

This method takes two arguments:

  1. An array reference, and

  2. A reference to a comparison subroutine.

The array reference is returned after being tied to the code reference for ordering, the array's contents are sorted, and the reference is blessed.

The method order is exported implicitly. The decision for this is simply because none of the module's other methods are of any use without it. Consider it this module's "new" method.

    sub lencmp { length $_[0] <=> length $_[1] }
    
    $array = order [], \&lencmp;            # Empty array orded by 'lencmp'
    
    order $array, sub { $_[0] cmp $_[1] };  # Now ordered by 'cmp'
    
    $array = order [];                      # Okay: Default comparison is sub { 0 }
    
    @items = { '3', '001', '02' };

    $array = order [@items], \&lencmp;      # Copy of @items ordered by '&lencmp':
                                            # @items is unchanged
    $array = order \@items,  \&lencmp;      # $array == \@items:
                                            # @items is sorted

Utility

size

Returns number of elements in referenced array.

    $size = $array->size;
    # Same as:
    $size = scalar @{$array};

clear

Removes and returns all elements from the ordered array.

    @array_contained = $array->clear;
    # Same as:
    @array_contained = splice( @{$array}, 0, $array->size );

Strictly Ordered

find

Alias for first.

insert

Alias for push.

find_or_insert

Returns first equivalent item if found, or inserts and returns a new item.

If no equivalent item is found, then:

  • If a code reference is passed, its return value is inserted; otherwise,
  • If a default value is passed, its value is inserted; otherwise,
  • The method inserts the value of $match.
    $object = $array->find_or_insert( $match, \&constructor );
    $elem   = $array->find_or_insert( $match, $default );
    $elem   = $array->find_or_insert( $match );
    
    # Examples:
    $object = $array->find_or_insert( 'Delta', sub { My::NamedObject->new( 'Delta' ) } );
    $elem   = $array->find_or_insert( 'DELTA', 'Delta' );
    $elem   = $array->find_or_insert( 'Delta' );

Use find_or_insert whenever possible! This is the only insertion method which verifies that the array is strictly ordered.

remove

Alias for shift.

position

Alias for first_position.

is_reduced

Returns 1 if the array is strictly ordered, otherwise ''.

    $strictly = $array->is_reduced;

reduce

Reduces the array into a strictly ordered array.

Only the last element of each equivalency sequence remains unless a TRUE argument is passed, in which case only the first of each remains.

    $array->reduce;
    # Same as:
    $array->reduce( 0 );
    
    # Or use:
    
    my $preserve_first = 1;
    $array->reduce( $preserve_first );

Unstrictly Ordered

first

Returns first equivalent item or undef if not found.

Optionally returns the position of the item or undef if not found. (via wantarray)

    $elem         = $array->first( $match );
    ($elem, $pos) = $array->first( $match );

last

Returns last equivalent item or undef if not found.

Optionally returns the position of the item or undef if not found. (via wantarray)

    $elem         = $array->last( $match );
    ($elem, $pos) = $array->last( $match );

unshift

Adds item(s), prepending them to their equivalent peers.

    $array->unshift( $item );
    $array->unshift( @items );

push

Adds item(s), appending them to their equivalent peers.

    $array->push( $item );
    $array->push( @items );

shift

Removes and returns first equivalent item or undef if not found.

    $item = $array->shift( $match );

pop

Removes and returns last equivalent item or undef if not found.

    $item = $array->pop( $match );

first_position

Returns position of first equivalent item or undef if not found.

    $pos = $array->first_position( $match );
    # Same as:
    $pos = ($array->first( $match ))[1];

last_position

Returns position of last equivalent item or undef if not found.

    $pos = $array->last_position( $match );
    # Same as:
    $pos = ($array->last( $match ))[1];

occurrences

Returns number of elements equivalent to $match.

    $count = $array->occurrences( $match );

is_sorted

Returns 1 if the array is ordered, otherwise ''.

There is no need to call this method as long as the referenced array is modified only via the methods in this module.

    $ordered = $array->is_sorted;

sort

Sorts the referenced array using its associated comparison subroutine.

There is no need to call this method as long as the referenced array is modified only via the methods in this module.

    $array->sort;

Multi-element

find_all

Returns array of all items equivalent to $match.

    @elems = $array->find_all( $match );

heads

Returns a strictly ordered array containing the first of each equivalency sequence.

    @elems = $array->heads;

tails

Returns a strictly ordered array containing the last of each equivalency sequence.

    @elems = $array->tails;

remove_all

Removes all items equivalent to $match and returns them as an array.

    @items = $array->remove_all( $match );

shift_heads

Removes the first of each equivalency sequence and returns them as a strictly ordered array.

    @items = $array->shift_heads;

pop_tails

Removes the last of each equivalency sequence and returns them as a strictly ordered array.

    @items = $array->pop_tails;

ACKNOWLEDGMENTS

This module's framework generated with module-starter.

AUTHOR

S. Randall Sawyer, <srandallsawyer at cpan.org>

BUGS

Please report any bugs or feature requests to bug-array-ordered at rt.cpan.org, or through the web interface at http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Array-Ordered. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.

SUPPORT

You can find documentation for this module with the perldoc command.

    perldoc Array::Ordered

TODO

Write a module for handling large sorted arrays. Probably use a balanced binary tree as a back-end for that.

SEE ALSO

List::Util, Scalar::Util

LICENSE AND COPYRIGHT

Copyright 2013 S. Randall Sawyer. All rights reserved.

This program is free software; you can redistribute it and/or modify it under the terms of the the Artistic License (2.0). You may obtain a copy of the full license at:

http://www.perlfoundation.org/artistic_license_2_0