Description: sorting customization of tstringlist by Nikolay

(active) Revisions in this set:
41167,41169,41170,41171,41172,41173,41174,41175,41176,41177,41178,41179,41180,41182,41183,41191,41194,41195,41196,41219,41222,41228,41229,41230,41231,41232
41233,41236,41237,41240,41241,41242,41245,41247,41248,41258,42798
This file as text.

Clicking a revision will expand files
 

+ 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.
Commit consists out of 8 lines
  • M /trunk/rtl/aix/Makefile
  • M /trunk/rtl/aix/Makefile.fpc
  • M /trunk/rtl/android/Makefile
  • M /trunk/rtl/android/Makefile.fpc
  • M /trunk/rtl/aros/Makefile
  • M /trunk/rtl/aros/Makefile.fpc
  • M /trunk/rtl/atari/Makefile
  • M /trunk/rtl/atari/Makefile.fpc
  • M /trunk/rtl/beos/Makefile
  • M /trunk/rtl/beos/Makefile.fpc
  • M /trunk/rtl/darwin/Makefile
  • M /trunk/rtl/darwin/Makefile.fpc
  • M /trunk/rtl/dragonfly/Makefile
  • M /trunk/rtl/dragonfly/Makefile.fpc
  • M /trunk/rtl/embedded/Makefile
  • M /trunk/rtl/embedded/Makefile.fpc
  • M /trunk/rtl/emx/Makefile
  • M /trunk/rtl/emx/Makefile.fpc
  • M /trunk/rtl/freebsd/Makefile
  • M /trunk/rtl/freebsd/Makefile.fpc
  • M /trunk/rtl/gba/Makefile
  • M /trunk/rtl/gba/Makefile.fpc
  • M /trunk/rtl/go32v2/Makefile
  • M /trunk/rtl/go32v2/Makefile.fpc
  • M /trunk/rtl/haiku/Makefile
  • M /trunk/rtl/haiku/Makefile.fpc
  • A /trunk/rtl/inc/sortbase.pp
  • M /trunk/rtl/linux/Makefile
  • M /trunk/rtl/linux/Makefile.fpc
  • M /trunk/rtl/morphos/Makefile
  • M /trunk/rtl/morphos/Makefile.fpc
  • M /trunk/rtl/msdos/Makefile
  • M /trunk/rtl/msdos/Makefile.fpc
  • M /trunk/rtl/nds/Makefile
  • M /trunk/rtl/nds/Makefile.fpc
  • M /trunk/rtl/netbsd/Makefile
  • M /trunk/rtl/netbsd/Makefile.fpc
  • M /trunk/rtl/netware/Makefile
  • M /trunk/rtl/netware/Makefile.fpc
  • M /trunk/rtl/netwlibc/Makefile
  • M /trunk/rtl/netwlibc/Makefile.fpc
  • M /trunk/rtl/objpas/classes/classesh.inc
  • M /trunk/rtl/objpas/classes/lists.inc
  • M /trunk/rtl/openbsd/Makefile
  • M /trunk/rtl/openbsd/Makefile.fpc
  • M /trunk/rtl/os2/Makefile
  • M /trunk/rtl/os2/Makefile.fpc
  • M /trunk/rtl/solaris/Makefile
  • M /trunk/rtl/solaris/Makefile.fpc
  • M /trunk/rtl/symbian/Makefile
  • M /trunk/rtl/symbian/Makefile.fpc
  • M /trunk/rtl/unix/classes.pp
  • M /trunk/rtl/watcom/Makefile
  • M /trunk/rtl/watcom/Makefile.fpc
  • M /trunk/rtl/wii/Makefile
  • M /trunk/rtl/wii/Makefile.fpc
  • M /trunk/rtl/win16/Makefile
  • M /trunk/rtl/win16/Makefile.fpc
  • M /trunk/rtl/win32/Makefile
  • M /trunk/rtl/win32/Makefile.fpc
  • M /trunk/rtl/win64/Makefile
  • M /trunk/rtl/win64/Makefile.fpc
  • M /trunk/rtl/wince/Makefile
  • M /trunk/rtl/wince/Makefile.fpc

+ added TList.Sort overload with a sorting algorithm parameter
Commit consists out of 3 lines
  • M /trunk/rtl/objpas/classes/classesh.inc
  • M /trunk/rtl/objpas/classes/lists.inc

* added PtrList to the names of the current sort algorithm callback functions and
types, to indicate they sort a list of pointers
Commit consists out of 4 lines
  • M /trunk/rtl/inc/sortbase.pp
  • M /trunk/rtl/objpas/classes/lists.inc

+ 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).
Commit consists out of 5 lines
  • M /trunk/rtl/inc/sortbase.pp

* the type of the ItemCount parameter changed from PtrUInt to SizeUInt
Commit consists out of 3 lines
  • M /trunk/rtl/inc/sortbase.pp

* the first parameter of QuickSort_PtrList_NoContext renamed ItemPtrs for
consistency with the other similar procedures
Commit consists out of 4 lines
  • M /trunk/rtl/inc/sortbase.pp

* the Compare parameter renamed Comparer for consistency
Commit consists out of 3 lines
  • M /trunk/rtl/inc/sortbase.pp

+ added and implemented QuickSort_ItemList_Context
Commit consists out of 3 lines
  • M /trunk/rtl/inc/sortbase.pp

* use the sortbase sorting algorithm in fgl as well
Commit consists out of 3 lines
  • M /trunk/rtl/objpas/fgl.pp

* fixed TFPList.Sort. Scary news: turns out we don't have any tests for
TFPList.Sort or TList.Sort... :(
Commit consists out of 4 lines
  • M /trunk/rtl/objpas/classes/lists.inc

* use Inc() and Dec() instead of v:=v+1
Commit consists out of 3 lines
  • M /trunk/rtl/inc/sortbase.pp

* hook TFPSList.QuickSort to also call the default sorting algorithm from sortbase
Commit consists out of 3 lines
  • M /trunk/rtl/objpas/fgl.pp

+ added sortbase as a dependency to unit fgl in the makefiles
Commit consists out of 3 lines
  • M /trunk/rtl/aix/Makefile
  • M /trunk/rtl/aix/Makefile.fpc
  • M /trunk/rtl/android/Makefile
  • M /trunk/rtl/android/Makefile.fpc
  • M /trunk/rtl/beos/Makefile
  • M /trunk/rtl/beos/Makefile.fpc
  • M /trunk/rtl/darwin/Makefile
  • M /trunk/rtl/darwin/Makefile.fpc
  • M /trunk/rtl/dragonfly/Makefile
  • M /trunk/rtl/dragonfly/Makefile.fpc
  • M /trunk/rtl/embedded/Makefile
  • M /trunk/rtl/embedded/Makefile.fpc
  • M /trunk/rtl/emx/Makefile
  • M /trunk/rtl/emx/Makefile.fpc
  • M /trunk/rtl/freebsd/Makefile
  • M /trunk/rtl/freebsd/Makefile.fpc
  • M /trunk/rtl/gba/Makefile
  • M /trunk/rtl/gba/Makefile.fpc
  • M /trunk/rtl/go32v2/Makefile
  • M /trunk/rtl/go32v2/Makefile.fpc
  • M /trunk/rtl/haiku/Makefile
  • M /trunk/rtl/haiku/Makefile.fpc
  • M /trunk/rtl/linux/Makefile
  • M /trunk/rtl/linux/Makefile.fpc
  • M /trunk/rtl/msdos/Makefile
  • M /trunk/rtl/msdos/Makefile.fpc
  • M /trunk/rtl/nds/Makefile
  • M /trunk/rtl/nds/Makefile.fpc
  • M /trunk/rtl/netbsd/Makefile
  • M /trunk/rtl/netbsd/Makefile.fpc
  • M /trunk/rtl/netware/Makefile
  • M /trunk/rtl/netware/Makefile.fpc
  • M /trunk/rtl/netwlibc/Makefile
  • M /trunk/rtl/netwlibc/Makefile.fpc
  • M /trunk/rtl/openbsd/Makefile
  • M /trunk/rtl/openbsd/Makefile.fpc
  • M /trunk/rtl/os2/Makefile
  • M /trunk/rtl/os2/Makefile.fpc
  • M /trunk/rtl/solaris/Makefile
  • M /trunk/rtl/solaris/Makefile.fpc
  • M /trunk/rtl/symbian/Makefile
  • M /trunk/rtl/symbian/Makefile.fpc
  • M /trunk/rtl/watcom/Makefile
  • M /trunk/rtl/watcom/Makefile.fpc
  • M /trunk/rtl/wii/Makefile
  • M /trunk/rtl/wii/Makefile.fpc
  • M /trunk/rtl/win16/Makefile
  • M /trunk/rtl/win16/Makefile.fpc
  • M /trunk/rtl/wince/Makefile
  • M /trunk/rtl/wince/Makefile.fpc

+ 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).
Commit consists out of 5 lines
  • M /trunk/rtl/inc/sortbase.pp

build/install fixes for the new sortbase unit for amiga, atari, aros and morphos
Commit consists out of 1 line
  • M /trunk/rtl/amiga/Makefile
  • M /trunk/rtl/amiga/Makefile.fpc
  • M /trunk/rtl/amiga/buildrtl.pp
  • M /trunk/rtl/aros/buildrtl.pp
  • M /trunk/rtl/atari/buildrtl.pp
  • M /trunk/rtl/morphos/buildrtl.pp

* 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
Commit consists out of 5 lines
  • M /trunk/rtl/inc/sortbase.pp

* use the sort algorithm from sortbase for TStringList
Commit consists out of 3 lines
  • M /trunk/rtl/objpas/classes/classesh.inc
  • M /trunk/rtl/objpas/classes/stringl.inc

+ added test for the sortbase unit
Commit consists out of 3 lines
  • M /trunk/tests/Makefile
  • M /trunk/tests/Makefile.fpc
  • A /trunk/tests/test/units/sortbase
  • A /trunk/tests/test/units/sortbase/tsortbase.pp

+ added .Sort() overloads with a SortingAlgorithm parameter to TFPGList,
TFPGObjectList, TFPGInterfacedObjectList and TFPSMap
Commit consists out of 4 lines
  • M /trunk/rtl/objpas/fgl.pp

+ 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.
Commit consists out of 6 lines
  • M /trunk/packages/rtl-extra/fpmake.pp
  • A /trunk/packages/rtl-extra/src/inc/sortalgs.pp

+ 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.
Commit consists out of 5 lines
  • M /trunk/rtl/inc/sortbase.pp

* use a try..finally block to protect against memory leaks if the comparison
callback function raises an exception in QuickSort_ItemList_Context
Commit consists out of 2 lines
  • M /trunk/rtl/inc/sortbase.pp

* 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.
Commit consists out of 4 lines
  • M /trunk/rtl/inc/sortbase.pp

* 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
Commit consists out of 6 lines
  • M /trunk/rtl/inc/sortbase.pp

* 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
Commit consists out of 2 lines
  • M /trunk/rtl/inc/sortbase.pp

+ added comment with information about QuickSort and its specific implementation in unit SortBase
Commit consists out of 1 line
  • M /trunk/rtl/inc/sortbase.pp

+ added additional notes in the comments for HeapSort
Commit consists out of 1 line
  • M /trunk/packages/rtl-extra/src/inc/sortalgs.pp

* fixed quicksort comment about memory use - our implementation uses O(log n) stack, not O(n log n)
Commit consists out of 1 line
  • M /trunk/rtl/inc/sortbase.pp

+ added randomized quicksort to unit sortalgs
Commit consists out of 1 line
  • M /trunk/packages/rtl-extra/src/inc/sortalgs.pp

Add sortbase unit to global units list, as it can be compiled for all CPUs
Commit consists out of 1 line
  • M /trunk/rtl/embedded/Makefile
  • M /trunk/rtl/embedded/Makefile.fpc

* select the middle element in the default quicksort implementation in a way
that doesn't generate arithmetic overflow for very large arrays
Commit consists out of 2 lines
  • M /trunk/rtl/inc/sortbase.pp

* some formatting changes to avoid very large lines in the source code
Commit consists out of 1 line
  • M /trunk/packages/rtl-extra/src/inc/sortalgs.pp
  • M /trunk/rtl/inc/sortbase.pp

Fix compilation on targets without Random: add $ifdef FPC_HAS_FEATURE_RANDOM
Commit consists out of 1 line
  • M /trunk/packages/rtl-extra/src/inc/sortalgs.pp

+ added test for unit sortalgs, that tests the heapsort and randomized quicksort algorithms
Commit consists out of 1 line
  • M /trunk/tests/Makefile
  • M /trunk/tests/Makefile.fpc
  • A /trunk/tests/test/units/sortalgs
  • A /trunk/tests/test/units/sortalgs/tsortalgs1.pp

+ 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.
Commit consists out of 5 lines
  • M /trunk/rtl/objpas/classes/classesh.inc
  • M /trunk/rtl/objpas/classes/lists.inc
  • M /trunk/rtl/objpas/classes/stringl.inc

+ implemented IntroSort (hybrid between QuickSort and HeapSort) in unit SortAlgs
Commit consists out of 1 line
  • M /trunk/packages/rtl-extra/src/inc/sortalgs.pp
  • M /trunk/tests/test/units/sortalgs/tsortalgs1.pp

* Allow context when sorting lists (patch from Ondrej Pokorny, bug ID 000035962)
Commit consists out of 1 line
  • M /trunk/rtl/objpas/classes/classesh.inc
  • M /trunk/rtl/objpas/classes/lists.inc