From 019d57a35441572024cd478da08a67149a1c865f Mon Sep 17 00:00:00 2001
From: tobigun <tobigun@b956fd51-792f-4845-bead-9b4dfca2ff2c>
Date: Sun, 27 Apr 2008 10:30:11 +0000
Subject: - 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
---
 Game/Code/Classes/UCommon.pas | 87 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 87 insertions(+)

(limited to 'Game/Code/Classes/UCommon.pas')

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();
 
-- 
cgit v1.2.3