go get github.com/jadekler/git-go-logictree- Navigate to the project directory
go test ./...(make sure mysql is running and root/no pwd is enabled)go run $GOPATH/src/github.com/jadekler/git-go-logictree/main.go- Navigate to
localhost:8080in your browser
To test locally, simply run go test -v ./... from the project root.
Note: Useful testing command: printf "$(go test $GOPATH/src/github.com/jadekler/git-go-logictree/app/home | sed 's/::/\\n/g')" && echo;
This program is a pretty simple lexical analyzer that accepts human-readable conditions, such as 'age greater than 5', and translates it to mysql-queryable language. The basic case is fairly simple, but the more advanced cases, such as '(age is greater than 5 or number of pets is less than 2) and age is less than 9', require a bit more work. The intermediary step between human-readable conditions and mysql conditions is implemented as a tree. Additionally, the human-readable conditions are stored in mysql as a left-right hierarchy tree (which represents nested sets). See more detail on the tree and nested sets below.
The setup for this app is: human-readable on the front, golang tree in the middle, mysql nested sets in the back. Here is a basic overview of how the stages interact:
Below are the explanation for each stage.
The front end is represented as a set of parenthesis, equality conditions, and logical conditions. Combined, they look like this:
Each block is draggable - by clicking the 'Save Re-ordering' button on the page, the re-ordered conditions are saved in mysql. The conditions will also be converted to a mysql query and executed against a dummy users table, with results displayed at the bottom of the page.
We use a tree as an intermediary between the human-readable conditions on the front and interactions with mysql, including saving the conditions, executing the conditions, and converting the conditions (via tree) into human-readable conditions for the front. The tree is a simple n-child tree that is generally traversed post-order. The branches are logical conditions, and the leaves are equality conditions. For instance, (A OR B) would be represented as OR being the branch and A and B being two children of OR, and so on. See below a larger example (taken from the app):
The general idea behind storing a tree in mysql as nested sets is well explained here. The basic idea, however, is that each condition is a set, and each child (in the aforementioned tree) is a set within the set that is its parent condition. Once we have so ordered our sets, we can assign lefts and rights to them as below:
In mysql, this becomes:
condition, left, right
----------------------
AND, 1, 24
OR, 2, 17
AND, 3, 14
age = 4, 4, 5
age = 5, 6, 7
age = 6, 8, 9
age = 7, 10, 11
age = 8, 12, 13
age = 1, 15, 16
OR, 18, 23
age = 2, 19, 20
age = 3, 21, 22
The space complexity is O(n) in both the server language and mysql - that is, we store each node and no additional information both in mysql and in our tree (we use pointers in the tree for parents and children).
The time complexity is as follows:
The function that deals with this is called unserializeRawTree. This function assumes a set of conditions pulled from mysql ordered by the LEFT column ascending. It iterates through the conditions, popping conditions off and creating the tree until the conditions are empty.
The two sides to the equation:
- Pop each condition from the array -
O(n) - Insert each condition into a non-binary, unbalanced tree. In the worst case, we assume a left-leaning tree. Each item must traverse over each item previously inserted. Therefore, the traversal operations per condition are
1+2+...+(n-1)+n. This series converges to(1/2)n(n+1), which gives usO(n^2).
Finally, we see that the time complexity is O(n)+O(n^2) = O(n^2).
The function that deals with this is called unserializeFormattedTree. I realize my naming scheme is awful. Anyways, this function iterates over leaves and recurses through branches, building the tree as it goes and relying on the recursive call to glue it all together. So once again, we touch each condition only once - this function runs in O(n).
The function that deals with this is called serializeTree. It traverses the tree post-order, building a linear array of conditions as it goes. Again, we traverse the tree touching each condition once - this function runs in O(n).
The function that deals with this is called toJSON (actually, the helper function toJSONRecursively does the real work) and once again simply traverses the tree post-order in O(n) time.
* By frontend, I mean a linear array of conditions, including parenthesis that surround children.
Please shoot any questions or feedback over to jadekler@gmail.com.