@Test public void testSimple() { List<IntPair> rangeSet1 = Arrays.asList(Pairs.intPair(0, 4), Pairs.intPair(6, 10)); List<IntPair> rangeSet2 = Arrays.asList(Pairs.intPair(4, 7), Pairs.intPair(8, 14)); List<List<IntPair>> newArrayList = Arrays.asList(rangeSet1, rangeSet2); List<IntPair> intersectionPairs = SortedRangeIntersection.intersectSortedRangeSets(newArrayList); Assert.assertEquals(intersectionPairs.size(), 2); Assert.assertEquals(intersectionPairs.get(0), Pairs.intPair(4, 4)); Assert.assertEquals(intersectionPairs.get(1), Pairs.intPair(6, 10)); }
public static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList) { if (sortedRangeSetList == null || sortedRangeSetList.size() == 0) { return Collections.emptyList(); } if (sortedRangeSetList.size() == 1) { return sortedRangeSetList.get(0); } for (List<IntPair> rangeSet : sortedRangeSetList) { if (rangeSet.size() == 0) { return Collections.emptyList(); } } int[] currentRangeSetIndex = new int[sortedRangeSetList.size()]; Arrays.fill(currentRangeSetIndex, 0); int maxHead = -1; int maxHeadIndex = -1; boolean reachedEnd = false; List<IntPair> result = new ArrayList<IntPair>(); while (!reachedEnd) { for (int i = 0; i < sortedRangeSetList.size(); i++) { int head = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]).getLeft(); if (head > maxHead) { maxHead = head; maxHeadIndex = i; } } for (int i = 0; i < sortedRangeSetList.size(); i++) { if (i == maxHeadIndex) { continue; } boolean found = false; while (!found && currentRangeSetIndex[i] < sortedRangeSetList.get(i).size()) { IntPair range = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (maxHead >= range.getLeft() && maxHead <= range.getRight()) { found = true; break; } if (range.getLeft() > maxHead) { maxHead = range.getLeft(); maxHeadIndex = i; i = -1; break; } currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; } if (i == -1) { continue; } if (!found) { reachedEnd = true; break; } } if (reachedEnd) { break; } IntPair intPair = sortedRangeSetList.get(0).get(currentRangeSetIndex[0]); IntPair intersection = Pairs.intPair(intPair.getLeft(), intPair.getRight()); for (int i = 1; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); int start = Math.max(intersection.getLeft(), pair.getLeft()); int end = Math.min(intersection.getRight(), pair.getRight()); intersection.setLeft(start); intersection.setRight(end); } if (result.size() > 0) { IntPair prevIntersection = result.get(result.size() - 1); if (intersection.getLeft() == prevIntersection.getRight() + 1) { prevIntersection.setRight(intersection.getRight()); } else { result.add(intersection); } } else { result.add(intersection); } for (int i = 0; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (pair.getRight() == intersection.getRight()) { currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; if (currentRangeSetIndex[i] == sortedRangeSetList.get(i).size()) { reachedEnd = true; break; } } } } return result; }
SortedRangeIntersection { public static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList) { if (sortedRangeSetList == null || sortedRangeSetList.size() == 0) { return Collections.emptyList(); } if (sortedRangeSetList.size() == 1) { return sortedRangeSetList.get(0); } for (List<IntPair> rangeSet : sortedRangeSetList) { if (rangeSet.size() == 0) { return Collections.emptyList(); } } int[] currentRangeSetIndex = new int[sortedRangeSetList.size()]; Arrays.fill(currentRangeSetIndex, 0); int maxHead = -1; int maxHeadIndex = -1; boolean reachedEnd = false; List<IntPair> result = new ArrayList<IntPair>(); while (!reachedEnd) { for (int i = 0; i < sortedRangeSetList.size(); i++) { int head = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]).getLeft(); if (head > maxHead) { maxHead = head; maxHeadIndex = i; } } for (int i = 0; i < sortedRangeSetList.size(); i++) { if (i == maxHeadIndex) { continue; } boolean found = false; while (!found && currentRangeSetIndex[i] < sortedRangeSetList.get(i).size()) { IntPair range = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (maxHead >= range.getLeft() && maxHead <= range.getRight()) { found = true; break; } if (range.getLeft() > maxHead) { maxHead = range.getLeft(); maxHeadIndex = i; i = -1; break; } currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; } if (i == -1) { continue; } if (!found) { reachedEnd = true; break; } } if (reachedEnd) { break; } IntPair intPair = sortedRangeSetList.get(0).get(currentRangeSetIndex[0]); IntPair intersection = Pairs.intPair(intPair.getLeft(), intPair.getRight()); for (int i = 1; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); int start = Math.max(intersection.getLeft(), pair.getLeft()); int end = Math.min(intersection.getRight(), pair.getRight()); intersection.setLeft(start); intersection.setRight(end); } if (result.size() > 0) { IntPair prevIntersection = result.get(result.size() - 1); if (intersection.getLeft() == prevIntersection.getRight() + 1) { prevIntersection.setRight(intersection.getRight()); } else { result.add(intersection); } } else { result.add(intersection); } for (int i = 0; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (pair.getRight() == intersection.getRight()) { currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; if (currentRangeSetIndex[i] == sortedRangeSetList.get(i).size()) { reachedEnd = true; break; } } } } return result; } }
SortedRangeIntersection { public static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList) { if (sortedRangeSetList == null || sortedRangeSetList.size() == 0) { return Collections.emptyList(); } if (sortedRangeSetList.size() == 1) { return sortedRangeSetList.get(0); } for (List<IntPair> rangeSet : sortedRangeSetList) { if (rangeSet.size() == 0) { return Collections.emptyList(); } } int[] currentRangeSetIndex = new int[sortedRangeSetList.size()]; Arrays.fill(currentRangeSetIndex, 0); int maxHead = -1; int maxHeadIndex = -1; boolean reachedEnd = false; List<IntPair> result = new ArrayList<IntPair>(); while (!reachedEnd) { for (int i = 0; i < sortedRangeSetList.size(); i++) { int head = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]).getLeft(); if (head > maxHead) { maxHead = head; maxHeadIndex = i; } } for (int i = 0; i < sortedRangeSetList.size(); i++) { if (i == maxHeadIndex) { continue; } boolean found = false; while (!found && currentRangeSetIndex[i] < sortedRangeSetList.get(i).size()) { IntPair range = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (maxHead >= range.getLeft() && maxHead <= range.getRight()) { found = true; break; } if (range.getLeft() > maxHead) { maxHead = range.getLeft(); maxHeadIndex = i; i = -1; break; } currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; } if (i == -1) { continue; } if (!found) { reachedEnd = true; break; } } if (reachedEnd) { break; } IntPair intPair = sortedRangeSetList.get(0).get(currentRangeSetIndex[0]); IntPair intersection = Pairs.intPair(intPair.getLeft(), intPair.getRight()); for (int i = 1; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); int start = Math.max(intersection.getLeft(), pair.getLeft()); int end = Math.min(intersection.getRight(), pair.getRight()); intersection.setLeft(start); intersection.setRight(end); } if (result.size() > 0) { IntPair prevIntersection = result.get(result.size() - 1); if (intersection.getLeft() == prevIntersection.getRight() + 1) { prevIntersection.setRight(intersection.getRight()); } else { result.add(intersection); } } else { result.add(intersection); } for (int i = 0; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (pair.getRight() == intersection.getRight()) { currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; if (currentRangeSetIndex[i] == sortedRangeSetList.get(i).size()) { reachedEnd = true; break; } } } } return result; }  }
SortedRangeIntersection { public static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList) { if (sortedRangeSetList == null || sortedRangeSetList.size() == 0) { return Collections.emptyList(); } if (sortedRangeSetList.size() == 1) { return sortedRangeSetList.get(0); } for (List<IntPair> rangeSet : sortedRangeSetList) { if (rangeSet.size() == 0) { return Collections.emptyList(); } } int[] currentRangeSetIndex = new int[sortedRangeSetList.size()]; Arrays.fill(currentRangeSetIndex, 0); int maxHead = -1; int maxHeadIndex = -1; boolean reachedEnd = false; List<IntPair> result = new ArrayList<IntPair>(); while (!reachedEnd) { for (int i = 0; i < sortedRangeSetList.size(); i++) { int head = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]).getLeft(); if (head > maxHead) { maxHead = head; maxHeadIndex = i; } } for (int i = 0; i < sortedRangeSetList.size(); i++) { if (i == maxHeadIndex) { continue; } boolean found = false; while (!found && currentRangeSetIndex[i] < sortedRangeSetList.get(i).size()) { IntPair range = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (maxHead >= range.getLeft() && maxHead <= range.getRight()) { found = true; break; } if (range.getLeft() > maxHead) { maxHead = range.getLeft(); maxHeadIndex = i; i = -1; break; } currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; } if (i == -1) { continue; } if (!found) { reachedEnd = true; break; } } if (reachedEnd) { break; } IntPair intPair = sortedRangeSetList.get(0).get(currentRangeSetIndex[0]); IntPair intersection = Pairs.intPair(intPair.getLeft(), intPair.getRight()); for (int i = 1; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); int start = Math.max(intersection.getLeft(), pair.getLeft()); int end = Math.min(intersection.getRight(), pair.getRight()); intersection.setLeft(start); intersection.setRight(end); } if (result.size() > 0) { IntPair prevIntersection = result.get(result.size() - 1); if (intersection.getLeft() == prevIntersection.getRight() + 1) { prevIntersection.setRight(intersection.getRight()); } else { result.add(intersection); } } else { result.add(intersection); } for (int i = 0; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (pair.getRight() == intersection.getRight()) { currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; if (currentRangeSetIndex[i] == sortedRangeSetList.get(i).size()) { reachedEnd = true; break; } } } } return result; }  static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList); }
SortedRangeIntersection { public static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList) { if (sortedRangeSetList == null || sortedRangeSetList.size() == 0) { return Collections.emptyList(); } if (sortedRangeSetList.size() == 1) { return sortedRangeSetList.get(0); } for (List<IntPair> rangeSet : sortedRangeSetList) { if (rangeSet.size() == 0) { return Collections.emptyList(); } } int[] currentRangeSetIndex = new int[sortedRangeSetList.size()]; Arrays.fill(currentRangeSetIndex, 0); int maxHead = -1; int maxHeadIndex = -1; boolean reachedEnd = false; List<IntPair> result = new ArrayList<IntPair>(); while (!reachedEnd) { for (int i = 0; i < sortedRangeSetList.size(); i++) { int head = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]).getLeft(); if (head > maxHead) { maxHead = head; maxHeadIndex = i; } } for (int i = 0; i < sortedRangeSetList.size(); i++) { if (i == maxHeadIndex) { continue; } boolean found = false; while (!found && currentRangeSetIndex[i] < sortedRangeSetList.get(i).size()) { IntPair range = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (maxHead >= range.getLeft() && maxHead <= range.getRight()) { found = true; break; } if (range.getLeft() > maxHead) { maxHead = range.getLeft(); maxHeadIndex = i; i = -1; break; } currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; } if (i == -1) { continue; } if (!found) { reachedEnd = true; break; } } if (reachedEnd) { break; } IntPair intPair = sortedRangeSetList.get(0).get(currentRangeSetIndex[0]); IntPair intersection = Pairs.intPair(intPair.getLeft(), intPair.getRight()); for (int i = 1; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); int start = Math.max(intersection.getLeft(), pair.getLeft()); int end = Math.min(intersection.getRight(), pair.getRight()); intersection.setLeft(start); intersection.setRight(end); } if (result.size() > 0) { IntPair prevIntersection = result.get(result.size() - 1); if (intersection.getLeft() == prevIntersection.getRight() + 1) { prevIntersection.setRight(intersection.getRight()); } else { result.add(intersection); } } else { result.add(intersection); } for (int i = 0; i < sortedRangeSetList.size(); i++) { IntPair pair = sortedRangeSetList.get(i).get(currentRangeSetIndex[i]); if (pair.getRight() == intersection.getRight()) { currentRangeSetIndex[i] = currentRangeSetIndex[i] + 1; if (currentRangeSetIndex[i] == sortedRangeSetList.get(i).size()) { reachedEnd = true; break; } } } } return result; }  static List<IntPair> intersectSortedRangeSets(List<List<IntPair>> sortedRangeSetList);  }