diff options
author | tobigun <tobigun@b956fd51-792f-4845-bead-9b4dfca2ff2c> | 2008-04-27 10:30:11 +0000 |
---|---|---|
committer | tobigun <tobigun@b956fd51-792f-4845-bead-9b4dfca2ff2c> | 2008-04-27 10:30:11 +0000 |
commit | 019d57a35441572024cd478da08a67149a1c865f (patch) | |
tree | 8b32a8ac1c9165bab25080c5b59046fca4f57d8a /Game/Code/Classes/UCommon.pas | |
parent | 2202a88128ea55b4e142d169db924b9dea8a02f1 (diff) | |
download | usdx-019d57a35441572024cd478da08a67149a1c865f.tar.gz usdx-019d57a35441572024cd478da08a67149a1c865f.tar.xz usdx-019d57a35441572024cd478da08a67149a1c865f.zip |
- Fixed several bugs with tabbed browsing (Tabs: on) which occurred after TSong was changed from a record to a class.
- Replaced BubbleSort with MergeSort for song sorting (QuickSort is not applicable here because it is instable)
- Added a constructor to TSong for Category-Buttons (this is a bad solution because category-buttons are not songs, a common super-class TCatItem would be nicer)
- Some cleanup
git-svn-id: svn://svn.code.sf.net/p/ultrastardx/svn/trunk@1039 b956fd51-792f-4845-bead-9b4dfca2ff2c
Diffstat (limited to '')
-rw-r--r-- | Game/Code/Classes/UCommon.pas | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/Game/Code/Classes/UCommon.pas b/Game/Code/Classes/UCommon.pas index 5af018b7..1872b789 100644 --- a/Game/Code/Classes/UCommon.pas +++ b/Game/Code/Classes/UCommon.pas @@ -67,6 +67,9 @@ function IsAlphaNumericChar(ch: WideChar): boolean; function IsPunctuationChar(ch: WideChar): boolean;
function IsControlChar(ch: WideChar): boolean;
+// A stable alternative to TList.Sort() (use TList.Sort() if applicable, see below)
+procedure MergeSort(List: TList; CompareFunc: TListSortCompare);
+
implementation
@@ -613,6 +616,90 @@ begin end;
end;
+(*
+ * Recursive part of the MergeSort algorithm.
+ * OutList will be either InList or TempList and will be swapped in each
+ * depth-level of recursion. By doing this it we can directly merge into the
+ * output-list. If we only had In- and OutList parameters we had to merge into
+ * InList after the recursive calls and copy the data to the OutList afterwards.
+ *)
+function _MergeSort(InList, TempList, OutList: TList; StartPos, BlockSize: integer;
+ CompareFunc: TListSortCompare): TList;
+var
+ LeftSize, RightSize: integer; // number of elements in left/right block
+ LeftEnd, RightEnd: integer; // Index after last element in left/right block
+ MidPos: integer; // index of first element in right block
+ Pos: integer; // position in output list
+begin
+ LeftSize := BlockSize div 2;
+ RightSize := BlockSize - LeftSize;
+ MidPos := StartPos + LeftSize;
+
+ // sort left and right halves of this block by recursive calls of this function
+ if (LeftSize >= 2) then
+ _MergeSort(InList, OutList, TempList, StartPos, LeftSize, CompareFunc)
+ else
+ TempList[StartPos] := InList[StartPos];
+ if (RightSize >= 2) then
+ _MergeSort(InList, OutList, TempList, MidPos, RightSize, CompareFunc)
+ else
+ TempList[MidPos] := InList[MidPos];
+
+ // merge sorted left and right sub-lists into output-list
+ LeftEnd := MidPos;
+ RightEnd := StartPos + BlockSize;
+ Pos := StartPos;
+ while ((StartPos < LeftEnd) and (MidPos < RightEnd)) do
+ begin
+ if (CompareFunc(TempList[StartPos], TempList[MidPos]) <= 0) then
+ begin
+ OutList[Pos] := TempList[StartPos];
+ Inc(StartPos);
+ end
+ else
+ begin
+ OutList[Pos] := TempList[MidPos];
+ Inc(MidPos);
+ end;
+ Inc(Pos);
+ end;
+
+ // copy remaining elements to output-list
+ while (StartPos < LeftEnd) do
+ begin
+ OutList[Pos] := TempList[StartPos];
+ Inc(StartPos);
+ Inc(Pos);
+ end;
+ while (MidPos < RightEnd) do
+ begin
+ OutList[Pos] := TempList[MidPos];
+ Inc(MidPos);
+ Inc(Pos);
+ end;
+end;
+
+(*
+ * Stable alternative to the instable TList.Sort() (uses QuickSort) implementation.
+ * A stable sorting algorithm preserves preordered items. E.g. if sorting by
+ * songs by title first and artist afterwards, the songs of each artist will
+ * be ordered by title. In contrast to this an unstable algorithm (like QuickSort)
+ * may destroy an existing order, so the songs of an artist will not be ordered
+ * by title anymore after sorting by artist in the previous example.
+ * If you do not need a stable algorithm, use TList.Sort() instead.
+ *)
+procedure MergeSort(List: TList; CompareFunc: TListSortCompare);
+var
+ TempList: TList;
+begin
+ TempList := TList.Create();
+ TempList.Count := List.Count;
+ if (List.Count >= 2) then
+ _MergeSort(List, TempList, List, 0, List.Count, CompareFunc);
+ TempList.Free;
+end;
+
+
initialization
InitConsoleOutput();
|