Sorting Pages in QuarkXPress: A Constrained Approach

[ktoz]

Hi

I have a sorting problem I haven't been able to solve and was hoping someone here could lend some insights.

The basic problem is resorting pages in a page layout application (QuarkXPress) where I'm constrained to only the functions Quark supplies for moving pages around in a document. Basically all I can do is place a page before or after another page. I have no access to the internal data structure so can't just grab the page array and swap pointers.

The difficulty arises when I perform an insert before/after a page, the indexes for everything after the insert changes which requires recomputing the entire array (at least in my very inefficient efforts thus far) and I'd like to come up with something a bit more elegant.

Here is the problem space

- Quark native page array with no access to it's elements or structure. The only known about this array is that pages are accessed by one based index using an accessor function.
- An unordered associative array (an Object-C http://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSDictionary_Class/Reference/Reference.html") where array keys are the unique page id stored in a database. The database and NSDictionary are mine and are not part of Quark. I use them to provide direct access to a page without having to search the entire array in a loop.
- The only Quark manipulation functions available are insert before/insert after.
- I would like any solution to use only one of the insert before/insert after functions so as to keep it simple and automatic.

With those in mind, here is a concrete example:

Say there is an array of 4 pages (1 thru 4) sorted correctly and the user renumbers page 2 to page 10

initial page sort: 
[1, 2, 3, 4]

initial associative array (NSDictionary) : 
{ 
	754: {
			id: 754, 
			number: 1,
			ads: {}, 
			images: {}, 
			stories: {}
		}, 
	755: {
			id: 755, 
			number: 2,
			ads: {}, 
			images: {}, 
			stories: {}
		}, 
	756: {
			id: 756, 
			number: 3,
			ads: {}, 
			images: {}, 
			stories: {}
		}, 
	757: {
			id: 757, 
			number: 4,
			ads: {}, 
			images: {}, 
			stories: {}
		}
}

User renumbers page 2

Quark order before resort: [1, [COLOR="red"]10[/COLOR], 3, 4]
NSDictionary after renumbering: 
{ 
	754: {
			id: 754, 
			number: 1,
			ads: {}, 
			images: {}, 
			stories: {}
		}, 
	755: {
			id: 755, 
			[COLOR="Red"]number: 10,[/COLOR]
			ads: {}, 
			images: {}, 
			stories: {}
		}, 
	756: {
			id: 756, 
			number: 3,
			ads: {}, 
			images: {}, 
			stories: {}
		}, 
	757: {
			id: 757, 
			number: 4,
			ads: {}, 
			images: {}, 
			stories: {}
		}
}

Sorted key array:
[754, 756, 757, [COLOR="Red"]755[/COLOR]]

Since the NSDictionary is mine, I'm free to do key sorts using standard sorting functions and can use this array as reference for sorting the Quark pages. Keep in mind that the actual NSDictionary itself is not resorted though. I can create arrays of sorted keys, but for efficiency sake, the dictionary preserves it's initial order.

Now using only "insert before" or "insert after" (but not both) resort the page array to match the order found in the key array.

This may actually be relatively easy but I've developed a brain block and haven't been able to figure it out. Any help greatly appreciated

 

[rcgldr]

I'm confused, somewhere in the process it would seem you'd need a delete for every insert, else the pages would just get duplicated. Given this, you could then implement a "swap" function, to swap two pages in the array, which would only affect the indexes during each swap operation.

 

[Hurkyl]

The first and most important question -- does this even matter? Does this sorting routine actually consume so many resources that it deserves to be optimized? (or alternatively, is this exercise intended for entertainment value?)


Anyways, I note that a quicksort moves pages around in a very predictable fashion -- you shouldn't have to recompute anything: any time you come to a page, you should just know how far it's moved from its original location. Mergesort may also share this quality.

Or, think outside the box: can you remove pages from the document? Maybe you can put them into your own handcrafted page array, and then put them back into the document. If you can't do this directly, can you move a page from one document into another? Then you could create new documents to serve that purpose.

 

[ktoz]

The first and most important question -- does this even matter? Does this sorting routine actually consume so many resources that it deserves to be optimized? (or alternatively, is this exercise intended for entertainment value?)

It's not an exercise. I need this for a real Quark plugin. The actual sort probably doesn't consume many resources, it's just that all my efforts have produced really strange results, pages sorted in ways that are hard to unravel.

Anyways, I note that a quicksort moves pages around in a very predictable fashion -- you shouldn't have to recompute anything: any time you come to a page, you should just know how far it's moved from its original location. Mergesort may also share this quality.

But I don't know. Quark seems to maintain it's own internal indexing list and any time you swap two pages, this internal list gets invalidated and you have to start at the beginning and reset all the indexes for each page. I may have this wrong, but as I said, I have a brain block on this one...

Or, think outside the box: can you remove pages from the document? Maybe you can put them into your own handcrafted page array, and then put them back into the document. If you can't do this directly, can you move a page from one document into another? Then you could create new documents to serve that purpose.

Not realistic. Pages can have links to other pages (Think of a newspaper where a story can jump to another page) so removing a page requires unlinking one or several stories, remembering which box on which page it jumped to and relinking etc. Not to mention that there are lots of large resources on a page (photos, graphics, ads) that can make copying the entire page very resource intensive.

As so often happens, the act of clarifying the problem for a post, has helped me see where the algorithm is messing up. It comes from using Quark's "renumber page" function. If I don't renumber the page, the following algorithm works perfectly

The actual Quark function is under NDA so here's an a fake function witrh the same arguments

QuarkNDAMovePageFunction(layoutRefNum, moveStartIndex, moveEndIndex, destIndex, insertOption);

Here's my XTLayoutView class's sort method

- (void) sortPageViews
{
	int		layoutRefNum	= [self qxLayoutRef],
			maxIndex	= [pageViews count] - 1, // pageViews is my internal list of which pages a document contains
			swapCount	= 1,
			i;
						
	XTPageView	*pg1,
			*pg2;
						
	
	while (swapCount > 0)
	{
		swapCount	= 0;
		
		for (i = 0; i < maxIndex; i++)
		{
			// page indexes in array are i, i + 1 (zero based)
			pg1	= [pageViews objectAtIndex: i];
			pg2	= [pageViews objectAtIndex: i + 1];
			
			NSLog(@"comparing %hi with: %hi", [pg1 pageNumber], [pg2 pageNumber]);
			
			if ([pg1 pageNumber] > [pg2 pageNumber])
			{
				NSLog(@"swapping: %hi", [pg1 pageNumber], [pg2 pageNumber]);
				
				// move the pg1 to it's new location
				// page indexes in document are i + 1, i + 2 (1 based)
				QuarkNDAMovePageFunction(layoutRefNum, i + 1, i + 1, i + 2, INSERT_AFTER);
				
				// update the qxPageRefs (index) for both pages
				[pg1 setQXPageRef: i + 2];
				[pg2 setQXPageRef: i + 1];
				
				// swap elements in array
				[pageViews swapObject: pg1 withObject: pg2];
				
				// increment swapcount
				swapCount++;
			}
		}
	}
}

I think if I sort the pages and then make another pass renumbering them, it will be all better. I was just trying to make the renumbering concurrent with the sort and this was what got me so confused.