当在PHP中的平面数组中给出它时，从层次结构中有效地修剪无效分支

I have a flat list of items. Some of the items in the list are parents of other items in the list. I need to go through each item, and make sure it's not invalid. Each item has an expiration time, and an item is invalid if it's own or any of it's parent's expiration times have passed. How can I efficiently remove all invalid items from the list?

Essentially I am given a hierarchical set of data in an array. Each item has it's own id, a parentID, the time information, and other non-useful data.

This is slightly complicated by the fact that there can also be multiple root nodes. It an item does not have a parentID, it is a root node.

Example array (datetime and other info omitted):

Array
(
    [0] => MyObject
        (
            [id:protected] => 1
            [parentID:protected] => 2
        )

    [1] => MyObject
        (
            [id:protected] => 4
        )

    [2] => MyObject
        (
            [id:protected] => 2
            [parentID:protected] => 4
        )

    [3] => MyObject
        (
            [id:protected] => 3
        )

    [4] => MyObject
        (
        [id:protected] => 5
        [parentID:protected] => 3
    )
)

I would like to find an efficient way to remove all items that are invalid according to the first paragraph, and return an array of the remaining items.

Thanks

I think the most efficient thing to do is to just loop through all the items and remove the nodes who are self expired. By doing this, when you later construct the tree(I assume eventually you will), any items that didn't manually get removed by the self expired criteria, will be orphaned because an ancestor is missing, and that covers the ancestor expired criteria. You could reconvert the tree back to flat if needed, but I'm guessing you want the tree eventually.