When talking about Array as a data structure in general (not in PHP), we know that arrays:

  • can contain any type of data
  • have a fixed size (they can’t grow)
  • have random access, meaning we use indexes to access any element at constant time O(1), which is really fast

Typical operations which can be done on arrays in general are:

  • get(index) – get value at specified index, which is O(1) constant time operation (because of random access feature)
  • set(index, value) – set specified value at specified index, overwriting existing value if present, which is again O(1) operation
  • insert(index, value) – insert specified value at specified index while preserving other values if present. Existing values are moved up in array, which is O(n) linear operation
  • delete(index) – delete item at specified index while preserving other values if present. Existing values are moved down in array, which is also O(n) operation

Arrays in PHP are actually an ordered map. It can be treated as an array or a dictionary and even other data types (more on this in PHP manual: [http://php.net/manual/en/language.types.array.php]http://php.net/manual/en/language.types.array.php). They are really flexible, they don’t have fixed length, but all that comes with a price of overhead (they use more memory than traditional arrays).

To cope with additional overhead, we could use SplFixedArray which is of fixed length and allows faster array implementation.

For the testing purposes I have implemented a FixedArray abstraction class which is based on SplFixedArray. In this FixedArray I only allow typical operations mentioned earlier.

You can find it in GitHub repo: [https://github.com/cicnavi/alg-ds-php/blob/master/src/Ds/Arrays/FixedArray.php]https://github.com/cicnavi/alg-ds-php/blob/master/src/Ds/Arrays/FixedArray.php

Let’s see how it could work. I have cloned the whole repo in ‘alg-ds-php’ folder on my computer, and used a shell to navigate to it. This is a Composer enabled repository, so I first enter the command ‘composer install’ to install any dependencies. This will enable me to use the ‘psys’ REPL for PHP, which is great for testing purposes. It is located in ‘vendor\bin\psysh’

Fixed Array

To recap, we have:

  • created a new FixedArray instance which with capacity of 10 items (new FixedArray(10))
  • checked its capacity using the getCapacity() method.
  • used the insert() method to add value ‘First item’ to index 0
  • checked the size using getSize() method
  • used the get() method to get an item at specified index

If you look at the source code, you’ll also find methods to add, delete, set items and to check if value exists. You can see how to use all those methods in the FixedArrayTest class which is available here: [https://github.com/cicnavi/alg-ds-php/blob/master/tests/Ds/Arrays/FixedArrayTest.php]https://github.com/cicnavi/alg-ds-php/blob/master/tests/Ds/Arrays/FixedArrayTest.php

You can also run all the specified tests by using PHPUnit command:

./vendor/bin/phpunit --bootstrap vendor/autoload.php --testdox tests/Ds/Arrays/FixedArrayTest.php

phpunit

Note that the original SplFixedArray class has a setSize() method (http://php.net/manual/en/splfixedarray.setsize.php) which allows to change the size of an array. I have purposely omitted such option to keep the array fixed in capacity. In one of the next articles I will show you how to create a dynamic array which will be able to change in capacity depending on the required size.