How could I have missed this?

http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/

Fantastic, although to squeeze the very last out of it you’ll be wanting to do all your calculations strictly in powers of 2… I look forward to putting this to use. Thanks Mike!

Been fiddling around with Mike Baczynski’s Data Structures for Game Developers (what benighted dabbler in Flash game programming hasn’t?), and have found a few things I’ve addressed in my own (heavily modified) version of some of his classes.

Mike’s original is aimed at execution speed rather than “correctness” in the sense of proper OO design principles. As game developers, speed is what we’re after, and what makes his Data Structures something quite special (as they kick the **** out of the native Array class in terms of performance).

Having said this, at the moment I’m more concerned with keeping maintainable code in certain areas than I am in having the fastest Linked List possible. So I started refactoring… and refactoring… and refactoring.

The first problem I spotted and the thing that got me going was the Iterators on the Collections. They are completely public, openly accesible to the code utilising the list. This makes no sense to me. The List has public methods of course, which is fine. But surely the List should provide the interface to the “user” code, encapsulating the Iterators along with the Nodes, which after all, are part and parcel of the List itself. (Why would you shift an Iterator from List to List? - this would seem to be the only reason for allowing public access to Iterators.)

I’m not sure if the author’s intention was to improve execution speed through allowing the user to reuse an already-created Iterator on a new list, but I definitely don’t find this code safe. What if you make a mistake somewhere in your code and accidentally modify the Iterator (”here I am, come and get me, my methods and properties are all public!”) while you are trying to use it for other purposes? Sounds like a debugging nightmare waiting to happen.

But that’s not all. The major reason I decided to forge ahead with all of these changes, in spite of the originals being usable straight out of the box, was my concerns when using the concat() and splice() methods of linked lists. If you look at the original Polygonal LinkedList code, you will see in the comments before each function a warning not to use attempt to use the lists which were spliced or concatenated into the current/active list, for they will have been invalidated by the calling of these methods. Is this good practice? Is a warning enough? Okay, we’re assuming that we’re talking about game developers here so the idea is these are probably people who know what they are doing. But does that prevent us, as developers, from making mistakes? And from suffering for hours trying to recover from those mistakes, because we used code that is inherently unsafe? I don’t think so. And I’m willing to take a performance hit if, in the long run, it means I can develop the overall product faster (due to safe/maintainable code), and spend time refactoring those things which I need to, at a later stage. In the words of Donald Knuth, “Premature optimization is the root of all evil.” And that means that, in a sense, even using prematurely optimised code like package de.polygonal.ds might be considered a mistake… except — time is money, and we can’t always write our own classes from scratch.

So, what was refactored?

• If a list is destroyed or invalidated, all iterators on that list must be destroyed as well so that no illegal operations can take place. Encapsulation is the answer. Iterator instantiation and use are now encapsulated within the list on which they are used. You cannot create an iterator externally as it is now an internal class within the package. The invalidated iterators are pointed to a “null node” by the list, which has a hashmap (another of Mike’s data structures) to keep track of all iterators on that list. FYI, the iterators are given string names for the hashmap to recognise them by - hashmaps being essentially associative arrays.
• Nodes still have public members but are meaningless unless placed into the context of a list — which can only be done by the list itself
• Any and all redundant or unused methods have been stripped out of the List, Node and Iterator classes.
• The Iterator interface no longer has a start() method declaration. Iterators know nothing of the list containing them - they know only of the nodes they operate on, and only the list can provide the gestalt knowledge of where the head and tail are.
• One thing I’m not sure about, and will consider as time goes forward and I develop these data structures further according to my own tastes, are the marker interfaces. From what I understand of markers they won’t be used in what I plan to develop. I could just be ignorant, though. So I’ve stripped all the marker interfaces out. But ONLY the marker interfaces, not the other interfaces. I hear your sighs of relief.

Obviously with these substantial changes, method calls in user code now look substantially different, for example:
var list:LinkedList = new LinkedList("a", "c", "h, "d"); //1
list.append("e"); //2
list.insertAfter("default", "b"); //3
list.advanceIterator("default"); //4
list.removeIterators("default"); //5
list.addIterators("newOne", "newTwo"); //6
list.advanceIterator("newOne", 4); //7
list.splice("default", 0, "f", "g"); //8
trace(list.conjoinData("|")); //9
//1. automatically creates a default iterator in it's internal hashmap, with a key name of "default". Since you'll often only need one iterator, this saves you creating one. It starts off pointing to the head.
//2. appends "e" to the end of the list without moving "default" iterator
//3. inserts "b" after "default" iterator, which is currently sitting on "a" (the head)
//4. is now pointing to "b"
//5. just for fun, delete the original iterator
//6. and replace it with two new iterators (positioned at head, of course)
//7. iterator "newOne" is now pointing to "e"
//8. without deleting anything (hence zero), splice "f" and "g" into the list at the current position.
//9. trace the final result.
Output:
a|b|c|d|e|f|g

I’d say I’m probably refactoring Mike’s work away from efficiency and back towards safe usability. I have not tested my version for performance although as far as I can see the time-crucial parts of the code are mostly unchanged, but this means there is a possibility that I’ve slowed it down. What can I say, he’s provided a pretty good base of structures to work from. I’ve seen some of his other work and his calibre as a programmer clearly exceeds mine by a considerable margin. So it makes me wonder at the reasons for his setting up the Linked Lists in this way. Was it all about optimisation, or was some of this design poorly thought out? In particular, the list-is-invalidated-but-not-removed problem, and other small things like having a remove() function on an iterator (which should access a list, not modify it). Can anyone clarify why these design decisions were made? I’d be interested to listen and learn. I’m fine with that though, it’s a worthwhile tradeoff in the context of my present project.