JDatalkog

//.h file code:

#include "Exception.h"
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cctype>
#include <stdexcept>
#include <any>
#include <optional>
#include <mutex>
#include "exceptionhelper.h"
#include "stringhelper.h"
#include "stringbuilder.h"

//JAVA TO C++ CONVERTER NOTE: Forward class declarations:
class Expr;
class Rule;
class DatalogException;
class StringBuilder;
class StackMap;
class NumberFormatException;
class ?;
class ? extends V;

/*
Java Datalog Engine with Stratified Negation
Copyright 2016 Werner Stoop
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
    http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Notes, Features and Properties:
 * It implements stratified negation, or Stratified Datalog~.
 * It can parse and evaluate Datalog programs from files and Strings (actually anything that implements java.io.Reader).
 * It has a fluent API through which it can be embedded in Java applications to run queries. See the main() method for
    examples.
 * It implements "=", "<>" (alternatively "!="), "<", "<=", ">" and ">=" as built-in predicates.
 * It avoids third party dependencies because it is a proof-of-concept. It should be able to stand alone.
 * Values with "quoted strings" are supported, but to prevent a value like "Hello World" from being confused with a
    variable, it is stored internally with a " prefix, i.e. "Hello" is stored as `"Hello`.
    This is why the toString(Map<String, String> bindings) method uses substring(1) on the term.
 * Also, predicates can't be in quotes. Is this a desirable feature?
2016/04/26 - It now supports built-in predicates "=", "<>" (alternatively "!="), "<", "<=", ">" and ">=".
2016/04/19 - It now implements stratified negation, or Stratified Datalog~.
2016/04/12 - It now implements simple negation for non-recursive programs, or semipositive Datalog~ (my keyboard
    doesn't have their "not" sign) as described in section 2.3.1 of [gree]. It won't be able to compute very
    complex negations correctly.
2016/04/11 - Work-In-Progress: I'm busy implementing negation.
2016/04/08 - I've replaced the code that uses the Streams API with more old-fashioned code. The Streams version
    worked properly, but my rough benchmarks show that the code is ever so slightly more efficient now.
2016/04/06 - It now implements "Semi-Naive Bottom-Up" evaluation.
2016/03/29 - Added a profiler
2016/03/24 - Implemented a parser - the original version only had the fluent API.
2016/03/23 - The original version was "Naive Bottom-Up"
Compile like so:
    > javac JDatalog.java
Run like so:
    > java JDatalog test.dl
References:
  [wiki]  Wikipedia topic, http://en.wikipedia.org/wiki/Datalog
  [elma]  Fundamentals of Database Systems (3rd Edition); Ramez Elmasri, Shamkant Navathe
  [ceri]  What You Always Wanted to Know About Datalog (And Never Dared to Ask); Stefano Ceri, Georg Gottlob, and Letizia Tanca
  [bra1]  Deductive Databases and Logic Programming; Stefan Brass, Univ. Halle, 2009
            http://dbs.informatik.uni-halle.de/Lehre/LP09/c6_botup.pdf
  [banc]  An Amateur’s Introduction to Recursive Query Processing Strategies; Francois Bancilhon, Raghu Ramakrishnan
  [mixu]  mixu/datalog.js; Mikito Takada, https://github.com/mixu/datalog.js
  [kett]  bottom-up-datalog-js; Frederic Kettelhoit http://fkettelhoit.github.io/bottom-up-datalog-js/docs/dl.html
  [davi]  Inference in Datalog; Ernest Davis, http://cs.nyu.edu/faculty/davise/ai/datalog.html
  [gree]  Datalog and Recursive Query Processing; Todd J. Green, Shan Shan Huang, Boon Thau Loo and Wenchao Zhou
            Foundations and Trends in Databases Vol. 5, No. 2 (2012) 105–195, 2013
            http://blogs.evergreen.edu/sosw/files/2014/04/Green-Vol5-DBS-017.pdf
  [bra2]  Bottom-Up Query Evaluation in Extended Deductive Databases, Stefan Brass, 1996
            https://www.deutsche-digitale-bibliothek.de/binary/4ENXEC32EMXHKP7IRB6OKPBWSGJV5JMJ/full/1.pdf
  [sund]  Datalog Evaluation Algorithms, Dr. Raj Sunderraman, 1998
            http://tinman.cs.gsu.edu/~raj/8710/f98/alg.html
  [ull1]  Lecture notes: Datalog Rules Programs Negation; Jeffrey D. Ullman;
            http://infolab.stanford.edu/~ullman/cs345notes/cs345-1.ppt
  [ull2]  Lecture notes: Datalog Logical Rules Recursion; Jeffrey D. Ullman;
            http://infolab.stanford.edu/~ullman/dscb/pslides/dlog.ppt
  [meye]  Prolog in Python, Chris Meyers, http://www.openbookproject.net/py4fun/prolog/intro.html
  [alec]  G53RDB Theory of Relational Databases Lecture 14; Natasha Alechina;
            http://www.cs.nott.ac.uk/~psznza/G53RDB07/rdb14.pdf
  [rack]  Datalog: Deductive Database Programming, Jay McCarthy, https://docs.racket-lang.org/datalog/
            (Datalog library for the Racket language)
---------------------------------
[davi] explains how using top-down evaluation might lead to infinite loops, but says that it is sufficient to prevent this by failing
the test if you encounter a goal that you've already encountered in the stack. A very early version of this module basically ported [mixu]'s
top-down evaluator to Java, but encountered this precise problem (and solved it in the way described).
---------------------------------
I initially just assumed that using the StackMap would be faster, so I tried an implementation with a HashMap where I just did a
newMap.putAll(parent) and removed the StackMap entirely. My rough benchmarks showed the StackMap-based implementeation to be about 30%
faster than the alternative.
---------------------------------
It occurred to me that if you /really/ want the equivalent of JDBC *prepared statements* then you can pass pass in a Map<String, String> containing
the bound variables. This map will then be sent all the way down to `matchRule()` where it can be passed as the `bindings` parameter in the call
to `matchGoals()` - so the map will end up at the bottom of the StackMap stack.
This will allow you to use statements like for example `jDatalog.query(new Expr("foo","X", "Y"), binding)`, with `binding = {X : "bar"}`, in the
fluent API to perform bulk inserts or queries and so on.
A problem is that the varargs ... operator must come last in the method declaration, but I can work around this by having a method that only accepts
List<Expr> as an argument rather than varargs.
You can then create a method `prepareStatement()` that can return a List<Expr> from a parsed query.
Actually, the List<Expr> should be wrapped in a JStatement (or something) interface so that you can run insert rules, insert facts and delete facts
through these "prepared statements".
---------------------------------
I've decided that the built-in predicates are to be written as `new Expr("!=", "X", "Y")` for `X != Y` in the fluent API. I've considered
special static methods and Builder objects, but none really appealed to me.
In a future I might consider `Expr.eq("X", "Y")`, `Expr.ne("X", "Y")`, `Expr.gt("X", "Y")`, `Expr.lt("X", "Y")`, `Expr.ge("X", "Y")` and
`Expr.le("X", "Y")`.
---------------------------------
There are opportunities to run some of the methods in parallel using the Java 8 Streams API (I'm thinking of the calls to expandStrata() in
buildDatabase() and the calls to matchRule() in expandStrata() in particular). The biggest obstacle at the moment is that the Expr#evalBuiltIn()
throws a DatalogException, and DatalogException is necessarily checked because it is used for proper reporting of user errors.
It seems the most practical solution is to wrap the DatalogException in a RuntimeException and then unwrap it at a higher level.
See http://stackoverflow.com/a/27648758/115589
---------------------------------
The Racket language has a Datalog module as part of its library [rack]. I've looked at its API for ideas for my own. They use the syntax
`<clause>~` for a retraction, e.g parent(bob, john)~, which is a syntax I might want to adopt. The [rack] implementation lacks some of the
features of my version, like negation and queries with multiple goals.
---------------------------------
It is conceptually possible to make the `List<String> terms` of Expr a `List<Object>` instead, so that you can store complex Java objects in the
database (as POJOs). The `isVariable()` method will just have to be modified to check whether its parameter is instanceof String and starts with
an uppercase character, the bindings will become a Map<String, Object>, the result of `query()` will be a List<Map<String, Object>> and a
couple of toString() methods will have to be modified. It won't be that useful a feature if you just use the parser, but it could be a "nice to
have" if you use the fluent API. I don't intend to implement it at the moment, though.
---------------------------------
I've decided against arithmetic built-in predicates, such as plus(X,Y,Z) => X + Y = Z, for now:
  - Arithmetic predicates aren't that simple. They should be evaluated as soon as the input variables (X and Y) in this case becomes available,
    so that Z can be computed and bound for the remaining goals.
  - Arithmetic expressions would require a more complex parser and there would be a need for Expr to have child Expr objects to build a parse tree.
    The parse tree would be simpler if the `terms` of Expr was a List<Object> - see my note above.
*/



class JDatalog
{

private:
    std::vector<Expr*> edb; // Facts
    Collection<Rule*>* idb; // Rules

    static bool debugEnable;

public:
    virtual ~JDatalog()
    {
        delete idb;
    }

    JDatalog();

public:
    class Expr
    {

    private:
        std::string predicate;
        std::vector<std::string> terms;

    protected:
        bool negated = false;

    public:
        Expr(const std::string& predicate, std::vector<std::string>& terms);

        Expr(const std::string& predicate, std::vector<std::string> &terms);

        virtual int arity();

        virtual bool isGround();

        virtual bool isNegated();

        virtual bool isBuiltIn();

        static Expr* not(const std::string& predicate, std::vector<std::string> &terms);

        virtual bool unify(Expr* that, std::unordered_map<std::string, std::string>& bindings);

        virtual Expr* substitute(std::unordered_map<std::string, std::string>& bindings);

        virtual bool evalBuiltIn(std::unordered_map<std::string, std::string>& bindings) throw(DatalogException);

        bool equals(std::any other) override;

        int hashCode() override;

        std::string toString() override;

    private:
        static StringBuilder* termToString(StringBuilder* sb, const std::string& term);

    };

    /* Reorganize the goals in a query so that negated literals are at the end.
    A rule such as `a(X) :- not b(X), c(X)` won't work if the `not b(X)` is evaluated first, since X will not
    be bound to anything yet, meaning there are an infinite number of values for X that satisfy `not b(X)`.
    Reorganising the goals will solve the problem: every variable in the negative literals will have a binding
    by the time they are evaluated if the rule is /safe/, which we assume they are - see Rule#validate()
    Also, the built-in predicates (except `=`) should only be evaluated after their variables have been bound
    for the same reason; see [ceri] for more information. */
private:
    static std::vector<Expr*> reorderQuery(std::vector<Expr*>& query);

public:
    class Rule
    {

    public:
        Expr* head;
        std::vector<Expr*> body;

        virtual ~Rule()
        {
            delete head;
        }

        Rule(Expr* head, std::vector<Expr*>& body);

        Rule(Expr* head, std::vector<Expr> &body);

        virtual void validate() throw(DatalogException);

        std::string toString() override;
    };

private:
    static bool isVariable(const std::string& term);

    // Methods for the fluent interface
public:
    virtual JDatalog* rule(Expr* head, std::vector<Expr> &body) throw(DatalogException);
    virtual JDatalog* rule(Rule* newRule) throw(DatalogException);

    virtual JDatalog* fact(const std::string& predicate, std::vector<std::string> &terms) throw(DatalogException);
    virtual JDatalog* fact(Expr* newFact) throw(DatalogException);

    /* If you're executing a file that may contain multiple queries, you can pass
    #execute(Reader, QueryOutput) a QueryOutput object that will be used to display
    all the results from the separate queries, with their goals.
    Otherwise #execute(Reader, QueryOutput) will just return the answers from the
    last query. */
public:
    class QueryOutput
    {
    public:
        virtual void writeResult(std::vector<Expr*>& goals, Collection<std::unordered_map<std::string, std::string> >* answers) = 0;
    };

    /* Default implementation of QueryOutput */
public:
    class StandardQueryOutput : public QueryOutput
    {
    public:
        void writeResult(std::vector<Expr*>& goals, Collection<std::unordered_map<std::string, std::string> >* answers) override override;
    };

    /* Executes all the statements in a file/string/whatever the Reader is wrapping */
public:
    virtual Collection<std::unordered_map<std::string, std::string> >* execute(Reader* reader, QueryOutput* output) throw(DatalogException);

private:
    Collection<std::unordered_map<std::string, std::string> >* parseStmt(StreamTokenizer* scan, std::vector<Expr*>& goals) throw(DatalogException);

    static Expr* parseExpr(StreamTokenizer* scan) throw(DatalogException);

    static const std::vector<std::string> validOperators;

    static Expr* parseBuiltInPredicate(const std::string& lhs, StreamTokenizer* scan) throw(DatalogException);

    static std::string numberToString(const double& nval);

    // Regex for tryParseDouble()
    // There are several suggestions at http://stackoverflow.com/q/1102891/115589, but I chose to roll my own.
    static Pattern* const  numberPattern;

    static bool tryParseDouble(const std::string& str);

    /* Normal Datalog exception. */
public:
    class DatalogException : public std::exception
    {
    public:
        DatalogException(const std::string& message);
        DatalogException(std::exception cause);
        DatalogException(const std::string& message, std::exception cause);
    };

public:
    virtual Collection<std::unordered_map<std::string, std::string> >* query(const std::string& statement) throw(DatalogException);

    virtual Collection<std::unordered_map<std::string, std::string> >* query(std::vector<Expr> &goals) throw(DatalogException);

    virtual Collection<std::unordered_map<std::string, std::string> >* query(std::vector<Expr*>& goals) throw(DatalogException);

    /* Returns a list of rules that are relevant to the query.
        If for example you're querying employment status, you don't care about family relationships, etc.
        The advantages of this of this optimization becomes bigger the complexer the rules get. */
private:
    Collection<Rule*>* getRelevantRules(std::vector<Expr*>& originalGoals);

    /* This basically constructs the dependency graph for semi-naive evaluation: In the returned map, the string
        is a predicate in the rules' heads that maps to a collection of all the rules that have that predicate in
        their body so that we can easily find the rules that are affected when new facts are deduced in different
        iterations of buildDatabase().
        For example if you have a rule p(X) :- q(X) then there will be a mapping from "q" to that rule
        so that when new facts q(Z) are deduced, the rule will be run in the next iteration to deduce p(Z) */
    std::unordered_map<std::string, Collection<Rule*>*> buildDependantRules(Collection<Rule*>* rules);

    Collection<Rule*>* getDependantRules(Collection<Expr*>* facts, std::unordered_map<std::string, Collection<Rule*>*>& dependants);

    Collection<Expr*>* buildDatabase(Set<Expr*>* facts, Collection<Rule*>* allRules) throw(DatalogException);

    std::vector<Collection<Rule*>*> computeStratification(Collection<Rule*>* allRules) throw(DatalogException);

    int depthFirstSearch(Expr* goal, Collection<Rule*>* graph, std::vector<Expr*>& visited, const int& level) throw(DatalogException);

    Collection<Expr*>* expandStrata(Set<Expr*>* facts, Collection<Rule*>* strataRules) throw(DatalogException);

    Set<Expr*>* matchRule(Collection<Expr*>* const facts, Rule* rule) throw(DatalogException);

    Collection<std::unordered_map<std::string, std::string> >* matchGoals(std::vector<Expr*>& goals, Collection<Expr*>* const facts, std::unordered_map<std::string, std::string>& bindings) throw(DatalogException);

public:
    virtual bool delete_RenamedTODO(std::vector<Expr> &facts) throw(DatalogException);

    /* Queries a set of goals and deletes all the facts that matches the query */
    virtual bool delete_RenamedTODO(std::vector<Expr*>& goals) throw(DatalogException);

    virtual void validate() throw(DatalogException);

    virtual void dump(PrintStream* out) throw(DatalogException);

    static void debug(const std::string& message);

    template<typename T1>
    static std::string toString(Collection<T1>* collection);

    static std::string toString(std::unordered_map<std::string, std::string>& bindings);

    // If you want to do benchmarking, run the file several times to get finer grained results.
private:
    static constexpr bool BENCHMARK = false;
    static constexpr int NUM_RUNS = 1000;

    static void main(std::vector<std::string> &args);

    /* Map<> implementation that has a parent Map<> where it looks up a value if the value is not in `this`. Its behaviour is equivalent
        to a HashMap that is passed a parent map in its constructor, except that it keeps a reference to the parent map rather than
        copying it. It never modifies the parent map. (If the behaviour deviates from this, it is a bug and must be fixed)
        Internally, it has two maps: `self` and `parent`. The `get()` method will look up a key in self and if it doesn't find it, looks
        for it in `parent`. The `put()` method always adds values to `self`. The parent in turn may also be a StackMap, so some method
        calls may be recursive. The `flatten()` method combines the map with its parents into a single one.
        It is used by JDatalog for the scoped contexts where the variable bindings enter and leave scope frequently during the
        recursive building of the database, but where the parent Map<> needs to be kept for subsequent recursions.
        Methods like entrySet(), keySet() and values() are required by the Map<> interface that their returned collections be backed
        by the Map<>. Therefore, their implementations here will flatten the map first. Once these methods are called StackMap just
        becomes a wrapper around the internal HashMap, hence JDatalog avoids these methods internally.
        The remove() method also flattens `this` to avoid modifying the parent while and the clear() method just sets parent to null
        and clears `self` .
        I've tried a version that extends AbstractMap, but it proved to be significantly slower.
    */
public:
    template<typename K, typename V>
    class StackMap : public std::unordered_map<K, V>
    {
    private:
        std::unordered_map<K, V> self;
        std::unordered_map<K, V> parent;

    public:
        StackMap()
        {
            self = std::unordered_map<K, V>();
            this->parent.clear();
        }

        StackMap(std::unordered_map<K, V>& parent)
        {
            self = std::unordered_map<K, V>();
            this->parent = parent;
        }

        virtual std::unordered_map<K, V> flatten()
        {
            std::unordered_map<K, V> map;
            // I don't use map.putAll(this) to avoid relying on entrySet()
            if(parent.size() > 0)
            {
                map.putAll(parent);
            }
            map.putAll(self);
            return map;
        }

        std::string toString() override
        {
            StringBuilder* sb = new StringBuilder("{");
            Set<K>* keys = std::unordered_set<K>(self.keySet());
            keys->addAll(parent.keySet());
            int s = keys->size(), i = 0;
            for(auto k : keys)
            {
                sb->append(k)->append(": ");
                sb->append(get(k));
                if(++i < s)
                {
                    sb->append(", ");
                }
            }
            sb->append("}");
            return sb->toString();
        }

        V put(K key, V value) override
        {
            return self.emplace(key, value);
        }

        bool containsKey(std::any key) override
        {
            if(self.find(key) != self.end())
            {
                return true;
            }
            if(parent.size() > 0)
            {
                return parent.find(key) != parent.end();
            }
            return false;
        }

        V get(std::any key) override
        {
            V value = self[key];
            if(value != nullptr)
            {
                return value;
            }
            if(parent.size() > 0)
            {
                return parent[key];
            }
            return nullptr;
        }

        Set<std::unordered_map::Entry<K, V>*>* entrySet() override
        {
            if(parent.size() > 0)
            {
                self = flatten(); // caveat emptor
                parent.clear();
            }
            return self.entrySet();
        }

        int size() override
        {
            int s = self.size();
            if(parent.size() > 0)
            {
                // Work around situations where self contains a `key` that's already in `parent`.
                // These situations shouldn't occur in JDatalog, though
                for(auto k : parent)
                {
                    if(self.find(k.first) == self.end())
                    {
                        s++;
                    }
                }
            }
            return s;
        }

        void clear() override
        {
            // We don't want to modify the parent, so we just orphan this
            parent.clear();
            self.clear();
        }

        bool equals(std::any o) override
        {
            if(o == nullptr || !(dynamic_cast<std::unordered_map>(o) != nullptr))
            {
                return false;
            }
            std::unordered_map that = std::any_cast<std::unordered_map>(o);
            return entrySet()->equals(that.entrySet());
        }
        int hashCode() override
        {
            int h = 0;
            for(auto entry : entrySet())
            {
                h += entry.hashCode();
            }
            return h;
        }
        Set<K>* keySet() override
        {
            if(parent.size() > 0)
            {
                self = flatten(); // caveat emptor
                parent.clear();
            }
            return self.keySet();
        }
        Collection<V>* values() override
        {
            if(parent.size() > 0)
            {
                self = flatten(); // caveat emptor
                parent.clear();
            }
            return self.values();
        }
        template<typename T1, typename T1>
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ template equivalent to this generic constraint:
//ORIGINAL LINE: @Override public void putAll(java.util.Map<? extends K,? extends V> m)
        void putAll(std::unordered_map<T1> m)
        {
            self.putAll(m);
        }
        V remove(std::any key) override
        {
            if(parent.size() > 0)
            {
                self = flatten(); // caveat emptor
                parent.clear();
            }
            return self.erase(key);
        }
        bool containsValue(std::any value) override
        {
            return self.containsValue(value) || (parent.size() > 0 && parent.containsValue(value));
        }
        bool isEmpty() override
        {
            if(self.empty())
            {
                if(parent.size() > 0)
                {
                    return parent.empty();
                } else
                {
                    return true;
                }
            }
            return false;
        }
    };

    /* Profiling class.
    I had to write my own because I didn't want to pull in any external dependencies.
    `buckets` maps the name of a bucket to a List of elapsed times so that you can have
    multiple timers under different names.
    */
public:
    class Profiler
    {

        // FYI: Java 8 actually has Instant and Duration classes.
        // Not sure whether they're really useful here, though.

    public:
        class Timer
        {
        private:
            long long start = 0;
            std::vector<long long> bucket;

        public:
            Timer(std::vector<long long>& bucket);

            virtual long long stop();
        };

    private:
        std::unordered_map<std::string, std::vector<long long> > buckets;

        static Profiler* instance;

        Profiler();

    public:
        static Profiler* getInstance();

        static void reset();

        static Timer* getTimer(const std::string& name);

        virtual std::vector<long long> getBucket(const std::string& name);

        static double average(const std::string& name);

        static long long total(const std::string& name);

        static int count(const std::string& name);

        static double stdDev(const std::string& name);

        static Set<std::string>* keySet();
    };
};

//stringhelper.h:

//----------------------------------------------------------------------------------------
//  Copyright © 2007 - 2018 Tangible Software Solutions Inc.
//  This class can be used by anyone provided that the copyright notice remains intact.
//
//  This class is used to replace some string methods, including
//  conversions to or from strings.
//----------------------------------------------------------------------------------------
#include <string>
#include <sstream>
#include <vector>
#include <exception>
#include <cctype>

class StringHelper
{
public:
    static std::string toLower(std::string source)
    {
        std::transform(source.begin(), source.end(), source.begin(), std::tolower);
        return source;
    }

    static std::string toUpper(std::string source)
    {
        std::transform(source.begin(), source.end(), source.begin(), std::toupper);
        return source;
    }

    static std::string trimStart(std::string source, const std::string &trimChars = " \t\n\r\v\f")
    {
        return source.erase(0, source.find_first_not_of(trimChars));
    }

    static std::string trimEnd(std::string source, const std::string &trimChars = " \t\n\r\v\f")
    {
        return source.erase(source.find_last_not_of(trimChars) + 1);
    }

    static std::string trim(std::string source, const std::string &trimChars = " \t\n\r\v\f")
    {
        return trimStart(trimEnd(source, trimChars), trimChars);
    }

    static std::string replace(std::string source, const std::string &find, const std::string &replace)
    {
        size_t pos = 0;
        while ((pos = source.find(find, pos)) != std::string::npos)
        {
            source.replace(pos, find.length(), replace);
            pos += replace.length();
        }
        return source;
    }

    static bool startsWith(const std::string &source, const std::string &value)
    {
        if (source.length() < value.length())
            return false;
        else
            return source.compare(0, value.length(), value) == 0;
    }

    static bool endsWith(const std::string &source, const std::string &value)
    {
        if (source.length() < value.length())
            return false;
        else
            return source.compare(source.length() - value.length(), value.length(), value) == 0;
    }

    static std::vector<std::string> split(const std::string &source, char delimiter)
    {
        std::vector<std::string> output;
        std::istringstream ss(source);
        std::string nextItem;

        while (std::getline(ss, nextItem, delimiter))
        {
            output.push_back(nextItem);
        }

        return output;
    }

    template<typename T>
    static std::string toString(const T &subject)
    {
        std::ostringstream ss;
        ss << subject;
        return ss.str();
    }

    template<typename T>
    static T fromString(const std::string &subject)
    {
        std::istringstream ss(subject);
        T target;
        ss >> target;
        return target;
    }

    template<typename T>
    static std::string formatSimple(const std::string &input, T arg1)
    {
        std::ostringstream ss;
        int lastFormatChar = -1;
        int percent = -1;
        while ((percent = input.find('%', percent + 1)) > -1)
        {
            if (percent + 1 < input.length())
            {
                if (input[percent + 1] == '%')
                {
                    percent++;
                    continue;
                }

                int formatEnd = -1;
                std::string index;
                for (int i = percent + 1; i < input.length(); i++)
                {
                    if (input[i] == 's')
                    {
                        index = "1";
                        formatEnd = i;
                        break;
                    }
                    else if (input[i] == '$' && i + 1 < input.length() && input[i + 1] == 's')
                    {
                        index = input.substr(percent + 1, i - percent - 1);
                        formatEnd = i + 1;
                        break;
                    }
                    else if (!std::isdigit(input[i]))
                        break;
                }

                if (formatEnd > -1)
                {
                    ss << input.substr(lastFormatChar + 1, percent - lastFormatChar - 1);
                    lastFormatChar = formatEnd;

                    if (index == "1")
                        ss << arg1;
                    else
                        throw std::exception("Only simple positional format specifiers are handled by the 'formatSimple' helper method.");
                }
            }
        }

        if (lastFormatChar + 1 < input.length())
            ss << input.substr(lastFormatChar + 1);

        return ss.str();
    }

    template<typename T1, typename T2>
    static std::string formatSimple(const std::string &input, T1 arg1, T2 arg2)
    {
        std::ostringstream ss;
        int lastFormatChar = -1;
        int percent = -1;
        while ((percent = input.find('%', percent + 1)) > -1)
        {
            if (percent + 1 < input.length())
            {
                if (input[percent + 1] == '%')
                {
                    percent++;
                    continue;
                }

                int formatEnd = -1;
                std::string index;
                for (int i = percent + 1; i < input.length(); i++)
                {
                    if (input[i] == 's')
                    {
                        index = "1";
                        formatEnd = i;
                        break;
                    }
                    else if (input[i] == '$' && i + 1 < input.length() && input[i + 1] == 's')
                    {
                        index = input.substr(percent + 1, i - percent - 1);
                        formatEnd = i + 1;
                        break;
                    }
                    else if (!std::isdigit(input[i]))
                        break;
                }

                if (formatEnd > -1)
                {
                    ss << input.substr(lastFormatChar + 1, percent - lastFormatChar - 1);
                    lastFormatChar = formatEnd;

                    if (index == "1")
                        ss << arg1;
                    else if (index == "2")
                        ss << arg2;
                    else
                        throw std::exception("Only simple positional format specifiers are handled by the 'formatSimple' helper method.");
                }
            }
        }

        if (lastFormatChar + 1 < input.length())
            ss << input.substr(lastFormatChar + 1);

        return ss.str();
    }

    template<typename T1, typename T2, typename T3>
    static std::string formatSimple(const std::string &input, T1 arg1, T2 arg2, T3 arg3)
    {
        std::ostringstream ss;
        int lastFormatChar = -1;
        int percent = -1;
        while ((percent = input.find('%', percent + 1)) > -1)
        {
            if (percent + 1 < input.length())
            {
                if (input[percent + 1] == '%')
                {
                    percent++;
                    continue;
                }

                int formatEnd = -1;
                std::string index;
                for (int i = percent + 1; i < input.length(); i++)
                {
                    if (input[i] == 's')
                    {
                        index = "1";
                        formatEnd = i;
                        break;
                    }
                    else if (input[i] == '$' && i + 1 < input.length() && input[i + 1] == 's')
                    {
                        index = input.substr(percent + 1, i - percent - 1);
                        formatEnd = i + 1;
                        break;
                    }
                    else if (!std::isdigit(input[i]))
                        break;
                }

                if (formatEnd > -1)
                {
                    ss << input.substr(lastFormatChar + 1, percent - lastFormatChar - 1);
                    lastFormatChar = formatEnd;

                    if (index == "1")
                        ss << arg1;
                    else if (index == "2")
                        ss << arg2;
                    else if (index == "3")
                        ss << arg3;
                    else
                        throw std::exception("Only simple positional format specifiers are handled by the 'formatSimple' helper method.");
                }
            }
        }

        if (lastFormatChar + 1 < input.length())
            ss << input.substr(lastFormatChar + 1);

        return ss.str();
    }
};

//stringbuilder.h:

//----------------------------------------------------------------------------------------
//  Copyright © 2007 - 2018 Tangible Software Solutions Inc.
//  This class can be used by anyone provided that the copyright notice remains intact.
//
//  This class is used to replace the Java StringBuilder in native C++.
//----------------------------------------------------------------------------------------
#include <string>
#include <sstream>

class StringBuilder
{
private:
    std::string privateString;

public:
    StringBuilder()
    {
    }

    StringBuilder(const std::string &initialString)
    {
        privateString = initialString;
    }

    StringBuilder(std::size_t capacity)
    {
        ensureCapacity(capacity);
    }

    char charAt(std::size_t index)
    {
        return privateString[index];
    }

    StringBuilder *append(const std::string &toAppend)
    {
        privateString += toAppend;
        return this;
    }

    template<typename T>
    StringBuilder *append(const T &toAppend)
    {
        privateString += toString(toAppend);
        return this;
    }

    StringBuilder *insert(std::size_t position, const std::string &toInsert)
    {
        privateString.insert(position, toInsert);
        return this;
    }

    template<typename T>
    StringBuilder *insert(std::size_t position, const T &toInsert)
    {
        privateString.insert(position, toString(toInsert));
        return this;
    }

    std::string toString()
    {
        return privateString;
    }

    std::size_t length()
    {
        return privateString.length();
    }

    void setLength(std::size_t newLength)
    {
        privateString.resize(newLength);
    }

    std::size_t capacity()
    {
        return privateString.capacity();
    }

    void ensureCapacity(std::size_t minimumCapacity)
    {
        privateString.reserve(minimumCapacity);
    }

    StringBuilder *remove(std::size_t start, std::size_t end)
    {
        privateString.erase(start, end - start);
        return this;
    }

    StringBuilder *replace(std::size_t start, std::size_t end, const std::string &newString)
    {
        privateString.replace(start, end - start, newString);
        return this;
    }

private:
    template<typename T>
    static std::string toString(const T &subject)
    {
        std::ostringstream ss;
        ss << subject;
        return ss.str();
    }
};

//exceptionhelper.h:

#include <exception>

class NumberFormatException : public std::exception
{
private:
    std::string msg;

public:
    NumberFormatException(const std::string& message = "") : msg(message)
    {
    }

    const char * what() const throw()
    {
        return msg.c_str();
    }
};

class IOException : public std::exception
{
private:
    std::string msg;

public:
    IOException(const std::string& message = "") : msg(message)
    {
    }

    const char * what() const throw()
    {
        return msg.c_str();
    }
};

//.cpp file code:

using namespace std;

#include "StringBuilder.h"
#include "StackMap.h"
#include "NumberFormatException.h"
#include "?.h"
#include "? extends V.h"

bool JDatalog::debugEnable = false;

JDatalog::JDatalog()
{
    this->edb = vector<>();
    this->idb = vector<>();
}

JDatalog::Expr::Expr(const wstring& predicate, vector<wstring>& terms)
{
    this->predicate = predicate;
    // I've seen both versions of the symbol for not equals being used, so I allow
    // both, but we convert to "<>" internally to simplify matters later.
    if(this->predicate == "!=")
    {
        this->predicate = "<>";
    }
    this->terms = terms;
}

JDatalog::Expr::Expr(const wstring& predicate, vector<wstring> &terms) : Expr(predicate, Arrays::asList(terms))
{
}

int JDatalog::Expr::arity()
{
    return terms.size();
}

bool JDatalog::Expr::isGround()
{
    for(auto term : terms)
    {
        if(isVariable(term))
        {
            return false;
        }
    }
    return true;
}

bool JDatalog::Expr::isNegated()
{
    return negated;
}

bool JDatalog::Expr::isBuiltIn()
{
    char op = predicate[0];
    return !isalnum(op) && op != '\"';
}

Expr* JDatalog::Expr::not(const wstring& predicate, vector<wstring> &terms)
{
    Expr* e = new Expr(predicate, terms);
    e->negated = true;
    return e;
}

bool JDatalog::Expr::unify(Expr* that, unordered_map<wstring, wstring>& bindings)
{
    if(this->predicate != that->predicate || this->arity() != that->arity())
    {
        return false;
    }
    for(int i = 0; i < this->arity(); i++)
    {
        wstring term1 = this->terms[i];
        wstring term2 = that->terms[i];
        if(isVariable(term1))
        {
            if(term1 != term2)
            {
                if(bindings.find(term1) == bindings.end())
                {
                    bindings.emplace(term1, term2);
                } else if(bindings[term1] != term2)
                {
                    return false;
                }
            }
        } else if(isVariable(term2))
        {
            if(bindings.find(term2) == bindings.end())
            {
                bindings.emplace(term2, term1);
            } else if(bindings[term2] != term1)
            {
                return false;
            }
        } else if(term1 != term2)
        {
            return false;
        }
    }
    return true;
}

Expr* JDatalog::Expr::substitute(unordered_map<wstring, wstring>& bindings)
{
    // that.terms.add() below doesn't work without the new ArrayList()
    Expr* that = new Expr(this->predicate, vector<>());
    that->negated = negated;
    for(auto term : this->terms)
    {
        wstring value;
        if(isVariable(term))
        {
            value = bindings[term];
            if(value == "")
            {
                value = term;
            }
        } else
        {
            value = term;
        }
        that->terms.push_back(value);
    }
    return that;
}

bool JDatalog::Expr::evalBuiltIn(unordered_map<wstring, wstring>& bindings) throw(DatalogException)
{
    //System.out.println("EVAL " + this + "; " + bindings);
    wstring term1 = terms[0];
    if(isVariable(term1) && bindings.find(term1) != bindings.end())
    {
        term1 = bindings[term1];
    }
    wstring term2 = terms[1];
    if(isVariable(term2) && bindings.find(term2) != bindings.end())
    {
        term2 = bindings[term2];
    }
    if(predicate == "=")
    {
        // '=' is special
        if(isVariable(term1))
        {
            if(isVariable(term2))
            {
                throw DatalogException("Both operands of '=' are unbound (" + term1 + ", " + term2 + ") in evaluation of " + this);
            }
            bindings.emplace(term1, term2);
            return true;
        } else if(isVariable(term2))
        {
            bindings.emplace(term2, term1);
            return true;
        } else
        {
            return term1 == term2;
        }
    } else
    {
        try
        {
            if(isVariable(term1))
            {
                throw DatalogException("Unbound variable " + term1 + " in evaluation of " + this);
            }
            if(isVariable(term2))
            {
                throw DatalogException("Unbound variable " + term2 + " in evaluation of " + this);
            }

            if(predicate == "<>")
            {
                // '<>' is also a bit special
                if(tryParseDouble(term1) && tryParseDouble(term2))
                {
                        double d1 = stod(term1);
                        double d2 = stod(term2);
                        return d1 != d2;
                } else
                {
                    return term1 != term2;
                }
            } else
            {
                // ordinary comparison operator
                if(!tryParseDouble(term1) || !tryParseDouble(term2))
                {
                    throw DatalogException("Both parameters of " + predicate + " must be numeric (" + term1 + ", " + term2 + ") in evaluation of " + this);
                }
                double d1 = stod(term1);
                double d2 = stod(term2);
                switch(predicate)
                {
                    case "<":
                        return d1 < d2;
                    case "<=":
                        return d1 <= d2;
                    case ">":
                        return d1 > d2;
                    case ">=":
                        return d1 >= d2;
                }
            }
        } catch(const NumberFormatException& e)
        {
            // You found a way to write a double in a way that the regex in tryParseDouble() doesn't understand.
//JAVA TO C++ CONVERTER TODO TASK: The std::exception constructor has no parameters:
//ORIGINAL LINE: throw new RuntimeException("tryParseDouble() experienced a false positive!?", e);
            throw exception();
        }
    }
//JAVA TO C++ CONVERTER TODO TASK: The std::exception constructor has no parameters:
//ORIGINAL LINE: throw new RuntimeException("Unimplemented built-in predicate " + predicate);
    throw exception();
}

bool JDatalog::Expr::equals(any other)
{
    if(other == nullptr || !(dynamic_cast<Expr*>(other) != nullptr))
    {
        return false;
    }
    Expr* that = (any_cast<Expr*>(other));
    if(this->predicate != that->predicate)
    {
        return false;
    }
    if(arity() != that->arity() || negated != that->negated)
    {
        return false;
    }
    for(int i = 0; i < terms.size(); i++)
    {
        if(terms[i] != that->terms[i])
        {
            return false;
        }
    }
    return true;
}

int JDatalog::Expr::hashCode()
{
    int hash = predicate.hashCode();
    for(auto term : terms)
    {
        hash += term.hashCode();
    }
    return hash;
}

wstring JDatalog::Expr::toString()
{
    StringBuilder* sb = new StringBuilder();
    if(isNegated())
    {
        sb->append("not ");
    }
    if(isBuiltIn())
    {
        termToString(sb, terms[0]);
        sb->append(" ")->append(predicate)->append(" ");
        termToString(sb, terms[1]);
    } else
    {
        sb->append(predicate)->append('(');
        for(int i = 0; i < terms.size(); i++)
        {
            wstring term = terms[i];
            termToString(sb, term);
            if(i < terms.size() - 1)
            {
                sb->append(", ");
            }
        }
        sb->append(')');
    }
    return sb->toString();
}

StringBuilder* JDatalog::Expr::termToString(StringBuilder* sb, const wstring& term)
{
    if(StringHelper::startsWith(term, "\""))
    {
        sb->append('"')->append(term.substr(1)->replaceAll("\"", "\\\\\""))->append('"');
    } else
    {
        sb->append(term);
    }
    return sb;
}

vector<Expr*> JDatalog::reorderQuery(vector<Expr*>& query)
{
    vector<Expr*> ordered = vector<Expr*>(query.size());
    for(auto e : query)
    {
        if(!e->isNegated() && !(e->isBuiltIn() && !e->predicate.equals("=")))
        {
            ordered.push_back(e);
        }
    }
    // Note that a rule like s(A, B) :- r(A, B), X = Y, q(Y), A > X. will cause an error relating to both sides
    // of the '=' being unbound, and it can be fixed by moving the '=' operators to here, but I've decided against
    // it, because the '=' should be evaluated ASAP, and it is difficult to determine programatically when that is.
    // The onus is thus on the user to structure '=' operators properly.
    for(auto e : query)
    {
        if(e->isNegated() || (e->isBuiltIn() && !e->predicate.equals("=")))
        {
            ordered.push_back(e);
        }
    }
    return ordered;
}

JDatalog::Rule::Rule(Expr* head, vector<Expr*>& body)
{
    this->head = head;

    this->body = reorderQuery(body);
}

JDatalog::Rule::Rule(Expr* head, vector<Expr> &body) : Rule(head, Arrays::asList(body))
{
}

void JDatalog::Rule::validate() throw(DatalogException)
{

    Set<wstring>* headVars = head->terms.stream().filter([&] (any term)
    {
        isVariable(term);
    }).collect(Collectors::toSet());

    Set<wstring>* bodyVars = body.stream().flatMap([&] (any expr)
    {
        expr::terms::stream();
    }).filter([&] (any term)
    {
        isVariable(term);
    }).collect(Collectors::toSet());

    // Enforce the rule that variables in the head must appear in the body
    headVars->removeAll(bodyVars);
    if(!headVars->isEmpty())
    {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
        throw DatalogException("These variables from the head of rule " + toString() + " must appear in the body: " + JDatalog::toString(headVars));
    }

    // Check for /safety/: each variable in the body of a rule should appear at least once in a positive expression,
    // to prevent infinite results. E.g. p(X) :- not q(X, Y) is unsafe because there are an infinite number of values
    // for Y that satisfies `not q`. This is a requirement for negation - [gree] contains a nice description.
    // We also leave out variables from the built-in predicates because variables must be bound to be able to compare
    // them, i.e. a rule like `s(A, B) :- r(A,B), A > X` is invalid ('=' is an exception because it can bind variables)
    // You won't be able to tell if the variables have been bound to _numeric_ values until you actually evaluate the
    // expression, though.
    Set<wstring>* positiveVars = body.stream().flatMap([&] (any expr)
    {
        (!expr::isNegated() && !(expr::isBuiltIn() && !expr::predicate::equals("="))) ? expr::terms::stream() : java::util::stream::Stream::empty();
    }).filter([&] (any term)
    {
        isVariable(term);
    }).collect(Collectors::toSet());
    bodyVars->removeAll(positiveVars);
    if(!bodyVars->isEmpty())
    {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
        throw DatalogException("Each variable of rule " + toString() + " must appear in at least one positive expression: " + JDatalog::toString(bodyVars));
    }
}

wstring JDatalog::Rule::toString()
{
    StringBuilder* sb = new StringBuilder();
    sb->append(head);
    sb->append(" :- ");
    for(int i = 0; i < body.size(); i++)
    {
        sb->append(body[i]);
        if(i < body.size() - 1)
        {
            sb->append(", ");
        }
    }
    return sb->toString();
}

bool JDatalog::isVariable(const wstring& term)
{
    return isupper(term[0]);
}

JDatalog* JDatalog::rule(Expr* head, vector<Expr> &body) throw(DatalogException)
{
    Rule* newRule = new Rule(head, body);
    return rule(newRule);
}

JDatalog* JDatalog::rule(Rule* newRule) throw(DatalogException)
{
    newRule->validate();
    idb->add(newRule);
    return this;
}

JDatalog* JDatalog::fact(const wstring& predicate, vector<wstring> &terms) throw(DatalogException)
{
    Expr tempVar(predicate, terms);
    return fact(&tempVar);
}

JDatalog* JDatalog::fact(Expr* newFact) throw(DatalogException)
{
    if(!newFact->isGround())
    {
        throw DatalogException("Facts must be ground: " + newFact);
    }
    if(newFact->isNegated())
    {
        throw DatalogException("Facts cannot be negated: " + newFact);
    }
    // You can also match the arity of the fact against existing facts in the EDB,
    // but it's more of a principle than a technical problem; see JDatalog#validate()
    edb.push_back(newFact);
    return this;
}

void JDatalog::StandardQueryOutput::writeResult(vector<Expr*>& goals, Collection<unordered_map<wstring, wstring> >* answers) override
{
    Profiler::Timer* timer = Profiler::getTimer("output");
    try
    {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
        cout << JDatalog::toString(goals) << "?" << endl;
        if(!answers->isEmpty())
        {
            if(answers->begin()->next()->isEmpty())
            {
                cout << "  Yes." << endl;
            } else
            {
                for(auto answer : answers)
                {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
                    cout << "  " << JDatalog::toString(answer) << endl;
                }
            }
        } else
        {
            cout << "  No." << endl;
        }
    } finally
    {
        timer->stop();
    }
}

Collection<unordered_map<wstring, wstring> >* JDatalog::execute(Reader* reader, QueryOutput* output) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("execute");
    try
    {
        debug("Executing reader...");

        StreamTokenizer* scan = new StreamTokenizer(reader);
        scan->ordinaryChar('.'); // '.' looks like a number to StreamTokenizer by default
        scan->commentChar('%'); // Prolog-style % comments; slashSlashComments and slashStarComments can stay as well.
        scan->quoteChar('"');
        scan->quoteChar('\'');
        //scan.parseNumbers(); // WTF? You can't disable parsing of numbers unless you reset the syntax (http://stackoverflow.com/q/8856750/115589)
        scan->nextToken();

        // Tracks the last query's answers
        Collection<unordered_map<wstring, wstring> >* answers = nullptr;

        // Tracks the last query's goals (for output purposes)
        vector<Expr*> goals = vector<Expr*>();

        while(scan->ttype != StreamTokenizer::TT_EOF)
        {
            scan->pushBack();
            answers = parseStmt(scan, goals);
            if(answers != nullptr && output != nullptr)
            {
                output->writeResult(goals, answers);
            }
            scan->nextToken();
        }
        return answers;
    } catch(const IOException& e)
    {
        throw DatalogException(e);
    } finally
    {
        timer->stop();
    }
}

Collection<unordered_map<wstring, wstring> >* JDatalog::parseStmt(StreamTokenizer* scan, vector<Expr*>& goals) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("parseStmt");
    try
    {

        scan->nextToken();
        // "delete a(b,X)." deletes facts from the IDB that matches the query.
        // It is not standard Datalog AFAIK.
        if(scan->ttype == StreamTokenizer::TT_WORD && scan->sval.equalsIgnoreCase("delete"))
        {
            goals.clear();
            do
            {
                Expr* e = parseExpr(scan);
                goals.push_back(e);
            } while(scan->nextToken() == ',');
            if(scan->ttype != '.')
            {
                throw DatalogException("[line " + scan->lineno() + "] Expected '.' after 'delete'");
            }
            if(debugEnable)
            {
                cout << "Parser [line " << scan->lineno() << "]: Deleting goals: " << toString(goals) << endl;
            }
            delete(goals);
            return nullptr;
        } else
        {
            scan->pushBack();
        }

        Expr* head = parseExpr(scan);
        if(scan->nextToken() == ':')
        {
            // We're dealing with a rule
            if(scan->nextToken() != '-')
            {
                throw DatalogException("[line " + scan->lineno() + "] Expected ':-'");
            }
            vector<Expr*> body = vector<Expr*>();
            do
            {
                Expr* arg = parseExpr(scan);
                body.push_back(arg);
            } while(scan->nextToken() == ',');

            if(scan->ttype != '.')
            {
                throw DatalogException("[line " + scan->lineno() + "] Expected '.' after rule");
            }
            try
            {
                Rule* newRule = new Rule(head, body);
                rule(newRule);
                debug("Parser [line " + scan->lineno() + "]: Got rule: " + newRule);
            } catch(const DatalogException& de)
            {
                throw DatalogException("[line " + scan->lineno() + "] Rule is invalid", de);
            }
        } else
        {
            // We're dealing with a fact, or a query
            if(scan->ttype == '.')
            {
                // It's a fact
                try
                {
                    fact(head);
                    debug("Parser [line " + scan->lineno() + "]: Got fact: " + head);
                } catch(const DatalogException& de)
                {
                    throw DatalogException("[line " + scan->lineno() + "] Fact is invalid", de);
                }
            } else
            {
                // It's a query
                goals.clear();
                goals.push_back(head);
                if(scan->ttype != '.' && scan->ttype != '?' && scan->ttype != ',')
                {
                    /* You _can_ write facts like `a = 5 .` but I recommend against it; if you do then you *must* have the space between the
                    5 and the '.' otherwise the parser sees it as 5.0 and the error message can be a bit confusing. */
                    throw DatalogException("[line " + scan->lineno() + "] Expected one of '.', ',' or '?' after fact/query expression");
                }
                while(scan->ttype == ',')
                {
                    goals.push_back(parseExpr(scan));
                    scan->nextToken();
                }
                debug("Parser [line " + scan->lineno() + "]: Got query: " + toString(goals));

                if(scan->ttype == '?')
                {
                    try
                    {
                        return query(goals);
                    } catch(const DatalogException& e)
                    {
                        // Attach the line number to any exceptions thrown; the small drawback is that you lose
                        // the original stacktrace, but the line number is more important for users.
                        throw DatalogException("[line " + scan->lineno() + "] " + e->what());
                    }
                } else
                {
                    throw DatalogException("[line " + scan->lineno() + "] Expected '?' after query");
                }
            }
        }
    } catch(const IOException& e)
    {
        throw DatalogException(e);
    } finally
    {
        timer->stop();
    }
    return nullptr;
}

JDatalog::Expr* JDatalog::parseExpr(StreamTokenizer* scan) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("parseExpr");
    try
    {
        scan->nextToken();

        bool negated = false;
        if(scan->ttype == StreamTokenizer::TT_WORD && scan->sval.equalsIgnoreCase("not"))
        {
            negated = true;
            scan->nextToken();
        }

        wstring lhs = "";
        bool builtInExpected = false;
        if(scan->ttype == StreamTokenizer::TT_WORD)
        {
            lhs = scan->sval;
        } else if(scan->ttype == '"' || scan->ttype == '\'')
        {
            lhs = scan->sval;
            builtInExpected = true;
        } else if(scan->ttype == StreamTokenizer::TT_NUMBER)
        {
            lhs = numberToString(scan->nval);
            builtInExpected = true;
        } else
        {
            throw DatalogException("[line " + scan->lineno() + "] Predicate or start of expression expected");
        }

        scan->nextToken();
        if(scan->ttype == StreamTokenizer::TT_WORD || scan->ttype == '=' || scan->ttype == '!' || scan->ttype == '<' || scan->ttype == '>')
        {
            scan->pushBack();
            Expr* e = parseBuiltInPredicate(lhs, scan);
            e->negated = negated;
            debug("Got built-in predicate: " + e);
            return e;
        }

        if(builtInExpected)
        {
            // LHS was a number or a quoted string but we didn't get an operator
            throw DatalogException("[line " + scan->lineno() + "] Built-in predicate expected");
        } else if(scan->ttype != '(')
        {
            throw DatalogException("[line " + scan->lineno() + "] Expected '(' after predicate or an operator");
        }

        vector<wstring> terms = vector<wstring>();
        if(scan->nextToken() != ')')
        {
            scan->pushBack();
            do
            {
                if(scan->nextToken() == StreamTokenizer::TT_WORD)
                {
                    terms.push_back(scan->sval);
                } else if(scan->ttype == '"' || scan->ttype == '\'')
                {
                    terms.push_back("\"" + scan->sval);
                } else if(scan->ttype == StreamTokenizer::TT_NUMBER)
                {
                    terms.push_back(numberToString(scan->nval));
                } else
                {
                    throw DatalogException("[line " + scan->lineno() + "] Expected term in expression");
                }
            } while(scan->nextToken() == ',');
            if(scan->ttype != ')')
            {
                throw DatalogException("[line " + scan->lineno() + "] Expected ')'");
            }
        }
        Expr* e = new Expr(lhs, terms);
        e->negated = negated;
        return e;
    } catch(const IOException& e)
    {
        throw DatalogException(e);
    } finally
    {
        timer->stop();
    }
}

const vector<wstring> JDatalog::validOperators = java::util::Arrays::asList(std::vector<wstring> { "=", "!=", "<>", "<", "<=", ">", ">=" });

JDatalog::Expr* JDatalog::parseBuiltInPredicate(const wstring& lhs, StreamTokenizer* scan) throw(DatalogException)
{
    try
    {
        wstring operator_RenamedTODO;
        scan->nextToken();
        if(scan->ttype == StreamTokenizer::TT_WORD)
        {
            // At some point I was going to have "eq" and "ne" for string comparisons, but it wasn't a good idea.
            operator_RenamedTODO = scan->sval;
        } else
        {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
            operator_RenamedTODO = Character::toString(static_cast<char>(scan->ttype));
            scan->nextToken();
            if(scan->ttype == '=' || scan->ttype == '>')
            {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
                operator_RenamedTODO = operator_RenamedTODO + Character::toString(static_cast<char>(scan->ttype));
            } else
            {
                scan->pushBack();
            }
        }

        if(!find(validOperators.begin(), validOperators.end(), operator_RenamedTODO) != validOperators.end())
        {
            throw DatalogException("Invalid operator '" + operator_RenamedTODO + "'");
        }

        wstring rhs = "";
        scan->nextToken();
        if(scan->ttype == StreamTokenizer::TT_WORD)
        {
            rhs = scan->sval;
        } else if(scan->ttype == '"' || scan->ttype == '\'')
        {
            rhs = scan->sval;
        } else if(scan->ttype == StreamTokenizer::TT_NUMBER)
        {
            rhs = numberToString(scan->nval);
        } else
        {
            throw DatalogException("[line " + scan->lineno() + "] Right hand side of expression expected");
        }

        return new Expr(operator_RenamedTODO, lhs, rhs);

    } catch(const IOException& e)
    {
        throw DatalogException(e);
    }
}

wstring JDatalog::numberToString(const double& nval)
{
    // Remove trailing zeros; http://stackoverflow.com/a/14126736/115589
    if(nval == static_cast<long long>(nval))
    {
        return wstring::format("%d",static_cast<long long>(nval));
    } else
    {
        return StringHelper::formatSimple("%s",nval);
    }
}

java::util::regex::Pattern* const  JDatalog::numberPattern = java::util::regex::Pattern::compile("[+-]?\\d+(\\.\\d*)?([Ee][+-]?\\d+)?");

bool JDatalog::tryParseDouble(const wstring& str)
{
    return numberPattern->matcher(str).matches();
}

JDatalog::DatalogException::DatalogException(const wstring& message) : Exception(message)
{
}

JDatalog::DatalogException::DatalogException(exception cause) : Exception(cause)
{
}

JDatalog::DatalogException::DatalogException(const wstring& message, exception cause) : Exception(message, cause)
{
}

Collection<unordered_map<wstring, wstring> >* JDatalog::query(const wstring& statement) throw(DatalogException)
{
    // It would've been fun to wrap the results in a java.sql.ResultSet, but damn,
    // those are a lot of methods to implement:
    // https://docs.oracle.com/javase/8/docs/api/java/sql/ResultSet.html
    StringReader* reader = new StringReader(statement);
    return execute(reader, nullptr);
}

Collection<unordered_map<wstring, wstring> >* JDatalog::query(vector<Expr> &goals) throw(DatalogException)
{
    return query(Arrays::asList(goals));
}

Collection<unordered_map<wstring, wstring> >* JDatalog::query(vector<Expr*>& goals) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("query");
    try
    {
        if(goals.empty())
        {
            return Collections::emptyList();
        }

        // Reorganize the goals so that negated literals are at the end.
        vector<Expr*> orderedGoals = reorderQuery(goals);

        // getRelevantRules() strips a large part of the rules, so if I want to
        // do some benchmarking of buildDatabase(), I use the IDB directly instead:
        // Collection<Rule> rules = idb;
        Collection<Rule*>* rules = getRelevantRules(goals);
        if(debugEnable)
        {
            cout << "To answer query, we need to evaluate: " << toString(rules) << endl;
        }

        // Build the database. A Set ensures that the facts are unique
        Collection<Expr*>* dataset = buildDatabase(unordered_set<Expr*>(edb), rules);
        if(debugEnable)
        {
            cout << "query(): Database = " << toString(dataset) << endl;
        }
        return matchGoals(orderedGoals, dataset, nullptr);
    } finally
    {
        timer->stop();
    }
}

Collection<Rule*>* JDatalog::getRelevantRules(vector<Expr*>& originalGoals)
{
    Profiler::Timer* timer = Profiler::getTimer("getRelevantRules");
    try
    {
        Collection<Rule*>* relevant = unordered_set<Rule*>();
        list<Expr*> goals = list<Expr*>(originalGoals);
        while(!goals.empty())
        {
            Expr* expr = goals.pop_front();
            for(auto rule : idb)
            {
                if(rule->head->predicate.equals(expr->predicate) && !relevant->contains(rule))
                {
                    relevant->add(rule);
                    goals.addAll(rule->body);
                }
            }
        }
        return relevant;
    } finally
    {
        timer->stop();
    }
}

unordered_map<wstring, Collection<Rule*>*> JDatalog::buildDependantRules(Collection<Rule*>* rules)
{
    Profiler::Timer* timer = Profiler::getTimer("buildDependantRules");
    try
    {
        unordered_map<wstring, Collection<Rule*>*> map = unordered_map<wstring, Collection<Rule*>*>();
        for(auto rule : rules)
        {
            for(auto goal : rule->body)
            {
                Collection<Rule*>* dependants = map[goal->predicate];
                if(dependants == nullptr)
                {
                    dependants = vector<>();
                    map.emplace(goal->predicate, dependants);
                }
                if(!dependants->contains(rule))
                {
                    dependants->add(rule);
                }
            }
        }
        return map;
    } finally
    {
        timer->stop();
    }
}

Collection<Rule*>* JDatalog::getDependantRules(Collection<Expr*>* facts, unordered_map<wstring, Collection<Rule*>*>& dependants)
{
    Profiler::Timer* timer = Profiler::getTimer("getDependantRules");
    try
    {
        Set<Rule*>* dependantRules = unordered_set<Rule*>();
        for(auto fact : facts)
        {
            Collection<Rule*>* rules = dependants[fact->predicate];
            if(rules != nullptr)
            {
                dependantRules->addAll(rules);
            }
        }
        return dependantRules;
    } finally
    {
        timer->stop();
    }
}

Collection<Expr*>* JDatalog::buildDatabase(Set<Expr*>* facts, Collection<Rule*>* allRules) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("buildDatabase");
    try
    {
        vector<Collection<Rule*>*> strata = computeStratification(allRules);
        for(int i = 0; i < strata.size(); i++)
        {
            debug("Expanding strata " + to_string(i));
            Collection<Rule*>* rules = strata[i];
            if(rules != nullptr && !rules->isEmpty())
            {
                expandStrata(facts, rules);
            }
        }
        return facts;
    } finally
    {
        timer->stop();
    }
}

vector<Collection<Rule*>*> JDatalog::computeStratification(Collection<Rule*>* allRules) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("computeStratification");
    try
    {
        vector<Collection<Rule*>*> strata = vector<Collection<Rule*>*>(10);

        unordered_map<wstring, int> strats = unordered_map<wstring, int>();
        for(auto rule : allRules)
        {
            wstring pred = rule->head->predicate;
            optional<int> stratum = strats[pred];
            if(!stratum)
            {
                stratum = depthFirstSearch(rule->head, allRules, vector<>(), 0);
                strats.emplace(pred, stratum);
                if(debugEnable)
                {
                    cout << "Strata{" << pred << "} == " << strats[pred] << endl;
                }
            }

            while(stratum >= strata.size())
            {
                strata.push_back(vector<>());
            }
            strata[stratum]->add(rule);
        }

        strata.push_back(allRules);
        return strata;
    } finally
    {
        timer->stop();
    }
}

int JDatalog::depthFirstSearch(Expr* goal, Collection<Rule*>* graph, vector<Expr*>& visited, const int& level) throw(DatalogException)
{
    wstring pred = goal->predicate;

    // Step (1): Guard against negative recursion
    bool negated = goal->isNegated();
    StringBuilder* route = new StringBuilder(pred); // for error reporting
    for(int i = visited.size() - 1; i >= 0; i--)
    {
        Expr* e = visited[i];
        route->append(e->isNegated() ? " <- ~" : " <- ")->append(e->predicate);
        if(e->predicate.equals(pred))
        {
            if(negated)
            {
                throw DatalogException("Program is not stratified - predicate " + pred + " has a negative recursion: " + route);
            }
            return 0;
        }
        if(e->isNegated())
        {
            negated = true;
        }
    }
    visited.push_back(goal);

    // Step (2): Do the actual depth-first search to compute the strata
    int m = 0;
    for(auto rule : graph)
    {
        if(rule->head->predicate.equals(pred))
        {
            for(auto expr : rule->body)
            {
                int x = depthFirstSearch(expr, graph, visited, level + 1);
                if(expr->negated)
                {
                    x++;
                }
                if(x > m)
                {
                    m = x;
                }
            }
        }
    }
    visited.pop_back();

    return m;
}

Collection<Expr*>* JDatalog::expandStrata(Set<Expr*>* facts, Collection<Rule*>* strataRules) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("expandStrata");
    try
    {
        Collection<Rule*>* rules = strataRules;

        unordered_map<wstring, Collection<Rule*>*> dependants = buildDependantRules(strataRules);

        while(true)
        {
            Profiler::Timer* loopTimer = Profiler::getTimer("loopTimer");
            try
            {

                // Match each rule to the facts
                Profiler::Timer* matchRuleTimer = Profiler::getTimer("matchRules");
                Set<Expr*>* newFacts = unordered_set<Expr*>();
                for(auto rule : rules)
                {
                    newFacts->addAll(matchRule(facts, rule));
                }
                matchRuleTimer->stop();

                // Delta facts: The new facts that have been added in this iteration for semi-naive evaluation.
                Profiler::Timer* deltaFactsTimer = Profiler::getTimer("deltaFacts");
                newFacts->removeAll(facts);
                deltaFactsTimer->stop();

                // Repeat until there are no more facts added
                if(newFacts->isEmpty())
                {
                    return facts;
                }
                if(debugEnable)
                {
                    cout << "expandStrata(): deltaFacts = " << toString(newFacts) << endl;
                }

                rules = getDependantRules(newFacts, dependants);

                Profiler::Timer* addAllTimer = Profiler::getTimer("addAll");
                facts->addAll(newFacts);
                addAllTimer->stop();

            } finally
            {
                loopTimer->stop();
            }
        }
    } finally
    {
        timer->stop();
    }
}

Set<Expr*>* JDatalog::matchRule(Collection<Expr*>* const facts, Rule* rule) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("matchRule");
    try
    {
        if(rule->body.empty()) // If this happens, you're using the API wrong.
        {
            return Collections::emptySet();
        }

        // Match the rule body to the facts.
        Collection<unordered_map<wstring, wstring> >* answers = matchGoals(rule->body, facts, nullptr);

        // For each match found, substitute the bindings into the head to create a new fact.
        Set<Expr*>* results = unordered_set<Expr*>();
        for(auto answer : answers)
        {
            results->add(rule->head->substitute(answer));
        }
        return results;
    } finally
    {
        timer->stop();
    }
}

Collection<unordered_map<wstring, wstring> >* JDatalog::matchGoals(vector<Expr*>& goals, Collection<Expr*>* const facts, unordered_map<wstring, wstring>& bindings) throw(DatalogException)
{

    Expr* goal = goals[0]; // First goal; Assumes goals won't be empty

    bool lastGoal = (goals.size() == 1);

    if(goal->isBuiltIn())
    {
        unordered_map<wstring, wstring> newBindings = new StackMap<wstring, wstring>(bindings);
        bool eval = goal->evalBuiltIn(newBindings);
        if(eval && !goal->isNegated() || !eval && goal->isNegated())
        {
            if(lastGoal)
            {
                if(debugEnable)
                {
                    cout << "** (+) Goal: " << goal << "; " << newBindings << endl;
                }
                return Collections::singletonList(newBindings);
            } else
            {
                return matchGoals(goals.subList(1, goals.size()), facts, newBindings);
            }
        }
        return Collections::emptyList();
    }

    Collection<unordered_map<wstring, wstring> >* answers = vector<unordered_map<wstring, wstring> >();
    if(!goal->isNegated())
    {
        // Positive rule: Match each fact to the first goal.
        // If the fact matches: If it is the last/only goal then we can return the bindings
        // as an answer, otherwise we recursively check the remaining goals.
        for(auto fact : facts)
        {
            if(!fact->predicate.equals(goal->predicate))
            {
                continue;
            }
            unordered_map<wstring, wstring> newBindings = new StackMap<wstring, wstring>(bindings);
            if(fact->unify(goal, newBindings))
            {
                if(lastGoal)
                {
                    if(debugEnable)
                    {
                        cout << "** (+) Goal: " << goal << "; " << newBindings << endl;
                    }
                    answers->add(newBindings);
                } else
                {
                    // More goals to match. Recurse with the remaining goals.
                    answers->addAll(matchGoals(goals.subList(1, goals.size()), facts, newBindings));
                }
            }
        }
    } else
    {
        // Negated rule: If you find any fact that matches the goal, then the goal is false.
        // See definition 4.3.2 of [bra2] and section VI-B of [ceri].
        // Substitute the bindings in the rule first.
        // If your rule is `und(X) :- stud(X), not grad(X)` and you're at the `not grad` part, and in the
        // previous goal stud(a) was true, then bindings now contains X:a so we want to search the database
        // for the fact grad(a).
        if(bindings.size() > 0)
        {
            goal = goal->substitute(bindings);
        }
        for(auto fact : facts)
        {
            if(!fact->predicate.equals(goal->predicate))
            {
                continue;
            }
            unordered_map<wstring, wstring> newBindings = new StackMap<wstring, wstring>(bindings);
            if(fact->unify(goal, newBindings))
            {
                return Collections::emptyList();
            }
        }
        // not found
        if(debugEnable)
        {
            cout << "** (-) Goal: " << goal << "; " << bindings << endl;
        }
        if(lastGoal)
        {
            answers->add(bindings);
        } else
        {
            answers->addAll(matchGoals(goals.subList(1, goals.size()), facts, bindings));
        }
    }
    return answers;
}

bool JDatalog::delete_RenamedTODO(vector<Expr> &facts) throw(DatalogException)
{
    return delete({ Arrays::asList(facts) });
}

bool JDatalog::delete_RenamedTODO(vector<Expr*>& goals) throw(DatalogException)
{
    Profiler::Timer* timer = Profiler::getTimer("delete");
    try
    {
        Collection<unordered_map<wstring, wstring> >* answers = query(goals);
        vector<Expr*> facts = answers->stream().flatMap([&] (any answer)
        {
            goals.stream().map([&] (any goal)
            {
                goal::substitute(answer);
            });
        }).collect(Collectors::toList());
            // and substitute the answer on each goal
        if(debugEnable)
        {
            cout << "Facts to delete: " << toString(facts) << endl;
        }
        return edb.removeAll(facts);
    } finally
    {
        timer->stop();
    }
}

void JDatalog::validate() throw(DatalogException)
{
    for(auto rule : idb)
    {
        rule->validate();
    }

    // Search for negated loops:
    computeStratification(idb);

    for(int i = 0; i < edb.size(); i++)
    {
        Expr* fact = edb[i];
        if(!fact->isGround())
        {
            throw DatalogException("Fact " + fact + " is not ground");
        } else if(fact->isNegated())
        {
            throw DatalogException("Fact " + fact + " is negated");
        }
        // else if(fact.isBuiltIn()) // I allow facts like `a = 5` or `=(a,5)`

        for(int j = i + 1; j < edb.size(); j++)
        {
            Expr* that = edb[j];
            if(fact->predicate.equals(that->predicate))
            {
                if(fact->arity() != that->arity())
                {
                    // Technically we don't really require the arity of two facts to be the same if they have the same
                    // predicate, since they simply won't unify with the goals in the queries.
                    throw DatalogException("Arity mismatch in EDB: " + fact->predicate + "/" + to_string(fact->arity()) + " vs " + that->predicate + "/" + to_string(that->arity()));
                }
            }
        }
    }
}

void JDatalog::dump(PrintStream* out) throw(DatalogException)
{
    out->println("% Facts:");
    for(auto fact : edb)
    {
        out->println(fact + ".");
    }
    out->println("\n% Rules:");
    for(auto rule : idb)
    {
        out->println(rule + ".");
    }
}

void JDatalog::debug(const wstring& message)
{
    // I'm not happy with this. Remove later.
    if(debugEnable)
    {
        cout << message << endl;
    }
}

template<typename T1>
wstring JDatalog::toString(Collection<T1>* collection)
{
    StringBuilder* sb = new StringBuilder("[");
    for(auto o : collection)
    {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
        sb->append(o.toString())->append(". ");
    }
    sb->append("]");
    return sb->toString();
}

wstring JDatalog::toString(unordered_map<wstring, wstring>& bindings)
{
    StringBuilder* sb = new StringBuilder("{");
    int s = bindings.size(), i = 0;
    for(auto k : bindings)
    {
        wstring v = bindings[k.first];
        sb->append(k.first)->append(": ");
        if(StringHelper::startsWith(v, "\""))
        {
            // Needs more org.apache.commons.lang3.StringEscapeUtils#escapeJava(String)
            sb->append('"')->append(v.substr(1)->replaceAll("\"", "\\\\\""))->append("\"");
        } else
        {
            sb->append(v);
        }
        if(++i < s)
        {
            sb->append(", ");
        }
    }
    sb->append("}");
    return sb->toString();
}

void JDatalog::main(vector<wstring> &args)
{

     if(args->length > 0)
     {
        // Read input from a file...
        try
        {

            if(BENCHMARK)
            {
                // Execute the program a couple of times without output
                // to "warm up" the JVM for profiling.
                for(int run = 0; run < 5; run++)
                {
                    cout << "" << (5 - run) << "...";
                    JDatalog* jDatalog = new JDatalog();
                    for(wstring arg : args)
                    {
//JAVA TO C++ CONVERTER NOTE: The following 'try with resources' block is replaced by its C++ equivalent:
//ORIGINAL LINE: try(java.io.Reader reader = new java.io.BufferedReader(new java.io.FileReader(arg)))
                        {
                            java::io::FileReader tempVar(arg);
                        java::io::Reader* reader = new java::io::BufferedReader(&tempVar);
                            jDatalog->execute(reader, nullptr);
                        delete reader;
                        }
                    }
                }
                Profiler::reset();
                System::gc();
                System::runFinalization();
                cout << endl;

                QueryOutput* qo = new StandardQueryOutput();
                for(int run = 0; run < NUM_RUNS; run++)
                {

                    JDatalog* jDatalog = new JDatalog();

                    for(wstring arg : args)
                    {
                        debug("Executing file " + arg);
//JAVA TO C++ CONVERTER NOTE: The following 'try with resources' block is replaced by its C++ equivalent:
//ORIGINAL LINE: try(java.io.Reader reader = new java.io.BufferedReader(new java.io.FileReader(arg)))
                        {
                            java::io::FileReader tempVar2(arg);
                        java::io::Reader* reader = new java::io::BufferedReader(&tempVar2);
                            jDatalog->execute(reader, qo);
                        delete reader;
                        }
                    }
                }

                cout << "Profile for running " << toString(Arrays::asList(args)) << "; NUM_RUNS=" << NUM_RUNS << endl;
                Profiler::keySet()->stream().sorted().forEach([&] (any key)
                {
                    double time = Profiler::average(key);
                    double total = Profiler::total(key);
                    int count = Profiler::count(key);
                    cout << wstring::format("%-20s time: %10.4fms; total: %12.2fms; count: %d", key, time, total, count) << endl;
                });
            } else
            {
                JDatalog* jDatalog = new JDatalog();
                QueryOutput* qo = new StandardQueryOutput();
                for(wstring arg : args)
                {
                    debug("Executing file " + arg);
//JAVA TO C++ CONVERTER NOTE: The following 'try with resources' block is replaced by its C++ equivalent:
//ORIGINAL LINE: try(java.io.Reader reader = new java.io.BufferedReader(new java.io.FileReader(arg)))
                    {
                        java::io::FileReader tempVar3(arg);
                    java::io::Reader* reader = new java::io::BufferedReader(&tempVar3);
                        jDatalog->execute(reader, qo);
                    delete reader;
                    }
                }
            }

        }
//JAVA TO C++ CONVERTER TODO TASK: There is no equivalent in C++ to Java 'multi-catch' syntax:
        catch(DatalogException | IOException e)
        {
            e::printStackTrace();
        }
     } else
     {
        // Get input from command line
        JDatalog* jDatalog = new JDatalog();
        InputStreamReader tempVar4(System::in);
        BufferedReader* buffer = new BufferedReader(&tempVar4);
        cout << "JDatalog: Java Datalog engine\nInteractive mode; type 'exit' to quit." << endl;
        while(true)
        {
            try
            {
                cout << "> ";
                wstring line = buffer->readLine();
                if(line == "")
                {
                    break; // EOF
                }
                line = StringHelper::trim(line);
                if(line.equalsIgnoreCase("exit"))
                {
                    break;
                } else if(line.equalsIgnoreCase("dump"))
                {
                    jDatalog->dump(System::out);
                    continue;
                } else if(line.equalsIgnoreCase("validate"))
                {
                    jDatalog->validate();
                    cout << "OK." << endl; // exception not thrown
                    continue;
                }

                Collection<unordered_map<wstring, wstring> >* answers = jDatalog->query(line);

                // If `answers` is null, the line passed to `jDatalog.query(line)` was a statement that didn't
                //      produce any results, like a fact or a rule, rather than a query.
                // If `answers` is empty, then it was a query that doesn't have any answers, so the output is "No."
                // If `answers` is a list of empty maps, then it was the type of query that only wanted a yes/no
                //      answer, like `siblings(alice,bob)?` and the answer is "Yes."
                // Otherwise `answers` is a list of all bindings that satisfy the query.
                if(answers != nullptr)
                {
                    if(!answers->isEmpty())
                    {
                        if(answers->begin()->next()->isEmpty())
                        {
                            cout << "Yes." << endl;
                        } else
                        {
                            for(auto answer : answers)
                            {
//JAVA TO C++ CONVERTER TODO TASK: There is no native C++ equivalent to 'toString':
                                cout << JDatalog::toString(answer) << endl;
                            }
                        }
                    } else
                    {
                        cout << "No." << endl;
                    }
                }

            }
//JAVA TO C++ CONVERTER TODO TASK: There is no equivalent in C++ to Java 'multi-catch' syntax:
            catch(DatalogException | IOException e)
            {
                e::printStackTrace();
            }
        }
    }

    /* //This is how you would use the fluent API:
    try {
        JDatalog jDatalog = new JDatalog();
        jDatalog.fact("parent", "a", "aa")
            .fact("parent", "a", "ab")
            .fact("parent", "aa", "aaa")
            .fact("parent", "aa", "aab")
            .fact("parent", "aaa", "aaaa")
            .fact("parent", "c", "ca");
        jDatalog.rule(new Expr("ancestor", "X", "Y"), new Expr("parent", "X", "Z"), new Expr("ancestor", "Z", "Y"))
            .rule(new Expr("ancestor", "X", "Y"), new Expr("parent", "X", "Y"))
            .rule(new Expr("sibling", "X", "Y"), new Expr("parent", "Z", "X"), new Expr("parent", "Z", "Y"), new Expr("!=", "X", "Y"))
            .rule(new Expr("related", "X", "Y"), new Expr("ancestor", "Z", "X"), new Expr("ancestor", "Z", "Y"));
        Collection<Map<String, String>> answers;
        // Run a query "who are siblings?"; print the answers
        answers = jDatalog.query(new Expr("sibling", "A", "B"));
        System.out.println("Siblings:");
        answers.stream().forEach(answer -> System.out.println(" -> " + toString(answer)));
        // Run a query "who are aa's descendants?"; print the answers
        answers = jDatalog.query(new Expr("ancestor", "aa", "X"));
        System.out.println("Descendants:");
        answers.stream().forEach(answer -> System.out.println(" -> " + toString(answer)));
        // This demonstrates how you would use a built-in predicate in the fluent API.
        System.out.println("Built-in predicates:");
        answers = jDatalog.query(new Expr("parent", "aa", "A"), new Expr("parent", "aa", "B"), new Expr("!=", "A", "B"));
        answers.stream().forEach(answer -> System.out.println(" -> " + toString(answer)));
        System.out.println("Before Deletion: " + toString(jDatalog.edb));
        jDatalog.delete(new Expr("parent", "aa", "X"), new Expr("parent", "X", "aaaa")); // deletes parent(aa,aaa) and parent(aaa,aaaa)
        System.out.println("After Deletion: " + toString(jDatalog.edb));
        // "who are aa's descendants now?"
        answers = jDatalog.query(new Expr("ancestor", "aa", "X"));
        System.out.println("Descendants:");
        answers.stream().forEach(answer -> System.out.println(" -> " + toString(answer)));
    } catch (DatalogException e) {
        e.printStackTrace();
    } */

    /* // The JDatalog.query(String) method runs queries directly.
    try{
        JDatalog jDatalog = new JDatalog();
        jDatalog.query("foo(bar). foo(baz).");
        Collection<Map<String, String>> answers = jDatalog.query("foo(What)?");
        answers.stream().forEach(answer -> System.out.println(" -> " + toString(answer)));
    } catch (DatalogException e) {
        e.printStackTrace();
    } */

}

JDatalog::Profiler::Timer::Timer(vector<long long>& bucket)
{
    start = System::currentTimeMillis();
    this->bucket = bucket;
}

long long JDatalog::Profiler::Timer::stop()
{
    long long elapsed = (System::currentTimeMillis() - start);
    bucket.push_back(elapsed);
    return elapsed;
}

Profiler* JDatalog::Profiler::instance;

JDatalog::Profiler::Profiler()
{
    buckets = new ConcurrentHashMap<wstring, vector<long long> >();
}

Profiler* JDatalog::Profiler::getInstance()
{
    if(instance == nullptr)
    {
        instance = new Profiler();
    }
    return instance;
}

void JDatalog::Profiler::reset()
{
    getInstance()->buckets.clear();
}

JDatalog::Profiler::Timer* JDatalog::Profiler::getTimer(const wstring& name)
{
    vector<long long> bucket = getInstance()->getBucket(name);
    return new Timer(bucket);
}

vector<long long> JDatalog::Profiler::getBucket(const wstring& name)
{
    if(buckets.find(name) == buckets.end())
    {
        vector<long long> list = Collections::synchronizedList(vector<long long>(NUM_RUNS));
        buckets.try_emplace(name, list);
    }
    return buckets[name];
}

double JDatalog::Profiler::average(const wstring& name)
{
    vector<long long> times = getInstance()->getBucket(name);
    if(times.empty())
    {
        return 0;
    }
    {
lock_guard<mutex> lock(times);
        long long sum = 0;
        for(* : :optional<long long> time : times)
        {
            sum += time;
        }
        return static_cast<double>(sum) / times.size();
    }
}

long long JDatalog::Profiler::total(const wstring& name)
{
    vector<long long> times = getInstance()->getBucket(name);
    long long sum = 0;
    {
lock_guard<mutex> lock(times);
        for(* : :optional<long long> time : times)
        {
            sum += time;
        }
    }
    return sum;
}

int JDatalog::Profiler::count(const wstring& name)
{
    return getInstance()->getBucket(name).size();
}

double JDatalog::Profiler::stdDev(const wstring& name)
{
    // I'm sure I'm going to be really embarrased when I figure out
    // why the stdDev looks so strange...
    vector<long long> times = getInstance()->getBucket(name);
    {
lock_guard<mutex> lock(times);
        double avg = average(name);
        double sumSq = 0.0;
        for(* : :optional<long long> time : times)
        {
            sumSq += (time - avg) * (time - avg);
        }
        double variance = sumSq / times.size();
        return sqrt(variance);
    }
}

Set<wstring>* JDatalog::Profiler::keySet()
{
    return getInstance()->buckets.keySet();
}