<?
/**
* @author Cory Marsh
* @license http://www.opensource.org/licenses/bsd-license.php BSD License
*/
interface iCompare
{
/**
* compare two objects of some type,
* @param mixed $element1
* @param mixed $element2
* @return integer <0 if $element1 is < $element2
* 0 if $element1 == $element2
* >0 if $element1 is > $element2
*/
public function compare($element1, $element2);
}
interface iList
{
/**
* Inserts the specified element at the end of the list (optional operation).
*
* @param Object $element the element to add to the list
* @return void
*/
public function add($element);
/**
* Inserts the specified element at the specified position in this list (optional operation).
*
* @param Integer $index the position in the list to add the element to
* @param Object $element the element to add to the list
* @retrun void
*/
public function addAt($index, $element);
/**
* Adds a List to this List
*
* @param Integer $index the position in this list to add to (0) maps to the beginning
* (-1) should map to the end of the list
* @param List $element the list to add to this list
* @retrun void
*/
public function addAll($index, iList $element);
/**
* Clear this list
*/
public function clear();
/**
* Test if this list contains an element
* @return true if this list contains this element
*/
public function contains($element);
/**
* Test if this list contains a subset of elements
* @param List $elements all of the elements to test
* @return true if this list contains all elements in $elements
*/
public function containsAll(iList $elements);
/**
* Returns the element at the specified position in this list.
* @param Indeter $index the position in the list
* @return Object the object at the specified position in the list
*/
public function get($index);
/**
* Removes an element at the specified position in the list.
* @param Indeter $index the position in the list
* @return Bool true if the element was removed, else false
*/
public function remove($index);
/**
* Returns the number of elements in this list.
* @return Integer the number of elements in the list.
*/
public function size();
/**
* Replaces the element at the specified position in this list with the specified element
* @param Integer $index the index to replace an element at
* @param Object $element the element to replace the index with
* @return Object the element previously at index $index, or false on error
*/
public function set($index, $element);
/**
* set the type of Object this List accepts
* @param String the type to set this list to (as returned by gettype();
*/
public function setType($type);
/**
* get the type of Object this List accepts
* @return String the type to set this list to (as returned by gettype();
*/
public function getType();
/**
* set the primative PHP data array. No data type checking
*/
public function setArray(array $data);
/**
* get the primative PHP data array. This returns the List as a PHP array
*/
public function getArray();
public function getIterator();
}
/**
* <code>
* $list = new ArrayList ('MyType');
* $list->add($myType);
* </code>
* @property array $data the actual storage
* @property string $type the data type accepted for the list (get_type or instanceOf)
*/
class ArrayList implements iList
{
// the internal storage
protected $data;
protected $type;
/**
* Create a new ArrayList.
* @param String $type the type of data this list accepts, or null if it
* should accept any Object.
* @param array $content the list contents
* @return ArrayList a new ArrayList
*/
public function __construct($type = null, array $content = null)
{
$this->type = null;
$this->data = array();
if($type != null)
$this->setType($type);
if ($content != null)
$this->data = $content;
}
/**
* sort the list contents acording to a comparator.
* @param iCompare $comparator the class to do the comparasons
*/
public function sort(iCompare $comparator)
{
$this->data = $this->quickSortRecursive($this->data, $comparator, 0, $this->size()-1);
return $this;
}
// Recursive version:
private function quickSortRecursive($arr, iCompare $comparator, $left, $right)
{
// when the call is recursive we need to change
//the array passed to the function yearlier
static $array = array();
if( $arr != NULL )
$array = $arr;
$i = $left;
$j = $right;
$tmp = $array[(int)( ($left+$right)/2 )];
// partion the array in two parts.
// left from $tmp are with smaller values,
// right from $tmp are with bigger ones
do
{
while ($comparator->compare($array[$i], $tmp) < 0)
$i++;
while ($comparator->compare($tmp, $array[$j]) < 0)
$j--;
// swap elements from the two sides
if( $i <= $j )
{
$w = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $w;
$i++;
$j--;
}
}
while( $i <= $j );
// devide left side if it is longer the 1 element
if( $left < $j )
$this->quickSortRecursive(NULL, $comparator, $left, $j);
// the same with the right side
if( $i < $right )
$this->quickSortRecursive(NULL, $comparator, $i, $right);
// when all partitions have one element
// the array is sorted
return $array;
}
/**
* Inserts the specified element at the end of the list (optional operation).
*
* @param Object $element the element to add to the list
* @return List a refernece to self
*/
public function add($element)
{
if($this->type != null && gettype($element) != $this->type && !($element instanceof $this->type))
throw new Exception('cannot add a ' . gettype($element) . " element to ArrayList of type {$this->type}");
$this->data[] = $element;
return $this;
}
/**
* Inserts the specified element at the specified position in this list (optional operation).
*
* @param Integer $index the position in the list to add the element to
* @param Object $element the element to add to the list
* @return List a refernece to self
*/
public function addAt($index, $element)
{
if($this->type != null && gettype($element) != $this->type && !($element instanceof $this->type))
throw new Exception('cannot add a ' . gettype($element) . " element to ArrayList of type {$this->type}");
if($index > count($this->data))
throw new Exception('cannot add an index past the end of ArrayList');
$this->data[$index] = $element;
return $this;
}
/**
* Inserts the a collection at the specified position in this list (optional operation).
*
* @param Integer $index the position in the list to add the elements to
* @param iList $collection the elements to add to the list, (must be the same type)
* @return List a refernece to self
*/
public function addAll($index, iList $collection)
{
$type = $collection->getType();
if($this->type != null && $this->type != $type)
throw new Exception("cannot add a $type element to ArrayList of type {$this->type}");
$this->data = array_merge($this->data, $collection->getArray());
return $this;
}
/**
* Clear this list
* @return List a refernece to self
*/
public function clear()
{
$this->data = array();
return $this;
}
/**
* Test if this list contains an element. Assumes unsorted list, Big O = n
* @return true if this list contains this element
*/
public function contains($element)
{
foreach($this->data as $key)
{
if($key == $element)
return true;
}
return false;
}
/**
* Test if this list contains a subset of elements
* @param List $elements all of the elements to test
* @return true if this list contains all elements in $elements
*/
public function containsAll(iList $elements)
{
$elements = $elements;
throw new Exception('ArrayList containsAll not yet implemented');
}
/**
* Returns the element at the specified position in this list.
* @param Indeter $index the position in the list
* @return Object the object at the specified position in the list
*/
public function get($index)
{
if($index > count($this->data))
throw new Exception('cannot get an index past the end of ArrayList');
return($this->data[$index]);
}
/**
* Removes an element at the specified position in the list.
* @param Indeter $index the position in the list
* @return Bool true if the element was removed, else false
*/
public function remove($index)
{
if($index > count($this->data) || $index < 0)
throw new Exception('cannot remove an index past the end of ArrayList');
unset($this->data[$index]);
return true;
}
/**
* Removes an element by its value
* @param mixed $value the value of the list to remove
* @return Bool true if the element was removed, else false
*/
public function removeValue($value)
{
if(count($this->data) < 1)
return false;
foreach ($this->data as $key => $testVal)
{
if ($testVal == $value)
{
unset($this->data[$key]);
return true;
}
}
return false;
}
/**
* Returns the number of elements in this list.
* @return Integer the number of elements in the list.
*/
public function size()
{
return (count($this->data));
}
/**
* Replaces the element at the specified position in this list with the specified element
* @param Integer $index the index to replace an element at
* @param Object $element the element to replace the index with
* @return Object the element previously at index $index, or false on error
*/
public function set($index, $element)
{
$ret = $this->data[$index];
$this->data[$index] = $element;
return $ret;
}
/**
* set the type of Object this List accepts
* @param String the type to set this list to (as returned by gettype();
* @return ArrayList the list reference $this
*/
public function setType($type)
{
$this->type = $type;
return $this;
}
/**
* get the type of Object this List accepts
* @return String the type to set this list to (as returned by gettype();
*/
public function getType()
{
return $this->type;
}
/**
* set the contents of this list from a PHP array
*
* @param array $data
* @return ArrayList the list reference $this
*/
public function setArray(array $data)
{
$this->data = $data;
return $this;
}
/**
* return the contents of this list as a PHP array
* @return the contents of this list as a PHP array
*/
public function getArray()
{
return $this->data;
}
/**
* return a new ArrayIterator
* <code>
* for ($iterator = $arrayList.getIterator(); $iterator->valid(); $iterator->next())
* {
* echo "value is " . $iterator->key . " = " . $iterator->current() . "\n";
* }
* foreach ($arrayList.getIterator as $entry)
* {
* echo "value is $entry\n";
* }
* </code>
* @return ArrayIterat$nameor of our array list data
*/
public function getIterator()
{
if (!is_array($this->data))
{
Logger::getLogger('internal')->fatal("ArrayList trying to create ArrayIterator from non array. FATAL ERROR AVOIDED. RETURNING EMPTY ARRAY. " . print_r($this->data, true));
return new ArrayIterator(array());
}
return new ArrayIterator($this->data);
}
/**
* returns the string ArrayList($type)
* @return string the string representation of ArrayList($type)
*/
public function __toString()
{
return 'ArrayList(' . $this->type . ')';
}
}
/**
* Implements List interface. Simialr to ArrayList but does not allow duplicate
* entries. Currently a "duplicate" id defined as $item1 == $item2.
*/
class Set extends ArrayList
{
public function add($element)
{
if (count($this->data) > 0)
foreach ($this->data as $elm)
{
if ($elm == $element)
return $this;
}
return parent::add($element);
return $this;
}
/**
* set the contents of this list from a php array, removing any duplicates
*
* @param array $data
*/
public function setArray(array $data)
{
$temp = array_unique($data);
return parent::setArray($temp);
}
}