Spike
Matt Liotta wrote:
Using a UUID would be overkill to represent individual nodes in a taxonomy and would likely result in poor performance for any complex taxonomy. I have found the easiest way to uniquely identify taxonomy nodes is with a hash that is the concatenation of the node's parent with that of the node's sequence. Of course, most taxonomies don't require their nodes to be sequenced in any way. Further, using this technique allows you to represent both the unique node and its relationship to the taxonomy with a single identifier.
For example, let's assume that your taxonomy looks as follows (ASCII drawing).
foobar | --foo --bar | --anything | --something --blah
I could represent the above with the following key map.
foobar: a foo: aa bar: ab anything: aba something: abaa blah: ac
In the above map I have used a simple single letter hash to represent each iteration in a sequence. Thus, bar's key is "a" (the parent's key) & "b" (the second iteration of foobar's child sequence). Assuming each iteration can only be a single lowercase letter then the above technique allows for a total of 26 children per parent. Of course, there needs to be a constraint on the size of the key length. If you limited the key length to 20 characters then it would give you a total of 520 (26 x 20) nodes. However, that would limit the width of the taxonomy because it would only support 20 generations. I point this out only to give you any idea how each constraint can effect both the width and height of the taxonomy as knowing this is important for selecting the correct hash technique. For example, if each iteration was represented by a single letter of any case and you limited the key length to 10 then you would have the same number of possible nodes 520 (52 x 10) allowing for a total of 52 children per parent, but you could only have 10 generations.
I don't know whether your taxonomy is tall or wide, so I can't recommend a specific hash technique. Although, I can explain how to implement something like the above example. First though, a few additional points on the above key stratergy.
1. A node's generation can be determined by moding its length against the sequence length i.e. a node of length 3 is third generation because 3 % 1 is 3.
2. All descendants of a node can be found by finding all keys that begin with its key.
3. A node's parent is simply its key minus its sequence character i.e. Left(key, Len(key) - 1).
With that in mind below is a quick (read untested) UDF to create a new node in the taxonomy and return its assigned key using the above technique. This is not quality code, but it should explain what you need to know.
<cffunction name="addNode" returntype="string"> <cfargument name="taxonomy" type="struct" required="true"> <cfargument name="parentKey" type="string" required="true"> <cfargument name="node" type="struct" required="true"> <cfset var count = 0> <cfset var nodeKey = ""> <cfloop collection="#arguments.taxonomy#" item="key"> <cfif Left(key, Len(arguments.key) eq arguments.key)> <cfset count = count + 1> </cfif> </cfloop> <cfset nodeKey = arguments.parentKey & Chr(97 + count)> <cfset taxonomy[nodeKey] = arguments.node> <cfreturn nodeKey> </cffunction>
-Matt
On Saturday, June 14, 2003, at 04:45 PM, Sean A Corfield wrote:
On Saturday, Jun 14, 2003, at 00:53 US/Pacific, Scott Barnes wrote:
ooooooh, i knew it was something quirky that was doing it wasn't sure what it exactly.
Don't fret... it took me quite a while to debug it (in between sessions at JavaOne!).
I need a shorter key system, if i use CreateUUID() it basically puts the +13 when I convert the structure to a query :) for sorting purposes.
I'm not sure what you mean "puts the +13 when I convert the structure to a query for sorting purposes" - can you explain how you're trying to use this and why you can't just have a longer key (a UUID)?
Sean A Corfield -- http://www.corfield.org/blog/
"If you're not annoying somebody, you're not really alive." -- Margaret Atwood
----------------------------------------------------------
You are subscribed to cfcdev. To unsubscribe, send an email
to [EMAIL PROTECTED] with the word 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
----------------------------------------------------------
You are subscribed to cfcdev. To unsubscribe, send an email
to [EMAIL PROTECTED] with the word 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
----------------------------------------------------------
You are subscribed to cfcdev. To unsubscribe, send an email
to [EMAIL PROTECTED] with the word 'unsubscribe cfcdev' in the message of the email.
CFCDev is run by CFCZone (www.cfczone.org) and supported by Mindtool, Corporation (www.mindtool.com).
