package nova;

import java.util.*;

/**
 * Warranty & Liability
 * To the extent permitted by applicable law and unless explicitly
 * otherwise agreed upon, XLOG Technologies AG makes no warranties
 * regarding the provided information. XLOG Technologies AG assumes
 * no liability that any problems might be solved with the information
 * provided by XLOG Technologies AG.
 * 
 * Rights & License
 * All industrial property rights regarding the information - copyright
 * and patent rights in particular - are the sole property of XLOG
 * Technologies AG. If the company was not the originator of some
 * excerpts, XLOG Technologies AG has at least obtained the right to
 * reproduce, change and translate the information.
 * 
 * Reproduction is restricted to the whole unaltered document. Reproduction
 * of the information is only allowed for non-commercial uses. Selling,
 * giving away or letting of the execution of the library is prohibited.
 * The library can be distributed as part of your applications and libraries
 * for execution provided this comment remains unchanged.
 * 
 * Restrictions
 * Only to be distributed with programs that add significant and primary
 * functionality to the library. Not to be distributed with additional
 * software intended to replace any components of the library.
 * 
 * Trademarks
 * Jekejeke is a registered trademark of XLOG Technologies AG.
 */
public final class Store {
    public static final int UNDEF_INT = -2;
    public static final Object UNDEF_OBJ = new Object();

    public static final int MASK_PRED_PREHASH = 0x00000010;
    public static final int MASK_PRED_ARITH = 0x00000008;
    public static final int MASK_PRED_SPECIAL = 0x00000004;
    public static final int MASK_PRED_TEST = 0x00000002;
    public static final int MASK_PRED_DYNAMIC = 0x00000001;

    public static final int MASK_TOUCH_PREHASH = 0x00000004;
    public static final int MASK_TOUCH_BOTTOM = 0x00000002;
    public static final int MASK_TOUCH_DYNAMIC = 0x00000001;

    public static final int MASK_REMOVE_REVERSE = 0x00000001;

    public static final int VAR_MASK_SEEN = 0x40000000;
    public static final int VAR_MASK_EVEN = 0x20000000;
    public static final int VAR_MASK_ODD = 0x10000000;
    public static final int VAR_MASK_STATE = VAR_MASK_EVEN | VAR_MASK_ODD;
    public static final int VAR_MASK_BITS = 28;
    public static final int VAR_MASK_SERNO = (1 << VAR_MASK_BITS) - 1;

    public static Map kb = new HashMap();
    public static int stage = -1;

    public static final int MAX_INDEX = 2;
    private static final int ROPE_LOW = 24;
    private static final int ROPE_HIGH = 40;
    private static final int BOUQUET_LOW = 12;
    private static final int BOUQUET_HIGH = 20;

    /**
     * Set the clause and predicate current stage.
     *
     * @param num The current stage.
     */
    public static void set_stage(int num) {
        stage = num;
    }

    /**
     * Set the clause current partition.
     *
     * @param path The current partition.
     */
    public static void set_partition(String path) {
        engine.partition = path;
    }

    /**************************************************************/
    /* Engine                                                     */
    /**************************************************************/

    public static final class Engine {
        public Object signal;
        public Runnable abort;
        public int flags;
        public runtime.Sink text_output;
        public runtime.Sink text_error;
        public runtime.Source text_input;
        public int low;
        public int high;
        public int serno;
        public Variable backtrail;
        public String partition;

        /**
         * Create a slow state engine.
         */
        public Engine() {
            this.signal = UNDEF_OBJ;
            this.abort = () -> { };
            this.flags = 0;
            this.text_output = null;
            this.text_error = null;
            this.text_input = null;
            this.low = 0;
            this.high = 0;
            this.serno = 0;
            this.backtrail = null;
            this.partition = (stage == -1 ? "system" : "user");
        }

    }

    public static Engine engine = new Engine();

    public static void set_engine(Engine ptr) {
        engine = ptr;
    }

    /**************************************************************/
    /* Variable & Compound                                        */

    /**************************************************************/

    public static final class Variable {
        public Object instantiated;
        public int flags;
        public Object tail;

        /**
         * Create a Prolog variable.
         */
        public Variable() {
            this.instantiated = UNDEF_OBJ;
            this.flags = VAR_MASK_SERNO;
            this.tail = null;
        }

    }

    /**
     * Check whether an object is a Prolog variable.
     *
     * @param obj The object.
     * @return boolean True if the object is a variable, otherwise false.
     */
    public static boolean is_variable(Object obj) {
        return obj instanceof Variable;
    }

    /**
     * Compute a variable serno.
     *
     * @param alpha The variable.
     * @return The serno.
     */
    public static int variable_serno(Variable alpha) {
        int val = alpha.flags & VAR_MASK_SERNO;
        if (val == VAR_MASK_SERNO) {
            if (engine.low < engine.high) {
                val = engine.low;
                engine.low = val + 1;
            } else {
                val = engine.serno;
                engine.serno = val + 1;
            }
            alpha.flags &= ~VAR_MASK_SERNO;
            alpha.flags |= val;
        }
        return val;
    }

    public static class Element {
        public Object functor;
        public Object[] args;

        /**
         * Create an element.
         *
         * @param functor The functor.
         * @param args    The arguments.
         */
        public Element(Object functor, Object[] args) {
            this.functor = functor;
            this.args = args;
        }

    }

    /**
     * Check whether an object is an element.
     *
     * @param obj The object.
     * @return True if the object is an element, otherwise false.
     */
    public static boolean is_element(Object obj) {
        return obj instanceof Element;
    }

    public static class Structure extends Element {

        /**
         * Create a Prolog structure.
         *
         * @param functor The functor.
         * @param args    The arguments.
         */
        public Structure(Object functor, Object[] args) {
            super(functor, args);
        }

    }

    /**
     * Check whether an object is a Prolog structure.
     *
     * @param obj The object.
     * @return True if the object is a compound, otherwise false.
     */
    public static boolean is_structure(Object obj) {
        return obj instanceof Structure;
    }

    public static final class Compound extends Structure {
        public int walk;

        /**
         * Create a Prolog compound.
         *
         * @param functor The functor.
         * @param args    The arguments.
         */
        public Compound(Object functor, Object[] args) {
            super(functor, args);
            this.walk = 0;
        }

    }

    /**
     * Check whether an object is a Prolog compound.
     *
     * @param obj The object.
     * @return True if the object is a compound, otherwise false.
     */
    public static boolean is_compound(Object obj) {
        return obj instanceof Compound;
    }

    /**************************************************************/
    /* Place & Skeleton                                           */
    /**************************************************************/

    public static final class Place {
        public final int index;

        /**
         * Create a Albufeira Code place.
         */
        public Place(int index) {
            this.index = index;
        }

    }

    /**
     * Check whether an object is a place.
     *
     * @param obj The object.
     * @return boolean True if the object is a place, otherwise false.
     */
    public static boolean is_place(Object obj) {
        return obj instanceof Place;
    }

    public static final class Skeleton extends Element {

        /**
         * Create a Albufeira Code skeleton.
         *
         * @param functor The functor.
         * @param args    The arguments.
         */
        public Skeleton(Object functor, Object[] args) {
            super(functor, args);
        }

    }

    /**
     * Check whether an object is a skeleton.
     *
     * @param obj The object.
     * @return boolean True if the object is a skeleton, otherwise false.
     */
    public static boolean is_skeleton(Object obj) {
        return obj instanceof Skeleton;
    }

    /**************************************************************/
    /* deref() and copy_term()                                    */
    /**************************************************************/

    /**
     * Dereference a Prolog term.
     *
     * @param term The Prolog term.
     * @return any The dereferenced Prolog term.
     */
    public static Object deref(Object term) {
        while (is_variable(term) &&
                ((Variable) term).instantiated != UNDEF_OBJ)
            term = ((Variable) term).instantiated;
        return term;
    }

    /**
     * Copy a Prolog term.
     * Can handle cyclic terms and deep recursion.
     *
     * @param first The Prolog term.
     * @return The copy.
     */
    public static Object copy_term(Object first) {
        Object res;
        try {
            res = walk_copy(first);
        } finally {
            walk_uncopy(first);
        }
        return res;
    }

    private static Object walk_copy(Object first) {
        List stack = null;
        for (; ; ) {
            first = Store.deref(first);
            if (Store.is_variable(first)) {
                if (((Store.Variable) first).tail == null) {
                    Store.Variable peek = new Store.Variable();
                    ((Store.Variable) first).tail = peek;
                    first = peek;
                } else {
                    first = ((Store.Variable) first).tail;
                }
            } else if (Store.is_compound(first)) {
                if (!Store.is_compound(((Store.Structure) first).functor)) {
                    ((Store.Structure) first).functor = new Store.Compound(((Store.Structure) first).functor,
                            new Object[((Store.Structure) first).args.length]);
                    ((Store.Compound) first).walk &= ~Store.VAR_MASK_SERNO;
                    stack = Store.stack_push(stack, first);
                    first = ((Store.Structure) first).args[0];
                    continue;
                } else {
                    first = ((Store.Structure) first).functor;
                }
            }
            Store.Compound item = (Store.Compound) Store.stack_peek(stack);
            while (item != null &&
                    (item.walk & Store.VAR_MASK_SERNO) == item.args.length - 1) {
                ((Store.Structure) item.functor).args[item.walk & Store.VAR_MASK_SERNO] = first;
                first = item.functor;
                Store.stack_pop(stack);
                item = (Store.Compound) Store.stack_peek(stack);
            }
            if (item == null) {
                return first;
            } else {
                ((Store.Structure) item.functor).args[item.walk & Store.VAR_MASK_SERNO] = first;
                item.walk++;
                first = item.args[item.walk & Store.VAR_MASK_SERNO];
            }
        }
    }

    private static void walk_uncopy(Object first) {
        List stack = null;
        for (; ; ) {
            first = Store.deref(first);
            if (Store.is_variable(first)) {
                if (((Store.Variable) first).tail != null)
                    ((Store.Variable) first).tail = null;
            } else if (Store.is_compound(first)) {
                if (Store.is_compound(((Store.Structure) first).functor)) {
                    ((Store.Structure) first).functor = ((Store.Structure) ((Store.Structure) first).functor).functor;
                    if (0 != ((Store.Structure) first).args.length - 1) {
                        ((Store.Compound) first).walk &= ~Store.VAR_MASK_SERNO;
                        stack = Store.stack_push(stack, first);
                    }
                    first = ((Store.Structure) first).args[0];
                    continue;
                }
            }
            Store.Compound item = (Store.Compound) Store.stack_peek(stack);
            if (item == null) {
                return;
            } else {
                item.walk++;
                first = item.args[item.walk & Store.VAR_MASK_SERNO];
                if ((item.walk & Store.VAR_MASK_SERNO) == item.args.length - 1)
                    Store.stack_pop(stack);
            }
        }
    }

    /**************************************************************/
    /* Binary Work                                                */
    /**************************************************************/

    public static final class Item {
        public final Structure first;
        public Object second;
        public int idx;

        /**
         * Create a binary work item.
         *
         * @param first The first Prolog term.
         * @param second The second Prolog term.
         * @param idx The index.
         */
        public Item(Structure first, Object second, int idx) {
            this.first = first;
            this.second = second;
            this.idx = idx;
        }

    }

    /**************************************************************/
    /* Stack Array                                                */
    /**************************************************************/

    /**
     * The function returns the same stack extended by a work item.
     *
     * @param stack The stack.
     * @param elem The work item.
     * @return The new stack.
     */
    public static List stack_push(List stack, Object elem) {
        if (stack == null)
            stack = new ArrayList();
        stack.add(elem);
        return stack;
    }

    /**
     * The function returns the top work item or null.
     *
     * @param stack The stack.
     * @return The work item.
     */
    public static Object stack_peek(List stack) {
        if (stack == null)
            return null;
        if (stack.size() == 0)
            return null;
        return stack.get(stack.size() - 1);
    }

    /**
     * The routine removes the top work item from the stack.
     *
     * @param stack The stack.
     */
    public static void stack_pop(List stack) {
        stack.remove(stack.size() - 1);
    }

    /**************************************************************/
    /* Clauses Lifecycle                                          */
    /**************************************************************/

    public static final class Goal {
        public final int size;
        public final Object[] body;
        public final int cutvar;

        public Goal(int size, Object[] body, int cutvar) {
            this.size = size;
            this.body = body;
            this.cutvar = cutvar;
        }

    }

    /**
     * Check whether the object is a goal.
     *
     * @param obj The object.
     * @return boolean if the object is a goal, otherwise false.
     */
    public static boolean is_goal(Object obj) {
        return obj instanceof Goal;
    }

    public static final class Clause {
        public final int size;
        public final Object functor;
        public final Object[] head;
        public final Object[] body;
        public final int cutvar;
        public int creator;
        public int remover;
        public String shard;

        public Clause(int size, Object functor, Object[] head,
                      Object[] body, int cutvar) {
            this.size = size;
            this.functor = functor;
            this.head = head;
            this.body = body;
            this.cutvar = cutvar;
            this.creator = UNDEF_INT;
            this.remover = UNDEF_INT;
            this.shard = "";
        }

    }

    /**
     * Check whether the object is a clause.
     *
     * @param obj The object.
     * @return boolean if the object is a clause, otherwise false.
     */
    public static boolean is_clause(Object obj) {
        return obj instanceof Clause;
    }

    public static final class Logical {
        public Clause[] cache;
        public int count;
        public SequencedCollection data;

        /**
         * Create a logical.
         *
         * @param cache The cache of non-deleted clauses.
         * @param count The counter of non-deleted clauses.
         * @param data  The clause list.
         */
        public Logical(Clause[] cache, int count, SequencedCollection data) {
            this.cache = cache;
            this.count = count;
            this.data = data;
        }

    }

    /**
     * Check whether an object is a logical.
     *
     * @param obj The object.
     * @return boolean if the object is a logical, otherwise false.
     */
    public static boolean is_logical(Object obj) {
        return obj instanceof Logical;
    }

    public static final class Stick {
        public Logical rope;
        public Object[] guards;
        public Map[] maps;

        /**
         * Create a stick.
         *
         * @param rope The rope.
         * @param guards The variable guards.
         * @param maps The index map.
         */
        public Stick(Logical rope, Object[] guards, Map[] maps) {
            this.rope = rope;
            this.guards = guards;
            this.maps = maps;
        }

    }

    /**
     * Check whether an object is a stick.
     *
     * @param obj The object.
     * @return boolean if the object is a stick, otherwise false.
     */
    public static boolean is_stick(Object obj) {
        return obj instanceof Stick;
    }

    public static Object index_value(Object temp, Object[] body, int flags) {
        int j = 0;
        for (;;) {
            if (!is_place(temp)) {
                if ((flags & MASK_PRED_PREHASH) != 0) {
                    if (Machine.is_frozen(temp)) {
                        temp = Integer.valueOf(((Machine.Frozen) temp).hash);
                    } else if (!is_skeleton(temp)) {
                        temp = Integer.valueOf(Objects.hashCode(temp));
                    } else {
                        temp = UNDEF_OBJ;
                    }
                } else {
                    if (is_element(temp))
                        temp = ((Element) temp).functor;
                }
                break;
            }
            if (temp != UNDEF_OBJ &&
                    (flags & MASK_PRED_DYNAMIC) == 0 &&
                    j < body.length) {
                Object peek = body[j];
                j++;
                if (is_element(peek) &&
                        "=".equals(site_name(((Element) peek).functor)) &&
                        ((Element) peek).args.length == 2) {
                    if (temp.equals(((Element) peek).args[0])) {
                        temp = ((Element) peek).args[1];
                    } else if (temp.equals(((Element) peek).args[1])) {
                        temp = ((Element) peek).args[0];
                    }
                    continue;
                } else if (is_element(peek) &&
                        "nonvar".equals(site_name(((Element) peek).functor)) &&
                        ((Element) peek).args.length == 1) {
                    continue;
                }
            }
            temp = UNDEF_OBJ;
            break;
        }
        return temp;
    }

    private static Object site_name(Object obj) {
        if (is_cache(obj)) {
            return ((Cache)obj).name;
        } else {
            return obj;
        }
    }

    /**************************************************************/
    /* Knowledgebase                                              */
    /**************************************************************/

    public static final class Provable {
        public int flags;
        public Object func;
        public int creator;
        public int remover;
        public Provable overlay;

        /**
         * Create a provable.
         */
        public Provable() {
            this.flags = 0;
            this.func = null;
            this.creator = stage;
            this.remover = UNDEF_INT;
            this.overlay = null;
        }

    }

    /**
     * Check whether an object is a provable.
     *
     * @param obj The object.
     * @return boolean True if the object is a provable, otherwise false.
     */
    public static boolean is_provable(Object obj) {
        return obj instanceof Provable;
    }

    public static final class Cache {
        public Provable link;
        public String name;

        /**
         * Create a cache node.
         *
         * @param name The functor.
         */
        public Cache(String name) {
            this.link = null;
            this.name = name;
        }
    }

    /**
     * Check whether an object is a cache.
     *
     * @param obj The object.
     * @return boolean True if the object is a cache, otherwise false.
     */
    public static boolean is_cache(Object obj) {
        return obj instanceof Cache;
    }

    /******************************************************************/
    /* Snapshot Data                                                  */
    /******************************************************************/

    public static Clause[] snapshot_peek(Object func) {
        if (is_stick(func)) {
            return snapshot_rope(((Stick)func).rope);
        } else {
            return snapshot_rope((Logical)func);
        }
    }

    /**
     * Make snapshot of a logical.
     *
     * @param rope The logical.
     * @return array The clause list snapshot.
     */
    public static Clause[] snapshot_rope(Logical rope) {
        Clause[] res = rope.cache;
        if (res == null) {
            res = new Clause[rope.count];
            copy_rope(res, rope);
            rope.cache = res;
        }
        return res;
    }

    private static void copy_rope(Clause[] res, Logical rope) {
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            int j = 0;
            for (int i = 0; i < data.size(); i++) {
                Clause clause = (Clause) data.get(i);
                if (clause.remover == UNDEF_INT)
                    res[j++] = clause;
            }
        } else {
            Set data = (Set) rope.data;
            Iterator it = data.iterator();
            int j = 0;
            while (it.hasNext()) {
                Clause clause = (Clause) it.next();
                if (clause.remover == UNDEF_INT)
                    res[j++] = clause;
            }
        }
    }

    /******************************************************************/
    /* Linked Provables                                               */
    /******************************************************************/

    /**
     * Retrieve a provable from monomorphic cache.
     *
     * @param cache The cache.
     * @param arity The arity.
     * @return The provable or null.
     */
    public static Provable ensure_link(Cache cache, int arity) {
        Provable peek = cache.link;
        if (peek == null || peek.remover != UNDEF_INT) {
            peek = pred_link(cache.name, arity);
            cache.link = peek;
        }
        return peek;
    }

    public static Provable pred_link(String functor, int arity) {
        if (arity < 0)
            return null;
        List temp = (List) kb.get(functor);
        if (temp == null)
            return null;
        Provable peek = (arity < temp.size() ? (Provable) temp.get(arity) : null);
        if (peek == null || peek.remover != UNDEF_INT)
            return null;
        return peek;
    }

    public static Provable resolve_link(Object functor, int arity) {
        if (is_cache(functor)) {
            return ensure_link((Cache) functor, arity);
        } else if (Machine.is_atom(functor)) {
            return pred_link((String) functor, arity);
        } else if (is_provable(functor)) {
            return (Provable) functor;
        } else {
            check_nonvar(functor);
            functor = copy_term(functor);
            throw Machine.make_error(new Compound("type_error",
                    new Object[]{"callable", functor}));
        }
    }

    /**
     * Assure that the object is a nonvar.
     *
     * @param beta The object.
     */
    public static void check_nonvar(Object beta) {
        if (is_variable(beta))
            throw Machine.make_error("instantiation_error");
    }

    /******************************************************************/
    /* Dynamic Predicates                                             */
    /******************************************************************/

    /**
     * Retrieve or create a provable from monomorphic cache.
     *
     * @param cache The cache.
     * @param arity The arity.
     * @return The provable.
     */
    public static Provable ensure_touch(Cache cache, int arity, int flags) {
        Provable peek = cache.link;
        if (peek == null || peek.remover != UNDEF_INT) {
            peek = pred_touch(cache.name, arity, flags);
            cache.link = peek;
        }
        return peek;
    }

    public static Provable pred_touch(String functor, int arity, int flags) {
        List temp = (List) kb.get(functor);
        if (temp == null) {
            temp = new Handler.Rope();
            kb.put(functor, temp);
        }
        Provable peek = (arity < temp.size() ? (Provable) temp.get(arity) : null);
        if (peek == null || peek.remover != UNDEF_INT) {
            Provable res = make_defined(Machine.VOID_ARGS);
            if (peek != null)
                res.overlay = peek;
            if ((flags & MASK_TOUCH_DYNAMIC) != 0)
                res.flags |= MASK_PRED_DYNAMIC;
            while (arity >= temp.size())
                temp.add(null);
            temp.set(arity, res);
            peek = res;
        } else {
            if (!is_logical(peek.func) && !is_stick(peek.func))
                throw Machine.make_error(new Compound("permission_error",
                        new Object[]{"modify", "static_procedure",
                                Machine.make_indicator(functor, arity)}));
            if ((flags & MASK_TOUCH_DYNAMIC) != 0)
                if ((peek.flags & MASK_PRED_DYNAMIC) == 0)
                    throw Machine.make_error(new Compound("permission_error",
                            new Object[]{"modify", "static_procedure",
                                    Machine.make_indicator(functor, arity)}));
        }
        if ((flags & MASK_TOUCH_PREHASH) != 0) {
            if ((peek.flags & MASK_PRED_PREHASH) == 0) {
                if (is_stick(peek.func))
                    peek.func = ((Stick)peek.func).rope;
                peek.flags |= MASK_PRED_PREHASH;
            }
        }
        return peek;
    }

    private static Provable resolve_touch(Object functor, int arity, int flags) {
        if (is_cache(functor)) {
            return ensure_touch((Cache) functor, arity, flags);
        } else if (Machine.is_atom(functor)) {
            return pred_touch((String) functor, arity, flags);
        } else if (is_provable(functor)) {
            return (Provable) functor;
        } else {
            check_nonvar(functor);
            functor = copy_term(functor);
            throw Machine.make_error(new Compound("type_error",
                    new Object[]{"callable", functor}));
        }
    }

    /******************************************************************/
    /* Index Extension                                                */
    /******************************************************************/

    /**
     * The function returns an anonymous predicate for the given clauses.
     * The index is not yet built, so only a logical is stored.
     *
     * @param data The clauses.
     * @return Provable predicate.
     */
    public static Provable make_defined(Object[] data) {
        Provable peek = new Provable();
        peek.func = new_rope();
        for (int i = 0; i < data.length; i++)
            add_peek(peek.func, 0, (Clause)data[i], MASK_TOUCH_BOTTOM, peek.flags);
        return peek;
    }

    private static Logical new_rope() {
        return new Logical(null, 0, new Handler.Rope());
    }

    public static Stick new_bouquet(Logical rope, int width) {
        Object[] guards = new Object[width];
        Map[] maps = new Map[width];
        return new Stick(rope, guards, maps);
    }

    public static void extend_bouquet(Stick peek, int j, int offset, Logical rope, int flags) {
        peek.guards[j] = new_rope();
        peek.maps[j] = new Handler.ArrayMap();
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            for (int i = 0; i < data.size(); i++) {
                Clause clause = (Clause) data.get(i);
                if (clause.remover == UNDEF_INT)
                    add_map(peek, j, offset, clause, MASK_TOUCH_BOTTOM, flags);
            }
        } else {
            Set data = (Set) rope.data;
            Iterator it = data.iterator();
            while (it.hasNext()) {
                Clause clause = (Clause) it.next();
                if (clause.remover == UNDEF_INT)
                    add_map(peek, j, offset, clause, MASK_TOUCH_BOTTOM, flags);
            }
        }
    }

    /**************************************************************/
    /* Clauses Retrieval                                          */
    /**************************************************************/

    /**
     * Retrieve a logical from a provable possibly using an index.
     * If only a logical is stored, build an index before retrieval.
     *
     * @param peek The provable.
     * @param args The actual arguments.
     * @return The logical.
     */
    public static Logical defined_pred(Object peek, Object[] args) {
        int width = Math.min(MAX_INDEX, args.length);
        int offset = 0;
        Object func = ((Provable)peek).func;
        int flags = ((Provable)peek).flags;
        Object val = null;
        int k = 0;
        for (;;) {
            Logical rope;
            if (is_stick(func)) {
                rope = ((Stick) func).rope;
            } else {
                rope = (Logical) func;
            }
            if (rope.count < 2)
                return rope;
            int i = 0;
            for (; i < width; i++) {
                Object key = key_value(args[i+offset], flags);
                if (key == UNDEF_OBJ)
                    continue;
                if (!is_stick(func)) {
                    func = new_bouquet(rope, width);
                    if (is_stick(peek)) {
                        if (val == UNDEF_OBJ) {
                            ((Stick)peek).guards[k] = func;
                        } else {
                            ((Stick)peek).maps[k].put(val, func);
                        }
                    } else {
                        ((Provable)peek).func = func;
                    }
                }
                peek = func;
                if (((Stick)peek).maps[i] == null)
                    extend_bouquet((Stick) peek, i, offset, rope, flags);
                if (((Stick)peek).maps[i].size() == 0)
                    continue;
                func = ((Stick)peek).maps[i].get(key);
                if (func == null) {
                    func = ((Stick)peek).guards[i];
                    val = UNDEF_OBJ;
                } else {
                    val = key;
                }
                k = i;
                width = width-i-1;
                offset = i+offset+1;
                i = -1;
                break;
            }
            if (!(i < width))
                return rope;
        }
    }

    private static Object key_value(Object term, int flags) {
        term = deref(term);
        if (!is_variable(term)) {
            if ((flags & MASK_PRED_PREHASH) != 0) {
                if (Machine.is_frozen(term)) {
                    term = Integer.valueOf(((Machine.Frozen) term).hash);
                } else if (!is_compound(term)) {
                    term = Integer.valueOf(Objects.hashCode(term));
                } else {
                    term = UNDEF_OBJ;
                }
            } else {
                if (is_structure(term))
                    term = ((Structure) term).functor;
            }
        } else {
            term = UNDEF_OBJ;
        }
        return term;
    }

    /*********************************************************************/
    /* Destroy Provable                                                 */
    /*********************************************************************/

    /**
     * Remove a predicate from the knowledge base.
     *
     * @param functor The functor.
     * @param arity   The arity.
     */
    public static void pred_destroy(String functor, int arity) {
        List temp = (List) kb.get(functor);
        if (temp == null)
            return;
        Provable peek = (arity < temp.size() ? (Provable) temp.get(arity) : null);
        if (peek == null || peek.remover != UNDEF_INT)
            return;
        if (peek.creator == stage) {
            peek = clear_pop(peek);
            temp.set(arity, peek);
            if (peek == null && trim_arities(temp))
                kb.remove(functor);
        } else {
            peek.remover = stage;
        }
    }

    /**
     * Clear and pop a provable.
     *
     * @param peek The provable.
     * @return The parent provable.
     */
    private static Provable clear_pop(Provable peek) {
        peek.remover = stage;
        peek.func = null;

        Provable back = peek;
        peek = back.overlay;
        back.overlay = null;
        return peek;
    }

    /**
     * Trim the arities array.
     *
     * @param peek The arities array.
     * @return boolean True if empty, otherwise fale.
     */
    private static boolean trim_arities(List peek) {
        int pos = peek.size();
        while (pos > 0 && peek.get(pos - 1) == null)
            pos--;
        if (pos == 0)
            return true;
        if (pos != peek.size())
            ((Handler.Rope) peek).removeRange(pos, peek.size());
        return false;
    }

    /**************************************************************/
    /* Clauses Transactions                                       */
    /**************************************************************/

    /**
     * Rollback the clauses.
     */
    public static void clear() {
        Iterator it = kb.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            List temp = (List) entry.getValue();
            for (int i = 0; i < temp.size(); i++) {
                Provable peek = (Provable) temp.get(i);
                if (peek == null)
                    continue;
                if (peek.creator == stage) {
                    peek = clear_pop(peek);
                    temp.set(i, peek);
                    if (peek == null)
                        continue;
                }
                if (peek.remover == stage)
                    peek.remover = UNDEF_INT;
                if (is_logical(peek.func) || is_stick(peek.func))
                    rollback_peek(peek.func, true);
            }
            if (trim_arities(temp))
                it.remove();
        }
    }

    private static void rollback_peek(Object func, boolean update) {
        if (is_stick(func)) {
            Stick peek = (Stick)func;
            if (!has_action(peek.rope))
                return;
            for (int i = 0; i < peek.maps.length; i++) {
                Map temp = peek.maps[i];
                if (temp == null)
                    continue;
                Iterator it = temp.entrySet().iterator();
                while (it.hasNext()) {
                    Map.Entry entry = (Map.Entry) it.next();
                    Object val = entry.getValue();
                    rollback_peek(val, false);
                    if (size_peek(val) == 0)
                        it.remove();
                }
                rollback_peek(peek.guards[i], false);
                if (temp instanceof HashMap &&
                        temp.size() < BOUQUET_LOW)
                    peek.maps[i] = new Handler.ArrayMap(temp);
            }
            rollback_rope(peek.rope, update);
        } else {
            if (!has_action((Logical)func))
                return;
            rollback_rope((Logical)func, update);
        }
    }

    public static int size_peek(Object func) {
        Logical rope;
        if (is_stick(func)) {
            rope = ((Stick)func).rope;
        } else {
            rope = (Logical)func;
        }
        if (rope.data instanceof List) {
            return rope.data.size();
        } else {
            return rope.data.size();
        }
    }

    /**
     * Check whether a logical has some action.
     *
     * @param rope The logical.
     * @return boolean if the logical has some action, false otherwise.
     */
    private static boolean has_action(Logical rope) {
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            for (int i = 0; i < data.size(); i++) {
                Clause clause = (Clause) data.get(i);
                if (clause.creator == stage)
                    return true;
                if (clause.remover == stage)
                    return true;
            }
            return false;
        } else {
            Set data = (Set) rope.data;
            Iterator it = data.iterator();
            while (it.hasNext()) {
                Clause clause = (Clause) it.next();
                if (clause.creator == stage)
                    return true;
                if (clause.remover == stage)
                    return true;
            }
            return false;
        }
    }

    /**
     * Rollback clauses from a logical.
     *
     * @param rope   The logical.
     * @param update The update flag.
     */
    private static void rollback_rope(Logical rope, boolean update) {
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            int j = 0;
            for (int i = 0; i < data.size(); i++) {
                Clause clause = (Clause) data.get(i);
                if (clause.creator == stage) {
                    rope.count--;
                } else {
                    if (clause.remover == stage) {
                        if (update)
                            clause.remover = UNDEF_INT;
                        rope.count++;
                    }
                    data.set(j++, clause);
                }
            }
            ((Handler.Rope) data).removeRange(j, data.size());
            rope.cache = null;
        } else {
            Set data = (Set) rope.data;
            Iterator it = data.iterator();
            while (it.hasNext()) {
                Clause clause = (Clause) it.next();
                if (clause.creator == stage) {
                    rope.count--;
                    it.remove();
                } else {
                    if (clause.remover == stage) {
                        if (update)
                            clause.remover = UNDEF_INT;
                        rope.count++;
                    }
                }
            }
            rope.cache = null;
        }
    }

    /******************************************************************/
    /* Provable Addition                                              */
    /******************************************************************/

    /**
     * Enhance the knowledge base by a provable.
     *
     * @param functor        The functor.
     * @param arity          The arity.
     * @param pred The provable.
     */
    public static void set(String functor, int arity,
                           Provable pred) {
        List temp = (Handler.Rope) kb.get(functor);
        if (temp == null) {
            temp = new Handler.Rope();
            kb.put(functor, temp);
        }
        Provable peek = (arity < temp.size() ? (Provable) temp.get(arity) : null);
        if (peek == null || peek.remover != UNDEF_INT) {
            if (peek != null)
                pred.overlay = peek;
            while (arity >= temp.size())
                temp.add(null);
            temp.set(arity, pred);
        } else {
            throw Machine.make_error(new Compound("permission_error",
                    new Object[]{"coerce", "procedure",
                            Machine.make_indicator(functor, arity)}));
        }
    }

    /******************************************************************/
    /* Clause Addition                                                */
    /******************************************************************/

    /**
     * Enhance the knowledge base by a clause.
     *
     * @param clause The clause.
     */
    public static void add(Clause clause) {
        add_clause(clause, MASK_TOUCH_BOTTOM);
    }

    public static void add_clause(Clause clause, int flags) {
        if (clause.remover != UNDEF_INT)
            throw Machine.make_error(new Compound("permission_error",
                    new Object[]{"modify", "static_procedure",
                            Machine.make_indicator(clause.functor, clause.head.length)}));
        if (clause.creator != UNDEF_INT)
            return;
        Provable peek = resolve_touch(clause.functor, clause.head.length, flags);
        add_peek(peek.func, 0, clause, flags, peek.flags);
        clause.creator = stage;
        if ((flags & MASK_TOUCH_DYNAMIC) == 0)
            clause.shard = engine.partition;
    }

   private static void add_peek(Object func, int offset, Clause clause, int flags, int flags2) {
        if (is_stick(func)) {
            Stick peek = (Stick) func;
            add_rope(peek.rope, clause, flags);
            for (int i = 0; i < peek.maps.length; i++)
                if (peek.maps[i] != null)
                  add_map(peek, i, offset, clause, flags, flags2);
        } else {
            add_rope((Logical)func, clause, flags);
        }
    }

    private static void add_map(Stick peek, int i, int offset, Clause clause, int flags, int flags2) {
        Object key = index_value(clause.head[i+offset], clause.body, flags2);
        Map temp = peek.maps[i];
        if (key == UNDEF_OBJ) {
            Iterator it = temp.entrySet().iterator();
            while (it.hasNext()) {
                Map.Entry entry = (Map.Entry) it.next();
                add_peek(entry.getValue(), i+offset+1, clause, flags, flags2);
            }
            add_peek(peek.guards[i], i+offset+1, clause, flags, flags2);
        } else {
            Object val = temp.get(key);
            if (val == null) {
                val = clone_peek(peek.guards[i]);
                temp.put(key, val);
            }
            add_peek(val, i+offset+1, clause, flags, flags2);
        }
        if (temp instanceof Handler.ArrayMap &&
                temp.size() >= BOUQUET_HIGH)
            peek.maps[i] = new HashMap(temp);
    }

    private static void add_rope(Logical rope, Clause clause, int flags) {
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            if ((flags & MASK_TOUCH_BOTTOM) != 0) {
                data.add(clause);
            } else {
                data.add(0, clause);
            }
            if (data.size() >= ROPE_HIGH)
                rope.data = new LinkedHashSet(data);
            rope.count++;
            rope.cache = null;
        } else {
            Set data = (Set) rope.data;
            if ((flags & MASK_TOUCH_BOTTOM) != 0) {
                data.add(clause);
            } else {
                ((SequencedSet) data).addFirst(clause);
            }
            rope.count++;
            rope.cache = null;
        }
    }

    private static Logical clone_peek(Object func) {
        Logical rope;
        if (is_stick(func)) {
            rope = ((Stick)func).rope;
        } else {
            rope = (Logical)func;
        }
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            return new Logical(rope.cache, rope.count,
                    (SequencedCollection) ((Handler.Rope) data).clone());
        } else {
            Set data = (Set) rope.data;
            return new Logical(rope.cache, rope.count,
                    (SequencedCollection) ((LinkedHashSet) data).clone());
        }
    }

    /******************************************************************/
    /* Clause Removal                                                 */
    /******************************************************************/

    /**
     * Remove a clause from the knowledge base.
     *
     * @param clause  The clause.
     * @param flags   The flags.
     * @return boolean True if the clause was removed, false otherwise.
     */
    public static boolean remove_clause(Clause clause, int flags) {
        if (clause.remover != UNDEF_INT)
            return false;
        if (clause.creator == UNDEF_INT)
            return false;
        Provable peek = resolve_link(clause.functor, clause.head.length);
        if (peek == null)
            return false;
        if (!is_logical(peek.func) && !is_stick(peek.func))
            throw Machine.make_error(new Compound("permission_error",
                    new Object[]{"modify", "static_procedure",
                            Machine.make_indicator(clause.functor, clause.head.length)}));
        remove_peek(peek.func, 0, clause, flags, peek.flags);
        if (clause.creator != stage) {
            clause.remover = stage;
        } else {
            clause.creator = UNDEF_INT;
        }
        return true;
    }

    private static void remove_peek(Object func, int offset, Clause clause, int flags, int flags2) {
        if (is_stick(func)) {
            Stick peek = (Stick) func;
            remove_rope(peek.rope, clause, flags);
            for (int i = 0; i < peek.maps.length; i++) {
                Map temp = peek.maps[i];
                if (temp == null)
                    continue;
                Object key = index_value(clause.head[i+offset], clause.body, flags2);
                if (key == UNDEF_OBJ) {
                    Iterator it = temp.entrySet().iterator();
                    while (it.hasNext()) {
                        Map.Entry entry = (Map.Entry) it.next();
                        Object val = entry.getValue();
                        remove_peek(val, i+offset+1, clause, flags, flags2);
                        if (size_peek(val) == 0)
                            it.remove();
                    }
                    remove_peek(peek.guards[i], i+offset+1, clause, flags, flags2);
                } else {
                    Object val = temp.get(key);
                    remove_peek(val, i+offset+1, clause, flags, flags2);
                    if (size_peek(val) == 0)
                        temp.remove(key);
                }
                if (temp instanceof HashMap &&
                        temp.size() < BOUQUET_LOW)
                    peek.maps[i] = new Handler.ArrayMap(temp);
            }
        } else {
            remove_rope((Logical) func, clause, flags);
        }
    }

    private static void remove_rope(Logical rope, Clause clause, int flags) {
        if (rope.data instanceof List) {
            List data = (List) rope.data;
            int index;
            if ((flags & MASK_REMOVE_REVERSE) == 0) {
                index = data.indexOf(clause);
            } else {
                index = data.lastIndexOf(clause);
            }
            if (clause.creator == stage) {
                if (index == -1)
                    throw new Error("rope corrupted");
                data.remove(index);
            } else {
                if (index == -1)
                    throw new Error("rope corrupted");
            }
            rope.count--;
            rope.cache = null;
        } else {
            Set data = (Set) rope.data;
            if (clause.creator == stage) {
                if (!data.remove(clause))
                    throw new Error("rope corrupted");
            } else {
                if (!data.contains(clause))
                    throw new Error("rope corrupted");
            }
            if (data.size() < ROPE_LOW)
                rope.data = new Handler.Rope(data);
            rope.count--;
            rope.cache = null;
        }
    }

}
