5

I've come across a problem like this more than once and I'd like to know the recommended approach(es) for dealing with it. Alternatively, I'd like to know if it has a name.

For concreteness, let's suppose we have a Colony object, one of whose members is a list of Organism objects. Organism objects have an Update method. Under certain conditions, the desired behavior upon calling Update is for the organism to "split itself in half" -- that is, to produce two new Organisms to be inserted into the collection, and then to have itself removed from the collection and destroyed.

To make things interesting, let's say the collection is ordered and we want the new Organisms inserted at the same point the old Organism previously occupied.

Moreover let's say we want to loop through the collection of Organisms calling Update on each, and we want to do this in such a way that Update does not get called on newly-created Organisms.

As a variant, perhaps the Organism wants to keep itself alive but to insert its offspring into the collection next to it.

I can think of a few ways to do this with various tradeoffs:

  1. Have Update return a list of Organisms, either itself or a list of new ones. Then have the loop calling Update construct a new collection from these and replace the old collection with it at the end.
  2. Pass Update some (callbacks / pointers / whatever) allowing it to insert items into the collection in such a way that the (iterator / loop index / whatever) gets moved past them.
  3. Have Update communicate its desire to insert new objects to the calling loop and have the calling code take care of the actual insertion.

Are there other reasonable ways to do this? Are there non-obvious advantages/disadvantages to them? Do they have names? Are there slick ways of doing them automatically?

  • Have you considered recursion? – Frank Hileman Mar 18 '17 at 0:08
  • Can you elaborate? Do you mean a recursive version of #1, something like UpdateList(x:xs)=Update(x):UpdateList(xs)? – Daniel McLaury Mar 18 '17 at 0:41
  • That is what I meant, yes. – Frank Hileman Mar 18 '17 at 0:57
  • Would a List really be a good topographical space for your artificial environment? Your organisms will live in a one-dimensional space, and will always be space. Have you considered a two-dimensional Cartesian layout instead? – John Wu Mar 18 '17 at 2:14
  • Do you have a realistic example of this problem? My first instinct would be option 1 (have Update return a list and concatenate the lists), so I'm wondering when that would not be a good solution. – Tanner Swett Mar 19 '17 at 9:42
1

Disclaimer

This solution is not object-oriented, but maybe still interesting.

TL;DR

Going with your first idea (have Update return a list of Organisms), in Haskell you can

  1. define a type Organism,
  2. define an update function update :: Organism -> [Organism],
  3. loop over a list organism :: [Organism] with organisms >>= update.

Detailed answer

In Haskell you can model the update function as a function that produces a list of organisms:

data Organism = ...

update :: Organism -> [Organism]

Then the function update can either produce two new organisms and forget about the old one, or repeat the old organism followed by its children:

-- Parent disappears
update x = [child1 x, child2 x]
  where
    child1 x = ...
    child2 x = ...

-- Parent followed by children
update x = [x, child1 x, child2 x]
  where
    child1 x = ...
    child2 x = ...

Now your iteration boils down to mapping the update function over the initial list of organism (which gives a list of lists of organisms) and then flattening the result using concat, like so

organisms = [..., ..., ]
newOrganisms = concat (map update organisms)

The combination concat - map can be expressed by another function called bind and written >>= in Haskell (in Scala, it is called flatMap), so you can also write:

organisms >>= update

This iterates over the list, applies update to each element, and flattens the result.

Note

If you need any information on how to try out this solution in a Haskell interpreter, I can provide more details.

3

Since the main operation here is inserting objects in the middle of a list where you already have a pointer to the correct Organism, a linked list would be one of the most efficient way to implement this.

Suppose you have a data structure like so:

class Organism(object):
    def __init__(self):
        # you don't have to have reference to 
        # the Node in the Organism, but having it makes
        # things slightly easier if Organism can only
        # belong to a single LinkedList. If you don't have 
        # a reference to the Node, you'd want to have
        # a mapping/dictionary in the LinkedList object
        # to lookup the Node representing an Organism
        # in that Linked List
        self.node = None

class Node(object):
    def __init__(self, obj):
        self.left = None
        self.right = None
        self.obj = obj
        self.obj.node = self

To insert an object into the linked list you do:

class Node(object):
    ...
    def insert_left(self, obj):
        node = Node(obj)
        node.left = self.left
        node.right = self
        self.left.right = node
        self.left = node

To remove an object from the linked list you do:

class Node(object):
    ...
    def remove(self):
        self.left.right = self.right
        self.right.left = self.left
        self.left = None
        self.right = None

To split an Organism, you do:

class Organism(object):
    ...
    def mitosis(self):
        c1 = Organism()
        c2 = Organism()
        node = self.node
        node.insert_left(c1)
        node.insert_left(c2)
        node.remove()

To have the original Organism survive the birth after its children you do:

class Organism(object):
    ...
    def birth(self):
        c = Organism()
        self.node.insert_left(c)

To iterate the linked list, you simply walk through the right nodes:

class LinkedList(object):
    def __iter__(self):
        node = self.list.head
        while node is not None:
            yield node.obj
            node = node.right

class Colony(object):
    def __init__(self):
        self.list = LinkedList()

    def update(self):
        for node in self.list:
            node.update()

Since you insert_left() when the Organism split() or birth(), any newly created Organisms won't be updated in the current iteration.

If you want an Organism to be able to decide whether or not its new children should get iterated next or if you want the flexibility of whether the new children is insert_left() or insert_right() and whether the newly created Organism still needs to be skipped, you can use Continuation Passing Style during the iteration and explicitly return the next Organism to iterate.

1

Option 3 will be the easiest, most fkexible and most performant one. Most often an object will merely update its internal state and "pass" on being split up.

Update does not get called on newly-created Organisms.

This does not seem to serve a purpose. You would want an object to keep track of the number of times it has been updated anyway (age) and it would be nicer to have a new object initialize itself on the first update rather than have it initialized by its parent.

You can use a for loop and insert any new objects ahead of the iterator value. This way any new objects will be the first to get hit for updating.

A practical way would be for a splitting object to return a child object. The knowledge of the splitting process and how to update the remaining part of the object could stay in the object itself. If update returns null there would be nothing to do (next). If a child is returned, the loop code could decide to either insert it ahead of the parent or in a different collection.

Assuming the updating process depends on the neighbors you would need objects to have references to those neighbors at the time of updating. Links in the object itself could serve that purpose but you may also have references to neighbors injected as arguments of the Update method. That would save you a lot of private references.

Alternatively, have objects keep track of their position in a plane and feed them any touching neighbors on each update. Program some behavior. You could visualize that in a bitmap. Should be fun.

  • Related: I once made something similar that also involved food. The food would be pre-scattered in the plane and/or rain down from the sky. The objects had a position and an inclination to move either straight ahead, take a left turn or a right turn. They could take a couple of steps before they needed to hit a food pixel or they would die. This would prove the entrepeneurial objects to be more successful than the local turners who would quickly run out of food. I called it Evolution. It was fun to play with parameters and just watch the show. – Martin Maat Mar 18 '17 at 10:09

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.