"""
This module contains the data_structures used in py_search. In particular, it
contains the the :class:`Problem` class, which is used to represent the
different search problems, and the :class:`AnnotatedProblem` class, which wraps
around a specific problem and keeps track of the number of core method calls.

At a lower level this module also contains the :class:`Node` class, which is
used to represent a node in the search space.

Finally, the module contains the :class:`Fringe` class, and its instantiations
(:class:`FIFOQueue`, :class:`LIFOQueue`, and :class:`PrioritySet`). A Fringe is
used to structure the way a search space is explored.
"""
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import absolute_import
from __future__ import division

from collections import deque
from random import choice
from bisect import insort


class Problem(object):
    """
    The basic problem to solve. The main functions that must be defined include
    successors and goal_test. Some search techniques also require the
    random_successor and predecessors methods to be implemented.
    """

    def __init__(self, initial, goal=None, initial_cost=0, extra=None):
        self.initial = Node(initial, None, None, initial_cost, extra=extra)
        self.goal = GoalNode(goal)

    def node_value(self, node):
        """
        Returns the the value of the current node. This is the value being
        minimized by the search. By default the cost is used, but this
        function can be overloaded to include a heuristic.
        """
        return node.cost()

    def predecessors(self, node):
        """
        An iterator that yields all of the predecessors of the current goal.
        """
        raise NotImplementedError("No predecessors function implemented")

    def successors(self, node):
        """
        An iterator that yields all of the successors of the current node.
        """
        raise NotImplementedError("No successors function implemented")

    def random_successor(self, node):
        """
        This method should return a single successor node. This is used
        by some of the search techniques. By default, this just computes all of
        the successors and randomly samples one. This default approach is not
        very efficient, but this funciton can be overridden to generate a
        single successor more efficiently.
        """
        return choice([s for s in self.successors(node)])

    def random_node(self):
        """