Find the point in the tree that minimizes the distance to the query.

    This method implements the nearest_point query for any structure
    implementing a kd-tree. The only requirement is a function capable to
    extract the relevant properties from a node representation of the
    particular implementation.

    Args:
        query (:obj:`tuple` of float or int): Stores the position of the
            node.
        root_id (:obj): The identifier of the root in the kd-tree
            implementation.
        get_properties (:obj:`function`): The function to extract the
            relevant properties from a node, namely its point, region,
            axis, left child identifier, right child identifier and
            if it is active. If the implementation does not uses
            the active attribute the function should return always True.
        dist_fun (:obj:`function`, optional): The distance function,
            euclidean distance by default.

    Returns:
        :obj:`tuple`: Tuple of length 2, where the first element is the
            identifier of the nearest node, the second is the distance
            to the query.

def nearest_point(query, root_id, get_properties, dist_fun=euclidean_dist):
    """Find the point in the tree that minimizes the distance to the query.

    This method implements the nearest_point query for any structure
    implementing a kd-tree. The only requirement is a function capable to
    extract the relevant properties from a node representation of the
    particular implementation.

    Args:
        query (:obj:`tuple` of float or int): Stores the position of the
            node.
        root_id (:obj): The identifier of the root in the kd-tree
            implementation.
        get_properties (:obj:`function`): The function to extract the
            relevant properties from a node, namely its point, region,
            axis, left child identifier, right child identifier and
            if it is active. If the implementation does not uses
            the active attribute the function should return always True.
        dist_fun (:obj:`function`, optional): The distance function,
            euclidean distance by default.

    Returns:
        :obj:`tuple`: Tuple of length 2, where the first element is the
            identifier of the nearest node, the second is the distance
            to the query.

    """

    k = len(query)
    dist = math.inf

    nearest_node_id = None

    # stack_node: stack of identifiers to nodes within a region that
    # contains the query.
    # stack_look: stack of identifiers to nodes within a region that
    # does not contains the query.
    stack_node = deque([root_id])
    stack_look = deque()

    while stack_node or stack_look:

        if stack_node:
            node_id = stack_node.pop()
            look_node = False
        else:
            node_id = stack_look.pop()
            look_node = True

        point, region, axis, active, left, right = get_properties(node_id)

        # Should consider this node?
        # As it is within a region that does not contains the query, maybe
        # there is no chance to find a closer node in this region
        if look_node:
            inside_region = True
            for i in range(k):
                inside_region &= interval_condition(query[i], region[i][0],
                                                    region[i][1], dist)
            if not inside_region:
                continue

        # Update the distance only if the node is active.
        if active:
            node_distance = dist_fun(query, point)
            if nearest_node_id is None or dist > node_distance:
                nearest_node_id = node_id
                dist = node_distance

        if query[axis] < point[axis]:
            side_node = left
            side_look = right
        else:
            side_node = right
            side_look = left

        if side_node is not None:
            stack_node.append(side_node)

        if side_look is not None:
            stack_look.append(side_look)

    return nearest_node_id, dist