def depth_limited_search_IDA(problem, h = None, limit=0):
    "depth first search with limited depth"
    h = memoize(h or problem.h, 'h')
    def recursive_dls(node,problem,limit):
        (result,nlimit) = recursive_dls_pom(node,problem,limit)
        if(result=='cutoff'):
           return recursive_dls(node,problem,nlimit)
        return result

    def recursive_dls_pom(node, problem, limit):
        "helper function for depth limited"


        if problem.goal_test(node.state):
            return (node,limit)
        else:
            if(h(node)+node.path_cost <= limit):
                list = node.expand(problem)
                #init with max integer number
                minlimit = sys.maxsize
                for successor in list: #[lista for lista in list if lista.path_cost + h(lista) <= limit]:
                    (result,limitt) = recursive_dls_pom(successor, problem, limit)
                    if(limitt<minlimit):
                        minlimit=limitt
                #if result == 'cutoff':
                #    cutoff_occurred = True
                #if result > limit:
                #    limit = result.path_cost + h(result)

                    #recursive_dls(result, problem, result.path_cost + h(result))
                    if result != None:
                        return (result,minlimit)
                return ('cutoff',minlimit)
            else:
                return (None,h(node)+node.path_cost)

        #if cutoff_occurred:
        #   return 'cutoff'
        #else:
        #    return None

    # Body of depth_limited_search:
    return recursive_dls(Node(problem.initial), problem, limit)

def idastar_search(problem, h=None):
    h = memoize(h or problem.h, 'h')
    return depth_limited_search_IDA(problem, h)


'''
#idaStar prebaruvanje

#def depth_limited_search2(problem, limit=50):
#    "depth first search with limited depth"

#    def recursive_dls(node, problem, limit):
#        "helper function for depth limited"
#        cutoff_occurred = False
#        if problem.goal_test(node.state):
#            return node
   # limitot treba da e pathcost + heuristika
#        elif node.f >= limit:
#            return 'cutoff'
#        else:
#            for successor in node.expand(problem):
#                result = recursive_dls(successor, problem, limit)
#                if result == 'cutoff':
#                    cutoff_occurred = True
#                elif result != None:
#                    return result
#        if cutoff_occurred:
#            return 'cutoff'
#        else:
#            return None

    # Body of depth_limited_search:
#    return recursive_dls(Node(problem.initial), problem, limit)

#def depth_limited(problem, h = None):

 #   def RBFS(problem, node, flimit):
 #       if problem.goal_test(node.state):
 #           return node, 0  # (The second value is immaterial)
 #       successors = node.expand(problem)
 #       if len(successors) == 0:
 #          return None, infinity
 #       for s in successors:
 #           s.f = max(s.path_cost + h(s), node.f)
 #       while True:
 #           # Order by lowest f value
 #           successors.sort(key=lambda x: x.f)
 #           best = successors[0]
 #           if best.f > flimit:
  #              return None, best.f
 #           if len(successors) > 1:
 #               alternative = successors[1].f
 #           else:
 #               alternative = infinity
 #           result, best.f = RBFS(problem, best, min(flimit, alternative))
 #           if result is not None:
 #               return result, best.f
'''