11#include "pathman.h"
22
3+ /* Check if two ranges are intersecting */
34bool
45irange_intersects (IndexRange a ,IndexRange b )
56{
67return (irange_lower (a ) <=irange_upper (b ))||
78 (irange_lower (b ) <=irange_upper (a ));
89}
910
11+ /* Check if two ranges are conjuncted */
1012bool
1113irange_conjuncted (IndexRange a ,IndexRange b )
1214{
1315return (irange_lower (a )- 1 <=irange_upper (b ))||
1416 (irange_lower (b )- 1 <=irange_upper (a ));
1517}
1618
19+ /* Make union of two ranges. They should have the same lossiness. */
1720IndexRange
1821irange_union (IndexRange a ,IndexRange b )
1922{
@@ -23,6 +26,7 @@ irange_union(IndexRange a, IndexRange b)
2326irange_is_lossy (a ));
2427}
2528
29+ /* Get intersection of two ranges */
2630IndexRange
2731irange_intersect (IndexRange a ,IndexRange b )
2832{
@@ -31,6 +35,9 @@ irange_intersect(IndexRange a, IndexRange b)
3135irange_is_lossy (a )|| irange_is_lossy (b ));
3236}
3337
38+ /*
39+ * Make union of two index rage lists.
40+ */
3441List *
3542irange_list_union (List * a ,List * b )
3643{
@@ -47,6 +54,7 @@ irange_list_union(List *a, List *b)
4754{
4855IndexRange next ;
4956
57+ /* Fetch next range with lesser lower bound */
5058if (ca && cb )
5159{
5260if (irange_lower (lfirst_irange (ca )) <=irange_lower (lfirst_irange (cb )))
@@ -73,13 +81,17 @@ irange_list_union(List *a, List *b)
7381
7482if (!have_cur )
7583{
84+ /* Put this range as current value if don't have it yet */
7685cur = next ;
7786have_cur = true;
7887}
7988else
8089{
8190if (irange_conjuncted (next ,cur ))
8291{
92+ /*
93+ * Ranges are conjuncted, try to unify them.
94+ */
8395if (irange_is_lossy (next )== irange_is_lossy (cur ))
8496{
8597cur = irange_union (next ,cur );
@@ -105,18 +117,26 @@ irange_list_union(List *a, List *b)
105117}
106118else
107119{
120+ /*
121+ * Next range is not conjuncted with current. Put current to the
122+ * result list and put next as current.
123+ */
108124result = lappend_irange (result ,cur );
109125cur = next ;
110126}
111127}
112128}
113129
130+ /* Put current value into result list if any */
114131if (have_cur )
115132result = lappend_irange (result ,cur );
116133
117134return result ;
118135}
119136
137+ /*
138+ * Find intersection of two range lists.
139+ */
120140List *
121141irange_list_intersect (List * a ,List * b )
122142{
@@ -132,10 +152,16 @@ irange_list_intersect(List *a, List *b)
132152{
133153ra = lfirst_irange (ca );
134154rb = lfirst_irange (cb );
155+
156+ /* Only care about intersecting ranges */
135157if (irange_intersects (ra ,rb ))
136158{
137159IndexRange intersect ,last ;
138160
161+ /*
162+ * Get intersection and try to "glue" it to previous range,
163+ * put it separately otherwise.
164+ */
139165intersect = irange_intersect (ra ,rb );
140166if (result != NIL )
141167{
@@ -156,6 +182,11 @@ irange_list_intersect(List *a, List *b)
156182}
157183}
158184
185+ /*
186+ * Fetch next ranges. We use upper bound of current range to determine
187+ * which lists to fetch, since lower bound of next range is greater (or
188+ * equal) to upper bound of current.
189+ */
159190if (irange_upper (ra ) <=irange_upper (rb ))
160191ca = lnext (ca );
161192if (irange_upper (ra ) >=irange_upper (rb ))
@@ -164,6 +195,7 @@ irange_list_intersect(List *a, List *b)
164195return result ;
165196}
166197
198+ /* Get total number of elements in range list */
167199int
168200irange_list_length (List * rangeset )
169201{
@@ -178,6 +210,7 @@ irange_list_length(List *rangeset)
178210return result ;
179211}
180212
213+ /* Find particular index in range list */
181214bool
182215irange_list_find (List * rangeset ,int index ,bool * lossy )
183216{