@Test public void testRandom() { int totalDocs = 1000000; int maxRange = 10000; int minRange = 1000; long randomSeed = System.currentTimeMillis(); Random r = new Random(randomSeed); int numLists = 3; List<List<IntPair>> sortedRangePairsList = new ArrayList<>(); List<Set<Integer>> rawIdSetList = new ArrayList<>(); for (int i = 0; i < numLists; i++) { List<IntPair> pairs = new ArrayList<>(); Set<Integer> rawIdSet = new HashSet<>(); int docId = 0; while (docId < totalDocs) { int start = docId + r.nextInt(maxRange); int end = start + Math.max(minRange, r.nextInt(maxRange)); if (end < totalDocs) { pairs.add(Pairs.intPair(start, end)); for (int id = start; id <= end; id++) { rawIdSet.add(id); } } docId = end + 1; } sortedRangePairsList.add(pairs); rawIdSetList.add(rawIdSet); } List<IntPair> expected = new ArrayList<>(); int tempStart = -1; for (int id = 0; id < totalDocs; id++) { boolean foundInAll = true; for (int i = 0; i < numLists; i++) { if (!rawIdSetList.get(i).contains(id)) { foundInAll = false; break; } } if (foundInAll) { if (tempStart == -1) { tempStart = id; } } else { if (tempStart != -1) { expected.add(Pairs.intPair(tempStart, id - 1)); tempStart = -1; } } } List<IntPair> actual = SortedRangeIntersection.intersectSortedRangeSets(sortedRangePairsList); if (!actual.equals(expected)) { LOGGER.error("Actual pairs not equal to expected pairs."); LOGGER.error("Actual pairs: {}", actual); LOGGER.error("Expected pairs: {}", expected); LOGGER.error("Random seed: {}", randomSeed); LOGGER.error("Sorted range pairs list: {}", sortedRangePairsList); Assert.fail(); } }
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);  }