Description: sorting customization of tstringlist by Nikolay (active) Revisions in this set 248fd313f8b5e37a8bb8a38bf92d8d1ec2fa1a5e,e8dc54c768639c9c99b599850e8b2eee67a4ad37,25f6da706626b6c6a09a8c9286f1e949e44ca501,848890e54be05d7f5ae18b98757ea21d656f4366,a2a0ed53b235492d0141759705b6043ed9077774,8cf5779297f990693e1511eda3280655501d634b,7f44f2535ec808acb333415e9c395eee742f52b8,4082b8c7fcd6705ad1ba4ee02f4dad2c179fb8cb,4ea42ab6d23c4e56f47f91cd0a0caac0891dc842,63f9afa6bd0fb9741e951166239717f2727a2875,59a75ea42955ea59c6765c4d856062df8dbc83c1,ad677070f41593a6f8bda86e5840c2006cc17c5e,178217821c41221aefafb166224859f8f789c08f,c7d8bd966646f98d9a5dca9a6a6e3583aed13cc8,cb5a1ed72784f8ded30149be51920d312f8ff80b,ea340b94816f65b6a170293073b31de9b566a6ea,d86da195707736005cbd7815d803bdf3440f8aee,5c4af27a7ae30d89923b197105b9268913252951,1d7ff66602c6ae042c39b6ac4ec5864056ba1386,ec45f0069a9f29c767cc632291c89b1a5a2aa774,26486bbaeac7aae4316d7b5f11c6a9bbeb424933,de80621e1e97e67b79a3cd3e58ff24a3eec93ed4,f5f25f7ae6312448bf71a500685761d660efbcad,bea9961d2d1a3962d5d3553422fb2eed94289234,eca60a0a89cb5b5afb264471aa561ab0afef57ff,f32748a8e7ae82084a5c0837a97f7da67af078b2,c728a1204a62846be24a5cfda23c61ce3eecb91a,f4718831ca31f2c332ba0d22301220f417b08114,52b4fc039c6e064b9720e16b34546bc7e18f4d71,e467d2387d64c175b6e09d38f15812ff41255673,00a67caa40dd518bf5476e6847257be9cc36a400,1c64f4c7512b4d84f1f628472e837f4fb935ce90,4d8dcfc42e965e3f5688b26f066c80512dfd7ee2,8b17af1f8995e8bd2c8ec3c522fca851e8622d1e,ff90e7622aaf4ac14695f30fa799b1faafeab558,b0ca862f32e037665167254d944838daf518ffdb,91ba1214d262265c80898e16748a68fad3875694 commit 248fd313f8b5e37a8bb8a38bf92d8d1ec2fa1a5e Author: nickysn Date: Sat Feb 2 20:06:50 2019 +0000 + introduced unit SortBase, which implements the foundation for pluggable sorting algorithms. A default QuickSort implementation is provided by the unit. Other units can be added, to provide other sorting algorithms (e.g. HeapSort, MergeSort, IntroSort, etc.) * TList and TFPList updated to use the current default sorting algorithm defined in SortBase for their .Sort method. git-svn-id: trunk@41167 - M .gitattributes M rtl/aix/Makefile M rtl/aix/Makefile.fpc M rtl/android/Makefile M rtl/android/Makefile.fpc M rtl/aros/Makefile M rtl/aros/Makefile.fpc M rtl/atari/Makefile M rtl/atari/Makefile.fpc M rtl/beos/Makefile M rtl/beos/Makefile.fpc M rtl/darwin/Makefile M rtl/darwin/Makefile.fpc M rtl/dragonfly/Makefile M rtl/dragonfly/Makefile.fpc M rtl/embedded/Makefile M rtl/embedded/Makefile.fpc M rtl/emx/Makefile M rtl/emx/Makefile.fpc M rtl/freebsd/Makefile M rtl/freebsd/Makefile.fpc M rtl/gba/Makefile M rtl/gba/Makefile.fpc M rtl/go32v2/Makefile M rtl/go32v2/Makefile.fpc M rtl/haiku/Makefile M rtl/haiku/Makefile.fpc A rtl/inc/sortbase.pp M rtl/linux/Makefile M rtl/linux/Makefile.fpc M rtl/morphos/Makefile M rtl/morphos/Makefile.fpc M rtl/msdos/Makefile M rtl/msdos/Makefile.fpc M rtl/nds/Makefile M rtl/nds/Makefile.fpc M rtl/netbsd/Makefile M rtl/netbsd/Makefile.fpc M rtl/netware/Makefile M rtl/netware/Makefile.fpc M rtl/netwlibc/Makefile M rtl/netwlibc/Makefile.fpc M rtl/objpas/classes/classesh.inc M rtl/objpas/classes/lists.inc M rtl/openbsd/Makefile M rtl/openbsd/Makefile.fpc M rtl/os2/Makefile M rtl/os2/Makefile.fpc M rtl/solaris/Makefile M rtl/solaris/Makefile.fpc M rtl/symbian/Makefile M rtl/symbian/Makefile.fpc M rtl/unix/classes.pp M rtl/watcom/Makefile M rtl/watcom/Makefile.fpc M rtl/wii/Makefile M rtl/wii/Makefile.fpc M rtl/win16/Makefile M rtl/win16/Makefile.fpc M rtl/win32/Makefile M rtl/win32/Makefile.fpc M rtl/win64/Makefile M rtl/win64/Makefile.fpc M rtl/wince/Makefile M rtl/wince/Makefile.fpc --- commit e8dc54c768639c9c99b599850e8b2eee67a4ad37 Author: nickysn Date: Sat Feb 2 20:31:16 2019 +0000 + added TList.Sort overload with a sorting algorithm parameter git-svn-id: trunk@41169 - M rtl/objpas/classes/classesh.inc M rtl/objpas/classes/lists.inc --- commit 25f6da706626b6c6a09a8c9286f1e949e44ca501 Author: nickysn Date: Sat Feb 2 20:56:59 2019 +0000 * added PtrList to the names of the current sort algorithm callback functions and types, to indicate they sort a list of pointers git-svn-id: trunk@41170 - M rtl/inc/sortbase.pp M rtl/objpas/classes/lists.inc --- commit 848890e54be05d7f5ae18b98757ea21d656f4366 Author: nickysn Date: Sat Feb 2 21:03:10 2019 +0000 + added the TItemListSorter_NoContext and TItemListSorter_Context procedure types to sortbase. No implementation for them yet. They will allow sorting an array with elements of arbitrary size (e.g. array of records). git-svn-id: trunk@41171 - M rtl/inc/sortbase.pp --- commit a2a0ed53b235492d0141759705b6043ed9077774 Author: nickysn Date: Sat Feb 2 21:05:02 2019 +0000 * the type of the ItemCount parameter changed from PtrUInt to SizeUInt git-svn-id: trunk@41172 - M rtl/inc/sortbase.pp --- commit 8cf5779297f990693e1511eda3280655501d634b Author: nickysn Date: Sat Feb 2 21:07:27 2019 +0000 * the first parameter of QuickSort_PtrList_NoContext renamed ItemPtrs for consistency with the other similar procedures git-svn-id: trunk@41173 - M rtl/inc/sortbase.pp --- commit 7f44f2535ec808acb333415e9c395eee742f52b8 Author: nickysn Date: Sat Feb 2 21:08:30 2019 +0000 * the Compare parameter renamed Comparer for consistency git-svn-id: trunk@41174 - M rtl/inc/sortbase.pp --- commit 4082b8c7fcd6705ad1ba4ee02f4dad2c179fb8cb Author: nickysn Date: Sat Feb 2 21:21:07 2019 +0000 + added and implemented QuickSort_ItemList_Context git-svn-id: trunk@41175 - M rtl/inc/sortbase.pp --- commit 4ea42ab6d23c4e56f47f91cd0a0caac0891dc842 Author: nickysn Date: Sat Feb 2 22:49:39 2019 +0000 * use the sortbase sorting algorithm in fgl as well git-svn-id: trunk@41176 - M rtl/objpas/fgl.pp --- commit 63f9afa6bd0fb9741e951166239717f2727a2875 Author: nickysn Date: Sat Feb 2 22:52:08 2019 +0000 * fixed TFPList.Sort. Scary news: turns out we don't have any tests for TFPList.Sort or TList.Sort... :( git-svn-id: trunk@41177 - M rtl/objpas/classes/lists.inc --- commit 59a75ea42955ea59c6765c4d856062df8dbc83c1 Author: nickysn Date: Sat Feb 2 22:58:52 2019 +0000 * use Inc() and Dec() instead of v:=v+1 git-svn-id: trunk@41178 - M rtl/inc/sortbase.pp --- commit ad677070f41593a6f8bda86e5840c2006cc17c5e Author: nickysn Date: Sat Feb 2 23:08:25 2019 +0000 * hook TFPSList.QuickSort to also call the default sorting algorithm from sortbase git-svn-id: trunk@41179 - M rtl/objpas/fgl.pp --- commit 178217821c41221aefafb166224859f8f789c08f Author: nickysn Date: Sat Feb 2 23:22:09 2019 +0000 + added sortbase as a dependency to unit fgl in the makefiles git-svn-id: trunk@41180 - M rtl/aix/Makefile M rtl/aix/Makefile.fpc M rtl/android/Makefile M rtl/android/Makefile.fpc M rtl/beos/Makefile M rtl/beos/Makefile.fpc M rtl/darwin/Makefile M rtl/darwin/Makefile.fpc M rtl/dragonfly/Makefile M rtl/dragonfly/Makefile.fpc M rtl/embedded/Makefile M rtl/embedded/Makefile.fpc M rtl/emx/Makefile M rtl/emx/Makefile.fpc M rtl/freebsd/Makefile M rtl/freebsd/Makefile.fpc M rtl/gba/Makefile M rtl/gba/Makefile.fpc M rtl/go32v2/Makefile M rtl/go32v2/Makefile.fpc M rtl/haiku/Makefile M rtl/haiku/Makefile.fpc M rtl/linux/Makefile M rtl/linux/Makefile.fpc M rtl/msdos/Makefile M rtl/msdos/Makefile.fpc M rtl/nds/Makefile M rtl/nds/Makefile.fpc M rtl/netbsd/Makefile M rtl/netbsd/Makefile.fpc M rtl/netware/Makefile M rtl/netware/Makefile.fpc M rtl/netwlibc/Makefile M rtl/netwlibc/Makefile.fpc M rtl/openbsd/Makefile M rtl/openbsd/Makefile.fpc M rtl/os2/Makefile M rtl/os2/Makefile.fpc M rtl/solaris/Makefile M rtl/solaris/Makefile.fpc M rtl/symbian/Makefile M rtl/symbian/Makefile.fpc M rtl/watcom/Makefile M rtl/watcom/Makefile.fpc M rtl/wii/Makefile M rtl/wii/Makefile.fpc M rtl/win16/Makefile M rtl/win16/Makefile.fpc M rtl/wince/Makefile M rtl/wince/Makefile.fpc --- commit c7d8bd966646f98d9a5dca9a6a6e3583aed13cc8 Author: nickysn Date: Sun Feb 3 00:33:43 2019 +0000 + added a sort algorithm interface that accepts a custom callback function for exchanging two elements. This is required for TStringList.Sort (and is the most generic form for a sort algorithm interface that I can think of). git-svn-id: trunk@41182 - M rtl/inc/sortbase.pp --- commit cb5a1ed72784f8ded30149be51920d312f8ff80b Author: Károly Balogh Date: Sun Feb 3 02:06:32 2019 +0000 build/install fixes for the new sortbase unit for amiga, atari, aros and morphos git-svn-id: trunk@41183 - M rtl/amiga/Makefile M rtl/amiga/Makefile.fpc M rtl/amiga/buildrtl.pp M rtl/aros/buildrtl.pp M rtl/atari/buildrtl.pp M rtl/morphos/buildrtl.pp --- commit ea340b94816f65b6a170293073b31de9b566a6ea Author: nickysn Date: Sun Feb 3 16:34:05 2019 +0000 * fixed bug in QuickSort_ItemList_CustomItemExchanger_Context and QuickSort_ItemList_Context and which can cause wrong sort results, due to not taking into account that the pivot can be moved by the swap operation git-svn-id: trunk@41191 - M rtl/inc/sortbase.pp --- commit d86da195707736005cbd7815d803bdf3440f8aee Author: nickysn Date: Sun Feb 3 17:00:21 2019 +0000 * use the sort algorithm from sortbase for TStringList git-svn-id: trunk@41194 - M rtl/objpas/classes/classesh.inc M rtl/objpas/classes/stringl.inc --- commit 5c4af27a7ae30d89923b197105b9268913252951 Author: nickysn Date: Sun Feb 3 19:16:48 2019 +0000 + added test for the sortbase unit git-svn-id: trunk@41195 - M .gitattributes M tests/Makefile M tests/Makefile.fpc A tests/test/units/sortbase/tsortbase.pp --- commit 1d7ff66602c6ae042c39b6ac4ec5864056ba1386 Author: nickysn Date: Sun Feb 3 19:49:35 2019 +0000 + added .Sort() overloads with a SortingAlgorithm parameter to TFPGList, TFPGObjectList, TFPGInterfacedObjectList and TFPSMap git-svn-id: trunk@41196 - M rtl/objpas/fgl.pp --- commit ec45f0069a9f29c767cc632291c89b1a5a2aa774 Author: nickysn Date: Mon Feb 4 14:34:13 2019 +0000 + added unit SortAlgs to rtl-extra. It implements extra sorting algorithms that can be used in place of the default QuickSort implementation from unit SortBase. Currently, only HeapSort is implemented, but others will be added in the future. git-svn-id: trunk@41219 - M .gitattributes M packages/rtl-extra/fpmake.pp A packages/rtl-extra/src/inc/sortalgs.pp --- commit 26486bbaeac7aae4316d7b5f11c6a9bbeb424933 Author: nickysn Date: Mon Feb 4 15:32:41 2019 +0000 + keep track of the pivot index in all quicksort implementations. No functional changes, but will be used to prevent overlap in the divided subregions and also infinite loops in case of an incorrect compare function. git-svn-id: trunk@41222 - M rtl/inc/sortbase.pp --- commit de80621e1e97e67b79a3cd3e58ff24a3eec93ed4 Author: nickysn Date: Tue Feb 5 12:14:09 2019 +0000 * use a try..finally block to protect against memory leaks if the comparison callback function raises an exception in QuickSort_ItemList_Context git-svn-id: trunk@41228 - M rtl/inc/sortbase.pp --- commit f5f25f7ae6312448bf71a500685761d660efbcad Author: nickysn Date: Tue Feb 5 16:00:42 2019 +0000 * use a more robust QuickSort implementation, that is guaranteed to never loop forever and never access index out of bounds elements from the array when being passed an incorrect comparison function. The resulting sort order is still undefined in this case, though. git-svn-id: trunk@41229 - M rtl/inc/sortbase.pp --- commit bea9961d2d1a3962d5d3553422fb2eed94289234 Author: nickysn Date: Tue Feb 5 16:20:56 2019 +0000 * use SizeUInt instead of longint for the array indices in the quicksort implementations. This: 1) allows sorting arrays with >4G elements on 64-bit systems 2) allows sorting arrays with up to 4G (>2G) elements on 32-bit systems 3) uses 16-bit instead of the less efficient 32-bit indices on 16-bit and 8-bit platforms git-svn-id: trunk@41230 - M rtl/inc/sortbase.pp --- commit eca60a0a89cb5b5afb264471aa561ab0afef57ff Author: nickysn Date: Tue Feb 5 17:32:28 2019 +0000 * partition elements equal to the pivot on both sides of the pivot, since that leads to much better performance when sorting lots of repeating elements git-svn-id: trunk@41231 - M rtl/inc/sortbase.pp --- commit f32748a8e7ae82084a5c0837a97f7da67af078b2 Author: nickysn Date: Tue Feb 5 18:02:48 2019 +0000 + added comment with information about QuickSort and its specific implementation in unit SortBase git-svn-id: trunk@41232 - M rtl/inc/sortbase.pp --- commit c728a1204a62846be24a5cfda23c61ce3eecb91a Author: nickysn Date: Tue Feb 5 18:25:27 2019 +0000 + added additional notes in the comments for HeapSort git-svn-id: trunk@41233 - M packages/rtl-extra/src/inc/sortalgs.pp --- commit f4718831ca31f2c332ba0d22301220f417b08114 Author: nickysn Date: Wed Feb 6 12:22:08 2019 +0000 * fixed quicksort comment about memory use - our implementation uses O(log n) stack, not O(n log n) git-svn-id: trunk@41236 - M rtl/inc/sortbase.pp --- commit 52b4fc039c6e064b9720e16b34546bc7e18f4d71 Author: nickysn Date: Wed Feb 6 14:20:40 2019 +0000 + added randomized quicksort to unit sortalgs git-svn-id: trunk@41237 - M packages/rtl-extra/src/inc/sortalgs.pp --- commit e467d2387d64c175b6e09d38f15812ff41255673 Author: pierre Date: Wed Feb 6 15:51:54 2019 +0000 Add sortbase unit to global units list, as it can be compiled for all CPUs git-svn-id: trunk@41240 - M rtl/embedded/Makefile M rtl/embedded/Makefile.fpc --- commit 00a67caa40dd518bf5476e6847257be9cc36a400 Author: nickysn Date: Wed Feb 6 18:05:48 2019 +0000 * select the middle element in the default quicksort implementation in a way that doesn't generate arithmetic overflow for very large arrays git-svn-id: trunk@41241 - M rtl/inc/sortbase.pp --- commit 1c64f4c7512b4d84f1f628472e837f4fb935ce90 Author: nickysn Date: Wed Feb 6 18:26:05 2019 +0000 * some formatting changes to avoid very large lines in the source code git-svn-id: trunk@41242 - M packages/rtl-extra/src/inc/sortalgs.pp M rtl/inc/sortbase.pp --- commit 4d8dcfc42e965e3f5688b26f066c80512dfd7ee2 Author: pierre Date: Thu Feb 7 10:46:41 2019 +0000 Fix compilation on targets without Random: add $ifdef FPC_HAS_FEATURE_RANDOM git-svn-id: trunk@41245 - M packages/rtl-extra/src/inc/sortalgs.pp --- commit 8b17af1f8995e8bd2c8ec3c522fca851e8622d1e Author: nickysn Date: Thu Feb 7 14:41:33 2019 +0000 + added test for unit sortalgs, that tests the heapsort and randomized quicksort algorithms git-svn-id: trunk@41247 - M .gitattributes M tests/Makefile M tests/Makefile.fpc A tests/test/units/sortalgs/tsortalgs1.pp --- commit ff90e7622aaf4ac14695f30fa799b1faafeab558 Author: nickysn Date: Thu Feb 7 15:45:13 2019 +0000 + added .Sort overloads, that specify an algorithm and use the sortbase defined algorithms for sorting TList, TFPList and TStringList when FPC_TESTGENERICS is defined as well. Unfortunately, I couldn't test it, because the RTL doesn't compile with FPC_TESTGENERICS, due to errors, completely unrelated to the sortbase changes. git-svn-id: trunk@41248 - M rtl/objpas/classes/classesh.inc M rtl/objpas/classes/lists.inc M rtl/objpas/classes/stringl.inc --- commit b0ca862f32e037665167254d944838daf518ffdb Author: nickysn Date: Fri Feb 8 15:34:29 2019 +0000 + implemented IntroSort (hybrid between QuickSort and HeapSort) in unit SortAlgs git-svn-id: trunk@41258 - M packages/rtl-extra/src/inc/sortalgs.pp M tests/test/units/sortalgs/tsortalgs1.pp --- commit 91ba1214d262265c80898e16748a68fad3875694 Author: michael Date: Sat Aug 24 10:46:51 2019 +0000 * Allow context when sorting lists (patch from Ondrej Pokorny, bug ID #0035962) git-svn-id: trunk@42798 - M rtl/objpas/classes/classesh.inc M rtl/objpas/classes/lists.inc