Todd Lipcon has posted comments on this change. Change subject: KUDU-2055 [part 2]: Add util to construct sorted disjoint interval ......................................................................
Patch Set 1: (1 comment) http://gerrit.cloudera.org:8080/#/c/8041/1/src/kudu/util/sorted_disjoint_interval.h File src/kudu/util/sorted_disjoint_interval.h: Line 94: IntervalVector sorted_intervals = Traits::sort(intervals); just looking at this quickly... curious why we need a specific Traits::sort for sorting intervals. Given the problem statement, I expected to see something like the following algorithm: // bool = false for starting points, true for end points vector<pair<point_type, bool>> points; for each interval: CHECK(interval.start <= interval.end) (or return error) points.emplace(interval.start, false); points.emplace(interval.end, true); sort(points) int active = 0; for each (point, is_end) in points: if !is_end: if (active++ == 0): cur_start = point else: if (--active == 0): result.emplace_back(cur_start, point) CHECK_EQ(active, 0) Wouldn't this work without having to define any interval comparator or Traits::Overlap, etc, so long as the 'point_type' itself is naturally comparable using operator<? -- To view, visit http://gerrit.cloudera.org:8080/8041 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-MessageType: comment Gerrit-Change-Id: I61a813c047be4882f246eaf404598e7e18fcac87 Gerrit-PatchSet: 1 Gerrit-Project: kudu Gerrit-Branch: master Gerrit-Owner: Hao Hao <hao....@cloudera.com> Gerrit-Reviewer: Alexey Serbin <aser...@cloudera.com> Gerrit-Reviewer: Andrew Wong <aw...@cloudera.com> Gerrit-Reviewer: David Ribeiro Alves <davidral...@gmail.com> Gerrit-Reviewer: Kudu Jenkins Gerrit-Reviewer: Tidy Bot Gerrit-Reviewer: Todd Lipcon <t...@apache.org> Gerrit-HasComments: Yes
