Location: PHPKode > scripts > RogePHP > RoguePHP-0.9.4/RoguePHP-0.9.4/types/List.php
<?
/**
 * @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);
	}

}
Return current item: RogePHP