1. Messages
  2. Data structures and user interaction conundrum

Re: Data structures and user interaction conundrum

Graham Cox
 

Thanks to everyone who chipped in so far — interesting ideas.

The zOrder is in fact a float (CGFloat, so 64 bit), but as Jens points out, it can’t go on indefinitely.

In experimenting with this, it turns out that limiting the reordering to just the objects that are visually intersected is a really, really nice behaviour from the user’s perspective. It means that every operation has a visible effect, rather than appearing to do nothing in the cases where you are reordering relative to an object some distance away. I believe from a usability perspective this is a good solution. I may add “global” reordering as an option, assuming I can find a solution I like. The trie idea is interesting, but possibly overkill for the feature… and tbh, learning enough about tries to implement one correctly is probably going to take more time than I’m willing to spend. Though I notice there is a class in Core Foundation - CFBurstTrie - that might fit the bill (not sure if it has a public interface however, seems it may be something private).

Regarding running out of precision when ’splitting the difference’ when reordering, the reality is that this is an uncommon operation in terms of sheer numbers. It probably comes up moderately frequently, but my feeling is that it would be unlikely to run out of numbers in most cases. Of course that’s not good enough - it means a potential bug in the limit when things don’t work as they should. But occasionally renumbering the whole stack is likely to work to solve that, and that can be done when the model is built or saved. Or Jens’ idea of using strings could work for reordering, but may be too slow to sort on that order for drawing (which is my main priority - drawing has to be fast). With local reordering, zOrder value clashes inevitably do occur, because objects further away are just not considered while the local renumbering is performed. Again, that doesn’t matter too much because nothing critical rests on this (unlike Jens’ To Do list example), the only time it would reveal itself is if the user drags an object across the canvas and it gets occluded by something and they didn’t expect that. But in an interactive drawing environment, I'd suggest that doesn’t especially matter - they can simply reorder as necessary in that new local area to get the visual result they want.


—Graham




On 24 Jul 2020, at 5:11 am, Jens Alfke <jens@...> wrote:



On Jul 22, 2020, at 7:19 PM, Peter Teeson via groups.io <pteeson@...> wrote:

Are the zObjects integers? If so would it help to make them floats? Intial value 3.0; Back one 2.9  or 2.09; Forward one 3.1 or 3.01?

Sadly, this only postpones the problem — you run out of precision after a while. A  64-bit double only has about 52 bits of mantissa, meaning that some sequences of 52 reorders will cause a collision between adjacent Z values.

I've actually seen this exact problem in other domains — usually having to do with distributed algorithms for preserving ordering, as in a collaborative to-do list with offline support. IIRC it also shows up in some P2P distributed hash tables like Chord and Kademlia.

A workable way to do this is to use strings, since you never run out of room. So the initial objects are labeled A, B, C, D… When you need to put an object in between C and D, you label it CM. When something has to go between CM and D, you label it CS. Eventually you have to fit something between CR and CS, so you label it CRM. (In a real implementation you'd probably use bit-strings instead. Which you can also interpret as fractional binary numbers … exactly like your suggestion except using infinite precision instead of floating point.)

The eventual problem is that over time the Z labels get longer and longer. Probably not an issue for a graphics editor? The usual solution is to occasionally renumber everything with short strings, perhaps when saving.

This is probably equivalent to David Young's radix-trie suggestion … the trie is a more complex data structure than a sorted array, but performs better. Sliding a mere 25,000 pointers around in an array shouldn't take a noticeable amount of time, though (it's only 200KB) provided you only do it once per user command. (And actually, I believe NSArray already turns into something more tree-like when the count grows large, to make inserts/deletes faster.)

—Jens
Join {cocoa@apple-dev.groups.io to automatically receive all group messages.