Skip to content

Commit b57c1c1

Browse files
livecodealilivecodeali
committed
Merge pull request livecode#2771 from livecodeali/feature-sort_using_handler
[[ Sort ]] Implement sort using arbitrary sort handler
2 parents 757d99e + 87455eb commit b57c1c1

4 files changed

Lines changed: 294 additions & 0 deletions

File tree

‎docs/lcb/notes/feature-sort_using_handler.md‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# LiveCode Builder Language
2+
3+
## Sort using arbitrary comparison handler
4+
5+
The ability to sort a list using an arbitrary comparison handler has been added. The syntax is
6+
7+
``` sort <List> using handler <Handler> ```
8+
9+
A public handler type SortCompare has been added to the sort module.
10+
The handler used for sort comparison must be of type SortCompare, i.e. be of the form
11+
12+
```MyComparisonHandler(in pLeft as any, in pRight as any) returns Integer```

‎libscript/src/module-sort.cpp‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -213,6 +213,41 @@ void MCSortExecSortListDescendingDateTime(MCProperListRef& x_target)
213213

214214
////////////////////////////////////////////////////////////////
215215

216+
static compare_t MCSortCompareUsingHandler(void *context, MCValueRef p_left, MCValueRef p_right)
217+
{
218+
MCHandlerRef t_handler;
219+
t_handler = *(MCHandlerRef *)context;
220+
221+
MCAutoValueRefArray t_values;
222+
t_values.Push(p_left);
223+
t_values.Push(p_right);
224+
225+
MCAutoValueRef t_result;
226+
MCHandlerInvoke(t_handler, t_values . Ptr(), t_values . Size(), &t_result);
227+
228+
if (*t_result != nil && MCValueGetTypeCode(*t_result) == kMCValueTypeCodeNumber)
229+
return MCNumberFetchAsInteger((MCNumberRef)*t_result);
230+
231+
return 0;
232+
}
233+
234+
extern "C" MC_DLLEXPORT_DEF void MCSortExecSortListUsingHandler(MCProperListRef& x_target, MCHandlerRef p_handler)
235+
{
236+
MCAutoProperListRef t_mutable_list;
237+
if (!MCProperListMutableCopy(x_target, &t_mutable_list))
238+
return;
239+
240+
MCProperListStableSort(*t_mutable_list, false, MCSortCompareUsingHandler, &p_handler);
241+
242+
MCAutoProperListRef t_sorted_list;
243+
if (!MCProperListCopy(*t_mutable_list, &t_sorted_list))
244+
return;
245+
246+
MCValueAssign(x_target, *t_sorted_list);
247+
}
248+
249+
////////////////////////////////////////////////////////////////
250+
216251
extern "C" bool com_livecode_sort_Initialize (void)
217252
{
218253
return true;

‎libscript/src/sort.mlc‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -245,4 +245,72 @@ end syntax
245245

246246
--
247247

248+
/*
249+
Summary: A handler type that can be used in the <SortListUsingHandler> command.
250+
251+
Parameters:
252+
pLeft: The left hand value to compare.
253+
pRight: The right hand value to compare.
254+
255+
Returns:
256+
An integer less than 0 if pLeft is less than pRight with respect to the intended ordering,
257+
an integer greater than 0 if pLeft is greater than pRight with respect to the intended ordering,
258+
or 0 if pLeft is equal to pRight.
259+
260+
Description:
261+
Any handler of type <SortCompare> can be passed to <SortListUsingHandler> to sort a list.
262+
It takes two arguments, and returns an integer based on the comparison.
263+
264+
Tags: Sorting
265+
*/
266+
public handler type SortCompare(in pLeft as any, in pRight as any) returns Integer
267+
268+
public foreign handler MCSortExecSortListUsingHandler(inout Target as List, in Handler as SortCompare) returns nothing binds to "<builtin>"
269+
270+
/*
271+
Summary: Sorts <Target> using <Handler> as a comparison function.
272+
Target: An expression that evaluates to a list.
273+
Handler: A handler of type <SortCompare>
274+
275+
Example:
276+
variable sKeyIndex as Number
277+
278+
private handler CompareListsByElement(in pLeft as any, in pRight as any) returns Integer
279+
variable tLeft as Number
280+
variable tRight as Number
281+
put pLeft[sKeyIndex] into tLeft
282+
put pRight[sKeyIndex] into tRight
283+
284+
if tLeft > tRight then
285+
return 1
286+
else if tLeft < tRight then
287+
return -1
288+
else
289+
return 0
290+
end if
291+
end handler
292+
293+
-- Sort lists according to value at specified index of each list
294+
public handler TestSortListOfLists(in pList as List, in pKeyIndex as Number) returns List
295+
put pKeyIndex into sKeyIndex
296+
sort pList using handler CompareListsByElement
297+
return pList
298+
end handler
299+
300+
Description:
301+
<SortListUsingHandler> sorts a list by comparing the elements of a list according to the
302+
comparison implemented by the <Handler> argument.
303+
304+
>*Note:* Supplying an inconsistent comparison operator to <SortListUsingHandler> causes
305+
undefined behavior.
306+
307+
Tags: Sorting
308+
*/
309+
310+
syntax SortListUsingHandler is statement
311+
"sort" <Target: Expression> "using" "handler" <Handler: Expression>
312+
begin
313+
MCSortExecSortListUsingHandler(Target, Handler)
314+
end syntax
315+
248316
end module

‎tests/lcb/stdlib/sort.lcb‎

Lines changed: 179 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@ along with LiveCode. If not see <http://www.gnu.org/licenses/>. */
1818
module com.livecode.sort.tests
1919

2020
use com.livecode.sort
21+
use com.livecode.__INTERNAL._testlib
2122

2223
----------------------------------------------------------------
2324
-- Utilities
@@ -68,6 +69,28 @@ handler RandomStringList() returns List
6869
return tList
6970
end handler
7071

72+
-- Create a list containing 100 random strings of 1-10 characters, or numbers from 1 to 100
73+
handler RandomMixedList() returns List
74+
variable tStringList as List
75+
variable tNumericList as List
76+
put RandomStringList() into tStringList
77+
put RandomNumericList() into tNumericList
78+
79+
variable tList
80+
put [] into tList
81+
82+
variable tCount
83+
repeat with tCount from 1 up to 100
84+
if any number > 0.5 then
85+
push tStringList[tCount] onto tList
86+
else
87+
push tNumericList[tCount] onto tList
88+
end if
89+
end repeat
90+
91+
return tList
92+
end handler
93+
7194
handler IsSorted(in pList as List, in pDescending as Boolean) returns Boolean
7295
if pList is empty then
7396
return true
@@ -90,6 +113,80 @@ handler IsSorted(in pList as List, in pDescending as Boolean) returns Boolean
90113
return tSorted
91114
end handler
92115

116+
handler CompareNumericAscending(in pLeft as any, in pRight as any) returns Integer
117+
return CompareNumeric(pLeft, pRight, false)
118+
end handler
119+
120+
handler CompareNumericDescending(in pLeft as any, in pRight as any) returns Integer
121+
return CompareNumeric(pLeft, pRight, true)
122+
end handler
123+
124+
-- Sorts numerically, converting strings to numbers where possible
125+
handler CompareNumeric(in pLeft as any, in pRight as any, in pDescending as Boolean) returns Integer
126+
variable tLeft as optional Number
127+
variable tRight as optional Number
128+
129+
if pLeft is a number then
130+
put pLeft into tLeft
131+
else
132+
put pLeft parsed as number into tLeft
133+
end if
134+
135+
if pRight is a number then
136+
put pRight into tRight
137+
else
138+
put pRight parsed as number into tRight
139+
end if
140+
141+
if tRight is tLeft then
142+
return 0
143+
end if
144+
145+
if tRight is nothing then
146+
return -1
147+
end if
148+
149+
if tLeft is nothing then
150+
return 1
151+
end if
152+
153+
if tLeft < tRight then
154+
if pDescending then
155+
return 1
156+
else
157+
return -1
158+
end if
159+
end if
160+
161+
if pDescending then
162+
return -1
163+
else
164+
return 1
165+
end if
166+
end handler
167+
168+
handler IsSortedUsingHandler(in pList as List, in pHandler as SortCompare) returns Boolean
169+
if pList is empty then
170+
return true
171+
end if
172+
173+
variable tLast
174+
pop front of pList into tLast
175+
176+
variable tSorted
177+
put true into tSorted
178+
179+
variable tIter
180+
repeat for each element tIter in pList
181+
if pHandler(tLast, tIter) > 0 then
182+
put false into tSorted
183+
exit repeat
184+
end if
185+
put tIter into tLast
186+
end repeat
187+
return tSorted
188+
end handler
189+
93190
----------------------------------------------------------------
94191
-- Tests
95192
----------------------------------------------------------------
@@ -202,4 +299,86 @@ public handler TestDescendingText() -- RANDOMIZED
202299
test "sort descending text is stable" when tList is tStable
203300
end handler
204301

302+
public handler TestAscendingNumericMixed() -- RANDOMIZED
303+
variable tRandom
304+
repeat forever
305+
put RandomMixedList() into tRandom
306+
if not IsSortedUsingHandler(tRandom, CompareNumericAscending) then
307+
exit repeat
308+
end if
309+
end repeat
310+
311+
variable tList
312+
313+
-- Test sorting
314+
put tRandom into tList
315+
sort tList using handler CompareNumericAscending
316+
test "sort using handler ascending numeric" when IsSortedUsingHandler(tList, CompareNumericAscending)
317+
318+
-- Test sorting stability
319+
variable tStable
320+
put tList into tStable
321+
sort tList using handler CompareNumericAscending
322+
test "sort using handler ascending numeric is stable" when tList is tStable
323+
end handler
324+
325+
public handler TestDescendingNumericMixed() -- RANDOMIZED
326+
variable tRandom
327+
repeat forever
328+
put RandomMixedList() into tRandom
329+
if not IsSortedUsingHandler(tRandom, CompareNumericDescending) then
330+
exit repeat
331+
end if
332+
end repeat
333+
334+
variable tList
335+
336+
-- Test sorting
337+
put tRandom into tList
338+
sort tList using handler CompareNumericDescending
339+
test "sort using handler descending numeric" when IsSortedUsingHandler(tList, CompareNumericDescending)
340+
341+
-- Test sorting stability
342+
variable tStable
343+
put tList into tStable
344+
sort tList using handler CompareNumericDescending
345+
test "sort using handler descending numeric is stable" when tList is tStable
346+
end handler
347+
348+
handler InvalidSortHandler_Args(in pValue as any) returns Integer
349+
return 1
350+
end handler
351+
352+
handler InvalidSortHandler_ReturnType(in pLeft as any, in pRight as any) returns String
353+
return ""
354+
end handler
355+
356+
handler InvalidSortHandler_MissingReturn(in pLeft as any, in pRight as any) returns Integer
357+
358+
end handler
359+
360+
handler TestSortUsingHandler_InvalidArgs()
361+
variable tList as List
362+
put [1,2,3,4] into tList
363+
sort tList using handler InvalidSortHandler_Args
364+
end handler
365+
366+
handler TestSortUsingHandler_InvalidReturnType()
367+
variable tList as List
368+
put [1,2,3,4] into tList
369+
sort tList using handler InvalidSortHandler_ReturnType
370+
end handler
371+
372+
handler TestSortUsingHandler_MissingReturn()
373+
variable tList as List
374+
put [1,2,3,4] into tList
375+
sort tList using handler InvalidSortHandler_MissingReturn
376+
end handler
377+
378+
public handler TestUsingHandlerErrors()
379+
MCUnitTestHandlerThrows(TestSortUsingHandler_InvalidArgs, "handler invalid number of args")
380+
MCUnitTestHandlerThrows(TestSortUsingHandler_InvalidReturnType, "handler invalid return type")
381+
MCUnitTestHandlerThrows(TestSortUsingHandler_MissingReturn, "handler missing return")
382+
end handler
383+
205384
end module

0 commit comments

Comments
 (0)