BsDiff { static Match searchForMatch( final RandomAccessObject groupArray, final RandomAccessObject oldData, final RandomAccessObject newData, final int newStart, final int oldDataRangeStartA, final int oldDataRangeStartB) throws IOException { if (oldDataRangeStartB - oldDataRangeStartA < 2) { return searchForMatchBaseCase( groupArray, oldData, newData, newStart, oldDataRangeStartA, oldDataRangeStartB); } final int rangeLength = oldDataRangeStartB - oldDataRangeStartA; final int pivot = oldDataRangeStartA + (rangeLength / 2); groupArray.seekToIntAligned(pivot); final int groupArrayPivot = groupArray.readInt(); if (BsUtil.lexicographicalCompare( oldData, groupArrayPivot, (int) oldData.length() - groupArrayPivot, newData, newStart, (int) newData.length() - newStart) < 0) { return searchForMatch(groupArray, oldData, newData, newStart, pivot, oldDataRangeStartB); } return searchForMatch(groupArray, oldData, newData, newStart, oldDataRangeStartA, pivot); }    }
@Test public void searchForMatchShortGroupArrayTest() throws IOException { final String s1 = "asdf;1234;this should match;5678"; final String s2 = "hkjl.9999.00vbn,``'=-this should match.9900-mmmnmn,,,.x??'"; final byte[] s1b = s1.getBytes(Charset.forName("US-ASCII")); final byte[] s2b = s2.getBytes(Charset.forName("US-ASCII")); final RandomAccessObject s1ro = new RandomAccessObject.RandomAccessByteArrayObject(s1b); final RandomAccessObject s2ro = new RandomAccessObject.RandomAccessByteArrayObject(s2b); final RandomAccessObject groupArrayRO = intArrayToRandomAccessObject(BsDiffTestData.SHORT_GROUP_ARRAY); BsDiff.Match ret = BsDiff.searchForMatch(groupArrayRO, s1ro, s2ro, 0, 0, 12); Assert.assertEquals(0, ret.length); Assert.assertEquals(10, ret.start); }
@Test public void searchForMatchLongGroupArrayTest() throws IOException { final RandomAccessObject groupArray2RO = intArrayToRandomAccessObject(BsDiffTestData.LONG_GROUP_ARRAY_100); final int scan = 1; BsDiff.Match ret = BsDiff.searchForMatch( groupArray2RO, BsDiffTestData.LONG_DATA_99_RO, BsDiffTestData.LONG_DATA_104_NEW_RO, scan, 0, BsDiffTestData.LONG_DATA_99.length); Assert.assertEquals(0, ret.length); Assert.assertEquals(52, ret.start); }
@Test public void searchForMatchVeryLongGroupArrayTest() throws IOException { final RandomAccessObject groupArray3RO = intArrayToRandomAccessObject(BsDiffTestData.LONGER_GROUP_ARRAY_350); final int scan = 1; BsDiff.Match ret = BsDiff.searchForMatch( groupArray3RO, BsDiffTestData.LONGER_DATA_349_RO, BsDiffTestData.LONGER_DATA_354_NEW_RO, scan, 0, BsDiffTestData.LONGER_DATA_349.length); Assert.assertEquals(0, ret.length); Assert.assertEquals(251, ret.start); }
@Test public void searchForMatch() throws Exception { String[] testCases = { "a", "aa", "az", "za", "aaaaa", "CACAO", "banana", "tobeornottobe", "the quick brown fox jumps over the lazy dog.", "elephantelephantelephantelephantelephant", "011010011001011010010110011010010", }; for (String testCase : testCases) { int size = testCase.length(); byte[] bytes = testCase.getBytes(StandardCharsets.US_ASCII); RandomAccessObject input = new RandomAccessObject.RandomAccessByteArrayObject(bytes); RandomAccessObject suffixArray = new DivSuffixSorter(new RandomAccessObjectFactory.RandomAccessByteArrayObjectFactory()) .suffixSort(input); for (int lo = 0; lo < size; ++lo) { for (int hi = lo + 1; hi <= size; ++hi) { byte[] query = Arrays.copyOfRange(bytes, lo, hi); int querySize = query.length; Assert.assertEquals(querySize, hi - lo); RandomAccessObject queryBuf = new RandomAccessObject.RandomAccessByteArrayObject(query); BsDiff.Match match = BsDiff.searchForMatch(suffixArray, input, queryBuf, 0, 0, size); Assert.assertEquals(querySize, match.length); Assert.assertTrue(match.start >= 0); Assert.assertTrue(match.start <= size - match.length); byte[] suffix = Arrays.copyOfRange(bytes, match.start, match.start + match.length); Assert.assertArrayEquals(query, suffix); } } } }