# Path: misc/functions.py
# def elapsed_time(start_time):
#   return time.time() - start_time
# 
# def first(function, iterable):
#   for item in iterable:
#     if function(item):
#       return item
#   return None
# 
# Path: misc/priority_queue.py
# class FILOPriorityQueue(PriorityQueue):
#   sign = -1
# 
# class FIFOPriorityQueue(PriorityQueue):
#   sign = 1
# 
# 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


from misc.functions import elapsed_time, first
from misc.priority_queue import FILOPriorityQueue, FIFOPriorityQueue
from planner.state_space import StateSpace


def semideferred_best_first_search(start, goal, generator, priority, stack, max_time, max_iterations,
                                   max_generations, max_cost, max_length, debug):
  # TODO: variants that don't add states to the search queue until parent revisited
  state_space = StateSpace(generator, start, 1, max_generations, max_cost, max_length)
  sv = state_space.root
  if sv.contained(goal):
    return state_space.plan(sv), state_space
  queue = (FILOPriorityQueue if stack else FIFOPriorityQueue)([(None, sv)])
  while not queue.empty() and (elapsed_time(state_space.start_time) < max_time) \

# Path: misc/functions.py
# def elapsed_time(start_time):
#   return time.time() - start_time
# 
# def first(function, iterable):
#   for item in iterable:
#     if function(item):
#       return item
#   return None
# 
# Path: misc/priority_queue.py
# class FILOPriorityQueue(PriorityQueue):
#   sign = -1
# 
# class FIFOPriorityQueue(PriorityQueue):
#   sign = 1
# 
# 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: planner/progression/retired/experimental.py
from misc.functions import elapsed_time, first
from misc.priority_queue import FILOPriorityQueue, FIFOPriorityQueue
from planner.state_space import StateSpace



def semideferred_best_first_search(start, goal, generator, priority, stack, max_time, max_iterations,
                                   max_generations, max_cost, max_length, debug):
  # TODO: variants that don't add states to the search queue until parent revisited
  state_space = StateSpace(generator, start, 1, max_generations, max_cost, max_length)
  sv = state_space.root
  if sv.contained(goal):
    return state_space.plan(sv), state_space
  queue = (FILOPriorityQueue if stack else FIFOPriorityQueue)([(None, sv)])
  while not queue.empty() and (elapsed_time(state_space.start_time) < max_time) \

          and (state_space.iterations < max_iterations):