Transifex autosync

[xonotic/xonotic-data.pk3dir.git] / qcsrc / lib / sort.qh

diff --git a/qcsrc/lib/sort.qh b/qcsrc/lib/sort.qh
index 0d3177a98a8fadfdb118b3a06d7ceef5024a6065..cd0000912dfcfb65b715bcfabebf889d29144adc 100644 (file)
--- a/qcsrc/lib/sort.qh
+++ b/qcsrc/lib/sort.qh
@@ -1,75 +1,58 @@
-#ifndef SORT_H
-#define SORT_H
+#pragma once
 
 /** is only ever called for i1 < i2 */
-typedef void(float i1, float i2, entity pass) swapfunc_t;
+USING(swapfunc_t, void (int i1, int i2, entity pass));
 /** <0 for <, ==0 for ==, >0 for > (like strcmp) */
-typedef float(float i1, float i2, entity pass) comparefunc_t;
+USING(comparefunc_t, int (int i1, int i2, entity pass));
 
-void heapsort(float n, swapfunc_t swap, comparefunc_t cmp, entity pass)
+ERASEABLE
+void heapsort(int n, swapfunc_t swap, comparefunc_t cmp, entity pass)
 {
-    int root, child;
+       #define heapify(_count) \
+               MACRO_BEGIN \
+                       for (int start = floor(((_count) - 2) / 2); start >= 0; --start) \
+                       { \
+                               siftdown(start, (_count) - 1); \
+                       } \
+               MACRO_END
 
-    // heapify
-    int start = floor((n - 2) / 2);
-    while (start >= 0) {
-        // siftdown(start, n - 1);
-        root = start;
-        while (root * 2 + 1 <= n - 1) {
-            child = root * 2 + 1;
-            if (child < n - 1 && cmp(child, child + 1, pass) < 0) {
-                child += 1;
-            }
-            if (cmp(root, child, pass) < 0) {
-                swap(root, child, pass);
-                root = child;
-            } else {
-                break;
-            }
-        }
-        // end of siftdown
-        --start;
-    }
+       #define siftdown(_start, _end) \
+               MACRO_BEGIN \
+                       for (int root = (_start); root * 2 + 1 <= (_end); ) \
+                       { \
+                               int child = root * 2 + 1; \
+                               if (child < (_end) && cmp(child, child + 1, pass) < 0) child += 1; \
+                               if (cmp(root, child, pass) >= 0) break; \
+                               swap(root, child, pass); \
+                               root = child; \
+                       } \
+               MACRO_END
 
-    // extract
-    int end = n - 1;
-    while (end > 0) {
-        swap(0, end, pass);
-        end -= 1;
-        // siftdown(0, end);
-        root = 0;
-        while (root * 2 + 1 <= end) {
-            child = root * 2 + 1;
-            if (child < end && cmp(child, child+1, pass) < 0) {
-                child += 1;
-            }
-            if (cmp(root, child, pass) < 0) {
-                swap(root, child, pass);
-                root = child;
-            } else {
-                break;
-            }
-        }
-        // end of siftdown
-    }
+       heapify(n);
+       int end = n - 1;
+       while (end > 0)
+       {
+               swap(0, end, pass);
+               end -= 1;
+               siftdown(0, end);
+       }
 }
 
+ERASEABLE
 void shuffle(float n, swapfunc_t swap, entity pass)
 {
-    for (int i = 1; i < n; ++i) {
-        // swap i-th item at a random position from 0 to i
-        // proof for even distribution:
-        //   n = 1: obvious
-        //   n -> n+1:
-        //     item n+1 gets at any position with chance 1/(n+1)
-        //     all others will get their 1/n chance reduced by factor n/(n+1)
-        //     to be on place n+1, their chance will be 1/(n+1)
-        //     1/n * n/(n+1) = 1/(n+1)
-        //     q.e.d.
-        int j = floor(random() * (i + 1));
-        if (j != i)
-            swap(j, i, pass);
-    }
+       for (int i = 1; i < n; ++i)
+       {
+               // swap i-th item at a random position from 0 to i
+               // proof for even distribution:
+               //   n = 1: obvious
+               //   n -> n+1:
+               //     item n+1 gets at any position with chance 1/(n+1)
+               //     all others will get their 1/n chance reduced by factor n/(n+1)
+               //     to be on place n+1, their chance will be 1/(n+1)
+               //     1/n * n/(n+1) = 1/(n+1)
+               //     q.e.d.
+               int j = floor(random() * (i + 1));
+               if (j != i) swap(j, i, pass);
+       }
 }
-
-#endif