phparrayssorting

Push a new object into a sorted objectArray at the correct position to avoid re-sorting

Is there any way to maintain a sorted array of objects?

For example, if I have an object with properties ID, Date, Name and a collection of these objects:

$col = array();

public function addNewObject($id, $date, $name)
{
    $col[] = new Object($id, $date, $name); 
    //but instead of appending, it should place it by Name desc
}

If I call something like getObjects, it would return the items in the collection by Name desc.

I think there were some answers for getting objects back in a sorted order, but for efficiency, I would think it be better to sort at insert as the "sort by" variable in my case will never change.

UPDATE: So based on the comments, I should resort the whole array each time something is added but that seems a bit memory intensive...

Since the array would always be in sorted order to start out with I can identify the location where I want to insert by traversing the array (would this be efficient, is there a better way?). Once I find that how could I "insert" a new object into the array?

I do not imagine that the array will be very large but I would like to implement this the most efficient way possible.

Solution

  • If you're not keen on resorting the array after you add (although I'd recommend it; realistically this wont be a performance issue and it keeps the code readable.

    However, if you definitely don't want to do this then you can, as you said, traverse the array and find out where to insert:

    $col = array();

public function addNewObject($id, $date, $name){
    //Find the index to insert at
    $index = 0;
    foreach($col as $i => $item){
        if($item->name > $name){
           //This item is after the item we want to insert. 
           //Use the previous index and stop traversing
           break;
        }
        $index = $i;
    }
    $col = array_splice($col, $index, 0,  new Object($id, $date, $name));
}

    Using array_splice to insert at an arbritary position thanks to https://stackoverflow.com/a/3797526/505722