Skip to content
This repository was archived by the owner on Aug 31, 2021. It is now read-only.

Commit 435898b

Browse files
author
runrevali
committed
Refactor various sorting functionality to allow binary sort; use icu collation for international sort
1 parent 2386175 commit 435898b

19 files changed

+328
-208
lines changed

‎engine/src/cmds.cpp‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2139,6 +2139,7 @@ Parse_stat MCSort::parse(MCScriptPoint &sp)
21392139
chunktype = CT_CARD;
21402140
break;
21412141
case ST_TEXT:
2142+
case ST_BINARY:
21422143
case ST_NUMERIC:
21432144
case ST_INTERNATIONAL:
21442145
case ST_DATETIME:

‎engine/src/exec-interface.cpp‎

Lines changed: 9 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -3862,59 +3862,6 @@ void MCInterfaceExecExportImageToFile(MCExecContext& ctxt, MCImage *p_target, in
38623862

38633863
////////////////////////////////////////////////////////////////////////////////
38643864

3865-
void MCInterfaceExecSortAddItem(MCExecContext &ctxt, MCSortnode *items, uint4 &nitems, int form, MCValueRef p_input, MCExpression *by)
3866-
{
3867-
MCAutoValueRef t_output;
3868-
if (by != NULL)
3869-
{
3870-
MCerrorlock++;
3871-
//ctxt . GetEP() . setvalueref(p_input);
3872-
MCeach->set(ctxt, p_input);
3873-
bool t_success;
3874-
t_success = false;
3875-
t_success = ctxt . EvalExprAsValueRef(by, EE_UNDEFINED, &t_output);
3876-
if (!t_success)
3877-
t_output = kMCEmptyString;
3878-
MCerrorlock--;
3879-
}
3880-
else
3881-
t_output = p_input;
3882-
3883-
MCAutoStringRef t_converted;
3884-
switch (form)
3885-
{
3886-
case ST_DATETIME:
3887-
if (MCD_convert(ctxt, *t_output, CF_UNDEFINED, CF_UNDEFINED, CF_SECONDS, CF_UNDEFINED, &t_converted))
3888-
if (ctxt.ConvertToNumber(*t_converted, items[nitems].nvalue))
3889-
break;
3890-
3891-
/* UNCHECKED */ MCNumberCreateWithReal(-MAXREAL8, items[nitems].nvalue);
3892-
break;
3893-
3894-
case ST_NUMERIC:
3895-
if (ctxt.ConvertToNumber(*t_output, items[nitems].nvalue))
3896-
break;
3897-
3898-
/* UNCHECKED */ MCNumberCreateWithReal(-MAXREAL8, items[nitems].nvalue);
3899-
break;
3900-
3901-
default:
3902-
if (ctxt . GetCaseSensitive())
3903-
/* UNCHECKED */ ctxt.ConvertToString(*t_output, items[nitems].svalue);
3904-
else
3905-
{
3906-
MCStringRef t_fixed, t_mutable;
3907-
/* UNCHECKED */ ctxt.ConvertToString(*t_output, t_fixed);
3908-
/* UNCHECKED */ MCStringMutableCopyAndRelease(t_fixed, t_mutable);
3909-
/* UNCHECKED */ MCStringLowercase(t_mutable, kMCSystemLocale);
3910-
/* UNCHECKED */ MCStringCopyAndRelease(t_mutable, items[nitems].svalue);
3911-
}
3912-
3913-
break;
3914-
}
3915-
nitems++;
3916-
}
3917-
39183865
bool MCInterfaceExecSortContainer(MCExecContext &ctxt, MCStringRef p_data, int p_type, Sort_type p_direction, int p_form, MCExpression *p_by, MCStringRef &r_output)
39193866
{
39203867
if (MCStringIsEmpty(p_data))
@@ -3937,6 +3884,8 @@ bool MCInterfaceExecSortContainer(MCExecContext &ctxt, MCStringRef p_data, int p
39373884
return false;
39383885

39393886
MCAutoStringRefArray t_chunks;
3887+
MCStringRef *t_sorted;
3888+
uindex_t t_sorted_count;
39403889

39413890
extern bool MCStringsSplit(MCStringRef p_string, MCStringRef p_separator, MCStringRef*&r_strings, uindex_t& r_count);
39423891

@@ -3945,54 +3894,31 @@ bool MCInterfaceExecSortContainer(MCExecContext &ctxt, MCStringRef p_data, int p
39453894

39463895
uindex_t t_item_count;
39473896
t_item_count = t_chunks . Count();
3948-
3897+
39493898
bool t_trailing_delim = false;
39503899
if (p_type != CT_ITEM && MCStringIsEmpty(t_chunks[t_item_count - 1]))
39513900
{
39523901
t_trailing_delim = true;
39533902
t_item_count--;
39543903
}
3955-
3956-
// OK-2008-12-11: [[Bug 7503]] - If there are 0 items in the string, don't carry out the search,
3957-
// this keeps the behavior consistent with previous versions of Revolution.
3958-
if (t_item_count < 1)
3959-
{
3960-
MCStringCopy(p_data, r_output);
3961-
return true;
3962-
}
3963-
3964-
// Now we know the item count, we can allocate an array of MCSortnodes to store them.
3965-
MCAutoArray<MCSortnode> t_items;
3966-
t_items.Extend(t_item_count + 1);
3967-
uindex_t t_added = 0;
3968-
3969-
// Next, populate the MCSortnodes with all the items to be sorted
3970-
for (uindex_t i = 0; i < t_item_count; i++)
3971-
{
3972-
MCInterfaceExecSortAddItem(ctxt, t_items . Ptr(), t_added, p_form, t_chunks[i], p_by);
3973-
t_items[t_added - 1] . data = (void *)t_chunks[i];
3974-
}
3975-
3904+
39763905
// Sort the array
3977-
MCU_sort(t_items.Ptr(), t_added, p_direction, (Sort_type)p_form);
3906+
MCStringsExecSort(ctxt, p_direction, (Sort_type)p_form, *t_chunks, t_item_count, p_by, t_sorted, t_sorted_count);
39783907

39793908
// Build the output string
39803909
MCAutoListRef t_list;
39813910
MCListCreateMutable(t_delimiter, &t_list);
39823911

39833912
uindex_t i;
3984-
for (i = 0; i < t_added; i++)
3985-
{
3986-
MCListAppend(*t_list, (MCStringRef)t_items[i] . data);
3987-
MCValueRelease((MCStringRef)t_items[i] . svalue);
3988-
}
3913+
for (i = 0; i < t_sorted_count; i++)
3914+
MCListAppend(*t_list, t_sorted[i]);
39893915

39903916
MCAutoStringRef t_list_string;
39913917
/* UNCHECKED */ MCListCopyAsString(*t_list, &t_list_string);
39923918

3993-
if (t_trailing_delim || i < t_added - 1)
3919+
if (t_trailing_delim)
39943920
{
3995-
return MCStringFormat(r_output, "%@%c", *t_list_string, t_delimiter);
3921+
return MCStringFormat(r_output, "%@%@", *t_list_string, t_delimiter);
39963922
}
39973923

39983924
r_output = MCValueRetain(*t_list_string);

‎engine/src/exec-strings.cpp‎

Lines changed: 191 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ along with LiveCode. If not see <http://www.gnu.org/licenses/>. */
3434
#include "exec-strings.h"
3535

3636
#include "chunk.h"
37+
#include "date.h"
3738

3839
////////////////////////////////////////////////////////////////////////////////
3940

@@ -2025,3 +2026,193 @@ void MCStringsEvalIsNotAscii(MCExecContext& ctxt, MCValueRef p_value, bool& r_re
20252026
}
20262027

20272028
////////////////////////////////////////////////////////////////////////////////
2029+
2030+
void MCStringsDoSort(MCSortnode *b, uint4 n, MCSortnode *t, Sort_type form, bool reverse, MCStringOptions p_options)
2031+
{
2032+
if (n <= 1)
2033+
return;
2034+
2035+
uint4 n1 = n / 2;
2036+
uint4 n2 = n - n1;
2037+
MCSortnode *b1 = b;
2038+
MCSortnode *b2 = b + n1;
2039+
2040+
MCStringsDoSort(b1, n1, t, form, reverse, p_options);
2041+
MCStringsDoSort(b2, n2, t, form, reverse, p_options);
2042+
2043+
MCSortnode *tmp = t;
2044+
while (n1 > 0 && n2 > 0)
2045+
{
2046+
// NOTE:
2047+
//
2048+
// This code assumes the types in the MCSortnodes are correct for the
2049+
// requested sort type. Bad things will happen if this isn't true...
2050+
bool first;
2051+
switch (form)
2052+
{
2053+
case ST_INTERNATIONAL:
2054+
{
2055+
const unichar_t *t1, *t2;
2056+
t1 = MCStringGetCharPtr(b1->svalue);
2057+
t2 = MCStringGetCharPtr(b2->svalue);
2058+
2059+
compare_t result = MCUnicodeCollate(kMCSystemLocale, MCUnicodeCollateOptionFromCompareOption((MCUnicodeCompareOption)p_options), t1, MCStringGetLength(b1->svalue), t2, MCStringGetLength(b2->svalue));
2060+
first = reverse ? result >= 0 : result <= 0;
2061+
break;
2062+
}
2063+
2064+
case ST_TEXT:
2065+
{
2066+
// This mode performs the comparison in a locale-independent,
2067+
// case-sensitive manner. The strings are sorted by order of
2068+
// codepoint values rather than any lexical sorting order.
2069+
compare_t result = MCStringCompareTo(b1->svalue, b2->svalue, kMCStringOptionCompareExact);
2070+
2071+
first = reverse ? result >= 0 : result <= 0;
2072+
break;
2073+
}
2074+
case ST_BINARY:
2075+
{
2076+
compare_t result = MCDataCompareTo(b1->dvalue, b2->dvalue);
2077+
2078+
first = reverse ? result >= 0 : result <= 0;
2079+
break;
2080+
}
2081+
default:
2082+
{
2083+
first = reverse
2084+
? MCNumberFetchAsReal(b1->nvalue) >= MCNumberFetchAsReal(b2->nvalue)
2085+
: MCNumberFetchAsReal(b1->nvalue) <= MCNumberFetchAsReal(b2->nvalue);
2086+
break;
2087+
}
2088+
}
2089+
if (first)
2090+
{
2091+
*tmp++ = *b1++;
2092+
n1--;
2093+
}
2094+
else
2095+
{
2096+
*tmp++ = *b2++;
2097+
n2--;
2098+
}
2099+
}
2100+
2101+
for (uindex_t i = 0; i < n1; i++)
2102+
tmp[i] = b1[i];
2103+
for (uindex_t i = 0; i < (n - n2); i++)
2104+
b[i] = t[i];
2105+
}
2106+
2107+
void MCStringsSort(MCSortnode *p_items, uint4 nitems, Sort_type p_dir, Sort_type p_form, MCStringOptions p_options)
2108+
{
2109+
if (nitems > 1)
2110+
{
2111+
MCSortnode *tmp = new MCSortnode[nitems];
2112+
MCStringsDoSort(p_items, nitems, tmp, p_form, p_dir == ST_DESCENDING, p_options);
2113+
delete[] tmp;
2114+
}
2115+
}
2116+
2117+
void MCStringsSortAddItem(MCExecContext &ctxt, MCSortnode *items, uint4 &nitems, int form, MCValueRef p_input, MCExpression *by)
2118+
{
2119+
bool t_success;
2120+
t_success = true;
2121+
2122+
MCAutoValueRef t_output;
2123+
if (by != NULL)
2124+
{
2125+
MCerrorlock++;
2126+
if (p_input != nil)
2127+
MCeach->set(ctxt, p_input);
2128+
t_success = ctxt . EvalExprAsValueRef(by, EE_UNDEFINED, &t_output);
2129+
MCerrorlock--;
2130+
}
2131+
else
2132+
t_output = p_input;
2133+
2134+
MCAutoStringRef t_converted;
2135+
switch (form)
2136+
{
2137+
case ST_DATETIME:
2138+
if (t_success && MCD_convert(ctxt, *t_output, CF_UNDEFINED, CF_UNDEFINED, CF_SECONDS, CF_UNDEFINED, &t_converted))
2139+
if (ctxt.ConvertToNumber(*t_converted, items[nitems].nvalue))
2140+
break;
2141+
2142+
/* UNCHECKED */ MCNumberCreateWithReal(-MAXREAL8, items[nitems].nvalue);
2143+
break;
2144+
2145+
case ST_NUMERIC:
2146+
if (t_success && ctxt.ConvertToNumber(*t_output, items[nitems].nvalue))
2147+
break;
2148+
2149+
/* UNCHECKED */ MCNumberCreateWithReal(-MAXREAL8, items[nitems].nvalue);
2150+
break;
2151+
case ST_BINARY:
2152+
if (t_success && ctxt.ConvertToData(*t_output, items[nitems].dvalue))
2153+
break;
2154+
items[nitems] . dvalue = MCValueRetain(kMCEmptyData);
2155+
default:
2156+
if (ctxt . GetCaseSensitive())
2157+
{
2158+
if (t_success && ctxt.ConvertToString(*t_output, items[nitems].svalue))
2159+
break;
2160+
}
2161+
else
2162+
{
2163+
MCStringRef t_fixed, t_mutable;
2164+
t_fixed = nil;
2165+
t_mutable = nil;
2166+
if (t_success)
2167+
t_success = ctxt.ConvertToString(*t_output, t_fixed) &&
2168+
MCStringMutableCopyAndRelease(t_fixed, t_mutable) &&
2169+
MCStringLowercase(t_mutable, kMCSystemLocale) &&
2170+
MCStringCopyAndRelease(t_mutable, items[nitems].svalue);
2171+
2172+
if (t_success)
2173+
break;
2174+
2175+
MCValueRelease(t_fixed);
2176+
MCValueRelease(t_mutable);
2177+
}
2178+
items[nitems].svalue = MCValueRetain(kMCEmptyString);
2179+
2180+
break;
2181+
}
2182+
nitems++;
2183+
}
2184+
2185+
void MCStringsExecSort(MCExecContext& ctxt, Sort_type p_dir, Sort_type p_form, MCStringRef *p_strings_array, uindex_t p_count, MCExpression *p_by, MCStringRef*& r_sorted_array, uindex_t& r_sorted_count)
2186+
{
2187+
// OK-2008-12-11: [[Bug 7503]] - If there are 0 items in the string, don't carry out the search,
2188+
// this keeps the behavior consistent with previous versions of Revolution.
2189+
if (p_count < 1)
2190+
{
2191+
r_sorted_count = 0;
2192+
return;
2193+
}
2194+
2195+
// Now we know the item count, we can allocate an array of MCSortnodes to store them.
2196+
MCAutoArray<MCSortnode> t_items;
2197+
t_items.Extend(p_count + 1);
2198+
uindex_t t_added = 0;
2199+
2200+
// Next, populate the MCSortnodes with all the items to be sorted
2201+
for (uindex_t i = 0; i < p_count; i++)
2202+
{
2203+
MCStringsSortAddItem(ctxt, t_items . Ptr(), t_added, p_form, p_strings_array[i], p_by);
2204+
t_items[t_added - 1] . data = (void *)p_strings_array[i];
2205+
}
2206+
2207+
MCStringsSort(t_items . Ptr(), t_added, p_dir, p_form, ctxt . GetStringComparisonType());
2208+
2209+
MCAutoArray<MCStringRef> t_sorted;
2210+
2211+
for (uindex_t i = 0; i < t_added; i++)
2212+
{
2213+
t_sorted . Push((MCStringRef)t_items[i] . data);
2214+
MCValueRelease(t_items[i] . svalue);
2215+
}
2216+
2217+
t_sorted . Take(r_sorted_array, r_sorted_count);
2218+
}

‎engine/src/exec-strings.h‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -88,4 +88,10 @@ MCPatternMatcher::~MCPatternMatcher()
8888
MCValueRelease(source);
8989
}
9090

91-
////////////////////////////////////////////////////////////////////////////////
91+
////////////////////////////////////////////////////////////////////////////////
92+
93+
void MCStringsExecSort(MCExecContext& ctxt, MCSortnode *items, uint4 nitems, Sort_type dir, Sort_type form);
94+
95+
96+
////////////////////////////////////////////////////////////////////////////////
97+

‎engine/src/exec.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2181,6 +2181,8 @@ void MCStringsExecFilterRegexIntoIt(MCExecContext& ctxt, MCStringRef p_source, M
21812181
void MCStringsEvalIsAscii(MCExecContext& ctxt, MCValueRef p_string, bool& r_result);
21822182
void MCStringsEvalIsNotAscii(MCExecContext& ctxt, MCValueRef p_string, bool& r_result);
21832183

2184+
void MCStringsExecSort(MCExecContext& ctxt, Sort_type p_dir, Sort_type p_form, MCStringRef *p_strings_array, uindex_t p_count, MCExpression *p_by, MCStringRef*& r_sorted_array, uindex_t& r_sorted_count);
2185+
21842186
void MCStringsEvalTextChunkByRange(MCExecContext& ctxt, MCStringRef p_source, Chunk_term p_chunk_type, integer_t p_first, integer_t p_last, bool p_eval_mutable, MCStringRef& x_string);
21852187
void MCStringsEvalTextChunkByExpression(MCExecContext& ctxt, MCStringRef p_source, Chunk_term p_chunk_type, integer_t p_first, bool p_eval_mutable, MCStringRef &x_string);
21862188
void MCStringsEvalTextChunkByOrdinal(MCExecContext& ctxt, MCStringRef p_source, Chunk_term p_chunk_type, Chunk_term p_ordinal_type, bool p_eval_mutable, MCStringRef& x_string);

0 commit comments

Comments
 (0)