4
\$\begingroup\$

I have been working lately on an educational framework project to learn more about web development and problems that arise in more complex applications. Part of the framework's principles is to be as Object Oriented as possible. For example, most data returned from queries to a data source will be returned as a particular domain object, or a set of domain objects. I could simply return an array with the appropriate objects, but this isn't really good enough for my needs. So, I need a better data structure.

Some key aspects of the data structure to store these objects:

  • Must only accept objects of a certain type; the type of object allowed to be stored should be passed in __construct() and should be a string representation of the interface or class name.
  • No other parameters should be needed in the __construct method.
  • Should be able to be iterated over in a foreach loop.
  • The data structure should have some mechanism to restrict the number of elements that can be added to it.

With these things in mind, I created the following interface: DataList. Since the data structure is intended to be used within the framework the objects passed must extend CoreObject, which is a very simple abstract class that provides an equals(CoreObject $Object), hashCode() and __toString() methods. This was done to ensure that there is a method to compare the equality of the objects for searching purposes.

Below are the classes used in my first implementation of the DataList interface. The first class is a BaseIteratingList that provides some basic list functionality and implements the Iterator interface to allow looping. The second class is UniqueList that will not add duplicate objects to the list and implements the remaining methods of the interface. The final class is ObjectTypeValidator used to ensure the objects being add() or set() implement or extends the correct parent type.

BaseIteratingList:

/**
 * This is a base list, it provides a means to store the objects and perform basic
 * common functionality on those elements.
 *
 * This list also implements the methods necessary for the list to be iterated
 * over.  This list should be able to be used in a foreach() loop
 */
abstract class BaseIteratingList extends CoreObject implements DataList {

    /**
     * The array structure used to store the objects
     *
     * @var array
     */
    protected $dataStorage = array();

    /**
     * The number of elements in the list.
     *
     * This value also represents the index used for the next saved element.
     *
     * @var int
     */
    protected $size = 0;

    /**
     * An object used to verify that the type of object being added to the list
     * implements the correct interface or extends the correct class.
     *
     * @var ObjectTypeValidator
     */
    private $TypeValidator;

    /**
     * The position of the pointer used for the iterator functions.
     *
     * @var int
     */
    private $currentPointer = 0;

    /**
     * Each list should be passed the name of the interface or class that is allowed to
     * be stored in the list.
     *
     * @param string $parentType
     */
    public function __construct($parentType) {
        $this->TypeValidator = new ObjectTypeValidator($parentType);
    }

    public function rewind() {
         $this->currentPointer = 0;
    }

    /**
     * @return CoreObject
     */
    public function current() {
        return $this->dataStorage[$this->currentPointer];
    }

    /**
     * @return int
     */
    public function key() {
        return $this->currentPointer;
    }

    public function next() {
        ++$this->currentPointer;
    }

    /**
     * @return boolean
     */
    public function valid() {
        return isset($this->dataStorage[$this->currentPointer]);
    }

    /**
     * Returns the number representing the index for the passed element, or -1 if
     * the element could not be found.
     *
     * @param CoreObject $Object
     * @return int
     */
    public function indexOf(CoreObject $Object) {
        $index = -1;
        for ($i = 0; $i < $this->size(); $i++) {
            $ListedObject = $this->dataStorage[$i];
            if ($Object->equals($ListedObject)) {
                $index = $i;
                break;
            }
        }
        return $index;
    }

    /**
     * Will ensure the index passed is a valid range and return the CoreObject
     * associated with it if it is a valid range.
     *
     * @param int $index
     * @return CoreObject
     * @throws OutOfRangeException
     */
    public function get($index) {
        $this->throwExceptionIfIndexOutOfRange($index);
        $Object = $this->dataStorage[$index];
        return $Object;
    }

    /**
     * @param int $index
     * @throws OutOfRangeException
     */
    protected function throwExceptionIfIndexOutOfRange($index) {
        if (!is_int($index) || $index < 0 || $index >= $this->size()) {
            throw new OutOfRangeException('The requested index is not valid.');
        }
    }

    /**
     * @param CoreObject $Object
     * @throws InvalidArgumentException
     */
    protected function throwExceptionIfObjectNotParentType(CoreObject $Object) {
        $isObjectValid = $this->TypeValidator->isObjectParentType($Object);
        if (!$isObjectValid) {
            throw new InvalidArgumentException('The object passed does not implement/extend ' . $this->TypeValidator->getParentType());
        }
    }

    /**
     * Determines whether or not the list contains the given object.
     *
     * @param CoreObject $Object
     * @return boolean
     */
    public function contains(CoreObject $Object) {
        $objectContained = false;
        $objectIndex = $this->indexOf($Object);
        if ($objectIndex >= 0) {
            $objectContained = true;
        }
        return $objectContained;
    }

    /**
     * @return boolean
     */
    public function isEmpty() {
        return ($this->size === 0);
    }

    /**
     * @return int
     */
    public function size() {
        return $this->size;
    }

} 

UniqueList:

/**
 * This class is an implementation of the DataList interface, with data storage and
 * iteration responsibilities being handled by its immediate superclass.
 *
 * This data structure guarantees that the objects added to it implement the appropriate
 * interface or extends the appropriate class.  This data structure will also ensure
 * that only unique objects are added to the List.  The only means in which to set the
 * type of objects stored in the class is through the constructor.  If you want
 * the list to store different types of objects you will need to create a new one.
 *
 * @see ObjectTypeValidator
 */
class UniqueList extends BaseIteratingList {

    /**
     * A zero in the $maxSize property value means the list may have an unlimited
     * number of objects.
     *
     * @var int
     */
    private $maxSize;

    /**
     * Will add the passed object to the list, given (a) there are enough empty buckets
     * in the list, (b) the object properly implements the $parentType and (c) the
     * object does not already exist in the list.
     *
     * @param CoreObject $Object
     * @throws OutOfRangeException
     *         IllegalArgumentException
     */
    public function add(CoreObject $Object) {
        $this->throwExceptionIfNoAvailableBuckets();
        $this->throwExceptionIfObjectNotParentType($Object);
        $isObjectInList = $this->contains($Object);
        if (!$isObjectInList) {
            $this->_add($Object);
        }
    }

    /**
     * @throws OutOfRangeException
     */
    private function throwExceptionIfNoAvailableBuckets() {
        $isThereBucketsInList = $this->hasAvailableBuckets();
        if (!$isThereBucketsInList) {
            throw new OutOfRangeException('The list does not have any buckets left to store the object.');
        }
    }

    /**
     * Will return whether or not the list has enough buckets to add 1 additional
     * element.
     *
     * Note, if the $maxSize is set to 0 then there will always be available buckets
     * for the list.
     *
     * @return boolean
     */
    private function hasAvailableBuckets() {
        $hasBuckets = true;
        if ($this->maxSize > 0) {
            if ($this->size >= $this->maxSize) {
                $hasBuckets = false;
            }
        } 
        return $hasBuckets;
    }

    /**
     * Will add the passed object to the storage and increment the size of the
     * list.
     *
     * @param CoreObject $Object
     */
    private function _add(CoreObject $Object) {
        $arrayIndex = $this->size;
        $this->dataStorage[$arrayIndex] = $Object;
        $this->size++;
    }

    /**
     * Should change the index of the given list to the object passed.
     *
     * @param int $index
     * @param CoreObject $Object
     * @throws OutOfRangeException
     *         IllegalArgumentException
     */
    public function set($index, CoreObject $Object) {
        $this->throwExceptionIfIndexOutOfRange($index);
        $this->throwExceptionIfObjectNotParentType($Object);
        $this->dataStorage[$index] = null;
        $this->dataStorage[$index] = $Object;
    }

    /**
     * Should remove the object from the list if it exists and resize the array.
     *
     * Please note that it is highly unrecommended that you remove objects from a
     * list while looping through the list, for example in a foreach() loop.  The
     * initial implementation simply wasn't sufficient to handle this, please avoid
     * doing so.  This feature may be added in a future release.
     *
     * @param CoreObject $Object
     */
    public function remove(CoreObject $Object) {
        $objectIndex = $this->indexOf($Object);
        if ($objectIndex >= 0) {
            $this->dataStorage[$objectIndex] = null;
            $this->resizeList();
        }
    }

    /**
     * Should be called after an element is removed from the list, will create a
     * new array that does not contain any null values and then assign that array
     * to the $dataStorage property.
     */
    private function resizeList() {
        $newArray = array();
        for ($i = 0; $i < $this->size(); $i++) {
            if (isset($this->dataStorage[$i])) {
                $newArray[] = $this->dataStorage[$i];
            }
        }
        $this->dataStorage = $newArray;
        $this->size = count($this->dataStorage);
    }

    /**
     * If the passed value is a valid, unsigned integer the maxSize is set.
     *
     * Note if this value is set to 0 this indicates that there is no limit on the
     * number of buckets that can be added to the list.  If the maxSize is set
     * AFTER the list has already been created the maxSize will automatically be
     * set to the maxSize of the existing list.  An error message should also be
     * triggered if this happens.
     *
     * @param int $maxSize
     * @return int
     */
    public function setMaxSize($maxSize) {
        $isSizeInteger = is_int($maxSize);
        $isSizeBigEnough = ($maxSize >= 0);
        $isSizeValid = ($isSizeInteger && $isSizeBigEnough);
        if (!$isSizeValid) {
            $maxSize = 0;
            error_log('The maximum size for the list was not a valid integer value, no maximum size set.');
        }
        $currentSize = $this->size();
        if ($currentSize > $maxSize) {
            $maxSize = $currentSize;
            error_log('The current size of the list is greater than the maximum size set, maximum size set to current size.');
        }
        return $this->maxSize = $maxSize;
    }

}

ObjectTypeValidator:

/**
 * This class ensures that a given object implements or extends a specific interface
 * or class.
 */
class ObjectTypeValidator extends CoreObject {

    /**
     * @var ReflectionClass
     */
    protected $ReflectedParentType;

    /**
     * Will create a ReflectionClass of the passed $parentType, if the
     *
     * @param string $parentType
     * @throws InvalidArgumentException
     */
    public function __construct($parentType) {
        $this->ReflectedParentType = $this->createReflectedParentType($parentType);
    }

    /**
     * @param string $parentType
     * @return ReflectionClass
     * @throws InvalidArgumentException
     */
    private function createReflectedParentType($parentType) {
        $ReflectedParent = null;
        try {
            $ReflectedParent = new ReflectionClass($parentType);
        } catch (ReflectionException $ReflectionExc) {
            throw new InvalidArgumentException('There was an error reflecting the parent type, ' . $parentType, null, $ReflectionExc);
        }
        return $ReflectedParent;
    }

    /**
     * Ensures that the passed $Object either is an instance of, extends  or implements
     * the $ReflectedParentType.
     *
     * We chose to go with Reflection instead of using the is_a() function or
     * instanceof operator due to the fact that the $parentType expected from the
     * user in __construct() is of type string.  By using Reflection we ensure that
     * the class can be included through the ClassLoader and can ensure that
     * interface implementation and class inheritance is covered.
     *
     * @param CoreObject $Object
     * @return boolean
     */
    public function isObjectParentType(CoreObject $Object) {
        $isValid = false;
        $ReflectedParent = $this->ReflectedParentType;
        $parentName = $ReflectedParent->getShortName();
        try {
            $ReflectedObject = new ReflectionClass($Object);
            if ($ReflectedParent->isInterface()) {
                if ($ReflectedObject->implementsInterface($parentName)) {
                    $isValid = true;
                }
            } else {
                if ($ReflectedObject->getShortName() === $parentName || $ReflectedObject->isSubclassOf($parentName)) {
                    $isValid = true;
                }
            }
        } catch (ReflectionException $ReflectionExc) {
            // @codeCoverageIgnoreStart
            error_log($ReflectionExc->getMessage());
            // @codeCoverageIgnoreEnd
        }
        return $isValid;
    }

    /**
     * @return string
     */
    public function getParentType() {
        return $this->ReflectedParentType->getShortName();
    }
}

Well, there's the implementation, it has been unit tested and does pass all tests. However, there are a couple of known issues or concerns I have with the code:

  • The "hidden" dependency of ObjectTypeValidator. I'm not sure what would be a reasonable solution for this. At one point this functionality was actually hard-coded in the list, however I am also going to want to implement some other data structures that will need object type validation so I abstracted it out. However, I don't want to ask the user to inject an ObjectTypeValidator object either. Should I try to hide this from the user or require the object dependency to be injected instead of the string?

  • When looping through the list there is unreliable behavior if an object is removed. For now, my solution is to document that it is not intended for objects to be removed from the list in a loop structure...however this is a less than ideal solution. How could I allow for the removal of objects from the list and ensure that the looping structure does not become corrupt or lose track of the proper object that should be pointed to?

  • Do you notice anything illogical, wrong or ugly about my code?

Well, I realize that's a lot to read so I'll leave it at that. I appreciate any feedback to the code or questions posed.

Edit in response to Yannis Rizos answer:

Admittedly I was not aware of the breadth of iterators available from the SPL, perhaps I will go back and refactor the data structure to use one of these iterators, perhaps fixing my looping issue. That being said, my reference for the DataList interface was the Java List interface and is really what I attempted to model my data structure after. When I look at the SPL classes they look far too big and bulky and the primary reason for my writing this project is the learning experience, I expect a few wheels to be reinvented. Sometimes you wanna learn about wheels though.


I definitely wouldn't want to base my CoreObject off of ArrayObject...that is far too much stuff for something really intending to only provide some common methods for other classes. I like to think of CoreObject as being stdClass or Object in Java, but for the framework. Essentially, it is only meant to provide a way to compare 2 objects to determine if they are the same or not and print a specific value when the object is used as a string, I don't want the CoreObject doing anything much more than that. However, perhaps I will implement this as an interface, Object, and simply supply CoreObject as the framework's implementation.


I chose -1 as the return value for indexOf() based on 2 reasons. (1) I was originally basing the list off of Java implementation and that's what they do. (2) I don't want users attempting to simply test for falsehood on the return value. For example:

$index = $List->indexOf($Object);

// uh oh!  $index is '0' and is really valid
if (!$index) {
    // do stuff here
}

You'd have to change this to a check for 0 AND a check for falsehood:

if (!$index && $index !== 0) {

}

I don't like this and would like to avoid it whenever possible.

\$\endgroup\$
  • \$\begingroup\$ Injecting is generally the way to go, but another option is defaulting the object for ObjectTypeValidator. \$\endgroup\$ – Paul Dec 7 '11 at 0:59
4
\$\begingroup\$

Why reinvent the wheel and not build upon the Traversable, ArrayAccess and Serializable SPL interfaces, or more realistically upon one of their concrete children?

On similar requirements I would have possibly build my CoreObject upon an ArrayObject.

/**
 * Returns the number representing the index for the passed element, or -1 if
 * the element could not be found.
 *
 * @param CoreObject $Object
 * @return int
 */
public function indexOf(CoreObject $Object) { ... }

I would suggest returning false instead of -1 when element not found. It feels a little more natural and expected.

public function set($index, CoreObject $Object) 

Since Part of the framework's principles is to be as Object Oriented as possible., you should consider using interfaces instead of classes, for object dependencies.

And as the "hidden" dependency of ObjectTypeValidator: It highly depends of what the framework is for. You've gone for the common practical approach instead of the academic one (injection). There's no right or wrong here, it highly depends on the framework's purpose and audience, the academic approach may not always be the educative approach.


Consider all of the above as extreme nitpicking, your code is way past the point of obvious flaws. The real value of the answer, if any, was to point you towards the SPL. If you did consider it and rejected it, would you care to share why?


Edit in response to the edit in response to my answer :)

That being said, my reference for the DataList interface was the Java List interface and is really what I attempted to model my data structure after.

I definitely wouldn't want to base my CoreObject off of ArrayObject...that is far too much stuff for something really intending to only provide some common methods for other classes.

As this is a learning experience, you should be concentrating on learning the language and its quirks. Java <> PHP, in quite a few ways. You shouldn't limit yourself in copying the Java interface, it's a good interface to clone but now that you've done that you should explore enhancing it with native PHP functionality. You should take as much advantage of native stuff as possible, the performance difference is noticeable.

I have to admit that the ArrayObject was an off hand example, my primary intention was to point you towards the SPL. I did base something similar on an ArrayObject, but the requirements weren't exactly the same.

Still bits and pieces of your code could be rewritten to take advantage of native functionality. For example, this:

public function remove(CoreObject $Object) {
    $objectIndex = $this->indexOf($Object);
    if ($objectIndex >= 0) {
        $this->dataStorage[$objectIndex] = null;
        $this->resizeList();
    }
}

could possibly be rewritten as:

public function remove(CoreObject $Object) {    
    $objectIndex = $this->indexOf($Object);
    if ($objectIndex >= 0) {
        unset($this->dataStorage[$objectIndex]);
        $this->dataStorage = array_values($this->dataStorage);

        return true;
    }

    return false;
}

and avoid the costly call to resizeList(). And do return something, tell the user if the operation succeeded or not, regardless of what the Java interface does.

I chose -1 as the return value for index() based on 2 reasons. ... (2) I don't want users attempting to simply test for falsehood on the return value.

Your users should check for falsehood like that:

if ($index !== false) {
    // do stuff here
}

You shouldn't have to compensate for users that are not familiar with PHP's comparison operators.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the good answer. I have addressed some of your questions in the edit to my answer. \$\endgroup\$ – Charles Sprayberry Dec 7 '11 at 15:22
  • \$\begingroup\$ @CharlesSprayberry I've updated my answer, primarily for your last point on checking falsehood, as your example if (!$index && $index !== 0) is not a standard PHP practice, but a common beginner mistake. \$\endgroup\$ – yannis Dec 7 '11 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.