Last active
September 1, 2017 05:36
-
-
Save mikee805/c6c2e6a35032a3ab74f643a1d0f8249c to your computer and use it in GitHub Desktop.
java binary search using a bytebuffer
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import static java.nio.file.Files.isWritable; | |
import static java.nio.file.StandardOpenOption.READ; | |
import static org.apache.commons.io.FileUtils.forceMkdir; | |
import static org.apache.commons.io.IOUtils.closeQuietly; | |
import static org.apache.commons.lang3.StringUtils.isBlank; | |
import static org.apache.commons.lang3.StringUtils.trimToNull; | |
import java.io.File; | |
import java.io.IOException; | |
import java.nio.Buffer; | |
import java.nio.MappedByteBuffer; | |
import java.nio.channels.FileChannel; | |
import java.nio.file.Path; | |
public class FileUtils { | |
private FileUtils() { | |
} | |
private static boolean found(final String candidate, final String prefix) { | |
return isBlank(candidate) || candidate.startsWith(prefix); | |
} | |
private static boolean before(final String candidate, final String prefix) { | |
return prefix.compareTo(candidate.substring(0, prefix.length())) < 0; | |
} | |
public static MappedByteBuffer getMappedByteBuffer(final Path path) { | |
FileChannel fileChannel = null; | |
try { | |
fileChannel = FileChannel.open(path, READ); | |
return fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size()).load(); | |
} | |
catch (Exception e) { | |
throw new RuntimeException(e); | |
} | |
finally { | |
closeQuietly(fileChannel); | |
} | |
} | |
public static String binarySearch(final String prefix, final MappedByteBuffer buffer) { | |
if (buffer == null) { | |
return null; | |
} | |
try { | |
long low = 0; | |
long high = buffer.limit(); | |
while (low < high) { | |
int mid = (int) ((low + high) / 2); | |
final String candidate = getLine(mid, buffer); | |
if (found(candidate, prefix)) { | |
return trimToNull(candidate); | |
} | |
else if (before(candidate, prefix)) { | |
high = mid; | |
} | |
else { | |
low = mid + 1; | |
} | |
} | |
} | |
catch (Exception e) { | |
throw new RuntimeException(e); | |
} | |
return null; | |
} | |
private static String getLine(int position, final MappedByteBuffer buffer) { | |
// search backwards to the find the proceeding new line | |
// then search forwards again until the next new line | |
// return the string in between | |
final StringBuilder stringBuilder = new StringBuilder(); | |
// walk it back | |
char candidate = (char)buffer.get(position); | |
while (position > 0 && candidate != '\n') { | |
candidate = (char)buffer.get(--position); | |
} | |
// we either are at the beginning of the file or a new line | |
if (position == 0) { | |
// we are at the beginning at the first char | |
candidate = (char)buffer.get(position); | |
stringBuilder.append(candidate); | |
} | |
// there is/are char(s) after new line / first char | |
if (isInBuffer(buffer, position)) { | |
//first char after new line | |
candidate = (char)buffer.get(++position); | |
stringBuilder.append(candidate); | |
//walk it forward | |
while (isInBuffer(buffer, position) && candidate != ('\n')) { | |
candidate = (char)buffer.get(++position); | |
stringBuilder.append(candidate); | |
} | |
} | |
return stringBuilder.toString(); | |
} | |
private static boolean isInBuffer(final Buffer buffer, int position) { | |
return position + 1 < buffer.limit(); | |
} | |
public static File getOrCreateDirectory(final String dirName) { | |
final File directory = new File(dirName); | |
try { | |
forceMkdir(directory); | |
isWritable(directory.toPath()); | |
} | |
catch (IOException e) { | |
throw new RuntimeException(e); | |
} | |
return directory; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment