Traversing array from the middle in PHP

Created:30 Aug 2017 15:51:20 , in  Maths

Traversing an array starting from the middle item in it is in many ways similar to traversing it from the beginning or the end. One small catch is such that, the middle item, or to be more accurate, the middle index of the array, has to be found before the rest of job can be gotten on with. Once that's done, it is just a matter of deciding which items in the array should be traversed next.

This article explores three middle-item-first array traversal schemes. With regards to how array items are visited and what steps are involved in each of them, these schemes can be described as follows:

• Middle, before, after - middle item, items before it, items after it:

• a) visit middle item,

• b) visit items before the middle item,

• c) visit items after the middle item.

• Middle, after, before - middle item, items after it, items before it:

  • a) visit the middle item,

  • b) visit items after the middle item,

  • c) visit items before the middle item.

• Middle, alternate - middle item, then next and previous items alternately:

  • a) visit the middle item,

  • b) visit an item after the middle item,

  • c) visit an item before the middle item,

  • d) repeat steps b and c until both fringe items have been reached.

Finding array middle item and index

Before proceeding to the main part of this article, I'm going to spend a while on describing a method of finding an array middle item. It involves two cases, one for even and one for odd number of items in the array:

#For arrays with even number of items:
$middle_index = count($arr) / 2;
$middle_item = $arr[$middle_index]; 

#For arrays with odd number of items:
$middle_index = (int)floor(count($arr) / 2); 
$middle_item = $arr[$middle_index];

In the above, $arr refers to a PHP array under consideration.

Traversing arrays using SwwwArrayTraversal class

For traversing arrays according to one of above-mentioned schemes I wrote SwwwArrayTraversal PHP class. At the high level it consists of three static class methods.

These methods, called outwardsBeforeAfter,outwardsAfterBefore and outwardsAlternate respectively, accept an array of values, and return a new array with items arranged according to the order they were traversed in. If they are given a second argument, a function, they'll apply it to each item in the original array.

All three methods in SwwwArrayTraversal use indices to carry out their job, hence they have no knowledge of what sort of items there are there in the original array. So, lists of numbers, strings, arrays, functions, objects or in fact arrays of anything can be traversed effectively with these methods.

If the second argument, a function, is provided it receives the current item in the array as its first argument and an index under which the item sits in the original array as the second one.

The SwwwArrayTraversal uses no loops. Recursion is used throughout it.

Finally, in order to make understanding of the code somewhat easier, I have left majority of comments intact.

/*
  Class: SwwwArrayTraversal 
  Description: Traverse array starting from the middle item in it
  Author: Sylwester Wojnowski
  WWW: wojnowski.net.pl

  Methods:
    outwardsBeforeAfter($a,$func = null) - traversal in order middle item, items before it, items after it
      parameters: 
        $a - array - array to traverse
        [$func] - function - callback function
      return array
    outwardsAfterBefore($a,$func = null) - traversal in order middle item, items after it, items before it
      parameters: 
        $a - array - array to traverse
        [$func] - function - callback function
      return array
    outwardsAlternate($a,$func = null) - traversal in order middle item, alternate items after and before it
      parameters: 
        $a - array - array to traverse
        [$func] - function - callback function
      return array  
*/

class SwwwArrayTraversal{

  public static function outwardsBeforeAfter($a,$func = null){
    return self::__outwardsBeforeAfter($a,$func);
  }
  
  public static function outwardsAfterBefore($a,$func = null){
    return self::__outwardsAfterBefore($a,$func);
  }

  public static function outwardsAlternate($a,$func = null){
    return self::__outwardsAlternate($a,$func);
  }

  private static function __outwardsBeforeAfter($a,$func = null,$c = null,$items = array(),$n = null,$m = null){
     // set n to 0 unless n is provided
     $n = $n === null ? 0 : $n;
     // find number of items in $a
     $c = $c === null ? count($a) : $c;
     // find middle index of $a
     $m = $m === null ? (($c % 2 === 0) ? $c / 2 : (int)floor(count($a) / 2)) : $m;
     // auxiliary variable
     $i = null;   
     // return once the end of $a has been reached
     if($n === $c){ return $items; }

     // cover indices laying before the middle index
     if( $n <= $m ){
       $i = $m - $n;
       $items[] = $func === null ? self::__map($a[$i]) : $func($a[$i],$i); 
     // cover indices laying after the middle index
     }else{
       $items[] = $func === null ? self::__map($a[$n]) : $func($a[$n],$n);
     }

     // move on to the next item in $a
     return self::__outwardsBeforeAfter($a,$func,$c,$items,$n + 1,$m);
  }

  public static function __outwardsAfterBefore($a,$func,$c = null,$items = array(),$n = null,$m = null){
     // set n to 0 unless n is provided
     $n = $n === null ? 0 : $n;
     // find number of items in $a
     $c = $c === null ? count($a) : $c;
     // find middle index of $a
     $m = $m === null ? (($c % 2 === 0) ? $c / 2 : (int)floor($c / 2)) : $m;
     // auxiliary variable
     $i = null;     
     // return once the end of $a has been reached
     if($n === $c){ return $items; }

     // cover items in positions before the middle item
     if( $n + $m < $c ){
       $i = $n + $m;
       $items[] = $func === null ? self::__map($a[$i]) : $func($a[$i],$i);
     // cover items in positions after the middle item
     }else{
       $i = $c - $n - 1;
       $items[] = $func === null ? self::__map($a[$i]) : $func($a[$i],$i); 
     }
     // move on to the next item in $a
     return self::__outwardsAfterBefore($a,$func,$c,$items,$n + 1,$m);
  }

  public static function __outwardsAlternate($a,$func = null,$c = null,$items = array(),$n = null,$m = null){
     // set n to 0 unless n is provided
     $n = $n === null ? 0 : $n;
     // find number of items in $a
     $c = $c === null ? count($a) : $c;
     // find middle index of $a
     $m = $m === null ? (($c % 2 === 0) ? $c / 2 : (int)floor($c / 2)) : $m;
     // set k on the basis of n being odd or even
     $k = ($n % 2 === 0) ? $n / 2 : (int)floor(($n / 2));
     // auxiliary variable
     $i = null;     
     // return once the end of $a has been reached
     if($n === $c){ return $items; }

     // cover even indices
     if($n % 2 === 0){
       $i = $m + $k;
       $items[] = $func === null ? self::__map($a[$i]) : $func($a[$i],$i);
     // cover odd indices
     }else{
       $i = $m - $k - 1;
       $items[] = $func === null ? self::__map($a[$i]) : $func($a[$i],$i);
     }
     // move on to the next item in the $a
     return self::__outwardsAlternate($a,$func,$c,$items,$n + 1,$m,$func);
  }

  // default mapping function
  private static function __map($v){
    $func = function($v){ return $v; };
    return $func($v);
  }
}

Examples of use

Here are some use examples.

Traversing an array in order: middle item, items before middle item, items after middle item:

$a = array('a','b','c','d','e','f')
SwwwArrayTraversal::outwardsBeforeAfter($a);
=> array('d','c','b','a','e','f')

Traversing an array in order: middle item, items after middle item, items before middle items:

$a = array('a','b','c','d','e');
SwwwArrayTraversal::outwardsAfterBefore($a);
=> array('c','d','e','b','a')

Traversing an array in order: middle item, alternate items:

$a = array('a','b','c','d','e','f');
SwwwArrayTraversal::outwardsAlternate($a);
=> array('d','c','e','b','f','a')

Applying callback function to items in original array:

$a = array(1,2,3,4,5);
SwwwArrayTraversal::outwardsAlternate($a,function($v,$i){ return pow($v,$i); })
=> array(9,2,64,1,625)

I hope, these examples both provide enough insight on how SwwwArrayTraversal works and shed light what it can be used for.

Final thoughts

Middle-item array traversals, perhaps due to larger number of variables involved compared to the count of them in popular first-item first or last-item first ones, are somewhat more demanding to code right. The complexity, given a careful approach is adopted, can be managed successfully, though. Moreover, these problems, apart from yielding useful code, are a great exercise and help in better understanding array data structure.

As always, I hope you've enjoyed the article and found its contents both instructive and useful.

This post was updated on 30 Aug 2017 16:01:02

Tags:  data structure ,  php ,  recursion