I had a dream I was making computer animation of dancing napkin-holders set to a song I know is dave_brubeck_4.mp3 in my playlist but I forget the title of the song and also the CD it came from.
Here's an algorithmic problem: (It's based on my understanding of the Flash stacking model, which may be incorrect) As far as I understand it, Flash requires you to specify a number for every visible thing in a given "movie clip" so it knows in what order to draw them. Things with higher numbers get drawn in front of things with lower numbers. If you're concerned about creating lots of things dynamically, you might want the ability to efficiently insert something between two existing objects in the stacking order. Apparently you can't necessarily do this without potentially having to shift up O(n) many things each up to a higher number. Surely you could do some heuristic things like trying to make sure all the objects start out 10 units apart in the stacking order (like I remember doing with BASIC line numbers back in like 198X) so there's likely to be some slack in between them, but an adversarial insert order could easy force you to move at least something around in O(log(g)) where g is the size of the largest gap.
So here's the specification I have in mind:
Make a data structure that maintains a mapping f from a set S to the integers (including negative) that satisfies:
* there exists a constant k such that at any time kn > maxs in S |f(s)|
* insertion of a new element s into S together with a request of "just above s'" or "just below s'" for some other s' in S, is efficient, like amortized O(log n) or better. The numbers that the elements of S are mapped to may change, but the relative order of all the old ones must remain the same, and the relative order of the new one must match the request.
* deletion is also efficient, but I don't expect this to be too hard.
I have some divide-and-conquer rebalance-when-necessary approach that I think has amortized O(log n) insertion, but I'm really rusty with this style of proof. I keep winding up with O(log2 n) half the time I work the calculation.