BufferTree.java

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());
    }
  }
}

TreeExample.java

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();
  }
  
}

TreeExample2.java

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();
  }

}