Skip to content

Instantly share code, notes, and snippets.

@quoll
Last active Sep 10, 2019
Embed
What would you like to do?
package tree;
import java.io.File;
import java.io.Closeable;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.channels.FileChannel;
import java.nio.ByteBuffer;
import java.nio.IntBuffer;
public class BufferTree implements Closeable {
public static int NODE_SIZE = 3 * Integer.BYTES;
public static int META_SIZE = 2 * Integer.BYTES;
public static int NULL = 0;
// META offsets
private static int NEXT_AVAILABLE_OFFSET = 0;
private static int ROOT_OFFSET = 1;
// Node offsets
private static int VALUE_OFFSET = 0;
private static int LEFT_OFFSET = 1;
private static int RIGHT_OFFSET = 2;
private final RandomAccessFile file;
private final FileChannel fileChannel;
private ByteBuffer buffer;
private IntBuffer metaBuffer;
private Node root;
public BufferTree() throws IOException {
this("buffer.bin", 20);
}
public BufferTree(int length) throws IOException {
this("buffer.bin", length);
}
public BufferTree(String filename) throws IOException {
this(filename, 20);
}
public BufferTree(String filename, int length) throws IOException {
long fileLength = NODE_SIZE * length;
File ioFile = new File(filename);
boolean exists = ioFile.exists();
file = new RandomAccessFile(filename, "rw");
if (exists && file.length() > fileLength) {
fileLength = file.length();
} else if (fileLength > file.length()) {
file.setLength(fileLength);
}
fileChannel = file.getChannel();
buffer = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, fileLength);
metaBuffer = buffer.limit(META_SIZE).position(0).slice().asIntBuffer();
if (!exists) {
setNextAvailable(1);
}
int rootIndex = metaBuffer.get(ROOT_OFFSET);
root = rootIndex == NULL ? null : new Node(rootIndex);
}
public void close() throws IOException {
fileChannel.force(true);
file.close();
}
public BufferTree add(int value) {
Node node = new Node(getAndIncNextAvailable(), value);
if (root == null) {
setRoot(node);
} else {
insertNode(root, node);
}
return this;
}
private void setNextAvailable(int next) {
metaBuffer.put(NEXT_AVAILABLE_OFFSET, next);
}
private int getAndIncNextAvailable() {
int next = metaBuffer.get(NEXT_AVAILABLE_OFFSET);
if ((next + 1) * NODE_SIZE > buffer.capacity()) {
throw new RuntimeException("Out of capacity");
}
metaBuffer.put(NEXT_AVAILABLE_OFFSET, next + 1);
return next;
}
private void setRoot(Node node) {
root = node;
metaBuffer.put(ROOT_OFFSET, node.getIndex());
}
public Node getRoot() {
return root;
}
public String toString() {
return root.toString();
}
private void insertNode(Node node, Node newNode) {
int value = node.getValue();
if (newNode.getValue() < value) {
Node left = node.getLeft();
if (left == null) {
node.setLeft(newNode);
} else {
insertNode(left, newNode);
}
} else {
Node right = node.getRight();
if (right == null) {
node.setRight(newNode);
} else {
insertNode(right, newNode);
}
}
}
public static String treeString(Node element) {
Node left = element.getLeft();
Node right = element.getRight();
return (left == null ? "" : treeString(left)) +
Integer.toString(element.getValue()) +
(right == null ? "" : treeString(right));
}
public class Node {
private final IntBuffer intBuffer;
private final int index;
Node(int index) {
this.index = index;
int offset = index * NODE_SIZE;
if (offset > buffer.limit()) {
intBuffer = buffer.limit(offset + NODE_SIZE).position(offset).slice().asIntBuffer();
} else {
intBuffer = buffer.position(offset).limit(offset + NODE_SIZE).slice().asIntBuffer();
}
}
Node(int index, int value) {
this(index);
setValue(value);
setLeft(null);
setRight(null);
}
public int getIndex() {
return index;
}
public int getValue() {
return intBuffer.get(VALUE_OFFSET);
}
public Node getLeft() {
int leftId = intBuffer.get(LEFT_OFFSET);
return leftId == NULL ? null : new Node(leftId);
}
public Node getRight() {
int rightId = intBuffer.get(RIGHT_OFFSET);
return rightId == NULL ? null : new Node(rightId);
}
public Node setValue(int value) {
intBuffer.put(VALUE_OFFSET, value);
return this;
}
public Node setLeft(Node left) {
intBuffer.put(LEFT_OFFSET, left == null ? NULL : left.getIndex());
return this;
}
public Node setRight(Node right) {
intBuffer.put(RIGHT_OFFSET, right == null ? NULL : right.getIndex());
return this;
}
public String toString() {
Node left = getLeft();
Node right = getRight();
return (left == null ? "" : left.toString() + ", ") +
Integer.toString(getValue()) +
(right == null ? "" : ", " + right.toString());
}
}
}
package tree;
import java.io.RandomAccessFile;
import java.io.IOException;
import java.nio.ByteBuffer;
public class TreeExample {
public static void main(String[] args) throws IOException {
BufferTree bufferTree = new BufferTree("tree.bin", 25);
bufferTree.add(3);
bufferTree.add(1);
bufferTree.add(4);
bufferTree.add(1);
bufferTree.add(5);
bufferTree.add(9);
bufferTree.add(2);
bufferTree.add(6);
bufferTree.add(5);
bufferTree.add(3);
System.out.println(bufferTree);
bufferTree.close();
}
}
package tree;
import java.io.IOException;
import java.nio.ByteBuffer;
public class TreeExample2 {
public static void main(String[] args) throws IOException {
BufferTree bufferTree = new BufferTree("tree.bin", 25);
System.out.println(bufferTree);
bufferTree.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment