;========================================================================================================================================== ; How to sort a dim-2 array. ; ; Detlev Dalitz.20040326.20090519. ;========================================================================================================================================== ; ; The following described method may also be usable for multi-dimensional arrays. ; ; Example array: ; ; Data Array ; +-------+-------------+------------+---------+ ; | Array | Col 0 | Col 1 | Col 2 | ; | Index | (Firstname) | (Lastname) | (Age) | ; +-------+-------------+------------+---------+ ; | 0 | Micky | Mouse | 33 | ; | 1 | Daisy | Duck | 17 | ; | 2 | Carlo | Cat | 22 | ; | 3 | Lupo | Dog | 11 | ; | 4 | Dagobert | Duck | 66 | ; +-------+-------------+------------+---------+ ; ; This array has 5 rows and 3 columns, overall 15 elements. ; ; We want to sort it on each column separately (Firstname, Lastname, Age) ; and on a combination of two columns (Lastname + Firstname). ; ; WinBatch has _no_ built in support for sorting arrays at the time when this script was written. ; But there exist several attempts by the WinBatch community to do so. ; Indeed, those approaches in WinBatch native script code are focused on one-dimensional arrays. ; ; Today there are known two WinBatch extenders, built by Alan Kreutzer and Detlev Dalitz, ; supporting array functions, which can work with multi-dimensional arrays and can sort them. ; ; Here I describe a practical way to sort a dim-2 array using WinBatch native script code. ; ; ; To sort a multi-dim array we need a helper array. ; This helper array, better say pointer array, does not need to have more than one column. ; This one column is initialized with integer numbers representing the corresponding row index numbers. ; The number of rows in the pointer array is the same as in the multi-dim data array. ; Each cell in the pointer array points to the corresponding row in the dim-2 data array. ; ; Pointer Array Data Array ; +-------+-----------+ +-------+-------------+------------+---------+ ; | Array | Col 0 | | Array | Col 0 | Col 1 | Col 2 | ; | Index | (DataRow) | | Index | (Firstname) | (Lastname) | (Age) | ; +-------+-----------+ +-------+-------------+------------+---------+ ; | 0 | 0 | ==> | 0 | Micky | Mouse | 33 | ; | 1 | 1 | ==> | 1 | Daisy | Duck | 17 | ; | 2 | 2 | ==> | 2 | Carlo | Cat | 22 | ; | 3 | 3 | ==> | 3 | Lupo | Dog | 11 | ; | 4 | 4 | ==> | 4 | Dagobert | Duck | 66 | ; +-------+-----------+ +-------+-------------+------------+---------+ ; ; ; To sort the column 'Lastname' we have to create a relation between two elements ; that become true for all elements when the data array has been sorted. ; ; In other words, for ascending sorting we use the relation: ; 'second element must be greater than first element' ; i. e. 'Array [i + 1] > Array [i]'. ; ; Same situation from another point of view: ; We have to swap elements if the first element is greater than the second element. ; This is the sort relation that we use in the array sort routine, code looks like: ; 'If (arrData [arrPointer [intI], intSortCol] > arrData [arrPointer [intK], intSortCol]) Then swap (...)'. ; ; So we only have to compare elements from the column 'Lastname' and have to re-order ; the 'DataRow' elements in the pointer array accordingly. ; ; ; Pointer Array Data Array ; +-------+-----------+ +-------+-------------+------------+---------+ ; | Array | Col 0 | | Array | Col 0 | Col 1 | Col 2 | ; | Index | (DataRow) | | Index | (Firstname) | (Lastname) | (Age) | ; +-------+-----------+ +-------+-------------+------------+---------+ ; | 0 | 2 | ===\ | 0 | Micky | Mouse | 33 | ; | 1 | 3 | \ | 1 | Daisy | Duck | 17 | ; | 2 | 1 | \==> | 2 | Carlo | Cat | 22 | ; | 3 | 4 | ===\ | 3 | Lupo | Dog | 11 | ; | 4 | 0 | \===> | 4 | Dagobert | Duck | 66 | ; +-------+-----------+ +-------+-------------+------------+---------+ ; ; Now, after an ascending sort on Col 2 'Lastname', the elements of Pointer Array point ; to the rows from Data Array. ; ; ; In general we have access to the value of an array cell by directly addressing the ; cell using integer numbers, referencing the row and column where the cell is located. ; This direct addressing method of array cells is common known standard. ; ; Example: ; The cell in Row 2 Column 0 has the value 'Carlo'. ; x = Data [2, 0] ; ==> x = 'Carlo' ; ; ; For our purposes we have to implement an indirect addressing method ; by using the pointer array as an interface to the multi-dim array. ; ; In the first unsorted situation the above example looks like: ; x = Data [Pointer [2], 0] ; ==> x = 'Carlo' ; ; This will be calculated as: ; x = Data [2, 0] ; ==> x = 'Carlo' ; Because array cell Pointer [2] has the value '2', it addresses row 2 in data array. ; ; After sorting the data array by Column 1 (Lastname) the pointer array cell Pointer [2] ; has got the value '1'. ; x = Data [Pointer [2], 0] ; ==> x = 'Daisy' ; ; This will be calculated as: ; x = Data [1, 0] ; ==> x = 'Daisy' ; Because array cell Pointer [2] has the value '1', it addresses row 1 in data array. ; ; ; Following example code uses the Shell-Metzner sort algorithm, ; because it is easy to read and easy to understand. ; This sorting algorithm is efficient for sorting small and medium sized arrays (100..1000 elements). ;------------------------------------------------------------------------------------------------------------------------------------------ GoSub Script1 GoSub Script2 Exit ;========================================================================================================================================== ;========================================================================================================================================== :Script1 ;========================================================================================================================================== ; How to sort a 2-dim array ; Detlev Dalitz.20040326. ;========================================================================================================================================== ; Define arrays. intMaxRows = 5 intMaxCols = 3 arrData = ArrDimension (intMaxRows, intMaxCols) arrPointer = ArrDimension (intMaxRows) ;.......................................................................................................................................... ; Populate array arrData. arrData [0, 0] = "Micky" arrData [0, 1] = "Mouse" arrData [0, 2] = 33 arrData [1, 0] = "Dagobert" arrData [1, 1] = "Duck" arrData [1, 2] = 66 arrData [2, 0] = "Carlo" arrData [2, 1] = "Cat" arrData [2, 2] = 22 arrData [3, 0] = "Lupo" arrData [3, 1] = "Dog" arrData [3, 2] = 11 arrData [4, 0] = "Daisy" arrData [4, 1] = "Duck" arrData [4, 2] = 17 ;.......................................................................................................................................... ; Hint: See moving the location of 'Dagobert Duck'. ;.......................................................................................................................................... ; Display array unsorted. strMsgText = "Array not sorted" GoSub PointerInit GoSub ArrayDisplay ;.......................................................................................................................................... ; Do the sort on Column1 (Lastname). strMsgText = "Array sorted on Column1 (Lastname)" intSortCol = 1 strSortRelation = `arrData [arrPointer [intI], intSortCol] > arrData [arrPointer [intK], intSortCol]` GoSub PointerInit GoSub ArraySortShellMetzner GoSub ArrayDisplay ;.......................................................................................................................................... ; Do the sort on Column2 (Age). strMsgText = "Array sorted on Column2 (Age)" intSortCol = 2 strSortRelation = `arrData [arrPointer [intI], intSortCol] > arrData [arrPointer [intK], intSortCol]` GoSub PointerInit GoSub ArraySortShellMetzner GoSub ArrayDisplay ;.......................................................................................................................................... ; Do the sort on Column2 (Age) descending. strMsgText = "Array sorted on Column2 (Age) descending" intSortCol = 2 strSortRelation = `arrData [arrPointer [intI], intSortCol] < arrData [arrPointer [intK], intSortCol]` GoSub PointerInit GoSub ArraySortShellMetzner GoSub ArrayDisplay ;.......................................................................................................................................... ; Do the sort on Column1 + Column0 (Lastname + Firstname). strMsgText = "Array sorted on Column1 + Column0 (Lastname + Firstname)" strSortRelation = `StrCat (arrData [arrPointer [intI], 1], arrData [arrPointer [intI], 0]) > StrCat (arrData [arrPointer [intK], 1], arrData [arrPointer [intK], 0])` GoSub PointerInit GoSub ArraySortShellMetzner GoSub ArrayDisplay ;.......................................................................................................................................... ;========================================================================================================================================== Return ; from GoSub Script1. ;========================================================================================================================================== ;------------------------------------------------------------------------------------------------------------------------------------------ ; Script1 GoSub's ;------------------------------------------------------------------------------------------------------------------------------------------ :PointerInit ; Populate array arrPointer. intHigh = ArrInfo (arrPointer, 1) - 1 For intI = 0 To intHigh arrPointer [intI] = intI Next Drop (intHigh, intI) Return ;------------------------------------------------------------------------------------------------------------------------------------------ :ArraySortShellMetzner ; Shell-Metzner sort algorithm. intHigh = ArrInfo (arrData, 1) - 1 intLow = 0 intMid = (intHigh - intLow + 1) / 2 While intMid intTop = intHigh - intMid For intI = intLow To intTop intK = intI + intMid If %strSortRelation% arrP = arrPointer [intI] arrPointer [intI] = arrPointer [intK] arrPointer [intK] = arrP EndIf Next For intI = intTop To intLow By -1 intK = intI + intMid If %strSortRelation% arrP = arrPointer [intI] arrPointer [intI] = arrPointer [intK] arrPointer [intK] = arrP EndIf Next intMid = intMid / 2 EndWhile Drop (arrP, intHigh, intI, intK, intLow, intMid, intTop) Return ;------------------------------------------------------------------------------------------------------------------------------------------ :ArrayDisplay ; Read arrData sorted by arrPointer. intIHigh = ArrInfo (arrData, 1) - 1 intKHigh = ArrInfo (arrData, 2) - 1 strTable = "" For intI = 0 To intIHigh strRow = "" For intK = 0 To intKHigh If !!VarType (arrData [arrPointer [intI], intK]) strRow = StrCat (strRow, @TAB, arrData [arrPointer [intI], intK]) Else strRow = StrCat (strRow, @TAB) EndIf Next strTable = ItemInsert (StrSub (strRow, 2, -1), -1, strTable, @LF) Next AskItemlist (strMsgText, strTable, @LF, @UNSORTED, @SINGLE) Drop (intI, intHigh, intK, intKHigh, strRow, strTable) :CANCEL Return ;------------------------------------------------------------------------------------------------------------------------------------------ ;========================================================================================================================================== :Script2 ;========================================================================================================================================== ; How to sort a 2-dim array ; Detlev Dalitz.20040326. ;========================================================================================================================================== ; It is also possible to encapsulate the sort code into a WinBatch UDF User Defined Function, ; and pass the data array and the sort directives by parameters into the function. ; ; If the array has to be sorted only by one column, the UDF parameter interface can be rather simple: ; '#DefineFunction udfArraySortShellMetzner (arrData, intSortCol)' ; All other coding can be done hidden in the inner UDF. ; ; The UDF returns the sorted pointer array, for further access to the data array. ; In case the data array has no elements the UDF returns an empty pointer array. ;------------------------------------------------------------------------------------------------------------------------------------------ ;------------------------------------------------------------------------------------------------------------------------------------------ #DefineFunction udfArraySortShellMetzner (arrData, intSortCol) If !ArrInfo (arrData, -1) Then Return ArrDimension (0) If !ArrInfo (arrData, 6) Then Return arrData intDim1 = ArrInfo (arrData, 1) If !intDim1 Then Return arrData ; Populate array arrPointer. arrPointer = ArrDimension (intDim1) intHigh = ArrInfo (arrPointer, 1) - 1 For intI = 0 To intHigh arrPointer [intI] = intI Next Drop (intHigh, intI) ; Do the sort. intHigh = intDim1 - 1 intLow = 0 intMid = (intHigh - intLow + 1) / 2 While intMid intTop = intHigh - intMid For intI = intLow To intTop intK = intI + intMid If arrData [arrPointer [intI], intSortCol] > arrData [arrPointer [intK], intSortCol] intP = arrPointer [intI] arrPointer [intI] = arrPointer [intK] arrPointer [intK] = intP EndIf Next For intI = intTop To intLow By -1 intK = intI + intMid If arrData [arrPointer [intI], intSortCol] > arrData [arrPointer [intK], intSortCol] intP = arrPointer [intI] arrPointer [intI] = arrPointer [intK] arrPointer [intK] = intP EndIf Next intMid = intMid / 2 EndWhile Drop (intP, intHigh, intI, intK, intLow, intMid, intTop) Return arrPointer #EndFunction ;------------------------------------------------------------------------------------------------------------------------------------------ ;------------------------------------------------------------------------------------------------------------------------------------------ #DefineFunction udfArrDisplay (intULx, intULy, intLRx, intLRy, strMsgText, arrData, arrPointer) ; Read arrData sorted by arrPointer. strTable = "[no displayable data]" intDims = ArrInfo (arrData, 0) intDim1 = ArrInfo (arrData, 1) If (intDims == 2) && (intDim1 > 0) intIHigh = intDim1 - 1 intKHigh = ArrInfo (arrData, 2) - 1 strTable = "" For intI = 0 To intIHigh strRow = "" For intK = 0 To intKHigh If !!VarType (arrData [arrPointer [intI], intK]) strRow = StrCat (strRow, @TAB, arrData [arrPointer [intI], intK]) Else strRow = StrCat (strRow, @TAB) EndIf Next strTable = ItemInsert (StrSub (strRow, 2, -1), -1, strTable, @LF) Next EndIf IntControl (63, intULx, intULy, intLRx, intLRy) ; Sets coordinates for AskFileText, AskItemList and AskTextBox windows. intLastIC28 = IntControl (28, 0, 0, 0, 0) ; Selects system font used in list boxes. p1=1=fixed pitch font. p1=0=proportional font (default) AskItemlist (strMsgText, strTable, @LF, @UNSORTED, @SINGLE) IntControl (28, intLastIC28, 0, 0, 0) :CANCEL #EndFunction ;------------------------------------------------------------------------------------------------------------------------------------------ ;------------------------------------------------------------------------------------------------------------------------------------------ ; Define array. intMaxRows = 5 intMaxCols = 3 arrData = ArrDimension (intMaxRows, intMaxCols) ;.......................................................................................................................................... ; Populate array arrData. arrData [0, 0] = "Micky" arrData [0, 1] = "Mouse" arrData [0, 2] = 33 arrData [1, 0] = "Dagobert" arrData [1, 1] = "Duck" arrData [1, 2] = 66 arrData [2, 0] = "Carlo" arrData [2, 1] = "Cat" arrData [2, 2] = 22 arrData [3, 0] = "Lupo" arrData [3, 1] = "Dog" arrData [3, 2] = 11 arrData [4, 0] = "Daisy" arrData [4, 1] = "Duck" arrData [4, 2] = 17 ;.......................................................................................................................................... ; Call the sort UDF. intSortCol = 0 arrPointer0 = udfArraySortShellMetzner (arrData, intSortCol) intSortCol = 2 arrPointer2 = udfArraySortShellMetzner (arrData, intSortCol) ;.......................................................................................................................................... ; Display data array using the sorted pointer array. udfArrDisplay (300, 300, 700, 700, "Script2: Array sorted on Column2 (Age)", arrData, arrPointer2) udfArrDisplay (300, 300, 700, 700, "Script2: Array sorted on Column0 (Firstname)", arrData, arrPointer0) ;========================================================================================================================================== Return ; from GoSub Script2. ;==========================================================================================================================================