# Path: planner/progression/utils.py
# def pop_random(queue):
#     queue.rotate(randint(0, len(queue) - 1))
#     return queue.popleft()
# 
# def pop_rrt(distance, sample, goal_sample=None, goal_probability=DEFAULT_GOAL_PROBABILITY):
#     return lambda queue: pop_min(
#         queue, lambda sv: distance(sv.state, sample_target(
#             sample, goal_sample=goal_sample, goal_probability=goal_probability)))
# 
# Path: planner/state_space.py
# class StateSpace(object):
#     def __init__(self, generator_fn, start, max_extensions=INF, max_generations=INF, max_cost=INF, max_length=INF,
#                  max_time=INF, max_iterations=INF, verbose=True, dump_rate=1.): # 0 | 1 | INF
#         # TODO: move queue here?
#         self.start_time = time.time()
#         self.iterations = 0
#         self.num_expanded = 0
#         self.num_generations = 0
#         self.vertices = {}
#         self.edges = [] # NOTE - allowing parallel-edges
#         #self.solutions = []
#         if isinstance(generator_fn, tuple): # TODO - fix this by making the operators a direct argument
#             self.generator_fn, self.axioms = generator_fn
#         else:
#             self.generator_fn, self.axioms = generator_fn, []
#         # TODO: could check whether these are violated generically
#         self.max_extensions = max_extensions
#         self.max_generations = max_generations
#         self.max_cost = max_cost
#         self.max_length = max_length
#         self.max_time = max_time
#         self.max_iterations = max_iterations
#         self.verbose = verbose
#         self.dump_rate = dump_rate
#         self.last_dump = time.time()
#         self.root = self[start]
#         self.root.cost = 0
#         self.root.length = 0
#         self.root.extensions += 1
#         self.best_h = None # None | INF
#     def has_state(self, state):
#         return state in self.vertices
#     __contains__ = has_state
#     def get_state(self, state):
#         if state not in self:
#             self.vertices[state] = Vertex(state, self)
#         return self.vertices[state]
#     __getitem__ = get_state
#     def __iter__(self):
#         return iter(self.vertices.values())
#     def __len__(self):
#         return len(self.vertices)
#     def new_iteration(self, vertex):
#         self.iterations += 1
#         if elapsed_time(self.last_dump) >= self.dump_rate:
#             self.dump()
#         # TODO: record dead ends here
#         #return vertex.is_dead_end() # TODO: might not have called h_cost
#     def is_active(self):
#         return (elapsed_time(self.start_time) < self.max_time) or (self.iterations < self.max_iterations)
#     def extend(self, vertex, operator):
#         if (vertex.cost + operator.cost <= self.max_cost) \
#                 and (vertex.length + len(operator) <= self.max_length) \
#                 and vertex.contained(operator):
#             #if vertex.state in operator:
#             if self.axioms:
#                 assert not isinstance(operator, MacroOperator)
#                 sink_state = operator.apply(vertex.state) # TODO - this won't work for MacroOperators yet?
#             else:
#                 sink_state = operator(vertex.state)[-1] if isinstance(operator, MacroOperator) else operator(vertex.state)
#             if (sink_state is not None) and (self[sink_state].extensions < self.max_extensions):
#                 sink_vertex = self[sink_state]
#                 self.edges.append(Edge(vertex, sink_vertex, operator, self))
#                 sink_vertex.extensions += 1
#                 return sink_vertex
#         return None
#     def retrace(self, vertex):
#         if vertex is not None:
#             if vertex == self.root:
#                 return []
#             sequence = self.retrace(vertex.parent_edge.source)
#             if sequence is not None:
#                 return sequence + list(vertex.parent_edge.operator)
#         return None
#     def plan(self, vertex):
#         sequence = self.retrace(vertex)
#         if sequence is None:
#             return None
#         return Plan(self.root.state, sequence)
#     def solution(self, vertex):
#         #self.dump()
#         return Solution(self.plan(vertex), self)
#     def failure(self):
#         self.dump()
#         return Solution(None, self)
#     def time_elapsed(self):
#         return elapsed_time(self.start_time)
#     def __repr__(self):
#      # TODO: deadends, backtracking, expanded/generated until last jump, etc.
#         return 'Iterations: {iterations} | State Space: {state_space} | Expanded: {expanded} | ' \
#                'Generations: {generations} | Heuristic: {heuristic} | Time: {time:.3f}'.format(
#             iterations=self.iterations, state_space=len(self), expanded=self.num_expanded,
#             generations=self.num_generations, heuristic=self.best_h, time=self.time_elapsed())
#     def dump(self):
#         if not self.verbose:
#             return
#         self.last_dump = time.time()
#         print(self)
#         # TODO: record iterations since last heuristic
# 
# Path: misc/functions.py
# def elapsed_time(start_time):
#   return time.time() - start_time


from collections import deque
from .utils import pop_random, pop_rrt
from ..state_space import StateSpace
from misc.functions import elapsed_time
        if debug is not None:
            debug(cv)

        while cv.generate():  # TODO: generate_all
            pass
        if cv.h_cost is None:
            break
        for nv in cv.unexplored():  # TODO - should reverse order for DFS
            if nv.contained(goal):
                return space.solution(nv)
            queue.append(nv)
    return space.failure()


##################################################

def dfs(*args):
    return simple_search(lambda queue: queue.pop(), *args)


def bfs(*args):
    return simple_search(lambda queue: queue.popleft(), *args)


def srandom_walk(*args):
    return simple_search(pop_random, *args)


def srrt(start, goal, generator, max_time, max_iterations, max_generations, max_cost, max_length, debug,
         distance, sample, goal_sample, goal_probability):

# Path: planner/progression/utils.py
# def pop_random(queue):
#     queue.rotate(randint(0, len(queue) - 1))
#     return queue.popleft()
# 
# def pop_rrt(distance, sample, goal_sample=None, goal_probability=DEFAULT_GOAL_PROBABILITY):
#     return lambda queue: pop_min(
#         queue, lambda sv: distance(sv.state, sample_target(
#             sample, goal_sample=goal_sample, goal_probability=goal_probability)))
# 
# Path: planner/state_space.py
# class StateSpace(object):
#     def __init__(self, generator_fn, start, max_extensions=INF, max_generations=INF, max_cost=INF, max_length=INF,
#                  max_time=INF, max_iterations=INF, verbose=True, dump_rate=1.): # 0 | 1 | INF
#         # TODO: move queue here?
#         self.start_time = time.time()
#         self.iterations = 0
#         self.num_expanded = 0
#         self.num_generations = 0
#         self.vertices = {}
#         self.edges = [] # NOTE - allowing parallel-edges
#         #self.solutions = []
#         if isinstance(generator_fn, tuple): # TODO - fix this by making the operators a direct argument
#             self.generator_fn, self.axioms = generator_fn
#         else:
#             self.generator_fn, self.axioms = generator_fn, []
#         # TODO: could check whether these are violated generically
#         self.max_extensions = max_extensions
#         self.max_generations = max_generations
#         self.max_cost = max_cost
#         self.max_length = max_length
#         self.max_time = max_time
#         self.max_iterations = max_iterations
#         self.verbose = verbose
#         self.dump_rate = dump_rate
#         self.last_dump = time.time()
#         self.root = self[start]
#         self.root.cost = 0
#         self.root.length = 0
#         self.root.extensions += 1
#         self.best_h = None # None | INF
#     def has_state(self, state):
#         return state in self.vertices
#     __contains__ = has_state
#     def get_state(self, state):
#         if state not in self:
#             self.vertices[state] = Vertex(state, self)
#         return self.vertices[state]
#     __getitem__ = get_state
#     def __iter__(self):
#         return iter(self.vertices.values())
#     def __len__(self):
#         return len(self.vertices)
#     def new_iteration(self, vertex):
#         self.iterations += 1
#         if elapsed_time(self.last_dump) >= self.dump_rate:
#             self.dump()
#         # TODO: record dead ends here
#         #return vertex.is_dead_end() # TODO: might not have called h_cost
#     def is_active(self):
#         return (elapsed_time(self.start_time) < self.max_time) or (self.iterations < self.max_iterations)
#     def extend(self, vertex, operator):
#         if (vertex.cost + operator.cost <= self.max_cost) \
#                 and (vertex.length + len(operator) <= self.max_length) \
#                 and vertex.contained(operator):
#             #if vertex.state in operator:
#             if self.axioms:
#                 assert not isinstance(operator, MacroOperator)
#                 sink_state = operator.apply(vertex.state) # TODO - this won't work for MacroOperators yet?
#             else:
#                 sink_state = operator(vertex.state)[-1] if isinstance(operator, MacroOperator) else operator(vertex.state)
#             if (sink_state is not None) and (self[sink_state].extensions < self.max_extensions):
#                 sink_vertex = self[sink_state]
#                 self.edges.append(Edge(vertex, sink_vertex, operator, self))
#                 sink_vertex.extensions += 1
#                 return sink_vertex
#         return None
#     def retrace(self, vertex):
#         if vertex is not None:
#             if vertex == self.root:
#                 return []
#             sequence = self.retrace(vertex.parent_edge.source)
#             if sequence is not None:
#                 return sequence + list(vertex.parent_edge.operator)
#         return None
#     def plan(self, vertex):
#         sequence = self.retrace(vertex)
#         if sequence is None:
#             return None
#         return Plan(self.root.state, sequence)
#     def solution(self, vertex):
#         #self.dump()
#         return Solution(self.plan(vertex), self)
#     def failure(self):
#         self.dump()
#         return Solution(None, self)
#     def time_elapsed(self):
#         return elapsed_time(self.start_time)
#     def __repr__(self):
#      # TODO: deadends, backtracking, expanded/generated until last jump, etc.
#         return 'Iterations: {iterations} | State Space: {state_space} | Expanded: {expanded} | ' \
#                'Generations: {generations} | Heuristic: {heuristic} | Time: {time:.3f}'.format(
#             iterations=self.iterations, state_space=len(self), expanded=self.num_expanded,
#             generations=self.num_generations, heuristic=self.best_h, time=self.time_elapsed())
#     def dump(self):
#         if not self.verbose:
#             return
#         self.last_dump = time.time()
#         print(self)
#         # TODO: record iterations since last heuristic
# 
# Path: misc/functions.py
# def elapsed_time(start_time):
#   return time.time() - start_time


# Path: planner/progression/simple.py
from collections import deque
from .utils import pop_random, pop_rrt
from ..state_space import StateSpace
from misc.functions import elapsed_time

        if debug is not None:
            debug(cv)

        while cv.generate():  # TODO: generate_all
            pass
        if cv.h_cost is None:
            break
        for nv in cv.unexplored():  # TODO - should reverse order for DFS
            if nv.contained(goal):
                return space.solution(nv)
            queue.append(nv)
    return space.failure()


##################################################

def dfs(*args):
    return simple_search(lambda queue: queue.pop(), *args)


def bfs(*args):
    return simple_search(lambda queue: queue.popleft(), *args)


def srandom_walk(*args):
    return simple_search(pop_random, *args)


def srrt(start, goal, generator, max_time, max_iterations, max_generations, max_cost, max_length, debug,
         distance, sample, goal_sample, goal_probability):

    return simple_search(pop_rrt(distance, sample, goal_sample, goal_probability), start, goal, generator,