MIURON@lure.latrobe.edu.au (12/12/90)
I have been trying to develop a sort routine which utilizes a binary tree sort with dynamic variables. I have managed this to some extent. I can sort on two keys using a two recursive procedures; one creates a binary tree which sorts on the first key, and the second binary tree called from within the first procedure to sort on the second key. What I have works, but I don't want to limit myself to only two keys. I would like the program to accept any number of keys. I can't help thinking that recursion is the answer, but I have already turned my brain inside out getting to this stage. If anyone knows of a routine which might be close to what I want I'd appreciate you contacting me. Ron Crichton
CDCKAB%EMUVM1.BITNET@cunyvm.cuny.edu ( Karl Brendel) (12/19/90)
In article 4892@lure.latrobe.edu.au, MIURON@lure.latrobe.edu.au (Ron Crichton) wrote: >I have been trying to develop a sort routine which utilizes a binary >tree sort with dynamic variables. I have managed this to some >extent. I can sort on two keys using a two recursive procedures; >one creates a binary tree which sorts on the first key, and the >second binary tree called from within the first procedure to sort on >the second key. > >What I have works, but I don't want to limit myself to only two >keys. I would like the program to accept any number of keys. I >can't help thinking that recursion is the answer, but I have already >turned my brain inside out getting to this stage. If anyone knows >of a routine which might be close to what I want I'd appreciate you >contacting me. Are you saying that you want to create two trees which contain the same nodes but built on different keys? Or that you want one tree which orders the nodes in a primary key/secondary key order? In either case, I think you would use a single tree-building routine. In the first case just call the routine twice with a starting node and the appropriate compare function. In the second case just call the routine once and put the knowledge of the keys into the compare function. You can do that several ways, among which are: Write separate compare functions as required for each key, then pass an array or list of pointers to those functions to the main compare function. Pseudocode could look something like: function compare(node1, node2, compareFunctionArray); var result : compareType; i := 0; while compareFunctionArray[i] <> nil do result := compareFunctionArray[i]^(node1, node2); if result <> compareEqual then return result; i := i+1; end while return compareEqual; end compare; If the nodes can be treated strictly as arrays of char or byte, then you can use a single compare function that operates on arbitrary arrays of that type, and pass it a list or array of records that specify the starting and ending bytes of each key and the order in which sorting on that key is to take place. Again, pseudocode: type node = record case byte of 1 : name, number = array[1..10]of char; 2 : all = array[1..20]of char; end; sortSpec = record start, stop : byte; ascending : Boolean; end; function compare(node1, node2, sortSpec_array); function compareAOC(a1, a2); if a1 > a2 then return compareGreaterThan; if a1 < a2 then return compareLessThan; return compareEqual; end compareAOC; var result : compareType; i := 0; while not ((sortSpec_array[i].start = 0) and (sortSpec_array[i].stop = 0)) do result := compareAOC(a1); if result <> compareEqual then begin if sortSpec_array[i].ascending then return result; if result = compareGreaterThan then return compareLessThan; end if; i := i+1; end while; return compareEqual; end compare; +--------------------------------------------------------------------+ | Karl Brendel Centers for Disease Control | | Internet: CDCKAB@EMUVM1.BITNET Epidemiology Program Office | | Bitnet: CDCKAB@EMUVM1 Atlanta, GA, USA | | Home of Epi Info 5.0 | +--------------------------------------------------------------------+