<commit_before>#include "../search/search.hpp"
#include "../structs/binheap.hpp"
#include "../utils/pool.hpp"
#include <limits>
#include <vector>
#include <cmath>

void dfrowhdr(FILE*, const char*, unsigned int ncols, ...);
void dfrow(FILE*, const char*, const char*, ...);
void fatal(const char*, ...);

template <class D> struct Arastar : public SearchAlgorithm<D> {

	typedef typename D::State State;
	typedef typename D::PackedState PackedState;
	typedef typename D::Cost Cost;
	typedef typename D::Oper Oper;

	struct Node : SearchNode<D> {
		Cost h;
		double fprime;
	
		static bool pred(Node *a, Node *b) {
			if (a->fprime == b->fprime)
				return a->g > b->g;
			return a->fprime < b->fprime;
		}
	};
	
	struct Incons {
		Incons(unsigned long szhint) : mem(szhint) { }
	
		void init(D &d) { mem.init(d); }
	
		void add(Node *n, unsigned long h) {
			if (mem.find(n->packed, h) != NULL)
				return;
			mem.add(n);
			incons.push_back(n);
		}
	
		std::vector<Node*> &nodes() { return incons; }
	
		void clear() {
			mem.clear();
			incons.clear();
		}
	
	private:
	 	ClosedList<SearchNode<D>, SearchNode<D>, D> mem;
		std::vector<Node*> incons;
	};

	Arastar(int argc, const char *argv[]) :
			SearchAlgorithm<D>(argc, argv), closed(30000001),
			incons(30000001), cost(-1) {

		wt0 = dwt = -1;
		for (int i = 0; i < argc; i++) {
			if (i < argc - 1 && strcmp(argv[i], "-wt0") == 0)
				wt0 = strtod(argv[++i], NULL);
			else if (i < argc - 1 && strcmp(argv[i], "-dwt") == 0)
				dwt = strtod(argv[++i], NULL);
		}

		if (wt0 < 1)
			fatal("Must specify initial weight ≥ 1 using -wt0");
		if (dwt <= 0)
			fatal("Must specify weight decrement > 0 using -dwt");

		wt = wt0;
		nodes = new Pool<Node>();
	}

	~Arastar() {
		delete nodes;
	}

	void search(D &d, typename D::State &s0) {
		this->start();
		closed.init(d);
		incons.init(d);

		dfrowhdr(stdout, "sol", 7, "num", "nodes expanded",
			"nodes generated", "weight", "solution bound", "solution cost",
			"wall time");


		Node *n0 = init(d, s0);
		closed.add(n0);
		open.push(n0);

		unsigned long n = 0;
		do {
			if (improve(d)) {
				n++;
				double epsprime = wt == 1.0 ? 1.0 : findbound();
				if (wt < epsprime)
					epsprime = wt;
	
				dfrow(stdout, "sol", "uuugggg", n, this->res.expd,
					this->res.gend, wt, epsprime, cost,
					walltime() - this->res.wallstrt);
			}

			if (wt <= 1.0)
				break;

			wt = wt - dwt > 1.0 ? wt - dwt : 1.0;
			if (wt < 1.0 + sqrt(std::numeric_limits<double>::epsilon()))
				wt = 1.0;

			updateopen();
			closed.clear();

		} while(!this->limit() && !open.empty());

		this->finish();
	}

	virtual void reset() {
		SearchAlgorithm<D>::reset();
		wt = wt0;
		open.clear();
		closed.clear();
		incons.clear();
		delete nodes;
		nodes = new Pool<Node>();
		cost = Cost(-1);
	}

	virtual void output(FILE *out) {
		SearchAlgorithm<D>::output(out);
		closed.prstats(stdout, "closed ");
		dfpair(stdout, "open list type", "%s", "binary heap");
		dfpair(stdout, "node size", "%u", sizeof(Node));
		dfpair(stdout, "initial weight", "%g", wt0);
		dfpair(stdout, "weight decrement", "%g", dwt);
	}<commit_msg>arastar: print if optimality was proven.<commit_after>#include "../search/search.hpp"
#include "../structs/binheap.hpp"
#include "../utils/pool.hpp"
#include <limits>
#include <vector>
#include <cmath>

void dfrowhdr(FILE*, const char*, unsigned int ncols, ...);
void dfrow(FILE*, const char*, const char*, ...);
void fatal(const char*, ...);

template <class D> struct Arastar : public SearchAlgorithm<D> {

	typedef typename D::State State;
	typedef typename D::PackedState PackedState;
	typedef typename D::Cost Cost;
	typedef typename D::Oper Oper;

	struct Node : SearchNode<D> {
		Cost h;
		double fprime;
	
		static bool pred(Node *a, Node *b) {
			if (a->fprime == b->fprime)
				return a->g > b->g;
			return a->fprime < b->fprime;
		}
	};
	
	struct Incons {
		Incons(unsigned long szhint) : mem(szhint) { }
	
		void init(D &d) { mem.init(d); }
	
		void add(Node *n, unsigned long h) {
			if (mem.find(n->packed, h) != NULL)
				return;
			mem.add(n);
			incons.push_back(n);
		}
	
		std::vector<Node*> &nodes() { return incons; }
	
		void clear() {
			mem.clear();
			incons.clear();
		}
	
	private:
	 	ClosedList<SearchNode<D>, SearchNode<D>, D> mem;
		std::vector<Node*> incons;
	};

	Arastar(int argc, const char *argv[]) :
			SearchAlgorithm<D>(argc, argv), closed(30000001),
			incons(30000001), cost(-1) {

		wt0 = dwt = -1;
		for (int i = 0; i < argc; i++) {
			if (i < argc - 1 && strcmp(argv[i], "-wt0") == 0)
				wt0 = strtod(argv[++i], NULL);
			else if (i < argc - 1 && strcmp(argv[i], "-dwt") == 0)
				dwt = strtod(argv[++i], NULL);
		}

		if (wt0 < 1)
			fatal("Must specify initial weight ≥ 1 using -wt0");
		if (dwt <= 0)
			fatal("Must specify weight decrement > 0 using -dwt");

		wt = wt0;
		nodes = new Pool<Node>();
	}

	~Arastar() {
		delete nodes;
	}

	void search(D &d, typename D::State &s0) {
		bool optimal = false;
		this->start();
		closed.init(d);
		incons.init(d);

		dfrowhdr(stdout, "sol", 7, "num", "nodes expanded",
			"nodes generated", "weight", "solution bound", "solution cost",
			"wall time");


		Node *n0 = init(d, s0);
		closed.add(n0);
		open.push(n0);

		unsigned long n = 0;
		do {
			if (improve(d)) {
				n++;
				double epsprime = wt == 1.0 ? 1.0 : findbound();
				if (wt < epsprime)
					epsprime = wt;
	
				dfrow(stdout, "sol", "uuugggg", n, this->res.expd,
					this->res.gend, wt, epsprime, cost,
					walltime() - this->res.wallstrt);
			}

			if (wt <= 1.0) {
				optimal = true;
				break;
			}

			wt = wt - dwt > 1.0 ? wt - dwt : 1.0;
			if (wt < 1.0 + sqrt(std::numeric_limits<double>::epsilon()))
				wt = 1.0;

			updateopen();
			closed.clear();

		} while(!this->limit() && !open.empty());

		this->finish();
		dfpair(stdout, "optimality proven", "%s", optimal ? "yes" : "no");
	}

	virtual void reset() {
		SearchAlgorithm<D>::reset();
		wt = wt0;
		open.clear();
		closed.clear();
		incons.clear();
		delete nodes;
		nodes = new Pool<Node>();
		cost = Cost(-1);
	}

	virtual void output(FILE *out) {
		SearchAlgorithm<D>::output(out);
		closed.prstats(stdout, "closed ");
		dfpair(stdout, "open list type", "%s", "binary heap");
		dfpair(stdout, "node size", "%u", sizeof(Node));
		dfpair(stdout, "initial weight", "%g", wt0);
		dfpair(stdout, "weight decrement", "%g", dwt);
	}
{'fraction_non_alphanumeric': 0.19522538087011151, 'fraction_numerical': 0.017904821737081827, 'mean_word_length': 3.206076618229855, 'pattern_counts': {'":': 0, '<': 55, '<?xml version=': 0, '>': 69, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1503271', 'n_tokens_mistral': 2847, 'n_tokens_neox': 2405, 'n_words': 633}