###
# Modern Albufeira Prolog Interpreter
#
# 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.
##

import functools
from nova.core import (exec_build, stack_push,
    equal_term, list_objects, objects_list, object_equals,
    Compound, exec_unify, is_structure, union_find,
    variable_serno, is_integer, is_float, is_special,
    make_error, set, make_check, check_nonvar, copy_term,
    is_variable, is_atom, deref, union_add, is_number,
    Item, stack_peek, stack_pop, union_undo)
import math

################################################################
# @</2, @=</2, @>/2, @>=/2 and compare/3                       #
################################################################

###
# X @< Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically less than Y, otherwise fails.
##
def test_less(args):
    alpha = exec_build(args[0])
    beta = exec_build(args[1])
    return compare_term(alpha, beta) < 0


###
# X @=< Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically less or equal to Y, otherwise fails.
##
def test_lessequal(args):
    alpha = exec_build(args[0])
    beta = exec_build(args[1])
    return compare_term(alpha, beta) <= 0


###
# X @>= Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically greater or equal to Y, otherwise fails.
##
def test_greaterequal(args):
    alpha = exec_build(args[0])
    beta = exec_build(args[1])
    return compare_term(alpha, beta) >= 0


###
# X @> Y: [ISO 8.4.1]
# The predicate succeeds when X is syntactically greater than Y, otherwise fails.
##
def test_greater(args):
    alpha = exec_build(args[0])
    beta = exec_build(args[1])
    return compare_term(alpha, beta) > 0


###
# compare(C, X, Y): [TC2 8.4.2]
# The predicate succeeds when C unifies with the result of comparing
# X to Y. The result is one of the following atoms <, = or >.
##
def test_compare(args):
    beta = exec_build(args[1])
    gamma = exec_build(args[2])
    beta = compare_term(beta, gamma)
    if beta < 0:
        beta = "<"
    elif beta == 0:
        beta = "="
    else:
        beta = ">"
    return exec_unify(args[0], beta)


###
# Determine the syntactic relationship between two Prolog terms.
# Can handle cyclic terms and deep recursion.
# Has left to right anomaly.
#
# @param alpha The first Prolog term.
# @param beta The second Prolog term.
# @return <0 for less, =0 for equal and >0 for greater
##
def compare_term(first, second):
    stack = None
    log = None
    try:
        while True:
            first = deref(first)
            second = deref(second)
            if not is_structure(first):
                if not object_equals(first, second):
                    break
            elif not is_structure(second):
                break
            elif len(first.args) != len(second.args):
                break
            else:
                first = union_find(first)
                second = union_find(second)
                if first is not second:
                    if first.functor != second.functor:
                        break
                    log = union_add(log, first, second)
                    if 0 != len(first.args) - 1:
                        item = Item(first, second, 0)
                        stack = stack_push(stack, item)
                    first = first.args[0]
                    second = second.args[0]
                    continue
            item = stack_peek(stack)
            if item is None:
                return 0
            else:
                item.idx += 1
                first = item.first.args[item.idx]
                second = item.second.args[item.idx]
                if item.idx == len(item.first.args) - 1:
                    stack_pop(stack)
        return compare_truncated(first, second)
    finally:
        union_undo(log)


###
# Determine the syntactic relationship between truncated Prolog terms.
# Prolog compounds are truncated to their arity and functor.
#
# @param first  The first Prolog term.
# @param second The second Prolog term.
# @return <0 for less, =0 for equal and >0 for greater
##
def compare_truncated(first, second):
    i = compare_type(first)
    k = i - compare_type(second)
    if k != 0:
        return k
    if i == 0:
        return variable_serno(first) - variable_serno(second)
    elif i == 2:
        return compare_atomic(first, second)
    elif i == 3:
        return compare_atomic(first, second)
    elif i == 9:
        return compare_atomic(first, second)
    elif i == 10:
        k = len(first.args) - len(second.args)
        if k != 0:
            return k
        return compare_atomic(first.functor, second.functor)
    else:
        return 0


###
# Determine the compare type of a Prolog term.
#
# @param first The Prolog term.
# @return The compare type.
##
def compare_type(first):
    if is_variable(first):
        return 0
    elif is_structure(first):
        return 10
    elif is_atom(first):
        return 9
    elif is_number(first):
        if is_integer(first):
            return 3
        elif is_special(first):
            if first == -math.inf:
                return 1
            elif first == math.inf:
                return 4
            elif math.isnan(first):
                return 5
        elif is_float(first):
            return 2
    elif first is False:
        return 7
    elif first is True:
        return 8
    elif first is None:
        return 6
    raise make_error(Compound("resource_error",
                        ["not_supported"]))


###
# Determine the syntactic relationship between two Prolog atomics.
#
# @param first The first Prolog atomic.
# @param second The second Prolog atomic.
# @return -1 for less, 0 for equal and 1 for greater
##
def compare_atomic(first, second):
    if first < second:
        return -1
    if first == second:
        return 0
    return 1


#######################################################################
# sort/2 and keysort/2                                                #
#######################################################################

###
# sort(L, R): [TC2 8.4.3]
# The predicate succeeds in R with the sorted list L.
##
def test_sort(args):
    alpha = exec_build(args[0])
    res = list_objects(alpha)
    res.sort(key=functools.cmp_to_key(compare_term))
    count = objects_dedup(res)
    return exec_unify(args[1], objects_list(res, 0, count))


def objects_dedup(res):
    j = 0
    i = 0
    while i < len(res):
        alpha = res[i]
        i += 1
        while i < len(res) and equal_term(alpha, res[i]):
            i += 1
        res[j] = alpha
        j += 1
    return j


###
# keysort(L, R): [TC2 8.4.4]
# The predicate succeeds in R with the key sorted list L.
##
def test_keysort(args):
    alpha = exec_build(args[0])
    res = list_objects(alpha)
    objects_pairs(res)
    res.sort(key=functools.cmp_to_key(lambda first, second:
                                      compare_term(get_key(first), get_key(second))))
    return exec_unify(args[1], objects_list(res, 0, len(res)))


def objects_pairs(res):
    i = 0
    while i < len(res):
        alpha = res[i]
        if (is_structure(alpha) and
                "-" == alpha.functor and
                len(alpha.args) == 2):
            pass
        else:
            check_nonvar(alpha)
            alpha = copy_term(alpha)
            raise make_error(Compound("type_error", ["pair", alpha]))
        i += 1


def get_key(peek):
    return peek.args[0]


#######################################################################
# Iso Lib Init                                                        #
#######################################################################

def main():
    # term specials, syntactic comparison
    set("@<", 2, make_check(test_less))
    set("@=<", 2, make_check(test_lessequal))
    set("@>=", 2, make_check(test_greaterequal))
    set("@>", 2, make_check(test_greater))
    set("compare", 3, make_check(test_compare))

    # list specials, miscellaneous sorting
    set("sort", 2, make_check(test_sort))
    set("keysort", 2, make_check(test_keysort))