Sunday 7 December 2014

Random Gutenberg

Random Gutenberg is a Twitter bot which tweets random sentences from random Project Gutenberg eBooks.

RandomGutenberg.java

package org.adrianwalker.randomgutenberg;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import static java.lang.String.format;
import java.net.URL;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.zip.ZipInputStream;
import org.apache.log4j.Logger;
import twitter4j.Status;
import twitter4j.Twitter;
import twitter4j.TwitterFactory;

public final class RandomGutenberg {

  private static final Logger LOGGER = Logger.getLogger(RandomGutenberg.class);
  private static final int MAX_OFFSET = 3934400;
  private static final String GUTENBERG_ROBOT_URL = "http://www.gutenberg.org/robot/harvest?offset=%s&filetypes[]=txt";
  private static final Pattern HREF_PATTERN = Pattern.compile("href=\"(http://.*)\"");
  private static final Pattern SENTENCE_ENDINGS_PATTERN = Pattern.compile("(?<=\\s?\"?[.!?]\"?\\s?)");
  private static final Pattern WORD_ENDINGS_PATTERN = Pattern.compile("\\s");
  private static final int MAX_TRIES = 3;
  private static final int MAX_TWEET_LENGTH = 140;
  private static final int MIN_WORD_COUNT = 3;

  public static void main(final String[] args) {

    Random randomNumberGenerator = new Random(new Random(System.currentTimeMillis()).nextLong());

    String eBookText = null;

    for (int tries = 0; tries < MAX_TRIES; tries++) {
      try {
        eBookText = getRandomEbookText(randomNumberGenerator);
        break;
      } catch (final Throwable t) {
        LOGGER.error("Error getting eBook text", t);
      }
    }

    if (null == eBookText) {
      return;
    }

    String sentence = getRandomSentence(eBookText, randomNumberGenerator);

    try {
      tweet(sentence);
    } catch (final Throwable t) {
      LOGGER.error("Error sending tweet", t);
    }
  }

  private static String getRandomSentence(final String eBookText, final Random randomNumberGenerator) {

    List<String> sentences = new ArrayList<>(Arrays.asList(SENTENCE_ENDINGS_PATTERN.split(eBookText)));

    Iterator<String> sentenceIterator = sentences.iterator();
    while (sentenceIterator.hasNext()) {

      String sentence = sentenceIterator.next();
      String[] words = WORD_ENDINGS_PATTERN.split(sentence);

      int sentenceLength = sentence.length();
      int wordCount = words.length;

      if (wordCount < MIN_WORD_COUNT || sentenceLength > MAX_TWEET_LENGTH) {
        sentenceIterator.remove();
      }
    }

    String sentence = sentences.get(randomNumberGenerator.nextInt(sentences.size()));

    return sentence;
  }

  private static String getRandomEbookText(final Random randomNumberGenerator) throws Throwable {

    int offset = randomNumberGenerator.nextInt(MAX_OFFSET);
    URL url = new URL(format(GUTENBERG_ROBOT_URL, offset));

    BufferedReader reader = new BufferedReader(new InputStreamReader(url.openStream()));
    List<String> hrefs = new ArrayList<>();

    String line;
    while (null != (line = reader.readLine())) {

      Matcher matcher = HREF_PATTERN.matcher(line);

      if (matcher.find()) {
        hrefs.add(matcher.group(1));
      }
    }

    reader.close();

    String randomHref = hrefs.get(randomNumberGenerator.nextInt(hrefs.size()));

    url = new URL(randomHref);

    ZipInputStream zis = new ZipInputStream(url.openStream());
    zis.getNextEntry();
    reader = new BufferedReader(new InputStreamReader(zis));
    StringBuilder eBookBuffer = new StringBuilder();

    while (null != (line = reader.readLine())) {

      if (eBookBuffer.length() > 0) {
        eBookBuffer.append(" ");
      }

      line = line.trim();
      eBookBuffer.append(line);
    }

    reader.close();

    String eBookText = eBookBuffer.toString();

    return eBookText;
  }

  private static Status tweet(final String sentence) throws Throwable {

    String message = sentence;

    Twitter twitter = TwitterFactory.getSingleton();
    Status status = twitter.updateStatus(message);

    return status;
  }
}

Source Code

Rule 30

Wolfram's Rule 30 is proper interesting, isn't it?

Here is a Java implementation:

Wolfram.java

package org.adrianwalker.cellularautomation;

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import javax.imageio.ImageIO;

public final class Wolfram {

  private static final int MAX_TIME = 500;
  private static final int MAX_SPACE = MAX_TIME * 2;
  private static final int WHITE = Color.WHITE.getRGB();
  private static final int BLACK = Color.BLACK.getRGB();
  private static final String FORMAT = "png";
  private static final String OUTPUT = "/var/tmp/output.png";

  // cell to RGB lookup
  private static final Map<Integer, Integer> CELL_RGB = new HashMap<>();
  static {
    CELL_RGB.put(0, WHITE);
    CELL_RGB.put(1, BLACK);
  }

  // RGB to cell lookup
  private static final Map<Integer, Integer> RGB_CELL = new HashMap<>();
  static {
    RGB_CELL.put(WHITE, 0);
    RGB_CELL.put(BLACK, 1);
  }

  // http://en.wikipedia.org/wiki/Rule_30
  //
  // current pattern          111 110 101 100 011 010 001 000
  // new state for center cell 0   0   0   1   1   1   1   0
  private static final Map<Integer, Integer> RULE_30 = new HashMap<>();
  static {
    RULE_30.put(Arrays.hashCode(new int[]{1, 1, 1}), 0);
    RULE_30.put(Arrays.hashCode(new int[]{1, 1, 0}), 0);
    RULE_30.put(Arrays.hashCode(new int[]{1, 0, 1}), 0);
    RULE_30.put(Arrays.hashCode(new int[]{1, 0, 0}), 1);
    RULE_30.put(Arrays.hashCode(new int[]{0, 1, 1}), 1);
    RULE_30.put(Arrays.hashCode(new int[]{0, 1, 0}), 1);
    RULE_30.put(Arrays.hashCode(new int[]{0, 0, 1}), 1);
    RULE_30.put(Arrays.hashCode(new int[]{0, 0, 0}), 0);
  }

  public static void main(final String[] args) throws Throwable {

    BufferedImage image = new BufferedImage(MAX_SPACE, MAX_TIME, BufferedImage.TYPE_INT_RGB);

    init(image);
    execute(image, RULE_30);

    ImageIO.write(image, FORMAT, new File(OUTPUT));
  }

  private static void init(final BufferedImage image) {

    int time;
    int space;
    for (time = 0; time < MAX_TIME; time++) {
      for (space = 0; space < MAX_SPACE; space++) {
        image.setRGB(space, time, WHITE);
      }
    }

    time = 0;
    space = MAX_SPACE / 2;
    image.setRGB(space, time, BLACK);
  }

  private static void execute(final BufferedImage image, final Map<Integer, Integer> rule) {

    for (int time = 1; time < MAX_TIME; time++) {
      for (int space = 1; space < MAX_SPACE - 1; space++) {

        int[] pattern = {
          RGB_CELL.get(image.getRGB(space - 1, time - 1)),
          RGB_CELL.get(image.getRGB(space, time - 1)),
          RGB_CELL.get(image.getRGB(space + 1, time - 1))
        };

        int cell = rule.get(Arrays.hashCode(pattern));
        image.setRGB(space, time, CELL_RGB.get(cell));
      }
    }
  }
}

Output


(Click To Enlarge)

Saturday 4 October 2014

Continued Fraction Database File System

After reading Joe Celko's SQL for Smarties on representing hierarchies in SQL databases, I wanted to have a go at creating a database backed file system.

Representing a file system using the Adjacency List Model detailed in chapter 2 is probably good enough for this sort of task, but that's a bit dull, and the Nested Set Model from chapter 4 is a cool way of looking at trees which I would have never have thought of.

Almost immediately the Nested Set model starts to look like a bad idea for a file system due to the performance implications of inserting into the middle of the tree.

Chapter 5 introduces the use of rational numbers and the Nested Interval Model from Vadim Tropashko, and at this point I quickly began not to care.

Then I came across this short but sweet report by Dan Hazel, Using rational numbers to key nested sets.

The paper quickly covers the Nested Set Model as described by Celko and touches on the similarity of the method presented to that of an encoding by Tropashko.

The paper describes a method of using rational numbers as node keys, and a way of calculating their numerators and denominators using the node positions in the tree represented as a continued fraction.

I wasn't taught continued fractions at school, so I had to go brush up before understanding the paper. It's actually a very interesting topic and there are a few good YouTube videos which can bring you up to speed. I liked this one.

I wont describe Dan Hazels report any further as I can't do it justice – it's very good, go read it now, and come back for a look at my implementation using Java and PostgreSQL.

Welcome back. First I needed a way of converting from a continued fraction node path into a fraction numerator and denominator.

  
public static int[] fraction(final int[] c) {

  int[] f = F[0];

  for (int i = c.length - 1; i >= 0; i--) {
    f = add(F[1], invert(f));
    f = add(fraction(c[i], 1), invert(f));
  }

  return f;
}

This function takes an array of integers which represent the continued fraction node path and returns a fraction as a 2 element integer array, containing the fractions numerator and denominator.

This operation is reversible and the function below takes a fraction as an integer array numerator and denominator and returns a continued fraction.

  
public static int[] continued(final int[] f) {

  int[] a = f;

  List<Integer> c = new ArrayList<>();
  while (a[0] > 0) {

    int i = a[0] / a[1];
    c.add(i);

    a = invert(subtract(a, fraction(i, 1)));
    a = invert(subtract(a, F[1]));
  }

  return toArray(c);
}

These are the two most important functions in a class which contains other operations required to manipulate fractions.

Fraction.java

package org.adrianwalker.continuedfractions;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.List;

public final class Fraction {

  private static final int[][] F = {
    {0, 1},
    {1, 1}
  };
  private static final int PRECISION = 16;

  private Fraction() {
  }

  public static int[] fraction(final int n, final int d) {

    return new int[]{n, d};
  }

  public static int[] fraction(final int[] pf, final int c, final int[] spf) {

    return fraction(pf[0] + c * spf[0], pf[1] + c * spf[1]);
  }

  public static int[] fraction(final int[] c) {

    int[] f = F[0];

    for (int i = c.length - 1; i >= 0; i--) {
      f = add(F[1], invert(f));
      f = add(fraction(c[i], 1), invert(f));
    }

    return f;
  }

  public static int[] continued(final int[] f) {

    int[] a = f;

    List<Integer> c = new ArrayList<>();
    while (a[0] > 0) {

      int i = a[0] / a[1];
      c.add(i);

      a = invert(subtract(a, fraction(i, 1)));
      a = invert(subtract(a, F[1]));
    }

    return toArray(c);
  }

  public static BigDecimal decimal(final int[] f) {

    return BigDecimal.valueOf(f[0]).divide(BigDecimal.valueOf(f[1]), PRECISION, RoundingMode.HALF_DOWN);
  }

  public static int[] add(final int[] f1, final int[] f2) {

    return fraction((f1[0] * f2[1]) + (f2[0] * f1[1]), f2[1] * f1[1]);
  }

  public static int[] subtract(final int[] f1, final int[] f2) {

    return fraction((f1[0] * f2[1]) - (f2[0] * f1[1]), f1[1] * f2[1]);
  }

  public static int[] invert(final int[] f) {

    return fraction(f[1], f[0]);
  }

  private static int[] toArray(final List<Integer> l) {

    int[] a = new int[l.size()];

    for (int i = 0; i < a.length; i++) {
      a[i] = l.get(i);
    }

    return a;
  }
}

Next I needed a class to manipulate Matrices and perform the sub tree moving calculations as detailed in the paper.

Matrix.java

package org.adrianwalker.continuedfractions;

public final class Matrix {

  private Matrix() {
  }

  public static int[][] matrix(
          final int M00, final int M01,
          final int M10, final int M11) {

    return new int[][]{{M00, M01}, {M10, M11}};
  }

  public static int[][] multiply(final int[][] M1, final int[][] M2) {

    return matrix(
            M1[0][0] * M2[0][0] + M1[0][1] * M2[1][0],
            M1[0][0] * M2[0][1] + M1[0][1] * M2[1][1],
            M1[1][0] * M2[0][0] + M1[1][1] * M2[1][0],
            M1[1][0] * M2[0][1] + M1[1][1] * M2[1][1]
    );
  }

  public static int[][] invert(final int[][] M) {

    return matrix(-M[1][1], M[0][1], M[1][0], -M[0][0]);
  }

  public static int[][] moveSubtree(final int[][] p0, final int m, final int[][] p1, int n, final int[][] M) {

    return multiply(multiply(multiply(p1, matrix(1, 0, m - n, 1)), invert(p0)), M);
  }
}

With the basic calculations nailed, next up is the database. The schema is a single table which uses the real value of the rational representation of the node as the primary key (id). Along with the primary key, the fractions numerator and denominator are stored (nv and dv), then the id and numerator and dominator of the nodes next largest sibling in the tree.

The level of the node in the tree is also stored, simply to help limit the depth of tree queries later on. And also the name of the node – what will be the file or directory name is stored in the row, along with a file content oid.

I've chosen PostgreSQL for this implementation - it provides an in row BYTEA type for storing binary data, or an off table Binary Large Object storage mechanism, with data accessible by an OID key. I've gone with the OIDs as they provide better support for IO streams, but the code could be easily modified to support BYTEA columns, or any other BLOB storage mechanism you might want to use in your RDBMS implementation.

files.sql

CREATE TABLE files
(
  id numeric NOT NULL,
  nv integer NOT NULL,
  dv integer NOT NULL,
  sid numeric NOT NULL,
  snv integer NOT NULL,
  sdv integer NOT NULL,
  level integer NOT NULL,
  name character varying NOT NULL,
  content oid NOT NULL,
  CONSTRAINT files_pkey PRIMARY KEY (id)
);

CREATE INDEX files_name_idx ON files (name);
CREATE INDEX files_level_idx ON files (level);

Next the Java database access code to perform basic operations on the database. This module uses continued fraction paths as inputs to almost all the methods, and is intended for lower level access to files held in the database.

FilesDAO.java

package org.adrianwalker.continuedfractions.filesystem;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.math.BigDecimal;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.List;
import static org.adrianwalker.continuedfractions.Fraction.decimal;
import static org.adrianwalker.continuedfractions.Fraction.fraction;
import static org.adrianwalker.continuedfractions.Matrix.matrix;
import static org.adrianwalker.continuedfractions.Matrix.moveSubtree;
import static org.adrianwalker.continuedfractions.filesystem.Path.parent;
import static org.adrianwalker.continuedfractions.filesystem.Path.sibling;
import org.postgresql.largeobject.LargeObject;
import org.postgresql.largeobject.LargeObjectManager;

public final class FilesDAO {

  private static final String WRITE
          = "insert into files (id, nv, dv, sid, snv, sdv, level, name, content) "
          + "values(?, ?, ?, ?, ?, ?, ?, ?, ?)";
  private static final String READ
          = "select id, nv, dv, sid, snv, sdv, level, name, content "
          + "from files "
          + "where id = ?";
  private static final String TREE
          = "select id, nv, dv, sid, snv, sdv, level, name, content "
          + "from files "
          + "where id >= ? "
          + "and id < (select sid from files where id = ?)";
  private static final String CHILDREN
          = TREE
          + " and level = ?";
  private static final String CHILD
          = CHILDREN
          + " and name = ?";
  private static final String LAST_CHILD
          = CHILDREN
          + " order by id desc "
          + "limit 1";
  private static final String RENAME
          = "update files "
          + "set name = ? "
          + "where id = ?";
  private static final String MOVE
          = "update files "
          + "set id = ?, nv = ?, dv = ?, sid = ?, snv = ?, sdv = ?, level = ? "
          + "where id = ?";
  private static final String REMOVE
          = "delete from files "
          + "where id >= ? "
          + "and id < (select sid from files where id = ?)";
  private static final String CLEAR = "delete from files";
  private static final String ORDER_BY_ID = " order by id";
  private static final String ORDER_BY_NAME = " order by name";

  private final Connection connection;
  private final LargeObjectManager lom;

  public FilesDAO(final Connection connection) throws SQLException {

    this.connection = connection;
    this.lom = ((org.postgresql.PGConnection) connection).getLargeObjectAPI();
  }

  private PreparedStatement prepareStatement(final String sql) throws SQLException {

    return connection.prepareStatement(sql);
  }

  public int clear() throws SQLException {

    PreparedStatement remove = prepareStatement(CLEAR);

    return remove.executeUpdate();
  }

  public File write(final String filename, final int... path) throws SQLException {

    int[] f = fraction(path);
    int[] sf = fraction(sibling(path));
    int level = path.length;

    BigDecimal id = decimal(f);
    BigDecimal sid = decimal(sf);
    long content = lom.createLO();

    PreparedStatement write = prepareStatement(WRITE);
    write.setBigDecimal(1, id);
    write.setInt(2, f[0]);
    write.setInt(3, f[1]);
    write.setBigDecimal(4, sid);
    write.setInt(5, sf[0]);
    write.setInt(6, sf[1]);
    write.setInt(7, level);
    write.setString(8, filename);
    write.setLong(9, content);

    write.executeUpdate();

    return new File(id, f[0], f[1], sid, sf[0], sf[1], level, filename, content);
  }

  public File read(final int... path) throws SQLException {

    BigDecimal id = decimal(fraction(path));

    PreparedStatement read = prepareStatement(READ);
    read.setBigDecimal(1, id);

    ResultSet rs = read.executeQuery();

    return toFile(rs);
  }

  public File[] children(final int... path) throws SQLException {

    BigDecimal id = decimal(fraction(path));

    PreparedStatement children = prepareStatement(CHILDREN + ORDER_BY_NAME);
    children.setBigDecimal(1, id);
    children.setBigDecimal(2, id);
    children.setInt(3, path.length + 1);

    return toFiles(children.executeQuery());
  }

  public File child(final String name, final int... path) throws SQLException {

    BigDecimal id = decimal(fraction(path));

    PreparedStatement child = prepareStatement(CHILD);
    child.setBigDecimal(1, id);
    child.setBigDecimal(2, id);
    child.setInt(3, path.length + 1);
    child.setString(4, name);

    return toFile(child.executeQuery());
  }

  public File lastChild(final int... path) throws SQLException {

    BigDecimal id = decimal(fraction(path));

    PreparedStatement lastChild = prepareStatement(LAST_CHILD);
    lastChild.setBigDecimal(1, id);
    lastChild.setBigDecimal(2, id);
    lastChild.setInt(3, path.length + 1);

    return toFile(lastChild.executeQuery());
  }

  public File[] tree(final int... path) throws SQLException {

    BigDecimal id = decimal(fraction(path));

    PreparedStatement tree = prepareStatement(TREE + ORDER_BY_ID);
    tree.setBigDecimal(1, id);
    tree.setBigDecimal(2, id);

    return toFiles(tree.executeQuery());
  }

  public int rename(final String filename, final int... path) throws SQLException {

    BigDecimal id = decimal(fraction(path));

    PreparedStatement rename = prepareStatement(RENAME);
    rename.setString(1, filename);
    rename.setBigDecimal(2, id);

    return rename.executeUpdate();
  }

  public int remove(final int... path) throws SQLException {

    for (File file : tree(path)) {
      lom.delete(file.getContent());
    }

    BigDecimal id = decimal(fraction(path));

    PreparedStatement remove = prepareStatement(REMOVE);
    remove.setBigDecimal(1, id);
    remove.setBigDecimal(2, id);

    return remove.executeUpdate();
  }

  public int[] move(final int[] from, final int[] to) throws SQLException, IOException {

    return moveCopy(MOVE, from, to);
  }

  public int[] copy(final int[] from, final int[] to) throws SQLException, IOException {

    return moveCopy(WRITE, from, to);
  }

  private int[] moveCopy(final String sql, final int[] from, final int[] to) throws SQLException, IOException {

    int[] p = parent(from);
    int[] pf0 = fraction(p);
    int[] psf0 = fraction(sibling(p));
    int[] pf1 = fraction(to);
    int[] psf1 = fraction(sibling(to));

    int m = 1;
    File lc = lastChild(to);
    if (null != lc) {
      m = (lc.getSnv() - pf1[0]) / psf1[0];
    }

    int n = from[from.length - 1];

    int[][] p0 = matrix(pf0[0], psf0[0], pf0[1], psf0[1]);
    int[][] p1 = matrix(pf1[0], psf1[0], pf1[1], psf1[1]);

    PreparedStatement move = prepareStatement(sql);

    for (File file : tree(from)) {

      int[][] M0 = matrix(file.getNv(), file.getSnv(), file.getDv(), file.getSdv());
      int[][] M1 = moveSubtree(p0, m, p1, n, M0);

      int[] f = fraction(M1[0][0], M1[1][0]);
      int[] sf = fraction(M1[0][1], M1[1][1]);
      BigDecimal id = decimal(f);
      BigDecimal sid = decimal(sf);
      int level = to.length + (file.getLevel() - p.length);

      move.setBigDecimal(1, id);
      move.setInt(2, f[0]);
      move.setInt(3, f[1]);
      move.setBigDecimal(4, sid);
      move.setInt(5, sf[0]);
      move.setInt(6, sf[1]);
      move.setInt(7, level);

      switch (sql) {

        case MOVE:
          move.setBigDecimal(8, file.getId());
          break;

        case WRITE:
          long oid = lom.createLO();

          move.setString(8, file.getName());
          move.setLong(9, oid);

          Stream.copy(getInputStream(file.getContent()), getOutputStream(oid));

          break;
      }

      move.addBatch();
    }

    return move.executeBatch();
  }

  public InputStream getInputStream(final long oid) throws SQLException {

    LargeObject obj = lom.open(oid, LargeObjectManager.READ);

    return obj.getInputStream();
  }

  public OutputStream getOutputStream(final long oid) throws SQLException {

    LargeObject obj = lom.open(oid, LargeObjectManager.WRITE);

    return obj.getOutputStream();
  }

  private File toFile(final ResultSet rs) throws SQLException {

    File file = null;

    if (rs.next()) {
      file = new File(rs.getBigDecimal(1), rs.getInt(2), rs.getInt(3),
              rs.getBigDecimal(4), rs.getInt(5), rs.getInt(6),
              rs.getInt(7), rs.getString(8), rs.getLong(9));
    }

    return file;
  }

  private File[] toFiles(final ResultSet rs) throws SQLException {

    List<File> l = new ArrayList<>();

    while (rs.next()) {
      l.add(new File(rs.getBigDecimal(1), rs.getInt(2), rs.getInt(3),
              rs.getBigDecimal(4), rs.getInt(5), rs.getInt(6),
              rs.getInt(7), rs.getString(8), rs.getLong(9)));
    }

    return l.toArray(new File[l.size()]);
  }
}

And finally a higher level API for dealing directly with file names and paths in a manner similar to how you might use them on a command line.

FileSystem.java

package org.adrianwalker.continuedfractions.filesystem;

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.sql.SQLException;
import static org.adrianwalker.continuedfractions.filesystem.Path.range;

public final class FileSystem {

  private static final String SEPERATOR = "/";
  private static final String EMPTY_STRING = "";
  private final FilesDAO dao;
  private final int[] rootPath;

  public FileSystem(final FilesDAO dao, final int... rootPath) throws FileSystemException {

    this.dao = dao;
    this.rootPath = rootPath;

    try {
      if (null == dao.read(rootPath)) {
        dao.write("", rootPath);
      }
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }
  }

  public int[] create(final String path) throws FileSystemException {

    try {
      return path(path, true);
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }
  }

  public File[] list(final String path) throws FileSystemException {

    try {
      return dao.children(path(path, false));
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }
  }

  public File[] tree(final String path) throws FileSystemException {

    try {
      return dao.tree(path(path, false));
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }
  }

  public void write(final String path, final String text) throws FileSystemException {

    OutputStream out = getOutputStream(path);

    try {
      Stream.fromString(text, out);
    } catch (final IOException ioe) {
      throw new FileSystemException(ioe);
    }
  }

  public OutputStream getOutputStream(final String path) throws FileSystemException {

    OutputStream out;

    try {
      out = dao.getOutputStream(dao.read(path(path, true)).getContent());
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }

    return out;
  }

  public String read(final String path) throws FileSystemException {

    InputStream in = getInputStream(path);

    if (null == in) {
      return EMPTY_STRING;
    }

    try {
      return Stream.toString(in);
    } catch (final IOException ioe) {
      throw new FileSystemException(ioe);
    }
  }

  public InputStream getInputStream(final String path) throws FileSystemException {

    InputStream in;

    try {
      in = dao.getInputStream(dao.read(path(path, false)).getContent());
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }

    return in;
  }

  public void delete(final String path) throws FileSystemException {

    try {
      dao.remove(path(path, false));
    } catch (final SQLException sqle) {
      throw new FileSystemException(sqle);
    }
  }

  public void move(final String from, final String to) throws FileSystemException {

    try {
      dao.move(path(from, false), path(to, true));
    } catch (final SQLException | IOException ex) {
      throw new FileSystemException(ex);
    }
  }

  public void copy(final String from, final String to) throws FileSystemException {

    try {
      dao.copy(path(from, false), path(to, true));
    } catch (final SQLException | IOException ex) {
      throw new FileSystemException(ex);
    }
  }

  private int[] path(final String s, final boolean create) throws SQLException {

    String[] names = s.split(SEPERATOR);
    int[] path = range(rootPath, 0, rootPath.length + (names.length > 0 ? names.length - 1 : 0));

    File f = dao.read(rootPath);

    for (int level = 1; level < names.length; level++) {

      File p = f;

      f = dao.child(names[level], range(path, 0, level));

      if (null != f) {

        path[level] = (f.getNv() - p.getNv()) / p.getSnv();

      } else if (null == f && create) {

        path[level] = 1;
        File lc = dao.lastChild(range(path, 0, level));
        if (null != lc) {
          path[level] = (lc.getSnv() - p.getNv()) / p.getSnv();
        }

        f = dao.write(names[level], range(path, 0, level + 1));
      }
    }

    return path;
  }
}

An example usage of the above high level API for creating directories, reading and writing files, and moving sub trees is below.

Example.java

package org.adrianwalker.continuedfractions.filesystem.example;

import java.sql.Connection;
import java.sql.DriverManager;
import org.adrianwalker.continuedfractions.filesystem.File;
import org.adrianwalker.continuedfractions.filesystem.FileSystem;
import org.adrianwalker.continuedfractions.filesystem.FilesDAO;
import static org.adrianwalker.continuedfractions.filesystem.Printer.print;

public class Example {

  private static final String DRIVER = "org.postgresql.Driver";
  private static final String URL = "jdbc:postgresql://localhost:5432/postgres";
  private static final String USERNAME = "postgres";
  private static final String PASSWORD = "postgres";

  public static void main(final String[] args) throws Exception {

    Class.forName(DRIVER);
    Connection connection = DriverManager.getConnection(URL, USERNAME, PASSWORD);
    connection.setAutoCommit(false);

    FilesDAO dao = new FilesDAO(connection);
    dao.clear();

    FileSystem fs = new FileSystem(dao, 1);

    System.out.println("Create directories\n");

    fs.create("/bin");
    fs.create("/dev");
    fs.create("/etc");
    fs.create("/home");
    fs.create("/sbin");
    fs.create("/usr");

    fs.create("/home/adrian");
    fs.create("/home/other");

    fs.create("/home/adrian/documents/text");
    fs.create("/home/adrian/documents/presentations");
    fs.create("/home/adrian/documents/spreadsheets");

    connection.commit();

    print(fs.tree("/"));

    System.out.println("\nWrite files\n");

    fs.write("/home/adrian/documents/text/test1.txt", "Hello");
    fs.write("/home/adrian/documents/text/test2.txt", "Database");
    fs.write("/home/adrian/documents/text/test3.txt", "File System");
    fs.write("/home/adrian/documents/text/test4.txt", "World!");

    connection.commit();

    print(fs.tree("/"));

    System.out.println("\nMove files\n");

    fs.move("/home/adrian/documents", "/home/other");

    connection.commit();

    print(fs.tree("/"));

    System.out.println("\nPrint files\n");

    for (File file : fs.list("/home/other/documents/text")) {
      System.out.println(fs.read("/home/other/documents/text/" + file.getName()));
    }
  }
}

The above example code produces the output:

Create directories

/
  /bin
  /dev
  /etc
  /home
    /adrian
      /documents
        /text
        /presentations
        /spreadsheets
    /other
  /sbin
  /usr

Write files

/
  /bin
  /dev
  /etc
  /home
    /adrian
      /documents
        /text
          /test1.txt
          /test2.txt
          /test3.txt
          /test4.txt
        /presentations
        /spreadsheets
    /other
  /sbin
  /usr

Move files

/
  /bin
  /dev
  /etc
  /home
    /adrian
    /other
      /documents
        /text
          /test1.txt
          /test2.txt
          /test3.txt
          /test4.txt
        /presentations
        /spreadsheets
  /sbin
  /usr

Print files

Hello
Database
File System
World!

Source Code

Saturday 9 August 2014

Lispy Java 8

After reading Peter Norvig's post (How to Write a (Lisp) Interpreter (in Python)), I thought I'd have a go at doing the same thing in Java 8:

Lispy.java

package org.adrianwalker.lispy;

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public final class Lispy {

  private class Env extends HashMap<String, Object> {

    private final Env outer;

    public Env(final List<String> params, final List<Object> args, final Env outer) {
      IntStream.range(0, params.size()).forEach(i -> put(params.get(i), args.get(i)));
      this.outer = outer;
    }

    public Env find(final Object var) {
      return this.containsKey(var) ? this : outer.find(var);
    }
  }

  private Env addGlobal(final Env env) {
    env.put("+", (Function<List<Double>, Double>) (List<Double> args) -> args.get(0) + args.get(1));
    env.put("-", (Function<List<Double>, Double>) (List<Double> args) -> args.get(0) - args.get(1));
    env.put("*", (Function<List<Double>, Double>) (List<Double> args) -> args.get(0) * args.get(1));
    env.put("/", (Function<List<Double>, Double>) (List<Double> args) -> args.get(0) / args.get(1));
    env.put(">", (Function<List<Double>, Boolean>) (List<Double> args) -> args.get(0) > args.get(1));
    env.put("<", (Function<List<Double>, Boolean>) (List<Double> args) -> args.get(0) < args.get(1));
    env.put(">=", (Function<List<Double>, Boolean>) (List<Double> args) -> args.get(0) >= args.get(1));
    env.put("<=", (Function<List<Double>, Boolean>) (List<Double> args) -> args.get(0) <= args.get(1));
    env.put("=", (Function<List<Double>, Boolean>) (List<Double> args) -> Objects.equals(args.get(0), args.get(1)));
    env.put("equal?", (Function<List<Double>, Boolean>) (List<Double> args) -> Objects.equals(args.get(0), args.get(1)));
    env.put("eq?", (Function<List<Object>, Boolean>) (List<Object> args) -> args.get(0).getClass().isInstance(args.get(1)));
    env.put("length", (Function<List<Object>, Integer>) (List<Object> args) -> args.size());
    env.put("cons", (Function<List<Object>, List<Object>>) (List<Object> args) -> Stream.concat(Stream.of(args.get(0)), Stream.of(args.get(1))).collect(Collectors.toList()));
    env.put("car", (Function<List<Object>, Object>) (List<Object> args) -> ((List) args.get(0)).get(0));
    env.put("cdr", (Function<List<Object>, List<Object>>) (List<Object> args) -> ((List) args.get(0)).subList(1, ((List) args.get(0)).size()));
    env.put("append", (Function<List<Object>, List<Object>>) (List<Object> args) -> (List) Stream.concat(((List) args.get(0)).stream(), ((List) args.get(1)).stream()).collect(Collectors.toList()));
    env.put("list", (Function<List<Object>, List<Object>>) (List<Object> args) -> args);
    env.put("list?", (Function<List<Object>, Boolean>) (List<Object> args) -> args.get(0) instanceof List);
    env.put("null?", (Function<List<Object>, Boolean>) (List<Object> args) -> ((List) args.get(0)).isEmpty());
    env.put("symbol?", (Function<List<Object>, Boolean>) (List<Object> args) -> args.get(0) instanceof String);
    return env;
  }

  private final Env globalEnv = addGlobal(new Env(Collections.EMPTY_LIST, Collections.EMPTY_LIST, null));

  private Object eval(final Object x, final Env env) {
    if (x instanceof String) {
      return env.find(x).get(x);
    } else if (!(x instanceof List)) {
      return x;
    } else if (((List) x).get(0).equals("quote")) {
      return ((List) x).get(1);
    } else if (((List) x).get(0).equals("if")) {
      return eval(((Boolean) eval(((List) x).get(1), env)) ? ((List) x).get(2) : ((List) x).get(3), env);
    } else if (((List) x).get(0).equals("set!")) {
      env.find(((List) x).get(1)).put((String) ((List) x).get(1), eval(((List) x).get(2), env));
    } else if (((List) x).get(0).equals("define")) {
      env.put((String) ((List) x).get(1), eval(((List) x).get(2), env));
    } else if (((List) x).get(0).equals("lambda")) {
      return (Function<List<Object>, Object>) (List<Object> args) -> eval(((List) x).get(2), new Env((List) ((List) x).get(1), args, env));
    } else if (((List) x).get(0).equals("begin")) {
      Object val = null;
      for (Object exp : ((List) x).subList(1, ((List) x).size())) {
        val = eval(exp, env);
      }
      return val;
    } else {
      List exps = (List) ((List) x).stream().map(exp -> eval(exp, env)).collect(Collectors.toList());
      Function proc = (Function) exps.get(0);
      return proc.apply(exps.subList(1, exps.size()));
    }
    return null;
  }

  private Object read(final String s) {
    return readFrom(new ArrayDeque<>(Arrays.asList(tokenize(s))));
  }

  private String[] tokenize(final String s) {
    return s.replace("(", " ( ").replace(")", " ) ").trim().split("\\s+");
  }

  private Object readFrom(final Deque<String> tokens) {

    if (tokens.isEmpty()) {
      throw new RuntimeException("unexpected EOF while reading");
    }

    String token = tokens.pop();
    if ("(".equals(token)) {
      List l = new ArrayList();
      while (!tokens.peek().equals(")")) {
        l.add(readFrom(tokens));
      }
      tokens.pop();
      return l;
    } else if (")".equals(token)) {
      throw new RuntimeException("unexpected )");
    } else {
      return atom(token);
    }
  }

  private Object atom(final String token) {
    try {
      return Double.valueOf(token);
    } catch (final NumberFormatException nfe) {
      return token;
    }
  }

  private String toString(final Object exp) {
    return exp instanceof List ? "(" + ((List) exp).stream().map(x -> toString(x)).collect(Collectors.joining(" ")) + ")" : exp.toString();
  }

  private void repl() {
    while (true) {
      System.out.print("lispy> ");
      Object val = eval(read(new Scanner(System.in).nextLine()), globalEnv);
      if (null != val) {
        System.out.println(toString(val));
      }
    }
  }

  public static void main(final String[] args) {
    new Lispy().repl();
  }
}

Source Code

  • Code available in GitHub - lispy

Saturday 12 July 2014

Optimise Your Own Fuckin' Tail Calls

I've heard a few people moaning that Java 8 still doesn't optimise tail calls. Not having programmed in a functional language since Moscow ML at University, I didn't really give a shit, but thought I should find out what the deal is.

A tail call method is a method where the final action is to call another method. And a tail-recursive method is when a method's final action is to call itself.

Now, we all know recursion is mathematically beautiful and elegant for people who write programs that don't do anything. For the rest of us, using recursion for anything non-trivial means you're going to run out of stack at some point.

For example NASA's JPL C Coding Standard disallows the use of recursion because:-

"The presence of statically verifiable loop bounds and the absence of recursion prevent runaway code, and help to secure predictable performance for all tasks. The absence of recursion also simplifies the task of deriving reliable bounds on stack use. The two rules combined secure a strictly acyclic function call graph and control-flow structure, which in turn enhances the capabilities for static checking tools to catch a broad range of coding defects."

Languages which support tail call optimisation replace tail call recursion with a loop so you don't have to worry about runaway stack usage. Think about that - the compiler tries to get rid of recursion for you, because it's inefficient and prone to causing defects. How elegant is your recursive algorithm really?

Also, in what other situation would you expect the compiler to so drastically change your code for you? Yeah I know you can expect the Java JIT compiler to perform optimisations, but tail call elimination is a step too far for me. While you're optimising my recursive calls, why don't you just go ahead and write the rest of my algorithms for me? - GET OFF MY LAWN!

A good example of converting a recursive algorithm to a while loop is available here: http://c2.com/cgi/wiki?TailCallOptimization and I've converted it to Java below.

I've used BigInteger in the code to avoid integer overflow, because I want to demonstrate stack overflow with the default JVM settings.

First, a recursive method which is NOT tail call recursive. The method is not tail call recursive because the final action in the method is not a call to itself but a multiplication:

    private static BigInteger notTailRecursionFactorial(final BigInteger n) {

        if (n.compareTo(TWO) < 0) {
            return ONE;
        } else {
            return n.multiply(notTailRecursionFactorial(n.subtract(ONE)));
        }
    }

Modifying the method to use an accumulator variable makes the method tail call recursive, and a candidate for tail call optimisation:

    private static BigInteger tailRecursionFactorial(final BigInteger n, final BigInteger accumulator) {

        if (n.compareTo(TWO) < 0) {
            return accumulator;
        } else {
            return tailRecursionFactorial(n.subtract(ONE), n.multiply(accumulator));
        }
    }

The recursive method converted to a while loop:

    private static BigInteger tailRecursionEliminationFactorial(BigInteger n, BigInteger accumulator) {

        while (n.compareTo(TWO) >= 0) {
            accumulator = accumulator.multiply(n);
            n = n.subtract(ONE);
        }

        return accumulator;
    }

Further optimisation to the tail call eliminated method:

    private static BigInteger tailRecursionEliminationFactorialOptimised(BigInteger n) {

        BigInteger accumulator = ONE;

        while (n.compareTo(TWO) >= 0) {
            accumulator = accumulator.multiply(n);
            n = n.subtract(ONE);
        }

        return accumulator;
    }

The full class looks like this:

TailCallOptimisation.java

package org.adrianwalker;

import java.math.BigInteger;

public class TailCallOptimisation {

  private static final BigInteger ONE = new BigInteger("1");
  private static final BigInteger TWO = new BigInteger("2");
  private static final BigInteger ONE_HUNDRED_THOUSAND = new BigInteger("100000");

  public static void main(final String[] args) {

    System.out.println("\nnotTailRecursionFactorial:");

    try {
      System.out.println(notTailRecursionFactorial(ONE_HUNDRED_THOUSAND));
    } catch (final Throwable t) {
      System.out.println("Stack Overflow Error");
    }

    System.out.println("\ntailRecursionFactorial:");

    try {
      System.out.println(tailRecursionFactorial(ONE_HUNDRED_THOUSAND, ONE));
    } catch (final Throwable t) {
      System.out.println("Stack Overflow Error");
    }

    System.out.println("\ntailRecursionEliminationFactorial:");

    System.out.println(tailRecursionEliminationFactorial(ONE_HUNDRED_THOUSAND, ONE));

    System.out.println("\ntailRecursionEliminationFactorialOptimised:");

    System.out.println(tailRecursionEliminationFactorialOptimised(ONE_HUNDRED_THOUSAND));
  }

  private static BigInteger notTailRecursionFactorial(final BigInteger n) {

    if (n.compareTo(TWO) < 0) {
      return ONE;
    } else {
      return n.multiply(notTailRecursionFactorial(n.subtract(ONE)));
    }
  }

  private static BigInteger tailRecursionFactorial(final BigInteger n, final BigInteger accumulator) {

    if (n.compareTo(TWO) < 0) {
      return accumulator;
    } else {
      return tailRecursionFactorial(n.subtract(ONE), n.multiply(accumulator));
    }
  }

  private static BigInteger tailRecursionEliminationFactorial(BigInteger n, BigInteger accumulator) {

    while (n.compareTo(TWO) >= 0) {
      accumulator = accumulator.multiply(n);
      n = n.subtract(ONE);
    }

    return accumulator;
  }

  private static BigInteger tailRecursionEliminationFactorialOptimised(BigInteger n) {

    BigInteger accumulator = ONE;

    while (n.compareTo(TWO) >= 0) {
      accumulator = accumulator.multiply(n);
      n = n.subtract(ONE);
    }

    return accumulator;
  }
}

And the output on my machine is:

notTailRecursionFactorial:
Stack Overflow Error

tailRecursionFactorial:
Stack Overflow Error

tailRecursionEliminationFactorial:
282422940796034787429342157802453551847749492609... (loads more)

tailRecursionEliminationFactorialOptimised:
282422940796034787429342157802453551847749492609... (loads more)

The recursive methods run out of stack way before getting anywhere near an answer for 100,000!.

Bottom line - optimise your own fuckin' tail calls.

Update - 24/08/14

A clever chap called Dr Rowan Davies got in touch about this post. Here's some food for thought:-

Just a small comment that your page "Optimise Your Own Fuckin' Tail Calls" is missing the point.

Basically, you've only considered the very simplest situation, a single recursive function that corresponds to a loop. Functional compilers like Scala do exactly the transformation to loops you've shown, so no one is complaining about that kind of tail call on the JVM.

It is the much more powerful uses of tail calls for things that don't correspond to loops. E.g., in F# on .NET (which supports tail calls) there is really nice support for asynchronous programming that depends on tail calls to avoid the stack increasing when you swap between different asynchronous handlers and lightweight software threads. The correspond code in Scala can't do that, the JVM just doesn't support it - and I challenge you to convert such asynchronous code using tail calls to Java code that doesn't chew up stack as it goes.

And, optimized tail-calls are not rewriting your code - they are exactly doing the tail call, just in a way that doesn't keep crap on your stack that clearly can never be needed in the future. Basically rejecting tail call optimization is demanding that the JVM keep this unneeded crap on the stack. Why do you insist that the JVM keep crap around? It's equivalent to insisting that for loops chew up stack space as they go through iterations - it really makes no sense at all to require that.

And this one as well:-

Your view is actually pretty common. But, it really is unnatural to make the implementation of tail calls consume stack when they don't have to. It's not so much about mathematical elegance, it's about whether certain powerful and natural ways of programming explode the stack or not. You're expecting a function call to always be implemented in a certain way that is really non-optimal sometimes. It's not really an optimization, it's about not doing something stupid that keeps potentially huge amounts of unnecessary data on the stack. gcc has done this basically forever. Indeed, many years ago I checked the machine code output and the C compiler cc in UNIX System V and it clearly supported efficient tail calls back in 1989.

The JVM doesn't include efficient tail calls largely because the JVM security model isn't so compatible with them, and changing the model would change the assumptions existing code could depend on. This is a basically a bureaucratic reason, the requirement to support earlier JVM programs that depend on the lack of efficient tail calls. But, many hackers and language implementers will celebrate if it is allowed sometime, otherwise those hackers and languages will eventually move on to VMs that do support what they need.

Cheers for the comments doc.

Friday 11 July 2014

Database Backed Map

I wanted an RDBMS backed Map, with it's keys and values immediately persisted to a relational database for use with a properties design pattern for prototype based programming.

I'm not sure if it'll be useful to anybody else, or even me for that matter, but I thought I'd put it out there anyway. The implementation, RdbmsMap, implements the java.util.Map interface and reads from, and writes to, a PostgreSQL database. The implementation supports key and values types of: null, Boolean, Integer, Double, String and RdbmsMap(the persistent Map class itself).

The ER diagram looks like this:


(Click To Enlarge)

The PostgreSQL code to create this schema is:

rdbms-map.sql

CREATE TABLE map
(
  id serial NOT NULL,
  CONSTRAINT map_pkey PRIMARY KEY (id)
);

CREATE TABLE entry
(
  id serial NOT NULL,
  map_id integer NOT NULL,
  key_type character(1) NOT NULL,
  value_type character(1) NOT NULL,
  CONSTRAINT entry_pkey PRIMARY KEY (id),
  CONSTRAINT entry_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX entry_key_type_idx ON entry (key_type);
CREATE INDEX entry_value_type_idx ON entry (value_type);

CREATE TABLE object_integer
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value integer NOT NULL,
  CONSTRAINT object_integer_pkey PRIMARY KEY (id),
  CONSTRAINT object_integer_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_integer_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_integer_type_idx ON object_integer (type);
CREATE INDEX object_integer_value_idx ON object_integer (value);


CREATE TABLE object_boolean
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value boolean NOT NULL,
  CONSTRAINT object_boolean_pkey PRIMARY KEY (id),
  CONSTRAINT object_boolean_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_boolean_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_boolean_type_idx ON object_boolean (type);
CREATE INDEX object_boolean_value_idx ON object_boolean (value);

CREATE TABLE object_numeric
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value numeric NOT NULL,
  CONSTRAINT object_numeric_pkey PRIMARY KEY (id),
  CONSTRAINT object_numeric_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_numeric_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_numeric_type_idx ON object_numeric (type);
CREATE INDEX object_numeric_value_idx ON object_numeric (value);

CREATE TABLE object_text
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value text NOT NULL,
  CONSTRAINT object_text_pkey PRIMARY KEY (id),
  CONSTRAINT object_text_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_text_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_text_type_idx ON object_text (type);
CREATE INDEX object_text_value_idx ON object_text (value);

CREATE TABLE object_null
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  CONSTRAINT object_null_pkey PRIMARY KEY (id),
  CONSTRAINT object_null_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_null_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_null_type_idx ON object_null (type);

CREATE TABLE object_map
(
  id serial NOT NULL,
  entry_id integer NOT NULL,
  map_id integer NOT NULL,
  type character(1) NOT NULL,
  value integer NOT NULL,
  CONSTRAINT object_map_pkey PRIMARY KEY (id),
  CONSTRAINT object_map_entry_id_fkey FOREIGN KEY (entry_id) REFERENCES entry (id) ON DELETE CASCADE,
  CONSTRAINT object_map_map_id_fkey FOREIGN KEY (map_id) REFERENCES map (id) ON DELETE CASCADE,
  CONSTRAINT object_map_value_fkey FOREIGN KEY (value) REFERENCES map (id) ON DELETE CASCADE
);

CREATE INDEX object_map_type_idx ON object_map (type);

The Map implementation is:

RdbmsMap.java

package org.adrianwalker.rdbmsmap;

import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public final class RdbmsMap<K, V> implements Map<K, V> {

  // object types
  private static final String OBJECT_NULL_TYPE = "0";
  private static final String OBJECT_INTEGER_TYPE = "I";
  private static final String OBJECT_BOOLEAN_TYPE = "B";
  private static final String OBJECT_NUMERIC_TYPE = "N";
  private static final String OBJECT_TEXT_TYPE = "T";
  private static final String OBJECT_MAP_TYPE = "M";
  // entry types
  private static final String ENTRY_KEY_TYPE = "K";
  private static final String ENTRY_VALUE_TYPE = "V";
  // object types
  private static final String OBJECT_TABLE = "object_table";
  private static final String OBJECT_NULL_TABLE = "object_null";
  private static final String OBJECT_INTEGER_TABLE = "object_integer";
  private static final String OBJECT_BOOLEAN_TABLE = "object_boolean";
  private static final String OBJECT_NUMERIC_TABLE = "object_numeric";
  private static final String OBJECT_TEXT_TABLE = "object_text";
  private static final String OBJECT_MAP_TABLE = "object_map";
  // inserts
  private static final String INSERT_MAP = "insert into map(id) values(nextval('map_id_seq')) returning id";
  private static final String INSERT_ENTRY = "insert into entry(id, map_id, key_type, value_type) values(nextval('entry_id_seq'), ?, ?, ?) returning id";
  private static final String INSERT_OBJECT = "insert into " + OBJECT_TABLE + "(id, entry_id, map_id, type, value) values(nextval('" + OBJECT_TABLE + "_id_seq'), ?, ?, ?, ?) returning id";
  // counts
  private static final String COUNT_ENTRIES = "select count(*) from entry where map_id = ?";
  private static final String COUNT_OBJECT = "select count(*) from " + OBJECT_TABLE + " where map_id = ? and type = ? and value = ?";
  // selects
  private static final String SELECT_ENTRIES = "select id, key_type, value_type from entry where map_id = ?";
  private static final String SELECT_ENTRY_BY_OBJECT = "select value_type, id from entry where id = (select entry_id from " + OBJECT_TABLE + " where map_id = ? and type = ? and value = ?)";
  private static final String SELECT_OBJECT_BY_ENTRY = "select value from " + OBJECT_TABLE + " where map_id = ? and type = ? and entry_id = ?";
  private static final String SELECT_OBJECT = "select value from " + OBJECT_TABLE + " where map_id = ? and type = ?";
  // deletes
  private static final String DELETE_ENTRIES = "delete from entry where map_id = ?";
  private static final String DELETE_ENTRY_BY_OBJECT = "delete from entry where id = (select entry_id from " + OBJECT_TABLE + " where map_id = ? and type = ? and value = ?)";
  // specific cases for nulls
  private static final String INSERT_OBJECT_NULL = "insert into " + OBJECT_NULL_TABLE + "(id, entry_id, map_id, type) values(nextval('" + OBJECT_NULL_TABLE + "_id_seq'), ?, ?, ?) returning id";
  private static final String COUNT_OBJECT_NULL = "select count(*) from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?";
  private static final String SELECT_ENTRY_BY_OBJECT_NULL = "select value_type, id from entry where id = (select entry_id from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?)";
  private static final String SELECT_OBJECT_NULL_BY_ENTRY = "select null from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ? and entry_id = ?";
  private static final String SELECT_OBJECT_NULL = "select null from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?";
  private static final String DELETE_ENTRY_BY_OBJECT_NULL = "delete from entry where id = (select entry_id from " + OBJECT_NULL_TABLE + " where map_id = ? and type = ?)";

  private final Connection connection;
  private final int mapId;

  public RdbmsMap(final Connection connection) {

    this.connection = connection;

    try {
      this.mapId = inserMap();

    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  private RdbmsMap(final Connection connection, final int mapId) {

    this.connection = connection;
    this.mapId = mapId;
  }

  public int getMapId() {
    return mapId;
  }

  @Override
  public void clear() {

    try {
      delete();
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public boolean containsKey(final Object key) {

    try {
      return countObjects(key, ENTRY_KEY_TYPE) > 0;
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public boolean containsValue(final Object value) {

    try {
      return countObjects(value, ENTRY_VALUE_TYPE) > 0;
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public Set<Entry<K, V>> entrySet() {

    try {
      return selectEntries();
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public V get(final Object key) {

    try {
      return select(key);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public Set<K> keySet() {

    try {
      return (Set<K>) selectObjects(ENTRY_KEY_TYPE);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public V put(final K key, final V value) {

    Object previousValue = remove(key);

    try {
      insert(key, value);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }

    return (V) previousValue;
  }

  @Override
  public void putAll(final Map<? extends K, ? extends V> m) {

    for (Entry<? extends K, ? extends V> entry : m.entrySet()) {
      put(entry.getKey(), entry.getValue());
    }
  }

  @Override
  public V remove(final Object key) {

    try {
      if (countObjects(key, ENTRY_KEY_TYPE) > 0) {
        V value = select(key);
        delete(key, ENTRY_KEY_TYPE);

        return value;
      }
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }

    return null;
  }

  @Override
  public int size() {

    try {
      return countEntries();
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  @Override
  public boolean isEmpty() {

    return size() == 0;
  }

  @Override
  public Collection<V> values() {

    try {
      return selectObjects(ENTRY_VALUE_TYPE);
    } catch (final SQLException sqle) {
      throw new RuntimeException(sqle);
    }
  }

  private PreparedStatement prepareStatement(final String sql) throws SQLException {

    return connection.prepareStatement(sql);
  }

  private int inserMap() throws SQLException {

    PreparedStatement insertMap = prepareStatement(INSERT_MAP);

    ResultSet result = insertMap.executeQuery();
    if (!result.next()) {
      throw new RuntimeException();
    }

    return result.getInt(1);
  }

  private int countEntries() throws SQLException {

    PreparedStatement countEntries = prepareStatement(COUNT_ENTRIES);
    countEntries.setInt(1, mapId);

    ResultSet result = countEntries.executeQuery();
    if (!result.next()) {
      return 0;
    }

    return result.getInt(1);
  }

  private int countObjects(final Object obj, final String entryType) throws SQLException {

    String objectType = getType(obj);

    PreparedStatement countObject;

    if (objectType.equals(OBJECT_NULL_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      countObject.setInt(3, (Integer) obj);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      countObject.setBoolean(3, (Boolean) obj);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      countObject.setDouble(3, (Double) obj);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      countObject.setString(3, (String) obj);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      countObject = prepareStatement(COUNT_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      countObject.setString(3, (String) obj);
    } else {
      return 0;
    }

    countObject.setInt(1, mapId);
    countObject.setString(2, entryType);
    countObject.executeQuery();

    ResultSet result = countObject.executeQuery();
    if (!result.next()) {
      return 0;
    }

    return result.getInt(1);
  }

  private V select(final Object key) throws SQLException {

    String keyType = getType(key);

    PreparedStatement selectEntry;

    if (keyType.equals(OBJECT_NULL_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT_NULL);
    } else if (keyType.equals(OBJECT_INTEGER_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      selectEntry.setInt(3, (Integer) key);
    } else if (keyType.equals(OBJECT_BOOLEAN_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      selectEntry.setBoolean(3, (Boolean) key);
    } else if (keyType.equals(OBJECT_NUMERIC_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      selectEntry.setDouble(3, (Double) key);
    } else if (keyType.equals(OBJECT_TEXT_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      selectEntry.setString(3, (String) key);
    } else if (keyType.equals(OBJECT_MAP_TYPE)) {
      selectEntry = prepareStatement(SELECT_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      selectEntry.setString(3, (String) key);
    } else {
      return null;
    }

    selectEntry.setInt(1, mapId);
    selectEntry.setString(2, ENTRY_KEY_TYPE);

    ResultSet result = selectEntry.executeQuery();
    if (!result.next()) {
      return null;
    }

    String objectType = result.getString(1);
    int entryId = result.getInt(2);

    Object value = selectObject(objectType, ENTRY_VALUE_TYPE, entryId);

    return (V) value;
  }

  private Collection selectObjects(final String entryType, final String objectType) throws SQLException {

    Collection objs;

    if (entryType.equals(ENTRY_KEY_TYPE)) {
      objs = new HashSet();
    } else if (entryType.equals(ENTRY_VALUE_TYPE)) {
      objs = new ArrayList();
    } else {
      return null;
    }

    PreparedStatement selectObject;

    if (objectType.equals(OBJECT_NULL_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
    } else {
      return objs;
    }

    selectObject.setInt(1, mapId);
    selectObject.setString(2, entryType);

    ResultSet result = selectObject.executeQuery();

    while (result.next()) {
      if (objectType.equals(OBJECT_NULL_TYPE)) {
        objs.add(null);
      } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
        objs.add(result.getInt(1));
      } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
        objs.add(result.getBoolean(1));
      } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
        objs.add(result.getDouble(1));
      } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
        objs.add(result.getString(1));
      } else if (objectType.equals(OBJECT_MAP_TYPE)) {
        objs.add(new RdbmsMap<K, V>(connection, result.getInt(1)));
      }
    }

    return objs;
  }

  private Collection selectObjects(final String entryType) throws SQLException {

    Collection objs = selectObjects(entryType, OBJECT_NULL_TYPE);
    objs.addAll(selectObjects(entryType, OBJECT_INTEGER_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_BOOLEAN_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_NUMERIC_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_TEXT_TYPE));
    objs.addAll(selectObjects(entryType, OBJECT_MAP_TYPE));

    return objs;
  }

  private String getType(final Object obj) {

    String keyType;

    if (null == obj) {
      keyType = OBJECT_NULL_TYPE;
    } else if (obj instanceof Integer) {
      keyType = OBJECT_INTEGER_TYPE;
    } else if (obj instanceof Boolean) {
      keyType = OBJECT_BOOLEAN_TYPE;
    } else if (obj instanceof Number) {
      keyType = OBJECT_NUMERIC_TYPE;
    } else if (obj instanceof String) {
      keyType = OBJECT_TEXT_TYPE;
    } else if (obj instanceof RdbmsMap) {
      keyType = OBJECT_MAP_TYPE;
    } else {
      return null;
    }

    return keyType;
  }

  private int insertEntry(final K key, final V value) throws SQLException {

    String keyType = getType(key);
    String valueType = getType(value);

    PreparedStatement insertEntry = prepareStatement(INSERT_ENTRY);
    insertEntry.setInt(1, mapId);
    insertEntry.setString(2, keyType);
    insertEntry.setString(3, valueType);

    ResultSet result = insertEntry.executeQuery();
    if (!result.next()) {
      return 0;
    }

    return result.getInt(1);
  }

  private void insertObject(final int entryId, final Object obj, final String entryType) throws SQLException {

    String objectType = getType(obj);

    PreparedStatement insertObject;

    if (objectType.equals(OBJECT_NULL_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      insertObject.setInt(4, (Integer) obj);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      insertObject.setBoolean(4, (Boolean) obj);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      insertObject.setDouble(4, (Double) obj);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      insertObject.setString(4, (String) obj);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      insertObject = prepareStatement(INSERT_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      insertObject.setInt(4, ((RdbmsMap) obj).mapId);
    } else {
      return;
    }

    insertObject.setInt(1, entryId);
    insertObject.setInt(2, mapId);
    insertObject.setString(3, entryType);
    insertObject.executeQuery();
  }

  private void insert(final K key, final V value) throws SQLException {

    int entryId = insertEntry(key, value);
    insertObject(entryId, key, ENTRY_KEY_TYPE);
    insertObject(entryId, value, ENTRY_VALUE_TYPE);
  }

  private void delete(final Object obj, final String entryType) throws SQLException {

    String objectType = getType(obj);

    PreparedStatement deleteEntry;
    if (objectType.equals(OBJECT_NULL_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT_NULL);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
      deleteEntry.setInt(3, (Integer) obj);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
      deleteEntry.setBoolean(3, (Boolean) obj);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
      deleteEntry.setDouble(3, (Double) obj);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
      deleteEntry.setString(3, (String) obj);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      deleteEntry = prepareStatement(DELETE_ENTRY_BY_OBJECT.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
      deleteEntry.setInt(3, ((RdbmsMap) obj).mapId);
    } else {
      return;
    }

    deleteEntry.setInt(1, mapId);
    deleteEntry.setString(2, entryType);
    deleteEntry.executeUpdate();
  }

  private void delete() throws SQLException {

    PreparedStatement deleteEntries = prepareStatement(DELETE_ENTRIES);
    deleteEntries.setInt(1, mapId);
    deleteEntries.executeUpdate();
  }

  private Object selectObject(final String objectType, final String entryType, final int entryId) throws SQLException {

    PreparedStatement selectObject;
    if (objectType.equals(OBJECT_NULL_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_NULL_BY_ENTRY);
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_INTEGER_TABLE));
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_BOOLEAN_TABLE));
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_NUMERIC_TABLE));
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_TEXT_TABLE));
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      selectObject = prepareStatement(SELECT_OBJECT_BY_ENTRY.replace(OBJECT_TABLE, OBJECT_MAP_TABLE));
    } else {
      return null;
    }

    selectObject.setInt(1, mapId);
    selectObject.setString(2, entryType);
    selectObject.setInt(3, entryId);

    ResultSet result = selectObject.executeQuery();

    if (!result.next()) {
      return null;
    }

    Object value;
    if (objectType.equals(OBJECT_NULL_TYPE)) {
      value = null;
    } else if (objectType.equals(OBJECT_INTEGER_TYPE)) {
      value = result.getInt(1);
    } else if (objectType.equals(OBJECT_BOOLEAN_TYPE)) {
      value = result.getBoolean(1);
    } else if (objectType.equals(OBJECT_NUMERIC_TYPE)) {
      value = result.getDouble(1);
    } else if (objectType.equals(OBJECT_TEXT_TYPE)) {
      value = result.getString(1);
    } else if (objectType.equals(OBJECT_MAP_TYPE)) {
      value = new RdbmsMap<K, V>(connection, result.getInt(1));
    } else {
      return null;
    }

    return value;
  }

  private Set<Entry<K, V>> selectEntries() throws SQLException {

    Set<Entry<K, V>> entries = new HashSet<Entry<K, V>>();

    PreparedStatement selectEntries = prepareStatement(SELECT_ENTRIES);
    selectEntries.setInt(1, mapId);

    ResultSet result = selectEntries.executeQuery();

    while (result.next()) {
      int entryId = result.getInt(1);
      String keyType = result.getString(2);
      String valueType = result.getString(3);

      Entry<K, V> entry = new AbstractMap.SimpleEntry<K, V>(
              (K) selectObject(keyType, ENTRY_KEY_TYPE, entryId),
              (V) selectObject(valueType, ENTRY_VALUE_TYPE, entryId));

      entries.add(entry);
    }

    return entries;
  }
}

For examples and tests check out the source code.

Source Code

Tuesday 3 June 2014

eCoster.co.uk – free recipe costing website

eCoster.co.uk is a free and simple recipe costing website for calculating a break down of what your meals cost.

eCoster.co.uk features:-

  • Recipe cost calculation - total cost and per serving cost.



  • Ingredients - unlimited ingredients, amount and cost entry.



  • Unit Conversions - standard weights and measures conversions, and also fully customisable.



  • Units - Use the default units or define you own custom measures.

eCoster is free to register and use, and the program source code is free to download and modify.

Source Code