# NAME

Array::Ordered - Methods for handling ordered arrays

# VERSION

Version 0.03

# 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 the means to access and modify arrays while keeping them sorted.

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

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

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'.

## 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** = <X_{0}, X_{1}, X_{2}, Y_{0}, Z_{0}, Z_{1}> 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*: **A**_{X} = <X_{0}, X_{1}, X_{2}>, **A**_{Y} = <Y_{0}>, and **A**_{Z} = <Z_{0}, Z_{1}>.

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

# METHODS

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:

An array reference, and

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 due to the fact that 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 }
my @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, `<srandalls 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 an XS version so that 'order' works syntactically like 'tie'. Write a module for handling large sorted arrays using a balanced binary tree as a back-end.

# SEE ALSO

# 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: