StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Use a range tree. A range tree is n log(n), just like the sorted begin/end points, but it has the additional advantage that overlapping ranges will reduce the number of elements (but maybe increase the cost of insertion) Snippet (untested)</p> <pre><code>struct segment { struct segment *ll, *rr; float lo, hi; }; struct segment * newsegment(float lo, float hi) { struct segment * ret; ret = malloc (sizeof *ret); ret->lo = lo; ret->hi = hi; ret->ll= ret->rr = NULL; return ret; } struct segment * insert_range(struct segment *root, float lo, float hi) { if (!root) return newsegment(lo, hi); /* non-overlapping(or touching) ranges can be put into the {l,r} subtrees} */ if (hi < root->lo) { root->ll = insert_range(root->ll, lo, hi); return root; } if (lo > root->hi) { root->rr = insert_range(root->rr, lo, hi); return root; } /* when we get here, we must have overlap; we can extend the current node ** we also need to check if the broader range overlaps the child nodes */ if (lo < root->lo ) { root->lo = lo; while (root->ll && root->ll->hi >= root->lo) { struct segment *tmp; tmp = root->ll; root->lo = tmp->lo; root->ll = tmp->ll; tmp->ll = NULL; // freetree(tmp); } } if (hi > root->hi ) { root->hi = hi; while (root->rr && root->rr->lo <= root->hi) { struct segment *tmp; tmp = root->rr; root->hi = tmp->hi; root->rr = tmp->rr; tmp->rr = NULL; // freetree(tmp); } } return root; } float total_width(struct segment *ptr) { float ret; if (!ptr) return 0.0; ret = ptr->hi - ptr->lo; ret += total_width(ptr->ll); ret += total_width(ptr->rr); return ret; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload