Description: sorting customization of tstringlist by Nikolay (active) Revisions in this set 25f6da706626b6c6a09a8c9286f1e949e44ca501,848890e54be05d7f5ae18b98757ea21d656f4366,a2a0ed53b235492d0141759705b6043ed9077774,8cf5779297f990693e1511eda3280655501d634b,7f44f2535ec808acb333415e9c395eee742f52b8,4082b8c7fcd6705ad1ba4ee02f4dad2c179fb8cb,59a75ea42955ea59c6765c4d856062df8dbc83c1,c7d8bd966646f98d9a5dca9a6a6e3583aed13cc8,ea340b94816f65b6a170293073b31de9b566a6ea,d86da195707736005cbd7815d803bdf3440f8aee,ec45f0069a9f29c767cc632291c89b1a5a2aa774,26486bbaeac7aae4316d7b5f11c6a9bbeb424933,de80621e1e97e67b79a3cd3e58ff24a3eec93ed4,f5f25f7ae6312448bf71a500685761d660efbcad,bea9961d2d1a3962d5d3553422fb2eed94289234,eca60a0a89cb5b5afb264471aa561ab0afef57ff,f32748a8e7ae82084a5c0837a97f7da67af078b2,c728a1204a62846be24a5cfda23c61ce3eecb91a,f4718831ca31f2c332ba0d22301220f417b08114,52b4fc039c6e064b9720e16b34546bc7e18f4d71,00a67caa40dd518bf5476e6847257be9cc36a400,1c64f4c7512b4d84f1f628472e837f4fb935ce90,4d8dcfc42e965e3f5688b26f066c80512dfd7ee2,ff90e7622aaf4ac14695f30fa799b1faafeab558,b0ca862f32e037665167254d944838daf518ffdb,db83f9ea44dcdf4c4de9b6f270477861141c4cd3 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 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 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 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 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 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 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 db83f9ea44dcdf4c4de9b6f270477861141c4cd3 Author: Michaël Van Canneyt Date: Mon Mar 6 14:58:06 2023 +0100 * Dotted filenames for package rtl-extra A packages/rtl-extra/namespaced/System.Matrix.pp A packages/rtl-extra/namespaced/System.Net.Sockets.pp A packages/rtl-extra/namespaced/System.Objects.pp A packages/rtl-extra/namespaced/System.Printer.pp A packages/rtl-extra/namespaced/System.Real48utils.pp A packages/rtl-extra/namespaced/System.Serial.pp A packages/rtl-extra/namespaced/System.Sockets.pp A packages/rtl-extra/namespaced/System.Sortalgs.pp A packages/rtl-extra/namespaced/System.Ucomplex.pp A packages/rtl-extra/namespaced/UnixApi.Clocale.pp A packages/rtl-extra/namespaced/UnixApi.Gpm.pp A packages/rtl-extra/namespaced/UnixApi.Ipc.pp A packages/rtl-extra/namespaced/UnixApi.Serial.pp A packages/rtl-extra/namespaced/UnixApi.Sockets.pp A packages/rtl-extra/namespaced/WinApi.Winsock.pp A packages/rtl-extra/namespaced/WinApi.Winsock2.pp A packages/rtl-extra/namespaces.lst M packages/rtl-extra/src/amiga/printer.pp M packages/rtl-extra/src/amiga/sockets.pp M packages/rtl-extra/src/android/clocale.pp M packages/rtl-extra/src/aros/sockets.pp M packages/rtl-extra/src/atari/printer.pp M packages/rtl-extra/src/go32v2/printer.pp M packages/rtl-extra/src/inc/matrix.pp M packages/rtl-extra/src/inc/objects.pp M packages/rtl-extra/src/inc/real48utils.pp M packages/rtl-extra/src/inc/sortalgs.pp M packages/rtl-extra/src/inc/ucomplex.pp M packages/rtl-extra/src/msdos/printer.pp M packages/rtl-extra/src/netware/sockets.pp M packages/rtl-extra/src/netwcomn/winsock.pp M packages/rtl-extra/src/netwlibc/sockets.pp M packages/rtl-extra/src/os2/printer.pp M packages/rtl-extra/src/os2commn/sockets.pp M packages/rtl-extra/src/unix/clocale.pp M packages/rtl-extra/src/unix/gpm.pp M packages/rtl-extra/src/unix/ipc.pp M packages/rtl-extra/src/unix/printer.pp M packages/rtl-extra/src/unix/serial.pp M packages/rtl-extra/src/unix/sockets.pp M packages/rtl-extra/src/unix/unixsockets.pp M packages/rtl-extra/src/win/fpwinsockh.inc M packages/rtl-extra/src/win/printer.pp M packages/rtl-extra/src/win/serial.pp M packages/rtl-extra/src/win/sockets.pp M packages/rtl-extra/src/win/winsock.pp M packages/rtl-extra/src/win/winsock2.pp M packages/rtl-extra/src/wince/winsock.pp M packages/rtl-extra/src/wince/winsock2.pp