Range consolidation: Difference between revisions

Content added Content deleted

Inline

@@ Line 148: / Line 148: @@
 (  4.0  3.0) (  2.0  1.0) ( -1.0 -2.0) (  3.9 10.0)                  ( -2.0 -1.0) (  1.0  2.0) (  3.0 10.0)
 (  1.0  3.0) ( -6.0 -1.0) ( -4.0 -5.0) (  8.0  2.0) ( -6.0 -6.0)     ( -6.0 -1.0) (  1.0  8.0)
+</pre>
+=={{header|C}}==
+<lang c>#include <stdio.h>
+#include <stdlib.h>
+typedef struct range_tag {
+    double low;
+    double high;
+} range_t;
+void normalize_range(range_t* range) {
+    if (range->high < range->low) {
+        double tmp = range->low;
+        range->low = range->high;
+        range->high = tmp;
+    }
+}
+int range_compare(const void* p1, const void* p2) {
+    const range_t* r1 = p1;
+    const range_t* r2 = p2;
+    if (r1->low < r2->low)
+        return -1;
+    if (r1->low > r2->low)
+        return 1;
+    if (r1->high < r2->high)
+        return -1;
+    if (r1->high > r2->high)
+        return 1;
+    return 0;
+}
+void normalize_ranges(range_t* ranges, size_t count) {
+    for (size_t i = 0; i < count; ++i)
+        normalize_range(&ranges[i]);
+    qsort(ranges, count, sizeof(range_t), range_compare);
+}
+// Consolidates an array of ranges in-place. Returns the
+// number of ranges after consolidation.
+size_t consolidate_ranges(range_t* ranges, size_t count) {
+    normalize_ranges(ranges, count);
+    for (size_t i = 0; i < count; ++i) {
+        size_t n = 0, j = i;
+        for (; ++j < count && ranges[j].low <= ranges[i].high; ++n) {
+            if (ranges[i].high < ranges[j].high)
+                ranges[i].high = ranges[j].high;
+        }
+        if (n > 0) {
+            count -= n;
+            for (size_t k = i + 1; k < count; ++k, ++j)
+                ranges[k] = ranges[j];
+        }
+    }
+    return count;
+}
+void print_range(const range_t* range) {
+    printf("[%g, %g]", range->low, range->high);
+}
+void print_ranges(const range_t* ranges, size_t count) {
+    if (count == 0)
+        return;
+    print_range(&ranges[0]);
+    for (size_t i = 1; i < count; ++i) {
+        printf(", ");
+        print_range(&ranges[i]);
+    }
+}
+void test_consolidate_ranges(range_t* ranges, size_t count) {
+    print_ranges(ranges, count);
+    printf(" -> ");
+    count = consolidate_ranges(ranges, count);
+    print_ranges(ranges, count);
+    printf("\n");
+}
+#define LENGTHOF(a) sizeof(a)/sizeof(a[0])
+int main() {
+    range_t test1[] = { {1.1, 2.2} };
+    range_t test2[] = { {6.1, 7.2}, {7.2, 8.3} };
+    range_t test3[] = { {4, 3}, {2, 1} };
+    range_t test4[] = { {4, 3}, {2, 1}, {-1, -2}, {3.9, 10} };
+    range_t test5[] = { {1, 3}, {-6, -1}, {-4, -5}, {8, 2}, {-6, -6} };
+    test_consolidate_ranges(test1, LENGTHOF(test1));
+    test_consolidate_ranges(test2, LENGTHOF(test2));
+    test_consolidate_ranges(test3, LENGTHOF(test3));
+    test_consolidate_ranges(test4, LENGTHOF(test4));
+    test_consolidate_ranges(test5, LENGTHOF(test5));
+    return 0;
+}</lang>
+{{out}}
+<pre>
+[1.1, 2.2] -> [1.1, 2.2]
+[6.1, 7.2], [7.2, 8.3] -> [6.1, 8.3]
+[4, 3], [2, 1] -> [1, 2], [3, 4]
+[4, 3], [2, 1], [-1, -2], [3.9, 10] -> [-2, -1], [1, 2], [3, 10]
+[1, 3], [-6, -1], [-4, -5], [8, 2], [-6, -6] -> [-6, -1], [1, 8]
 </pre>