React/Java/Spring project archetype

I’ve created another maven archetype, based on Happyfaces one. This time it’s for React front end. It’s called Happyreaction.
I’ve hosted maven archetype on github this time so make sure you check that repo out. You can run this maven command to start your new React.js/Java/Spring project right away:
mvn org.apache.maven.plugins:maven-archetype-plugin:2.4:generate -DarchetypeGroupId=org.happyreaction -DarchetypeArtifactId=HappyReaction-archetype -DarchetypeVersion=1.0.1 -DarchetypeRepository=https://raw.github.com/ignl/HappyReaction/mvn-repo/ -DgroupId=com.test -DartifactId=TestProject
It does lack some features (like authentication system for example) that I would like to add some time in the future. On the other hand all the CRUD and entity search functionality works right out of the box. You just need to create your entities and provide some parameters so React components know which search fields and form fields to render. And that’s it – no need to write any logic – it just works!
Here are some screenshots of sample application that you get from maven archetype.

Search form and search result

Entity edit form

So visit github repo to read more about it and start working on your very own React.js/Java/Spring app with HappyReaction maven archetype!

Advertisements

Memory efficient HashSet implementation for Java

In the previous post I introduced you to hash tables and how they work. Now I will show how I did implement it some time ago and saved more than 3.5 times the memory. I want to add though that it was a special case (works only on the hexadecimal strings) and most of the time it’s best not to reinvent the wheel.

So what had to be done was to save a hexadecimal strings as keys in a hash table and then check if a new incoming string is not already there. Basically a check for duplicates. Let’s see how much memory is taken if we solve it with just few lines :

public class Main {

	public static void main(String[] args) {
		Set<String> javaSet = new java.util.HashSet<>(SET_SIZE);
		for (int i = 0; i < SET_SIZE; i++) {
			String randomHexString = UUID.randomUUID().toString().replaceAll("-", "");
			javaSet.add(randomHexString);
		}
		
		System.out.println(MemoryMeasurer.measureBytes(javaSet));
	}

}

Result was 144388704, which is 144 MBs for one million strings. It is not that bad and probably would be the end of the story for most cases. But what if you want to keep a lot more and want to optimize for memory consumption?

Compressing strings

The first thing to notice is that inputs are hexadecimal strings. That means one letter can be converted to 4 bits (e.g. ‘F’ to 1111) and that means two letters can be converted to one byte! Instead of using 32 letter strings we can just use 16 elements byte array! On top of saving memory per one string character we are also saving memory because we don’t use String objects which have kinda large overhead (40 bytes vs 16 bytes for pure array). This is my converter between a hexadecimal string and an array. Here is a nice stackoverflow question about memory that java objects consume and here is the one with details on strings.

Once we decide to use byte[] instead of String we face a problem. Arrays derive hashCode() and equals() methods from an Object class itself so they won’t work correctly with java’s HashMap and HashSet. I still wanted to optimize more and using another object as a wrapper would add additional overhead so I decided to roll my own HashSet implementation.

Implementing HashSet

I will not copy all the source code here as that would take too much space. Instead I will explain the main idea and provide links to the source on github.

From my previous article you can see that a simple chaining hash table is quite simple to implement. All the values in a hash table are put into the buckets. That means it basically would be an array of linked lists of byte arrays. Something like this:

untitled-diagram

And that means that each input value is saved as a byte array which is an object in java. Each object is additional memory overhead. So if all the values are of fixed size (which in this situation is true) then it’s very easy just to merge all those byte arrays into one large array and keep them there. Hash table then becomes an array of linked lists of integers who just points to an index in the big array where the value is. To save even more space instead of a linked list a simple array was used for a bucket. If bucket gets full, array is resized to accommodate more data. It is downsized if elements are deleted and space is not needed anymore.

So it looks something like this (source is here)

diag

Implementation notes

One thing to note is that by using a big array for data we allocate a lot of memory right from the start. That could be solved by starting with a smaller one and increasing it’s size gradually. This implementation however does not do that. Another special case for this implementation is the bounded size. Once the data array is full the oldest element is overwritten with the new one. Again it depends on the requirements – it could be like that (good for checking for duplicates over last n entries which was the case) or it could grow infinitely. One more thing in this implementation is that hash table size and data array size is the same. It is trivial to change though if you want to have a load factor of more than one. This HashSet also do not have remove operation implemented simply because it didn’t need one but again it’s also just a standard remove from hash table. Data array can be kept as is as without a pointer in hash table the value can not be retrieved and simply will be overridden later.
Here is the source code to the main logic of hash table insert and search operations.

Now let’s try to compare our new HashSet using a string conversion trick with our initial implementation.


	public static void main(String[] args) {
		Set<String> javaSet = new java.util.HashSet<>(SET_SIZE);
		Set<String> memoryEfficientSet = new org.intelligentjava.HashSet(SET_SIZE);
		String[] simpleArray = new String[SET_SIZE];
		for (int i = 0; i < SET_SIZE; i++) {
			String randomHexString = UUID.randomUUID().toString().replaceAll("-", "");
			javaSet.add(randomHexString);
			memoryEfficientSet.add(randomHexString);
			simpleArray[i] = randomHexString;
		}
		
		System.out.println(MemoryMeasurer.measureBytes(javaSet));
		System.out.println(MemoryMeasurer.measureBytes(simpleArray));
		System.out.println(MemoryMeasurer.measureBytes(memoryEfficientSet));
	}
	

My results: 144388704 for java’s HashSet, 108000016 for a simple String array and 40383488 for my HashSet implementation. As you can see we save more than 3.5 times of the memory. And probably it could still be improved. One thing I see is to use open addressing hashing but let’s leave that for the next time. As always you can find my code in github and try it for yourself! Looking forward to your feedback. Happy coding and see you later!

Introduction to hash tables

Some time ago I wrote a post about binary search trees. I mostly described them as a data structure for more efficient search than naive search in an array. But in fact another data structure that is very very widely used is much better if you need only the basic set operations – add, search, delete. It’s a hash table – one of the most used data structure in programming. I am sure you are already using it a lot with HashMaps or HashSets from java collections. Binary search trees can not compete with their O(1) time complexity. However trees have additional advantages – they require less memory and additionally to basic add/search/delete operations they support traversing elements in order, finding closest elements, searching in ranges – things that hash tables are not designed for. It is designed for retrieving elements fast and that’s basically it. So if you don’t need anything else – you should use hash table. In this post I will explain how they work and share my very simple sample implementations.

Hash table idea is very simple. For each element we insert we calculate its unique address, its index in the array and we put it to that “address”. Then once we need to find it, we again calculate its index and just return it with a single operation (something like return array[calculatedIndex]). That’s why it is has O(1) time complexity. The process of calculating element’s unique address is called hashing and the algorithm how it is done is called a hash function.

Hash table illustration
Hash table illustration

Now you probably already see a problem. How does hash function manages to give unique address to every element? Well it doesn’t. It tries to give an unique address but how well it succeeds depends on how good a hash function is. If two different elements get the same hash it’s called collision and the two most popular ways to solve it are chaining and open addressing (explained later). If you already know all the inputs in advance it is possible to create a perfect hash function (when each hash is guaranteed to be unique). Check out tools like gperf or CMPH for that.

Hash function

When you are writing a hash function your main goal is that all the hashes would be distributed uniformly. That will minimize probability of collisions. For example if you know that all the values are strings with different lengths then a simple string length can be a good hash function. However if your values are English words then such a hash function would perform very poorly as majority of words are 4-10 letter words so there would be a lot of collisions. Another example of a simple hash function is for real numbers between 0 and 1. Sufficiently good hash function could be value * hashTableSize (if input values are uniformly distributed). Those are just few simple examples to illustrate how you can think about hash functions. There are of course other hash functions developed by mathematicians and probably you should do your homework before choosing one for your particular use case. Here is one interesting comparison of some well known hash functions.

Solving collisions

As I previously mentioned there are two ways to solve collisions problem. First one is chaining when we simply use a linked list and put all the values with the same hash into it. So basically hash table becomes an array of buckets (linked lists) where the hash points to the bucked where the element can be found. For that reason if hash function simply returns a constant then all the elements would end up in a linked list and worst case search performance from our expected O(1) would degrade to O(n)! That’s why it is so important to choose a good hash function for your data.

Hash table with chaining illustration
Hash table with chaining illustration

Here is my very simplified java implementation of chaining. Hash table is an array of linked lists with no dynamic resizing and it supports only String values but it’s fine for illustrative purposes. Code actually is pretty self explanatory – calculate hash, find bucket, add/remove/find value in the bucket.

public class HashTable {
	
	private static int SIZE = 1000;
	
	private LinkedList<String>[] hashtable = (LinkedList<String>[])new LinkedList[SIZE];
	
	public void add(String value) {
		int hash = hash(value);
		if (hashtable[hash] == null) {
			hashtable[hash] = new LinkedList<>();
		}
		LinkedList<String> bucket = hashtable[hash];
		bucket.add(value);
	}
	
	public boolean contains(String value) {
		int hash = hash(value);
		LinkedList<String> bucket = hashtable[hash];
		if (bucket != null) {
			Iterator<String> it = bucket.iterator();
			while (it.hasNext()) {
				if (it.next().equals(value)) {
					return true;
				}
			}
		}
		// value not found
		return false;
	}

      // exactly the same as contains() just additionally remove value
	public boolean remove(String value) {
		int hash = hash(value);
		LinkedList<String> bucket = hashtable[hash];
		if (bucket != null) {
			Iterator<String> it = bucket.iterator();
			while (it.hasNext()) {
				if (it.next().equals(value)) {
					it.remove();
					return true;
				}
			}
		}
		// value not found
		return false;
	}
	
	// use guave library for hash function
	private int hash(String value) {
		HashFunction hf = Hashing.murmur3_128(); // can choose any hash function
		return Math.abs(hf.newHasher()
	       .putString(value, Charsets.UTF_8)
	       .hash().asInt()) % SIZE;
	}
}

Open addressing

In an open addressing method all the elements occupy hash table array itself. There are no buckets – only a value or null. That means that hash table can fill up and no further insertions are possible. However because it does not need to keep additional pointers it’s more memory efficient so you can allocate a larger array which should result in less collisions and possibly better performance. So how do we solve collision problem after all? When inserting an element we probe hash table until we find a place for it. In other words we calculate hash then check if the slot is empty if not calculate another hash and check that slot and continue until a place for the element is found. To do that we extend hash function with additional parameter – probe index.

Hash table with open addressing
Hash table with open addressing

Here is my implementation in java:

public class OpenAddressingHashTable {

	private static int SIZE = 1000;

	private String[] hashtable = new String[SIZE];

	public void add(String value) {

		int probe = 0;

		do {
			int hash = hash(value, probe);
			if (hashtable[hash] == null) {
				hashtable[hash] = value;
				return;
			}
			probe++;
		} while (probe < SIZE);

		// hash table is full
		throw new RuntimeException("Hash table overflow");
	}

	public boolean contains(String value) {
		int probe = 0;

		do {
			int hash = hash(value, probe);
			if (hashtable[hash] == null) {
				return false;
			} else {
				if (hashtable[hash].equals(value)) {
					return true;
				}
				probe++;
			}

		} while (probe < SIZE);

		return false;
	}

	private int hash(String value, int probe) {
		HashFunction hf = Hashing.murmur3_128(); // can choose any hash function
		int hash = Math.abs(hf.newHasher().putString(value, Charsets.UTF_8).hash().asInt()) % SIZE;

		return (hash + probe) % SIZE;
	}

}

The algorithm is quite simple – run the loop incrementing probe variable and recalculate hash for different probes until an empty slot is found (so for add() operation insert can be performed and for contains() operation we can know that the element is not in the table) or until probe index reaches size of the hash table which then means that the table is full.

This exact hash function extension with probes is called linear probing. Formula for it is:

h(value, probe) = (h(value) + 1) mod size

It is easy to implement but not necessarily the best. It might increase sequences of occupied slots which might decrease the performance. There are other methods like quadratic probing and double hashing which might be a better choice but I skip it here since this is only an introductory article. Lastly I did not implement delete operations as it is a little bit more complicated. In essence it can be implemented the same way just it can’t set null value when removing and instead it should be some special value DELETED. We can not set null values because then search would start working incorrectly and some values might be lost because chain of probes could be broken. I wanted to keep code as clean as possible for illustrative purposes so I decided to skip remove operation. You can easily do it yourself and it could be a good exercise actually.

To summarize you will probably never need to implement a hash table yourself and java collection’s HashMap and HashSet will be enough for majority of use cases. However it’s always good to understand how it works and sometimes in some special rare use cases you might need to develop and improve your own algorithm. In the next article I will show one example of a special case where you can save some memory if you implement hash table yourself.

So after reading this piece you now know and understand the basics about hash functions and importance of its choice, differences between chaining and open addressing, what linear probing is and have some very simple and clear code to start working on after learning more nuances (you can start of course in wikipedia). However in real world it’s better to use the battle tested and optimized library. For example HashMap even starts using a binary tree data structure instead of linked list in a bucket if it the bucket becomes quite large. Anyway I hope you liked this post and as always you can find code on my github. Don’t forget to override your hashCode and equals and happy coding!

Machine learning: Decision tree

Finally I have implemented decision tree and I want to share it with you! Decision tree concept is deceptively simple and I thought it will be very easy to implement. However it was not as easy as I thought it will be. But first things first. What is decision tree?

Decision tree

It is one of the most popular and effective machine learning algorithms. It can do classification, regression, ranking, probability estimation, clustering. Decision tree is not a black box and its results is easily interpretable. Data does not need to be normalized or specifically prepared. It is intuitive and even a child can understand the basics of how decision trees work. They are also widely applied in practice especially with ensembles (multiple decision trees, for example random forests). All of this makes them perfect algorithm to start with machine learning.

titanicSurvivorsDecisionTree

How decision trees work

As you can see in the picture above this particular decision tree tries to classify if titanic passenger survived or died during the catastrophe. For example if he is a male and older than 9.5 years then it is most likely he did not survive (this specific example also contains probability of correct answer). There is basically nothing much to add. Once you have a built decision tree and want to classify some data sample you simply start at the root node and check if your data has a feature from the node. You do that until you reach a leaf node which already has an answer you were seeking. I really recommend watching this udacity course on decision trees to understand them better and get some intuitions on how tree is build. They explain it so much better than me.

How decision tree is built

To build a decision tree we take a set of possible features. Then we take one feature create tree node for it and split training data. Once training data is split into 2 (or n) sublists same thing is repeated on those sublists with recursion until whole tree is built.
Now of course you may have some questions about this simplified explanation. First of all how do we select a feature to do a split on? Then how do we stop the recursion?
To select best feature for a split we check which split gives us most information gain (or has least impurity as in pseudo code later). Lets say one split returns 80 entries with TRUE label and 20 with FALSE label. It is obviously better split as 50 TRUE labels and 50 FALSE labels. So we check each feature and select best one. We stop when there are no more features left, or data list is already fully homogenous (all entries with same label) or tree is already reached maximum depth (parameter set).
And once again I recommend to check out that udacity course.

Decision tree training pseudocode

I used pseudocode from this book to implement my decision tree. It goes like this:

GrowTree(D, F) – grow a feature tree from training data.

Input : data D; set of features F.
Output : feature tree T with labelled leaves.
 if Homogeneous(D) then return Label(D) ;
 S = BestSplit(D, F) ; 
 split D into subsets Di according to the literals in S;
 for each i do
 if Di not empty then Ti = GrowTree(Di, F) else Ti is a leaf labelled with Label(D);
 end
 return a tree whose root is labelled with S and whose children are Ti


BestSplit(D, F) – find the best split for a decision tree.

Input : data D; set of features F.
Output : feature f to split on.
 Imin  =1;
 for each f ∈ F do
 split D into subsets D1 ,..., Dl according to the values Vj of f;
 if Impurity({D1 ,..., Dl}) < Imin then
 Imin = Impurity({D1 ,..., Dl});
 fbest =  f;
 end
 end
 return fbest

Java implementation

First of all lets think how we are going to represent Feature. My Feature must know if it does belong to a data sample. This wont handle categorical features, but its OK for now. So here is Interface which defines a feature:

public interface Feature {
    
    boolean belongsTo(DataSample dataSample);

    default List<List<DataSample>> split(List<DataSample> data) {
        List<List<DataSample>> result = Lists.newArrayList();
        
        Map<Boolean, List<DataSample>> split = data.parallelStream().collect(partitioningBy(dataSample -> belongsTo(dataSample)));
        
        if (split.get(true).size() > 0) {
            result.add(split.get(true));
        } else {
            result.add(Lists.newArrayList());
        }
        if (split.get(false).size() > 0) {
            result.add(split.get(false));
        } else {
            result.add(Lists.newArrayList());
        }
        return result;
    }

}

As you can see it has belongsTo() method which returns true if data sample contains the feature and also default method for splitting data into 2 sub lists – one which contains feature and one which doesn’t. I happily use java 8 streams and even though I am sure it could be contracted to one liner it still saves a lot of time. God bless java 8.
Now here is my single implementation for Feature interface – PredicateFeature. It takes column name and java 8 Predicate function (which allows it to accept lambda expressions!). So it simply checks value of data sample on provided column and checks it with Predicate function. If it returns true – data has that feature. For example Predicate feature with column “age” and predicate age -> age > 10 will return true to all data samples that has age more than 10 in “age” column. You can also check out some commonly used predicates in P class.


public class PredicateFeature<T> implements Feature {
    
    /** Data column used by feature. */
    private String column;

    /** Predicate used for splitting. */
    private Predicate<T> predicate;
    
    /** Feature Label used for visualization and testing the tree. */
    private String label;

    private PredicateFeature(String column, Predicate<T> predicate, String label) {
        super();
        this.column = column;
        this.predicate = predicate;
        this.label = label;
    }

    @SuppressWarnings("unchecked")
    @Override
    public boolean belongsTo(DataSample dataSample) {
        Optional<Object> optionalValue = dataSample.getValue(column);
        return optionalValue.isPresent() ? predicate.test((T)optionalValue.get()) : false;
    }
    
    public static <T> Feature newFeature(String column, T featureValue) {
        return new PredicateFeature<T>(column, P.isEqual(featureValue), String.format("%s = %s", column, featureValue));
    }

    public static <T> Feature newFeature(String column, Predicate<T> predicate, String predicateString) {
        return new PredicateFeature<T>(column, predicate, String.format("%s %s", column, predicateString));
    } 
    
}

As we already introduced DataSamples lets check my simple implementation:


public class SimpleDataSample implements DataSample {
    
    private Map<String, Object> values = Maps.newHashMap();
    
    /** Column name which contains data labels. */
    private String labelColumn;
    
    private SimpleDataSample(String labelColumn, String[] header, Object... dataValues) {
        super();
        this.labelColumn = labelColumn;
        for (int i = 0; i < header.length; i++) {
            this.values.put(header[i], dataValues[i]);
        }
    }

    @Override
    public Optional<Object> getValue(String column) {
        return Optional.ofNullable(values.get(column));
    }
    
    @Override
    public Label getLabel() {
        return (Label)values.get(labelColumn);
    }

    public static SimpleDataSample newClassificationDataSample(String[] header, Object... values) {
        Preconditions.checkArgument(header.length == values.length);
        return new SimpleDataSample(null, header, values);
    }

    public static SimpleDataSample newSimpleDataSample(String labelColumn, String[] header, Object... values) {
        Preconditions.checkArgument(header.length == values.length);
        return new SimpleDataSample(labelColumn, header, values);
    }
    
}

It is simple Hashmap with Map key being column name. It also has one more property – “labelColumn”. This is a column name which contains Labels of training data. Value of label column must be of type Label.

OK now we are ready to implement GrowTree and BestSplit routines from previously mentioned pseudocode:

    public void train(List<DataSample> trainingData, List<Feature> features) {
        root = growTree(trainingData, features, 1);
    }

     protected Node growTree(List<DataSample> trainingData, List<Feature> features, int currentDepth) {

        Label currentNodeLabel = null;
        // if dataset already homogeneous enough (has label assigned) make this node a leaf
        if ((currentNodeLabel = getLabel(trainingData)) != null) {
            log.debug("New leaf is created because data is homogeneous: {}", currentNodeLabel.getName());
            return Node.newLeafNode(currentNodeLabel);
        }
        
        boolean stoppingCriteriaReached = features.isEmpty() || currentDepth >= maxDepth;
        if (stoppingCriteriaReached) {
            Label majorityLabel = getMajorityLabel(trainingData);
            log.debug("New leaf is created because stopping criteria reached: {}", majorityLabel.getName());
            return Node.newLeafNode(majorityLabel);
        }

        Feature bestSplit = findBestSplitFeature(trainingData, features); // get best set of literals
        log.debug("Best split found: {}", bestSplit.toString());
        List<List<DataSample>> splitData = bestSplit.split(trainingData);
        log.debug("Data is split into sublists of sizes: {}", splitData.stream().map(List::size).collect(Collectors.toList()));

        // remove best split from features (TODO check if it is not slow)
        List<Feature> newFeatures = features.stream().filter(p -> !p.equals(bestSplit)).collect(toList());
        Node node = Node.newNode(bestSplit);
        for (List<DataSample> subsetTrainingData : splitData) { // add children to current node according to split
            if (subsetTrainingData.isEmpty()) {
                // if subset data is empty add a leaf with label calculated from initial data
                node.addChild(Node.newLeafNode(getMajorityLabel(trainingData)));
            } else {
                // grow tree further recursively
                node.addChild(growTree(subsetTrainingData, newFeatures, currentDepth + 1));
            }
        }

        return node;
    }

And finding best Feature to split:


    protected Feature findBestSplitFeature(List<DataSample> data, List<Feature> features) {
        double currentImpurity = 1;
        Feature bestSplitFeature = null; // rename split to feature

        for (Feature feature : features) {
            List<List<DataSample>> splitData = feature.split(data);
            // totalSplitImpurity = sum(singleLeafImpurities) / nbOfLeafs
            // in other words splitImpurity is average of leaf impurities
            double calculatedSplitImpurity = splitData.parallelStream().filter(list -> !list.isEmpty()).mapToDouble(list -> impurityCalculationMethod.calculateImpurity(list)).average().getAsDouble();
            if (calculatedSplitImpurity < currentImpurity) {
                currentImpurity = calculatedSplitImpurity;
                bestSplitFeature = feature;
            }
        }

        return bestSplitFeature;
    }

Code pretty much follows pseudocode and is pretty self explanatory. One thing you might wonder is impurityCalculationMethod. It is simple interface to choose a formula for impurity calculation. Right now I have 2 – Gini and Entropy and you can check them out here.

Usage

So how we can use this decision tree? Here is simple example:


public static void main(String[] args) throws FileNotFoundException, IOException {
        List<DataSample> trainingData = readData(true);
        DecisionTree tree = new DecisionTree();
        
        List<Feature> features = getFeatures();
        
        tree.train(trainingData, features);
        
        // print tree after training
        tree.printTree();
        
        // read test data
        List<DataSample> testingData = readData(false);
        
        // classify all test data
        for (DataSample dataSample : testingData) {
           tree.classify(dataSample);
        }
        
    }

Here is an example how I solved kaggle titanic competition using this decision tree. Only 0.7655 but still nice to do it with your own decision tree implementation:)

As always you can find source code on my github.
Happy coding!

Self balancing binary search trees comparison

In this post I will try to review some of the main versions of self balancing binary trees, provide Java implementations and micro benchmark their performance under various conditions.

Why do we need binary search trees?
Lets say we have a list as an input and we need to find some element in it. What is the best way to do it? Naive implementation could be simply iterating through all the elements and check each one. That maybe be fine for small lists and simple use cases. But can we do better? Probably not with a simple random array. However if we sort it beforehand it is possible to “divide and conqueror”. That is we can check element in the middle and if the one we are looking for is larger we do the same with sub list n/2 to n (where n is number of elements in the list). So we cut through search space considerably (O(log n) complexity instead of O(n)). That is fine but we need to sort the input before with some sorting algorithm. And if we are constantly modifying (inserting/deleting) the input and searching through it, it’s not practical to sort it each time before search. Here is where binary search trees steps in. We modify the way data is kept. Not in a simple list/array but in a tree like data structure. Looking at the picture you probably already see why it is easier to search in such a structure.

AVLtreef.svg

However binary search tree can get unbalanced and then loose its efficiency. To solve that problem self balancing binary search trees were invented. I am not going to explain how they work in detail here just provide general information and some ideas how they can be used. Also I will provide my implementations in java and some benchmarks so you can start playing with it if you want.

AVL tree

One of the oldest, most well known and most popular tree data structure. It saves additional height information in each node and re balances tree if height of one node is higher than its sibling by 2. That keeps tree rigidly balanced so search is extremely fast on AVL tree. However that comes with a cost of rebalancing and that can make insert/delete operations slightly more expensive than other trees.

Quick link to my implementation on GitHub

Red-Black tree

Most widely used self balancing binary search tree. It also saves additional information on nodes (black node or red node) and preserves tree balance based on certain rules about how nodes are colored. It can be less balanced than AVL tree (which means slower search) but with more efficient inserts and deletes. Also because only two colors required, Red-Black tree needs only one bit of additional information per node. All of this makes it most popular choice for general use cases. Java TreeSet is implemented as Red-Black tree.

Quick link to my implementation on GitHub

Scapegoat tree

This tree has advantage that it doesn’t need any additional memory per node. Once it finds out that the tree has to be re balanced it finds a scapegoat node and performs re balance operation on it. So it might be a good choice when memory is an issue. To find out if the tree is out of balance it uses parameter alpha. This allows to parametrise a scapegoat tree with different values of alpha which means different degrees of balance which means a choice between faster search or faster inserts. Imagine doing that dynamically – when there is heavy load on searches and not too much on inserts/deletes, you can lower alpha and increase it when amount of inserts/deletes increases.

Quick link to my implementation on GitHub

Treap

Basically randomized binary search tree and heap hybrid. It randomly generates and saves additional node parameter priority. Tree is then balanced such as priority values satisfies heap property. It is easy to implement and I think has a possibility of fast set operations (I did not implement it in my code). Other than that I don’t know if it has any advantage over other trees. Maybe instead of random priority flag we can use a non random (somehow calculated) importance flag which would keep more important nodes at the top?

Quick link to my implementation on GitHub

Splay tree

Splay tree is pretty interesting. It performs operation called splaying not only on inserts and deletes, but also when searching. This operation performs tree rotations and brings element up to the top. It means that recently accessed elements are always near the top. You can see how it can be very useful in certain use cases like some cache implementations. However additional rotations on search adds additional overhead and if each element is as likely to be searched then splaying doesn’t do that much good.

Quick link to my implementation on GitHub

Short summary

First choice for BST is a Red-Black tree as it is most universal data structure. However if your tree will be used mostly for search then take a look at AVL tree. If mostly the same elements are retrieved again and again then Splay tree can be even better. If sometimes there is a heavy read and sometimes a heavy write load then Scapegoat tree with different parameters alpha might be helpful. If for some reason you need to implement tree yourself and don’t yet feel very confident about your coding skills – Treap might be you choice.

Benchmarks

Here I have prepared some simple benchmarks for my own implementations of each tree. Please keep in mind that I might have made some mistakes or my implementation can be inefficient so let me know if you find that to be the case. Keep in mind that ms/op in units column means whole 100k elements test in ms. I’ve used jmh framework for benchmarking.

This first benchmark inserts elements from 1 to 100K. We see that all scapegoat trees performed very poorly. Not sure why. Splay tree performed phenomenally, however it is not that good once you realize that tree is not balanced at all and in fact is basically a linked list. Interesting that AVL tree was much better than Red-Black tree. Treap was quite good too (maybe even the best choice as it is much simpler than only slightly faster AVL tree). Another interesting observation is that less balanced Scapegoat tree (0.9 alpha) had slower inserts than 0.75 alpha balanced Scapegoat tree. In this case it is no surprise because we insert sorted elements. Having tree re balance too rarely in this situation increases costs for finding next element’s place once tree grows larger.

Insert sorted elements benchmark Score Score error Units
AVL tree 9.420 0.270 ms/op
JDK TreeSet 13.981 0.479 ms/op
Red-Black tree 17.430 0.917 ms/op
Scapegoat tree (alpha 0.6) 131.432 4.159 ms/op
Scapegoat tree (alpha 0.75) 76.769 2.538 ms/op
Scapegoat tree (alpha 0.9) 77.999 1.775 ms/op
Splay tree 1.229 0.039 ms/op
Treap 9.576 1.102 ms/op

Once again lets insert 100k elements but this time they are random and not sorted. My AVL tree implementation did quite well and Red-Black tree implementation was much slower than we could expect (remember, it suppose to be faster on inserts). Maybe my implementation is not very efficient or I made a mistake somewhere. Red-Black tree implementation from JDK was fastest here (but only barely faster than my non optimized AVL tree) and Splay tree was slowest so no more surprises.

Insert random elements benchmark Score Score error Units
AVL tree 39.051 1.998 ms/op
JDK TreeSet 38.811 4.356 ms/op
Red-Black tree 59.052 7.871 ms/op
Scapegoat tree (alpha 0.6) 50.738 4.400 ms/op
Scapegoat tree (alpha 0.75) 44.077 1.192 ms/op
Scapegoat tree (alpha 0.9) 44.862 2.168 ms/op
Splay tree 76.457 4.114 ms/op
Treap 47.978 1.656 ms/op

This next benchmark inserts 100K elements and then deletes them one by one. One more time my implementation of Red-Black tree under performs (any help why is that would be appreciated!). Interesting that more rigidly balanced Scapegoat trees couldn’t even complete this test (even when I rewrote tree flattening algorithm to iterative from recursion). My explanation is that it is not very good scenario for Scapegoat tree, as constant deletion triggers re balancing at the root too often (scapegoat tree re balances at  the root node on deletion) and it is an expensive operation as it has to flatten and then rebuild the whole tree (not just a scapegoat sub tree as in inserts). However it should do OK when there are not too many deletes in a row. Loosely balanced Scapegoat tree did quite well however. JDK Red-Black tree was fastest and Splay tree was slowest once again.

Delete elements benchmark Score Score error Units
AVL tree 88.266 4.713 ms/op
JDK TreeSet 67.010 5.138 ms/op
Red-Black tree 114.527 12.326 ms/op
Scapegoat tree (alpha 0.9) 75.266 1.758 ms/op
Splay tree 151.600 8.451 ms/op
Treap 97.886 7.516 ms/op

Now lets check searching 100K size trees. Surprisingly JDK Red-Black tree slightly outperformed also very fast AVL tree. Low alpha Scapegoat tree was just slightly slower than AVL tree. Because of splaying overhead on each search operation Splay tree is performing very poorly in such situation.

Search elements benchmark Score Score error Units
AVL tree 29.360 1.719 ms/op
JDK TreeSet 26.630 4.192 ms/op
Red-Black tree 45.811 4.770 ms/op
Scapegoat tree (alpha 0.6) 30.151 1.285 ms/op
Scapegoat tree (alpha 0.75) 34.001 2.171 ms/op
Scapegoat tree (alpha 0.9) 31.732 1.892 ms/op
Splay tree 91.072 5.093 ms/op
Treap 31.564 1.688 ms/op

This benchmark was specially created for the Splay tree. It is the same as previous search elements benchmark, just now we are constantly searching for only the same 100 elements. Splay tree “is splaying” those to the top after search and that should have given it a superior performance! However probably my benchmark or implementation is flawed in some way and Splay tree under performed!

Search same few elements benchmark Score Score error Units
AVL tree 2.301 0.192 ms/op
JDK TreeSet 2.667 0.182 ms/op
Red-Black tree 15.921 4.166 ms/op
Scapegoat tree (alpha 0.6) 1.993 0.192 ms/op
Scapegoat tree (alpha 0.75) 2.029 0.110 ms/op
Scapegoat tree (alpha 0.9) 1.870 0.196 ms/op
Splay tree 19.690 0.761 ms/op
Treap 7.887 0.392 ms/op

That is it. As always you can check out all source code from GitHub repo. It is pretty clear my Red-Black tree is not implemented correctly and is inefficient. And probably Splay tree too. It would be great if someone could take a look into it (and other implementations). I hope you liked this little benchmark and it did help you to choose your favorite binary search tree 🙂 Happy coding!

Stock market simulation with Cellular automaton

In my previous post I have created cellular automaton framework and implemented Conway’s game of life with it. In this post I will show you how you can use cellular automaton for one very interesting simulation – stock market. What I am going to do is a very simplified model of market micro structure. However it still can be fascinating to watch! And of course source code is provided and explained so you can try various things yourself! Even though it’s not necessary it could be helpful to read previous article first if you are going to really dive into the source code of this stock market simulation as I’m not going to explain application design here.

First of all you can download jar file and simply try out application by running this command (you will need java8 installed):

java -jar simulation.jar

Here is screenshot of how it looks like:

stockmarketautomaton

So how is it implemented? Firstly I have created 2d cellular world where each cell represents market participant. And as in the real stock market every participant affects other participants. To make it simple each cell in our stock market simulation has certain amount of money and number of shares on their balance. Before each iteration it also has action set – will it buy or sell shares next. As you can see and guess from the screenshot red cells are selling, green cells are buying and grey cells are neutral.

For market to function it must support two types of orders: limit and market. For example lets say you want to sell your phone. You put an ad that the price is 500$. That’s your offer and your limit order. Some other guy puts an ad that he is buying the phone but will only pay 450$. Now we have best bid 450$ and best offer 500$. Market order in this case would be simply to execute transaction at price offered or bid (in this case buying right away for 500$ or selling for 450$). For simplicity I made that 20% of participants are using limit orders to buy or sell and all neutral participants also put their bids and offers at much wider spreads. Other participants use market orders to buy/sell from those who did put their limit orders. The rules how market participant decides of his next action is simple: if he has 3 to 7 neighbors which are bullish – his next action is to buy. Same the other way around. However if all 8 of his neighbors are bullish or bearish – he takes contrarian view and does the opposite. Now once he has an open position he calculates his profit or loss and exit that position if loss exceeds 2% of the position size or profit is more than 6% of the position size. Participant with an open position also exits if neighbors become bullish and he is short or neighbors become bearish and he is long. And that’s it. As can you see rules are pretty simple. Now Lets walk you through the implementation and source code.

As in Conway’s game of life main class is very simple:

public class Main {
    public static void main(final String[] args) throws IOException, InterruptedException {
        final WorldGui<Action> gui = new SwingStockMarketGui();
        final World<Action> world = new StockMarketWorld(10, 10, new StockMarketAutomatonRule());
        gui.showWorld(world);
        for (int i = 0; i < 100; i++) {
            Thread.sleep(1000);
            world.nextState();
            gui.showWorld(world);
            System.out.println("Iteration " + i);
        }
    }
}

We iterate 100 times through world states and show results in GUI (which shows us final candlestick chart with each candle representing one iteration). Now obviously all the magic happens behind the scenes. First of all lets see how StockMarketWorld is implemented:

public class StockMarketWorld extends SimpleTwoDimensionalGrid<Action> {

    private static final int INITIAL_PRICE = 100;
    private final StockExchangeLevel2Book level2;
    private List<Candle> candles = new ArrayList<>(Arrays.asList(new Candle(INITIAL_PRICE, INITIAL_PRICE, INITIAL_PRICE, INITIAL_PRICE)));
    private Integer currentOpen = INITIAL_PRICE;
    private Integer currentHigh = INITIAL_PRICE;
    private Integer currentLow = INITIAL_PRICE;
    private Integer currentClose = INITIAL_PRICE;

    @Override
    protected Cell<Action> createNewCell(final XYCoordinates coordinates, final CellularAutomatonRule<Action> rule) {
        final Random random = new Random();
        // 33% chance to buy, sell, or neutral initial state
        int randomInt = random.nextInt(3);
        final Action action = randomInt == 0 ? Action.NEUTRAL : randomInt == 1 ? Action.BUY : Action.SELL;
        return new MarketParticipant(action, rule, coordinates, this);
    }

    @Override
    public void nextState() {
        currentOpen = getLastCandle().getClose();
        currentHigh = currentOpen;
        currentLow = currentOpen;
        currentClose = currentOpen;
        
        List<MarketParticipant> participants = new ArrayList<>();
        
        for (final Cell<Action>[] cellArray : worldGrid) {
            for (final Cell<Action> cell : cellArray) {
                final MarketParticipant participant = (MarketParticipant) cell;
                participants.add(participant);
            }
        }
        
        // make participants to act in random order during each iteration
        Collections.shuffle(participants);
        boolean useLimitOrders = true;
        int i = 0;
        for (MarketParticipant participant : participants) {
            participant.act(useLimitOrders);
            if (useLimitOrders && (i++ > participants.size() / 5)) { // 20% participants use limit orders
                useLimitOrders = false;
            }
        }
        
        candles.add(new Candle(currentOpen, currentHigh, currentLow, currentClose));
        
        // CellularAutomatonRule sets new values for next round
        super.nextState();
    }
}

Method createNewCell() is used to initialize world and create new cells which in this case is of MarketParticipant type. NextState() method randomly shuffle market participants and invoke their act() methods (this way they are acting in random order). First 20% of them uses limit orders for their actions. I left out other methods like placing orders on the market and returning candles or order book as I am concentrating on the behaviour of the market participants and want to save some space. You can check out full source from github.

Now lets see how Cell implementation is done. I called it MarketParticipant:

public class MarketParticipant extends SimpleCell<Action> {

    private int totalCapital = 1000000;
    private int sharesHold = 0;
    private int positionSize = 0;
    
    public MarketParticipant(final Action value, final CellularAutomatonRule<Action> rule, final Coordinates cellCoordinates,
            final World<Action> world) {
        super(value, rule, cellCoordinates, world);
    }

    public void act(boolean withLimitOrder) {
        final StockMarketWorld stockMarket = (StockMarketWorld) world;
        final int lastPrice = stockMarket.getLastCandle().getClose();
        final Random random = new Random(System.nanoTime());
        
        // buy or sell random amount from 0 to 400 shares
        final int randomNumberOfShares = (random.nextInt(4) + 1) * 100;
        final int numberOfShares = sharesHold != 0 ? Math.abs(sharesHold) : randomNumberOfShares;
        
        if (getValue() == Action.NEUTRAL) {
            int spread = random.nextInt(10) + 4;
            // if market maker undecided he simply bids and offers with big spread
            stockMarket.placeBid(this, randomNumberOfShares, lastPrice - spread);
            stockMarket.placeOffer(this, randomNumberOfShares, lastPrice + spread);
        } else if (withLimitOrder && (getValue() == Action.BUY || getValue() == Action.SELL)) {
            if (getValue() == Action.BUY) {
                int spread = random.nextInt(3) + 1; // first offer @ random spread no more than 4
                stockMarket.placeBid(this, numberOfShares, lastPrice - spread);
            } else if (getValue() == Action.SELL) {
                int spread = random.nextInt(3) + 1; // first offer @ random spread no more than 4
                stockMarket.placeOffer(this, numberOfShares, lastPrice + spread);
            }
        } else if (!withLimitOrder && (getValue() == Action.BUY || getValue() == Action.SELL)) {
            // if there is open position then size is of current position size otherwise its random number of shares
            if (getValue() == Action.BUY) {
                stockMarket.buyMarket(this, numberOfShares);
            } else if (getValue() == Action.SELL) {
                stockMarket.sellMarket(this, numberOfShares);
            }
        }
    }
}

public enum Action {
    BUY,
    SELL, 
    NEUTRAL
}

Market participant action depends on the cell value which in this case is of type Action. It is set by StockMarketAutomatonRule after the iteration for the next iteration. As you can see from the code if action is set to be NEUTRAL, market participant puts limit orders with wide spread, otherwise depending on withLimitOrder flag it puts limit or market orders to the market. And that’s about it.

The last important class is StockMarketAutomatonRule which decides what each cell is going to do during next iteration. In this case – buy, sell or stay neutral.

public class StockMarketAutomatonRule implements CellularAutomatonRule<Action> {

    @Override
    public Action calculateNewValue(final Action currentValue, final World<Action> world, final Coordinates coordinates) {
        final XYCoordinates gridCoordinates = (XYCoordinates) coordinates;
        final StockMarketWorld marketWorld = (StockMarketWorld) world;

        final MarketParticipant marketParticipant = (MarketParticipant) world.getCell(new XYCoordinates(gridCoordinates.getX(),
                gridCoordinates.getY()));
        
        final int bullishNeighbors = getNumberOfBulishNeighbors(marketWorld, gridCoordinates);
        final int bearishNeighbors = getNumberOfBearishNeighbors(marketWorld, gridCoordinates);

        if (marketParticipant.getSharesHold() == 0) {
            return calculateActionFromNeighbors(marketWorld, gridCoordinates, bullishNeighbors, bearishNeighbors);
        } else {
            int currentPositionValue = marketParticipant.getSharesHold() * marketWorld.getLastCandle().getClose();
            int profitLoss = marketParticipant.getPositionSize() - currentPositionValue;
            double profitLossPrc = (double)(profitLoss * 100)/(double)currentPositionValue;
            boolean sameCloseTwice = marketWorld.getLastCandle().getClose() == marketWorld.getCandles().get(marketWorld.getCandles().size() - 2).getClose();
            if (marketParticipant.getSharesHold() > 0) {  // if already long
                if (sameCloseTwice) {
                    return Action.SELL; // if closed same twice in a row - exit position
                } else if (bearishNeighbors >= 4) {
                    return Action.SELL;
                } else if (profitLossPrc > 6) {
                    return Action.SELL;
                } else if (profitLossPrc < -2) {
                    return Action.SELL;
                }
                    
            } else { // if already short
                if (sameCloseTwice) {
                    return Action.BUY; // if closed same twice in a row - exit position
                } else if (bullishNeighbors >= 4) {
                    return Action.BUY;
                } else if (profitLossPrc > 6) {
                    return Action.BUY;
                } else if (profitLossPrc < -2) {
                    return Action.BUY;
                }
            }
        }
        
        return Action.NEUTRAL;
    }
    
    private Action calculateActionFromNeighbors(StockMarketWorld marketWorld, XYCoordinates gridCoordinates, int bullishNeighbors, int bearishNeighbors) {
        
        boolean between3and7Bulish = 3 <= bullishNeighbors && bullishNeighbors <= 7;
        boolean between3and7Bearish = 3 <= bearishNeighbors && bearishNeighbors <= 7;
        
        if (between3and7Bearish && between3and7Bulish) {// if have both 4 bullish and 4 bearish neighbors then be neutral
            return Action.NEUTRAL;
        } else if (between3and7Bulish || bearishNeighbors > 7) {// if more than 7 bearish - take contrarian view and buy
            return Action.BUY;
        } else if (between3and7Bearish || bullishNeighbors > 7) {// if more than 7 bullish - take contrarian view and sell
            return Action.SELL;
        } else {
            return Action.NEUTRAL;
        }
    }
}

Rules are pretty simple. If participant does not have open position then it checks how many of his neighbors are bullish and how many bearish. If 3 to 7 are bullish his next action is to buy and if 3 to 7 is bearish his next action is to sell. If all 8 neighbors are bullish he takes opposite view and sells. Same if all 8 neighbors are bearish – he takes opposite view and buys. If he has open position he takes profits if it’s more than 6% of his open position and cut losses if it exceeds 2% of open position. Also exit position if last 2 candles closes at the same price or neighbors become too bearish/bullish to the opposite side. And that’s it.

Summary

As you can see it is extremely simplified simulation. It can be a lot of fun to play with different parameters and add additional features. You can check out source code from github and do it yourself. Maybe it would make sense to separate market participants into two types like market makers who use only limit orders and speculators who use market orders. It would be interesting to add participants with more different and longer term strategies. For example some moving average or stochastic (or other indicator) strategies. Each cell could look not only at their own neighbors but market sentiment as a whole. Some market “news” feature could be added that changes perception of participants and it could be interesting to watch how they react to it. If you read good book about market microstructure I am sure there will be no shortage for ideas.

Can it be useful for real world trading? Well I am not sure. One possible use case could be to identify all types of real world market participants and build realistic market microstructure model based on that. Then by running a lot of simulations try to guess current market composition and then run simulation further which could provide a peek into the future under various conditions. Could it work? I don’t know but I hope to find out 🙂

Cellular automaton mini framework and Conway’s Game of Life implementation

In this article I am going to create mini cellular automaton framework and then implement Conway’s game of life with it.  I will try to put attention to proper coding techniques, API design,  OOP and code documentation so its not only about cellular automaton but also about my thought process when I design new application.

Lets get started. First of all what is cellular automaton? Let’s look at wikipedia:

A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays.

A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off (in contrast to a coupled map lattice). The grid can be in any finite number of dimensions. For each cell, a set of cells called its neighborhood is defined relative to the specified cell. An initial state (time t=0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood. Typically, the rule for updating the state of cells is the same for each cell and does not change over time, and is applied to the whole grid simultaneously, though exceptions are known, such as the stochastic cellular automaton and asynchronous cellular automaton.

In other words it is a grid of cells and each cell changes its state during time iteration according to certain rules.

I want API to be as simple as possible and my goal is that it should work like this for any automaton at the end of the day:

World<Boolean> world = // create world implementation

for (int i = 0; i < 1000; i++) {
            Thread.sleep(100);
            world.nextState();
}

I don’t know if World is the best name for grid of cells abstraction but decided to use it anyway.

So the main classes will be  World and Cell .  Lets create them. Because I promised mini framework in the title I’m looking for a flexible solution and will create interfaces first which later can be implemented according to our needs.


public interface Cell<T> {
    
    T getValue();
    
    void revaluateCell();

    void commitRevaluation();
    
}

public interface World<T> {

    public void nextState();
    
    public void addPattern(Pattern pattern, Coordinates coordinates);
    
    public Cell<T> getCell(Coordinates coordinates);

}

World of course has method nextState() which is used for iterating through states and also provide additional methods for cell retrieval based on its coordinates and addition of new pattern. Cell can return its value with getValue() method. Also it is capable of reevaluating itself and then commit new reevaluated value. The reason for such design is that I want each cell to be “smart” and handle its own value independently. The 2 step process of reevaluation and commit is required because in most cases cell reevaluates itself depending on other cells in the world. That means that cell cannot commit its value before all cells reevaluate theirs first otherwise cell’s states would be inconsistent.  Lets see how such cell’s  implementation looks like:

public class SimpleCell<T> implements Cell<T> {

    private T value;

    private T revaluatedValue;

    private CellularAutomatonRule<T> rule;

    private Coordinates cellCoordinates;

    private World<T> world;

    public SimpleCell(T value, CellularAutomatonRule<T> rule,
            Coordinates cellCoordinates, World<T> world) {
        super();
        this.value = value;
        this.rule = rule;
        this.cellCoordinates = cellCoordinates;
        this.world = world;
    }

    @Override
    public T getValue() {
        return value;
    }

    @Override
    public void revaluateCell() {
        revaluatedValue = rule.calculateNewValue(value, world, cellCoordinates);
    }

    @Override
    public void commitRevaluation() {
        value = revaluatedValue;
        revaluatedValue = null;
    }

}

public interface CellularAutomatonRule<T> {
    T calculateNewValue(T currentValue, World<T> grid, Coordinates coordinates);
}
public interface Coordinates {
    int[] getCoordinates();
}

This SimpleCell implementation should be enough for most of the simple use cases. Here we have added two new abstractions – Coordinates and CellularAutomatonRule. Coordinates tells us where the Cell is in the world. Even though most often cellular automatons are in 2D grid world we want the design which allows any dimension and any type of Cell.  CellularAutomatonRule implementations defines rules how cell changes its value from one step to the next. In perfect world and perfect framework this should be the only class that has to be implemented when creating a new custom automaton.

Because each class should be responsible for only one thing lets add last abstraction – WorldGui.

public interface WorldGui<T> {
    public void showWorld(World<T> world);
}

It has only one method called showWorld() which must be invoked after each iteration to display World in a new state for the user. Today I will implement very simple text GUI just to show Conway’s game of life but because we code to abstraction it is very easy to replace it with other types of more interesting GUIs for example Swing.

So with current design our framework is used like this: user implements CellularAutomatonRule which defines what his automaton is doing and how each Cell changes its values. Then he constructs World which contains Cells of certain value type. Ideally all required World and Cell implementations are already provided by framework and can be simply reused. Then he simply iterate and invoke World.nextState() and WorldGui.showWorld() methods. And that is it.

OK lets implement interfaces we have left. Here is implementation of simple 2D coordinates which is really simple and self explanatory:

public class XYCoordinates implements Coordinates {

    private int x;
    private int y;

    public XYCoordinates(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    @Override
    public int[] getCoordinates() {
        return new int[] { x, y };
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

}

Now World implementation for 2d grid world. As you can see here we have 2 classes SimpleTwoDimensionalGrid which is abstract class and SimpleBooleanGridWorld which extends SimpleTwoDimensionalGrid. The reason for this is to encapsulate all logic for 2d worlds in abstract class and reuse it later with various types of cells. In this example we create 2d world with cells with boolean values.

public abstract class SimpleTwoDimensionalGrid<T> implements World<T> {

    private Cell<T>[][] worldGrid = null;
    
    private int height;

    private int lenght;
    
    private CellularAutomatonRule<T> rule;

    @SuppressWarnings("unchecked")
    public SimpleTwoDimensionalGrid(int height, int length, CellularAutomatonRule<T> rule) {
        super();
        this.height = height;
        this.lenght = length;
        this.rule = rule;
        this.worldGrid = new Cell[height][lenght];
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < lenght; x++) {
                worldGrid[y][x] = createNewCell(new XYCoordinates(x, y), rule);
            }
        }
    }

    @Override
    public void nextState() {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < lenght; j++) {
                worldGrid[i][j].revaluateCell();
            }
        }
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < lenght; j++) {
                worldGrid[i][j].commitRevaluation();
            }
        }
    }

    @Override
    public Cell<T> getCell(Coordinates coordinates) {
        XYCoordinates gridCoordinates = (XYCoordinates) coordinates;
        return worldGrid[gridCoordinates.getY()][gridCoordinates.getX()];
    }
    
    @Override
    public void addPattern(Pattern pattern, Coordinates coordinates) {
        @SuppressWarnings("unchecked")
        T[][] patternValues = ((GridPattern<T>)pattern).get();
        XYCoordinates gridCoordinates = ((XYCoordinates)coordinates);
        for (int y = gridCoordinates.getY(); y < getHeight() && y < gridCoordinates.getY() + patternValues.length; y++) {
            for (int x = gridCoordinates.getX(); x < getLenght() && x < gridCoordinates.getX() + patternValues[0].length; x++) {
                worldGrid[y][x] = new SimpleCell<T>(patternValues[y - gridCoordinates.getY()][x - gridCoordinates.getX()], rule, new XYCoordinates(x, y), this);
            }
        }
    }

    public int getHeight() {
        return height;
    }

    public int getLenght() {
        return lenght;
    }
    
    protected abstract Cell<T> createNewCell(XYCoordinates coordinates, CellularAutomatonRule<T> rule);
}

public class SimpleBooleanGridWorld extends SimpleTwoDimensionalGrid<Boolean> {
    public SimpleBooleanGridWorld(int height, int length, CellularAutomatonRule<Boolean> rule) {
        super(height, length, rule);
    }

    @Override
    protected Cell<Boolean> createNewCell(XYCoordinates coordinates, CellularAutomatonRule<Boolean> rule) {
        return new SimpleCell<Boolean>(false, rule, coordinates, this);
    }
}

public interface Pattern {
    Object get();
}
public abstract class GridPattern<T> implements Pattern {
    public abstract T[][] get();
}
public class ToadPattern extends GridPattern<Boolean> {
    @Override
    public Boolean[][] get() {
        return new Boolean[][] {{false, true, true, true}, {true, true, true, false}};
    }
}

Code is pretty much self explanatory.  In constructor we create a new 2 dimensional array and fill it by invoking createNewCell() method for each position.  SimpleBooleanGridWorld returns SimpleCell with Boolean type value.  And in nextState() method we simply iterate through each cell two times – first to reevaluate and then commit new value.  Also World has the method to add some custom patterns to it so I have added some sample Pattern interface implementations.

For GUI I am a bit lazy and will create very simple text GUI with simple System.out.println().  It is printing grid world and then it is printing empty lines. If everything is correct this creates textual animation.

public class TextBooleanGridWorldGui implements WorldGui<Boolean> {

    @Override
    public void showWorld(World<Boolean> world) {
        SimpleBooleanGridWorld booleanGridWorld = (SimpleBooleanGridWorld)world;
        for (int y = 0; y < booleanGridWorld.getHeight(); y++) {
            for (int x = 0; x < booleanGridWorld.getLenght(); x++) {
                System.out.print(booleanGridWorld.getCell(new XYCoordinates(x, y)).getValue() ? "@" : "-");
            }
            System.out.println();
        }
        for (int y = 0; y < booleanGridWorld.getHeight(); y++) { // print empty lines to separate different states (if its large enough it will create animation for changing states)
            System.out.println();
        }
    }

}

And last interface to implement before running our example is of course CellularAutomatonRule:

public class ConwaysGameOfLifeRule implements CellularAutomatonRule<Boolean> {
    
    private static Cell<Boolean> EMPTY_CELL = new SimpleCell<Boolean>(false, null, null, null);

    @Override
    public Boolean calculateNewValue(Boolean currentValue, World<Boolean> world, Coordinates coordinates) {
        XYCoordinates gridCoordinates = (XYCoordinates)coordinates;
        SimpleTwoDimensionalGrid<Boolean> gridWorld = (SimpleBooleanGridWorld)world;
        int sum = (getUpperNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getLowerNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0)
                + (getLeftNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getRightNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0)
                + (getUpperLeftNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getUpperRightNeighbor(gridWorld, gridCoordinates).getValue() ? 1 : 0)
                + (getLowerLeftNeigbhor(gridWorld, gridCoordinates).getValue() ? 1 : 0) + (getLowerRightNeigbhor(gridWorld, gridCoordinates).getValue() ? 1 : 0);
        return currentValue ? sum == 2 || sum == 3 : sum == 3;
    }
    
    private Cell<Boolean> getUpperNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX();
        int neighborY = coordinates.getY() - 1;
        return (neighborY >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLowerNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX();
        int neighborY = coordinates.getY() + 1;
        return (neighborY < world.getHeight()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLeftNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() - 1;
        int neighborY = coordinates.getY();
        return (neighborX >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getRightNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() + 1;
        int neighborY = coordinates.getY();
        return (neighborX < world.getLenght()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getUpperLeftNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() - 1;
        int neighborY = coordinates.getY() - 1;
        return (neighborX >= 0 && neighborY >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getUpperRightNeighbor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() + 1;
        int neighborY = coordinates.getY() - 1;
        return (neighborX < world.getLenght() && neighborY >= 0) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLowerLeftNeigbhor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() - 1;
        int neighborY = coordinates.getY() + 1;
        return (neighborX >= 0 && neighborY < world.getHeight()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

    private Cell<Boolean> getLowerRightNeigbhor(SimpleTwoDimensionalGrid<Boolean> world, XYCoordinates coordinates) {
        int neighborX = coordinates.getX() + 1;
        int neighborY = coordinates.getY() + 1;
        return (neighborX < world.getLenght() && neighborY < world.getHeight()) ? world.getCell(new XYCoordinates(neighborX, neighborY)) : EMPTY_CELL;
    }

}

Implementation of ConwaysGameOfLifeRule provides some getters to retrieve cell’s neighbors. In calculateNewValue() method it returns new value of the cell according to the Conway’s game of life rules which are following:
1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

And that’s it. Lets create main method and see Conway’s game of life in action:

public class Main {
    
    public static void main(String[] args) throws IOException, InterruptedException {
        WorldGui<Boolean> gui = new TextBooleanGridWorldGui();
        World<Boolean> world = new SimpleBooleanGridWorld(30, 100, new ConwaysGameOfLifeRule());
 world.addPattern(new ToadPattern(), new XYCoordinates(15, 15));
        gui.showWorld(world);
        for (int i = 0; i < 1000; i++) {
            Thread.sleep(100);
            world.nextState();
            gui.showWorld(world);
        }
    }

}

Pretty much as I wanted. If you run it from your eclipse you might see your toad pattern  similar to this (if you have not implemented your own GUIclass) :

toad

You can read more about game of life and its other patterns in wikipedia.

So what if you want one dimensional or 3d automaton. Well you will need implement all classes e.g create 3dCoordinates, 3D World, 3DGui etc. Same goes for different values of the cell. It can be as simple as boolean or as complex as you want when creating value class. And the good news is after you do this, its easy just to change rule class and experiment with different cellular automatons. However in most cases 2d grid automatons should be enough 🙂

So this article was not only about cellular automaton but also about OOP and my thought process when designing new application. I hope you liked it and learned something from it. I welcome any criticism, remarks, ways to improve, suggestions, bugfixes etc. If you implement different kinds of cellular automatons on top of it let me know! All code can be downloaded from Github!

You might wonder how cellular automatons can be used in practice. It is useful for doing various kinds of simulations. For example traffic simulation or electronic circuits simulation or some particles movement simulation etc. You could even try to play with cellular automatons and try to create some music!

In the next article I will try to implement something more interesting with automaton – simplified stock market simulation. Cheers!