An Indexed Array of Objects

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

Post Reply
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

An Indexed Array of Objects

Post by Ollie Saunders »

I think most people on here know that this:

Code: Select all

$array = array('some' => true, 'indexed' => true, 'data' => true, 'in' => true,
               'an'   => true, 'array'   => true);
isset($array ['data']);
is many times faster than this

Code: Select all

$array = array('some', 'unindexed', 'data', 'in', 'an', 'array');
array_search('data', $array);
(assuming that several requests are made for data in $array)

Now the problem, what if I want to used objects as keys. Only strings and integers are allowed.
Here is what I would really like to do:

Code: Select all

class ObjectIndex implements ArrayAccess
{
    private $_objs = array();
    public function offsetExists($obj)
    {
        return isset($this->_objs[get_obj_id($key)]);
    }
    public function offsetSet($key, $obj)
    {
        if ($key !== null) {
            throw new Exception('Keys not permitted'); // we generate our own
        }
        $this->_obj[get_obj_id($obj)] = $obj;
    }
    public function offsetGet($obj)
    {
        return $this->_objs[get_obj_id($obj)];
    }
    public function offsetUnset($obj)
    {
        unset($this->_objs[get_obj_id($obj)]);
    }
}
$index = new ObjectIndex();
$index[] = $a = new stdClass;
$index[] = $b = new Exception;
$index[] = $c = new DOMDocument;
$found = $index[$b]; // etc.
Sub PHP 5.2 you can

Code: Select all

function get_obj_id($obj)
{
    static $prefixLen = strlen('Object Id#');
    if (!is_object($obj)) {
        return false;
    }
    return (int)substr((string)$obj, $prefixLen);
}
but come PHP 5.2 this will no longer work for an object implementing __tostring() as the (string) cast will not return the object id information i so valuibly need.

Ideas?
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post by Jenk »

The moment you said you want to use objects as keys you were flawed.

You appear to be confusing keys with values.

Code: Select all

$index[] = $a = new stdClass;
That does not create a key with the object of stdClass, it creates the vlue with and automatically generated key.

in_array() is a lot quicker than array_search() by the way.
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post by timvw »

If i understand well, you're trying to implement your own 'GetHashCode' function for objects... And untill now you relied on a __toString to exist on the objects...

- Option1: You could use serialize to generate a string representation of your object... And then apply a hashing algorithm on that string to convert it to a number.

- Option 2: Restrict the input to objects that implement the toString method.. So you define an interface that contains the method, and you add typehinting to your ObjectIndex methods...
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

The moment you said you want to use objects as keys you were flawed.
Why?
You appear to be confusing keys with values.
I'm sorry, no. I know what keys and values are.
That does not create a key with the object of stdClass, it creates the vlue with and automatically generated key.
Yep. A key which can be obtained from the object, making it possible to get an object's position in the array without searching it comparing identicalness.
in_array() is a lot quicker than array_search() by the way.
I think you will find there is very little difference (bool)array_search is effectively in_array().

----
If i understand well, you're trying to implement your own 'GetHashCode' function for objects...
Bingo!
And untill now you relied on a __toString to exist on the objects...
Nope, until now I relied on __tostring to NOT exist. When you call (string)new stdClass; you get 'Object id#1', its that string that I need because that is the only way I can ascertain class inspecific object uniqueness. A object that implements __tostring doesn't give me that string.
- Option1: You could use serialize to generate a string representation of your object... And then apply a hashing algorithm on that string to convert it to a number.
Yep thought of that. But then there would be no difference between these two objects of the same type and properties despite them being separate objects:

Code: Select all

$obj1= new stdClass; $obj2 = new stdClass;
they both contain no properties and thus would be serialized to the same string. Also there's a performance hit for serializing. I don't see why I would need to hash a serialized object though.
- Option 2: Restrict the input to objects that don't implement the toString method..
Thought of that as well I don't know how you can do that.
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post by Jenk »

ole wrote:
The moment you said you want to use objects as keys you were flawed.
Why?
You appear to be confusing keys with values.
I'm sorry, no. I know what keys and values are.
Then why post what you posted? What you posted does not assign any key, it leaves it to php to assign a key, as below.
That does not create a key with the object of stdClass, it creates the vlue with and automatically generated key.
Yep. A key which can be obtained from the object, making it possible to get an object's position in the array without searching it comparing identicalness.
Nope. It will assign max(array_keys($array)) + 1 to the key.
in_array() is a lot quicker than array_search() by the way.
I think you will find there is very little difference (bool)array_search is effectively in_array().

Code: Select all

<?php

$array[0] = 'foo';

var_dump((bool)array_search('foo', $array), in_array('foo', $array)); 

?>
Big difference. ;)
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Jenk wrote:
ole wrote:
The moment you said you want to use objects as keys you were flawed.
Why?
You appear to be confusing keys with values.
I'm sorry, no. I know what keys and values are.
Then why post what you posted? What you posted does not assign any key, it leaves it to php to assign a key, as below.
That does not create a key with the object of stdClass, it creates the vlue with and automatically generated key.
Yep. A key which can be obtained from the object, making it possible to get an object's position in the array without searching it comparing identicalness.
Nope. It will assign max(array_keys($array)) + 1 to the key.
have you ever written a class that implements ArrayAccess before Jenk? My class is handling the behaviour of the subscript syntax.

Code: Select all

$array[0] = 'foo';

var_dump((bool)array_search('foo', $array), in_array('foo', $array));
Ahh yes that is a big difference. How about this:

Code: Select all

$array = array($data = 'foo');
var_dump(array_search($data, $array) !== false, in_array($data, $array));
Now they are the same :)
sike
Forum Commoner
Posts: 84
Joined: Wed Aug 02, 2006 8:33 am

Post by sike »

var_dump may be of use here.
but with larger objects there might be some serious performance problems.

chris
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

var_dump may be of use here.
but with larger objects there might be some serious performance problems.
Hmm yes that does work but yes kinda defeats the purpose.
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post by Jenk »

ole wrote:I'm sorry, no. I know what keys and values are.

Yep. A key which can be obtained from the object, making it possible to get an object's position in the array without searching it comparing identicalness.

have you ever written a class that implements ArrayAccess before Jenk? My class is handling the behaviour of the subscript syntax.
What you are trying to achieve is not covered by the ArrayAccess interface, so there's no discussion to be had regarding ArrayAccess..
Ahh yes that is a big difference. How about this:

Code: Select all

$array = array($data = 'foo');
var_dump(array_search($data, $array) !== false, in_array($data, $array));
Now they are the same :)
The same, but unecessary when you should just use in_array()..

--

You're trying to create a Registry object to store values, and want to implement a method of checking if such a value has been added to the registry already, by using a key. So why not structure the return value of a setter to be the key?

Code: Select all

<?php

$key = $reg->addValue($obj);

// ...

if ($reg->offsetExists($key))
{
    $obj = $reg->offsetGet($key);
}

// ...

?>
$key just being a 0 indexed value, like any other array... or you can use the offsetSet for it's intended design and assign a key as you assign the value.

If you really want a random int or string and not just an incremental number:

Code: Select all

do 
{
    $key = rand(0, 9999);
} while (isset($this->_values[$key]));

return $key;
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Jenk, you're missing the point slightly here.
You're trying to create a Registry object to store values
Yes
and want to implement a method of checking if such a value has been added to the registry already
Yes... but I don't want to have to iterate through the entire array to find that out, as per array_search, in_array and foreach. That is why keys are so great because they are indexed. PHP stores keys in order (an internal one you don't see), keeps them in the correct order despite any manipulations and then when a specific key is requested is able to binary search for the data the key represent which is very fast). I suppose what I am really asking is how can I binary search through objects?
So why not structure the return value of a setter to be the key?
Yes that's a good idea actually but I still need to know if the object (the key) exists. In fact offsetGet could be rewritten, and probably more correctly so, as:

Code: Select all

public function offsetGet($obj)
    {
        if (isset($this[$obj])) {
            return $obj;
        }
        return null;
    }
User avatar
Jenk
DevNet Master
Posts: 3587
Joined: Mon Sep 19, 2005 6:24 am
Location: London

Post by Jenk »

A method to return it's unchanged parameter, or null if it doesn't exist as a key in an internal array... right..

Tbh, you're fussing over nothing. If you are worried about performance (which we are talking pecoseconds in difference here) you should also take into consideration the time it takes to call a method (__toString()) when assigning an object as string..

Code: Select all

public function offsetGet($key)
{
    if (!isset($this->_array[$key])) throw new OutOfBoundsException('Offset does not exist.');

    return $this->_array[$key];
}

public function offsetSet($key, $val)
{
    $this->_array[$key] = $val;
}

public function keyExists($key)
{
    return isset($this->_array[$key]); // or array_key_exists()
}

public function inArray($val)
{
    return in_array($val, $this->_array);
}
User avatar
johno
Forum Commoner
Posts: 36
Joined: Fri May 05, 2006 6:54 am
Location: Bratislava/Slovakia
Contact:

Post by johno »

What about this?

Code: Select all

class ObjectRegistry {
		private static $counter = 0;
		
		public static function getObjectIndex($instance) {
			if(!property_exists($instance, '__objectIndex')) {
				$instance->__objectIndex = self::$counter++;
			}
			return $instance->__objectIndex;
		}
	}
	
	class ObjectArray implements ArrayAccess {
		private $array = array();
	
		function offsetExists($object) {
			$index = ObjectRegistry::getObjectIndex($object);
			return isset($this->array[$index]);
		}
		
		function offsetGet($object) {
			$index = ObjectRegistry::getObjectIndex($object);
			return $this->array[$index];
		}
		
		function offsetSet($object, $value) {
			$index = ObjectRegistry::getObjectIndex($object);
			$this->array[$index] = $value;
		}
		
		function offsetUnset($object) {
			$index = ObjectRegistry::getObjectIndex($object);
			unset($this->array[$index]);
		}
	}
	
	class Test {
		public $value;
		public function __construct($value) {
			$this->value = $value;
		}
	}
	
	$array = new ObjectArray();
	$test1 = new Test(1);
	$test2 = new Test(2);
	$test3 = new Test(3);
	$array[$test1] = 'a';
	$array[$test2] = 'b';
	$array[$test3] = 'c';
	
	// tests
	assert($array[$test3] == 'c');
	assert($array[$test2] == 'b');
	assert($array[$test1] == 'a');
	assert(!isset($array[new Test(1)]));
Is this behaviour what you wanted to do?
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Oh wow I think that'll do the job.
I'll test this out and get back to you.
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Works!
Many thanks johno.
Post Reply