FYI: SimSet/SimObjectList does not maintain order

#1 Okay, now I am feeling bad about pointing out an easily solved problem without providing a solution. The following adds a script method, SimSet::setMaintainOrder(bool), which allows you to specify that a SimSet maintain its internal order. It also implements the currently broken SimObjectList::removeStable().

I've only tested this a tiny bit, but it seems to survive removeObject calls. If there are any other order-wrecking methods in SimSet, I've not run into them yet.

changes to SimBase.cc

//// ADD THIS
void SimObjectList::removeStable(SimObject* obj)
{
  // Where is the thing we are removing?
  iterator ptr = find(begin(),end(),obj);
  
  // Did we find it?
  if (ptr != end()) 
  {
    // Yes!  Copy everything after it to the left
    //  The guy we are removing gets copied over
    iterator prev = ptr;
    ++ptr; 
    for ( ; end() != ptr; ++ptr)
    {
      *prev = *ptr;  // copy the element
      prev = ptr;
    }
    
    erase(prev);  // the last element in the list, now identical to the next-to-last
  }
}

//// ADD THIS
ConsoleMethod(SimSet, setMaintainOrder, void, 3, 3, "set.setMaintainOrder(bool)")
{
  argc;
  object->setMaintainOrder( dAtob(argv[2]) );
}

// Change SimSet::removeObject
////// OLD VERSION
void SimSet::removeObject(SimObject* obj)
{
   objectList.remove(obj);
   clearNotify(obj);
}

////// NEW VERSION
void SimSet::removeObject(SimObject* obj)
{
   if (bMaintainOrder)
    objectList.removeStable(obj);
   else
    objectList.remove(obj);
   clearNotify(obj);
}

And in simBase.h:

/// Change this line in the SimObjectList class
void removeStable(SimObject* pObject) { /* remove is stable at the moment */ remove(pObject); }
/// To this one
void removeStable(SimObject* pObject);

/// Add this variable to the SimSet class:
bool          bMaintainOrder;     // true if we care about maintaining list order (slower code)

/// Add this to the SimSet constructor:
bMaintainOrder = false;

/// And finally, add this member function to access the new variable:
void setMaintainOrder(bool b) { bMaintainOrder = b; }

edited for formatting

#2 I noticed this too when I was trying to use a SimSet as a stack. "popObject" seems to mess up the order. The strange thing is the SimSet docs imply just the opposite. popObject calls "removeStable" on the SimObjectList (which just calls "remove") and the docs for it say "guaranteed to preserve list order".

Anyway, that's why I ended up going with the Array class someone developed:

www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=4711

which has it's own weirdnesses but at least it seems to push and pop correctly. :-)

#3 Oh, right, I forgot about the array class. That would've saved me some work. :-) Thanks for the pointer!

#4 Just out of curiosity, why leave the option for the regular remove? Why not just force the stable remove. I have never seen anyone say "I'd like my objects to jump around strangly", nor can I think of any reason at this time that I might "need" my objects to jump around. But there are plenty of reasons to maintain the order of a simgroup, so it seems to me it should just be changed to force a stable remove and forgotten, lol.

EDIT:

BTW, great work! Had you come up with this about a month ago, you would have saved me a tremendous amount of manual editing to correct those types of replacements. But thank you still for saving me the future replacements.

#5 Purely at the hypothetical/abstract design level for purposes of discussion, a "set" by nature has no positional relation within the data abstraction...but an "ordered set" does. So to be "pure", you'd want the normal remove, and save the stable (or order maintaining) remove for ordered sets.

Heh..I realize that this doesn't really matter that much, but from a purist's perspective there is a difference!

#6 I had two reasons to leave the default behavior as is. First was performance, but I suspect that the difference is slight. Speed could be a problem if some code somewhere added and removed several thousand objects per second.... Okay, that's unlikely. :-)

The bigger reason is a matter of not breaking old code. I can easily imagine some part of Torque somewhere that relies on the wrong but predictable behavior of SimSet. I almost coded around it rather than fixing it, and it would only take one similar occurance somewhere in the code to create a new, nigh-untraceable bug. Not likely, but not unlikely, either.

#7 Hmm. There are a few other calls to removeStable() in the SimSet implementation. If my notions of why leaving the old style remove as the default have any merit, I suppose I ought to wrap them, too, since they will change the way they remove things. They can just be replaced with calls to removeObject().

#8 The old style remove is fast (or should be). When you have large sets this makes a potentially major difference, especially if you don't care.