limiting a collection of objects to a unique set

Question

Currently I have a PHP class called Collection. It uses an array to hold set of unique objects. They are unique, not in the sense that they have different memory addresses (though obviously they do), but in the sense that there are no equivalent objects in the set.

I've been reading about SplObjectStorage which has significant speed advantages over an array and might be easier to maintain than my Collection class. My problem is that SplObjectStorage does not concern itself with equivalency, only identity. For example:

class Foo {
  public $id;

  function __construct($int){
    $this->id=$int;
  }

  function equals(self $obj){
    return $this->id==$obj->id;
  }
}

$f1a = new Foo(1);
$f1b = new Foo(1);//equivalent to $f1a
$f2a = new Foo(2);
$f2b = $f2a; //identical to $f2a

$s=new SplObjectStorage;
$s->attach($f1a);
$s->attach($f1b);//attaches (I don't want this)
$s->attach($f2a);
$s->attach($f2b);//does not attach (I want this)

foreach($s as $o) echo $o->id; //1 1 2, but I wish it would be 1 2

So I've been thinking about how to subclass SplObjectStorage so its attach() would be restricted by object equivalency, but so far it involves setting the $data of the object to an "equivalency signature" which seems to require looping through the datastructure until I find (or not) a matching value.

e.g.:

class MyFooStorage extends SplObjectStorage {

  function attach(Foo $obj){
    $es=$obj->id;
    foreach($this as $o=>$data) {//this is the inefficient bit
      if($es==$data) return;
    }
    parent::attach($obj);
    $this[$obj]=$es;
  }
}

Is there a better way?

Answer 1

If the only thing that defines equality is relative to another object, then I am afraid that what you want is impossible. Think about it, there is no way to determine that an object is already included in the array unless I check every object, so I will have a complexity of O(n) no matter what.

However, if you make the equality absolute then this is possible. In order to do that, you will have to produce a hash value for each of the objects. Two objects will be equal if and only if their hashes are equal. Once you have that, then you can achieve O(1) with a HashMap.

Under the hoods, this is exactly what SplObjectStorage does, by taking the address of an object as its hash value.