[Drawkit] Keeping objects sorted

[Graham Cox]

The guide layer doesn't require sorted guides for what it was designed  
to do, so you need to subclass it to keep the guides sorted. You can't  
sort an NSArray because it's immutable, but if you're subclassing,  
you'll notice that in fact the guide arrays are NSMutableArrays  
internally, so they can indeed be sorted "in place". You just need to  
use -sortUsingFunction:context: and write a short comparison function,  
e.g:

static int cmpGuidePositions (DKGuide* lh, DKGuide* rh, void *context)
{
	#pragma unused(context)
	
	float lp = [lh position];
	float rp = [rh position];
	
	if (lp < rp)
		return NSOrderedAscending;
	else if (lp > rp)
		return NSOrderedDescending;
	else
		return NSOrderedSame;
}


You can also sort drawables by position in a similar manner, either by  
subclassing the layer on which they live, or just implementing an  
external method in a suitable place. Bear in mind that the ordering of  
objects in a layer is actually their z-position or stacking order, so  
you would be forcing the x and z positions to be the same. You'd need  
to grab the objects into a mutable copy, sort them, then put them back  
(-setObjects:)

A much better alternative approach would be just to keep another list  
of objects sorted by x position, and leave the normal stuff "as is".  
Whenever you add an object to the layer, you'd also add it to your  
sorted list, and vice versa on removal. Additional lists of objects  
ordered in a different way is an efficient way to do things because a)  
the objects themselves are not copied, just retained, and the sorting  
of the additional list doesn't require any redrawing or other  
potentially time-consuming side effects to be triggered - it's your  
private list.

The drawback is making sure the lists are synchronised with respect to  
the objects they contain. Since there are a number of ways that  
objects can get added or removed from layers, a possible approach  
would be just to make a new copy of the list of objects every time  
that happened. The new notifications suggested by Linan Wang will ease  
this operation in the next version, but it's still doable in beta3 by  
various means. On balance I'd say subclassing DKObjectDrawingLayer is  
probably the best option, so you can simply override the various add/ 
remove methods to manage your sorted array, then call super for the  
normal stuff. The subclass would also own the sorted list so you can  
declare methods to simply get the sorted objects or even - 
objectNearestToTime: type stuff.

hth,

cheers, Graham

On 4 Jul 2008, at 4:06 am, James Maxwell wrote:

> Hi All,
>
> In my particular app, it would be really helpful if I could keep  
> drawn objects sorted by x position.
> Does anyone know a simple and straightforward way of doing that? For  
> example, I want my vertical guides to always be sorted by - 
> position:, so I can efficiently get the closest guide "before" or  
> "after" a particular object (this is a music app, so time runs left  
> to right). I also want to do this with my main drawing layer's  
> objects - keeping them ordered by x position (i.e., time). Is there  
> no simple way to sort an array, like m_vGuides, for example, "in- 
> place", without making a new sorted array and assigning it?