Update: Sorting Target XML Node Sets In ColdFusion XML Documents
Ok, so last week, I was having some issues sorting target XML node sets in ColdFusion XML documents. I created a user defined function that would sort nodes given a parent node, but that never sat well with me; unfortunately, I didn't know how to fix it so that a target node set could be given rather than a parent node reference. Then, yesterday, Adam Cameron and Justin Carter suggested that if I use Duplicate() when copying XML node references, I won't create pointer-conflicts.
With this new information in hand, I re-tooled my XmlSort() ColdFusion user defined function to work using the XPath of a target node set rather than a parent node reference:
| <!--- Create a ColdFusion XML document. ---> | |
| <cfxml variable="xmlData"> | |
| <toes> | |
| <toe id="1"> | |
| <cuteness>5</cuteness> | |
| </toe> | |
| <toe id="2"> | |
| <cuteness>8</cuteness> | |
| </toe> | |
| <toe id="3"> | |
| <cuteness>2</cuteness> | |
| </toe> | |
| <toe id="4"> | |
| <cuteness>8</cuteness> | |
| </toe> | |
| <toe id="5"> | |
| <cuteness>10</cuteness> | |
| </toe> | |
| </toes> | |
| </cfxml> | |
| <!--- Create sorting values. ---> | |
| <cfset arrSorting = [ | |
| "cuteness", | |
| "@id" | |
| ] /> | |
| <!--- Sort TOE nodes with cuteness descending. ---> | |
| <cfset xmlData = XmlSort2( | |
| xmlData, | |
| "//toe", | |
| arrSorting, | |
| "DESC" | |
| ) /> | |
| <!--- Dump out resultant XML. ---> | |
| <cfdump | |
| var="#xmlData#" | |
| label="Xml In Cutness DESC Order." | |
| /> |
Notice here that I want to sort the "toe" nodes; so, rather than passing it a "toes" (parent node) XPath, I pass in the reference to the actual target node set:
"//toe"
Then, the sorting paths are relative to each node of the target node set:
| <!--- Create sorting values. ---> | |
| <cfset arrSorting = [ | |
| "cuteness", | |
| "@id" | |
| ] /> |
This makes my very happy since now the target XPath and the sorting XPath are each relative to the target node set and NOT to the parent node. This is the kind of uniformity that I wanted in the original XmlSort() attempt but was not smart enough to figure out.
When I run the above code, I get the following output:
As you can see, the XML nodes are sorted in descending order according to the XmlText of the "cuteness" node. Notice also that in the case where the two toes have the same cuteness, the deciding factor is the second sort option, the ID attribute of the toe node.
Sweet, it worked! Ok, it worked, but the UDF for this is not exactly pretty; it's long and convoluted, but it gets the job done:
| <cffunction | |
| name="XmlSort2" | |
| access="public" | |
| returntype="xml" | |
| output="true" | |
| hint="I sort part of an XML documument based on the given XPath and sort characteristics."> | |
| <!--- Define arguments. ---> | |
| <cfargument | |
| name="Xml" | |
| type="any" | |
| required="true" | |
| hint="I am an XML string or ColdFusion XML document." | |
| /> | |
| <cfargument | |
| name="XPath" | |
| type="string" | |
| required="true" | |
| hint="I am the XPath to the target node set." /> | |
| <cfargument | |
| name="SortXPath" | |
| type="any" | |
| required="false" | |
| default="text()" | |
| hint="I am the XPath value upon which the sort is being conducted. This can be a string or an array (if multiple sorting options are required)." | |
| /> | |
| <cfargument | |
| name="Direction" | |
| type="string" | |
| required="false" | |
| default="ASC" | |
| hint="I am the sort direction. ASC or DESC." | |
| /> | |
| <!--- Define the local scope. ---> | |
| <cfset var LOCAL = {} /> | |
| <!--- | |
| Check to see if our XML document is an Xml document. | |
| If is not, then we want to convert it into a true | |
| ColdFusion XML document. | |
| ---> | |
| <cfif NOT IsXmlDoc( ARGUMENTS.Xml )> | |
| <!--- Convert to an XML document. ---> | |
| <cfset ARGUMENTS.Xml = XmlParse( | |
| Trim( ARGUMENTS.Xml ) | |
| ) /> | |
| </cfif> | |
| <!--- | |
| Check to see if the given sorting option is a string or | |
| an array. If it's a string, then let's convert it to an | |
| array so that we can treat it uniformily later on. | |
| ---> | |
| <cfif IsSimpleValue( ARGUMENTS.SortXPath )> | |
| <!--- | |
| We need to copy this to get around a bug in the way | |
| ColdFusion handles implicit array creation involving | |
| its own values. | |
| ---> | |
| <cfset LOCAL.SortCopy = ARGUMENTS.SortXPath /> | |
| <!--- Convert simple value to an array. ---> | |
| <cfset ARGUMENTS.SortXPath = [ LOCAL.SortCopy ] /> | |
| </cfif> | |
| <!--- Get the set of target nodes. ---> | |
| <cfset LOCAL.TargetNodes = XmlSearch( | |
| ARGUMENTS.Xml, | |
| ARGUMENTS.XPath | |
| ) /> | |
| <!--- | |
| Check to make sure we have target nodes. If not, | |
| then just return the original XML. | |
| ---> | |
| <cfif (ArrayLen( LOCAL.TargetNodes ) LT 2)> | |
| <cfreturn ARGUMENTS.Xml /> | |
| </cfif> | |
| <!--- | |
| ASSERT: At this point, we know that we have a valid | |
| set of target nodes that can be sorted. | |
| ---> | |
| <!--- Perform bubble sort on target nodes. ---> | |
| <cfloop | |
| index="LOCAL.EndIndex" | |
| from="#(ArrayLen( LOCAL.TargetNodes ) - 1)#" | |
| to="1" | |
| step="-1"> | |
| <!--- | |
| Loop over nodes starting at 1 and then proceeding | |
| until we reach the "end index". This way, we will | |
| not duplicate our comparison of the last value. | |
| ---> | |
| <cfloop | |
| index="LOCAL.Index" | |
| from="1" | |
| to="#LOCAL.EndIndex#" | |
| step="1"> | |
| <!--- Get the two target nodes. ---> | |
| <cfset LOCAL.NodeOne = LOCAL.TargetNodes[ LOCAL.Index ] /> | |
| <cfset LOCAL.NodeTwo = LOCAL.TargetNodes[ LOCAL.Index + 1 ] /> | |
| <!--- | |
| Now that we have the two target nodes, we have | |
| to sort them based on the array of comparison | |
| values. We only need to proceed through the | |
| comparisons if the previous comparison is equal. | |
| ---> | |
| <cfloop | |
| index="LOCAL.SortXPath" | |
| array="#ARGUMENTS.SortXPath#"> | |
| <!--- Get the comparison value for given node. ---> | |
| <cfset LOCAL.ValueOne = XmlSearch( | |
| LOCAL.NodeOne, | |
| LOCAL.SortXPath | |
| ) /> | |
| <!--- Get the comparison value for next node. ---> | |
| <cfset LOCAL.ValueTwo = XmlSearch( | |
| LOCAL.NodeTwo, | |
| LOCAL.SortXPath | |
| ) /> | |
| <!--- | |
| Now, we have to get our values down to | |
| something that is usable. If this is a node, | |
| then get the text value. If this is an | |
| attribute then get the attribute value. | |
| ---> | |
| <cfif StructKeyExists( | |
| LOCAL.ValueOne[ 1 ], | |
| "XmlText" | |
| )> | |
| <!--- Get node text. ---> | |
| <cfset LOCAL.ValueOne = LOCAL.ValueOne[ 1 ].XmlText /> | |
| <cfset LOCAL.ValueTwo = LOCAL.ValueTwo[ 1 ].XmlText /> | |
| <cfelse> | |
| <!--- Get attribute value. ---> | |
| <cfset LOCAL.ValueOne = LOCAL.ValueOne[ 1 ].XmlValue /> | |
| <cfset LOCAL.ValueTwo = LOCAL.ValueTwo[ 1 ].XmlValue /> | |
| </cfif> | |
| <!--- | |
| Check to see if these two values are equal. | |
| If they are, then we just want to proceed | |
| to the next sorting condition. It is only if | |
| they are unequal that we can take action. | |
| ---> | |
| <cfif (LOCAL.ValueOne NEQ LOCAL.ValueTwo)> | |
| <!--- | |
| Check to see which direction we are | |
| sorting in. | |
| ---> | |
| <cfif ( | |
| ( | |
| (ARGUMENTS.Direction EQ "ASC") AND | |
| (LOCAL.ValueOne GT LOCAL.ValueTwo) | |
| ) OR | |
| ( | |
| (ARGUMENTS.Direction EQ "DESC") AND | |
| (LOCAL.ValueOne LT LOCAL.ValueTwo) | |
| ))> | |
| <!--- Swap nodes. ---> | |
| <cfset ArraySwap( | |
| LOCAL.TargetNodes, | |
| LOCAL.Index, | |
| (LOCAL.Index + 1) | |
| ) /> | |
| </cfif> | |
| <!--- | |
| Break out of the comparison sub-loop | |
| since we found two values which are | |
| not equal. | |
| ---> | |
| <cfbreak /> | |
| </cfif> | |
| </cfloop> | |
| </cfloop> | |
| <!--- END: Comparison loop. ---> | |
| </cfloop> | |
| <!--- END: Outer loop. ---> | |
| <!--- | |
| ASSERT: At this point our disconnected set of target nodes | |
| is in the appropriate sort order. | |
| ---> | |
| <!--- | |
| Before we do anything, we need to set up a unique ID for | |
| each XML node. This way, as we go through and compare | |
| them, we can make unique comparisons. This is utilitarian | |
| and will have to be removed afterwards. | |
| ---> | |
| <cfloop | |
| index="LOCAL.TargetNode" | |
| array="#LOCAL.TargetNodes#"> | |
| <!--- | |
| Set unique ID. Use a function name space to make | |
| sure we don't have have and attribute conflicts. | |
| ---> | |
| <cfset LOCAL.TargetNode.XmlAttributes[ "XmlSort:UUID" ] = CreateUUID() /> | |
| </cfloop> | |
| <!--- | |
| Now, it's time to take that set of nodes and apply the | |
| order to the XML document. Because we don't know the | |
| placement within the existing document, we need to | |
| iterate over the parent node and check for matches. | |
| ---> | |
| <cfset LOCAL.ParentNode = XmlSearch( | |
| LOCAL.TargetNodes[ 1 ], | |
| ".." | |
| ) /> | |
| <!--- Get the parent node from the returned node set. ---> | |
| <cfset LOCAL.ParentNode = LOCAL.ParentNode[ 1 ] /> | |
| <!--- | |
| As we replace our children, we need to keep a pointer | |
| to the index of the child we are replacing INTO the | |
| existing document. As we go along, this will help us | |
| to keep track since we don't know what order the matching | |
| nodes are going to show up in. | |
| ---> | |
| <cfset LOCAL.ReplaceIndex = 1 /> | |
| <!--- Loop over the xml children. ---> | |
| <cfloop | |
| index="LOCAL.ChildIndex" | |
| from="1" | |
| to="#ArrayLen( LOCAL.ParentNode.XmlChildren )#" | |
| step="1"> | |
| <!--- | |
| Check to see if this node is one of the nodes in | |
| our target node set. | |
| ---> | |
| <cfloop | |
| index="LOCAL.TargetNode" | |
| array="#LOCAL.TargetNodes#"> | |
| <!--- | |
| Check to see if this target node is the child | |
| node that we are currently examining. When | |
| comparing, make sure that the child node actually | |
| has the sorting UUID. | |
| ---> | |
| <cfif ( | |
| StructKeyExists( LOCAL.ParentNode.XmlChildren[ LOCAL.ChildIndex ].XmlAttributes, "XmlSort:UUID" ) AND | |
| (LOCAL.ParentNode.XmlChildren[ LOCAL.ChildIndex ].XmlAttributes[ "XmlSort:UUID" ] EQ LOCAL.TargetNode.XmlAttributes[ "XmlSort:UUID" ]) | |
| )> | |
| <!--- | |
| The current child IS in our target node set. | |
| That means that we can replace in one of our | |
| target nodes in this child index. Use the | |
| current index of replacement to select the | |
| target node. | |
| Use the post-incrementer to make sure that the | |
| replce index is upped after we copy over the | |
| taret node. | |
| Use Duplicate() so that we don't mess up our | |
| node references and accidentally delete one | |
| of the nodes from the parent document. | |
| ---> | |
| <cfset LOCAL.ParentNode.XmlChildren[ LOCAL.ChildIndex ] = Duplicate( LOCAL.TargetNodes[ LOCAL.ReplaceIndex++ ] ) /> | |
| <!--- Remove the UUID. ---> | |
| <cfset StructDelete( | |
| LOCAL.ParentNode.XmlChildren[ LOCAL.ChildIndex ].XmlAttributes, | |
| "XmlSort:UUID" | |
| ) /> | |
| <!--- | |
| We matched a node - no need to keep checking | |
| for a match in our taret node set (there | |
| should be a one-to-one match). | |
| ---> | |
| <cfbreak /> | |
| </cfif> | |
| </cfloop> | |
| </cfloop> | |
| <!--- Return the updated XML document. ---> | |
| <cfreturn ARGUMENTS.Xml /> | |
| </cffunction> |
It's not pretty, but at least the arguments are much more appropriate.
Want to use code from this post? Check out the license.
Reader Comments
I didn't quite finish reading the new function code. Kudos for making it work without the parent reference. :)
Thought I'd throw in a couple of hints. First if you're not already familiar with it, there's a "quick sort" algorithm that may be faster than the bubble sort here -- there's a quicksort function on cflib with the code for doing that. Second, I don't think you need local.sortcopy near the top, I'm pretty sure you can do that in one line like this:
<cfset ARGUMENTS.SortXPath = [ ARGUMENTS.SortXPath ] />
@Ike,
I'll take a look at the quicker sorting algorithm; bubble sort is the only one I can remember from my Algorithms class 8 years ago :) Plus, it took me 3 mugs of tea just to get through the rest of this method!
Making something an implicit struct (or array) of itself should work, but unfortunately causes a strange bug in ColdFusion:
www.bennadel.com/index.cfm?dax=blog:1237.view
I am not 100% comfortable having to modify the XML nodes during the sorting algorithm, but as I am using a name-space to the method, I am not too worried about it.
What I am happy about in this method is that the target nodes can be mixed in with other nodes. In my previous attempts, the entire childNode set was ordered; in this one, only the target nodes get ordered regardless of where they are.
@Ike,
Just took a look at the Quick Sort algorithm. That's a tough one to visualize.
Yeah, I try not to visualize it. :P Basically, you just need a small piece that can order 2 items (as opposed to the entire set) and then you feed that into the quick sort algorithm and let it do its own thing. Like "Sue and Harry... Sue is taller, she's first". :)
That is a bizarre error... It's supposed to be a "nameless" array until it passes the equal sign, at which point it should reset the pointer, irrespective of what it was before... Oops! Somebody wasn't too careful with their encapsulation.
@Ike,
Yeah, same thing happens if you try to go from simple value to implicit struct as well.
The one thing that I'm not digging about the Quick Sort is that I need two functions just to do the sort plus whatever function is actually tying it all together. While the bubble sort may be slower, the benefit is that it is all contained within the target function.
Now, if ColdFusion had headless (anonymous) functions like Javascript, then we'd be in a different ball game :)
Well you only need a 2nd function if you're planning to use it the way the one on cflib was written. If you're okay with reproducing the quick sort code, then you can just swap out the dependency on the ternary function for having your ternary logic in-line. Yeah, it's liable to be more complex and ultimately it may not matter much given that we're talking about xml nodes and the size of the array may never really get large enough that you'd notice the difference. I just figured I'd throw it out there. :)
@Ike,
Thanks for the reality check :) It's true, we sometimes get caught up (as developers) in the theory of computer science and we forget that our universe of sortable sets will probably not be very large at all.
Still, I appreciate you pointing out the alternate sorting as its good to have in the bag.
Welcome. Yeah, I had put the quicksort function into the onTap framework libraries, so I end up using it as kind of a generic go-to when (not often) I do sorting because my stuff is all DLL-like that way. :)