Queryable data structures.

While creating Alarm, I ran up against the problem of how to answer what seemed like a simple question.

When is the next scheduled call?

Initially, I setup my storage as a mapping of block number to a list of calls.  This seemed sufficient until I realized that in order to find the next scheduled call, I'd have to iterate through the upcoming blocks one at a time, querying for whether there were calls scheduled.

A few iterations and I settled on a tree structure.  It seemed functionally the same using a linked list.  Something about trees always feels elegant to me.  Each node of the tree has a left and a right child.  Anything left comes before the node, and anything right comes after.  Simple right.

It turns out that the tree implementation accounts for almost a third of the code.

In the world of web apps, I'm used to having a database that I can query.  It was so easy to take that for granted.  Only now am I seeing what it looks like when you have to start an ecosystem from scratch.

Today I released what I hope to be a step towards powerful queryable data storage for contracts.  Grove implements a more generic version of the tree management code that was created for the Alarm service.  It currently uses the AVL implementation of a self balancing binary tree.  As nodes are added to it, the tree continues to rebalance itself such that all leaf nodes remain within one level of each other in terms of depth.  Lookups, Insertions, and Deletions are all O(log n) both in average and the worst case scenarios where n is the number of nodes in the tree.

Currently grove can query for the first node that is >, >=, <, <=, == a given value.  I'm hoping it can be the first stepping stone towards contract APIs with powerful querying capabilities.  And to eat my own dog food, the next release of Alarm will change over to using Grove, making room for new feature development that I currently don't have.