<commit_before>#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <float.h>
#include <string.h>
#include "svm.h"
template <class T> inline T min(T x,T y) { return (x<y)?x:y; }
template <class T> inline T max(T x,T y) { return (x>y)?x:y; }
#define EPS_A 1e-12
#define INF DBL_MAX

// Kernel Cache
class Cache
{
private:
	int l;
	int size;
	struct head_t
	{
		head_t *prev, *next;	// a cicular list
		int index;
		double *data;
	};

	head_t* head;
	head_t* lru_head;
	head_t** index_to_head;
	void move_to_last(head_t *h);
public:
	Cache(int _l,int _size);
	~Cache();

	// return 1 if returned data is valid (cache hit)
	// return 0 if returned data needs to be filled (cache miss)
	int get_data(const int index,double **data);
};

Cache::Cache(int _l,int _size):l(_l),size(_size)
{
	head = new head_t[size];
	int i;
	for(i=0;i<size;i++)
	{
		head[i].next = &head[i+1];
		head[i].prev = &head[i-1];
		head[i].index = -1;
		head[i].data = new double[l];
	}

	head[0].prev = &head[size-1];
	head[size-1].next = &head[0];
	lru_head = &head[0];

	index_to_head = new head_t *[l];
	for(i=0;i<l;i++)
		index_to_head[i] = 0;
}

Cache::~Cache()
{
	for(int i=0;i<size;i++)
		delete[] head[i].data;
	delete[] head;
	delete[] index_to_head;
}

void Cache::move_to_last(head_t *h)
{
	if(lru_head == h)
		lru_head = lru_head->next;
	else
	{
		// delete from current location
		h->prev->next = h->next;
		h->next->prev = h->prev;

		// insert to last position
		h->next = lru_head;
		h->prev = lru_head->prev;
		h->prev->next = h;
		h->next->prev = h;
	}
}

int Cache::get_data(const int index,double **data)
{
	head_t *h=index_to_head[index];
	if(h)
	{
		move_to_last(h);
		*data = h->data;
		return 1;
	}		
	else
	{
		// get one from lru_head
		h = lru_head;
		lru_head = lru_head->next;
		if(h->index!=-1)
			index_to_head[h->index] = 0;
		h->index = index;
		index_to_head[index] = h;
		*data = h->data;
		return 0;
	}
}

// dot

static double dot(const svm_node *px, const svm_node *py)
{
	double sum = 0;
	while(px->index != -1 && py->index != -1)
	{
		if(px->index == py->index)
		{
			sum += px->value * py->value;
			++px;
			++py;
		}
		else
		{
			if(px->index > py->index)
				++py;
			else
				++px;
		}			
	}
	return sum;
}

// The Q Matrix
class Kernel {
private:
	// svm_problem
	const int l;
	const svm_node * const * const x;
	const signed char *y;

	// svm_parameter
	const int kernel_type;
	const double degree;
	const double gamma;
	const double coef0;

	Cache *cache;
	double *x_square;
	double (Kernel::*kernel_function)(int i, int j) const;
	double kernel_linear(int i, int j) const
	{
		return dot(x[i],x[j]);
	}
	double kernel_poly(int i, int j) const
	{
		return pow(gamma*dot(x[i],x[j])+coef0,degree);
	}
	double kernel_rbf(int i, int j) const
	{
		return exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));
	}
	double kernel_sigmoid(int i, int j) const
	{
		return tanh(gamma*dot(x[i],x[j])+coef0);
	}
public:
	Kernel(const svm_problem& prob, const svm_parameter& param);
	~Kernel();
	double *get_Q(int i) const;
};

Kernel::Kernel(const svm_problem& prob, const svm_parameter& param)
:l(prob.l),x(prob.x),y(prob.y),
 kernel_type(param.kernel_type),degree(param.degree),gamma(param.gamma),
 coef0(param.coef0)
{
	cache = new Cache(l,(int)min((double)l,(param.cache_size*(1<<20))/(sizeof(double)*l)));

	switch(kernel_type)
	{
		case LINEAR:
			kernel_function = kernel_linear;
			break;
		case POLY:
			kernel_function = kernel_poly;
			break;
		case RBF:
			kernel_function = kernel_rbf;
			break;
		case SIGMOID:
			kernel_function = kernel_sigmoid;
			break;
		default:
			fprintf(stderr,"unknown kernel function.\n");
			exit(1);
	}

	if(kernel_type == RBF)
	{
		x_square = new double[l];
		for(int i=0;i<l;i++)
			x_square[i] = dot(x[i],x[i]);
	}
	else
		x_square = 0;
}

Kernel::~Kernel()
{
	delete x_square;
	delete cache;
}

double *Kernel::get_Q(int i) const
{
	double *data;
	if(cache->get_data(i,&data)==0)
	{
		for(int j=0;j<l;j++)
			data[j] = y[i]*y[j]*(this->*kernel_function)(i,j);
	}<commit_msg>libsvm-1.01<commit_after>#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <float.h>
#include <string.h>
#include "svm.h"
template <class T> inline T min(T x,T y) { return (x<y)?x:y; }
template <class T> inline T max(T x,T y) { return (x>y)?x:y; }
#define EPS_A 1e-12
#define INF DBL_MAX

// Kernel Cache
class Cache
{
private:
	int l;
	int size;
	struct head_t
	{
		head_t *prev, *next;	// a cicular list
		int index;
		double *data;
	};

	head_t* head;
	head_t* lru_head;
	head_t** index_to_head;
	void move_to_last(head_t *h);
public:
	Cache(int _l,int _size);
	~Cache();

	// return 1 if returned data is valid (cache hit)
	// return 0 if returned data needs to be filled (cache miss)
	int get_data(const int index,double **data);
};

Cache::Cache(int _l,int _size):l(_l),size(_size)
{
	head = new head_t[size];
	int i;
	for(i=0;i<size;i++)
	{
		head[i].next = &head[i+1];
		head[i].prev = &head[i-1];
		head[i].index = -1;
		head[i].data = new double[l];
	}

	head[0].prev = &head[size-1];
	head[size-1].next = &head[0];
	lru_head = &head[0];

	index_to_head = new head_t *[l];
	for(i=0;i<l;i++)
		index_to_head[i] = 0;
}

Cache::~Cache()
{
	for(int i=0;i<size;i++)
		delete[] head[i].data;
	delete[] head;
	delete[] index_to_head;
}

void Cache::move_to_last(head_t *h)
{
	if(lru_head == h)
		lru_head = lru_head->next;
	else
	{
		// delete from current location
		h->prev->next = h->next;
		h->next->prev = h->prev;

		// insert to last position
		h->next = lru_head;
		h->prev = lru_head->prev;
		h->prev->next = h;
		h->next->prev = h;
	}
}

int Cache::get_data(const int index,double **data)
{
	head_t *h=index_to_head[index];
	if(h)
	{
		move_to_last(h);
		*data = h->data;
		return 1;
	}		
	else
	{
		// get one from lru_head
		h = lru_head;
		lru_head = lru_head->next;
		if(h->index!=-1)
			index_to_head[h->index] = 0;
		h->index = index;
		index_to_head[index] = h;
		*data = h->data;
		return 0;
	}
}

// dot

static double dot(const svm_node *px, const svm_node *py)
{
	double sum = 0;
	while(px->index != -1 && py->index != -1)
	{
		if(px->index == py->index)
		{
			sum += px->value * py->value;
			++px;
			++py;
		}
		else
		{
			if(px->index > py->index)
				++py;
			else
				++px;
		}			
	}
	return sum;
}

// The Q Matrix
class Kernel {
private:
	// svm_problem
	const int l;
	const svm_node * const * const x;
	const signed char *y;

	// svm_parameter
	const int kernel_type;
	const double degree;
	const double gamma;
	const double coef0;

	Cache *cache;
	double *x_square;
	double (Kernel::*kernel_function)(int i, int j) const;
	double kernel_linear(int i, int j) const
	{
		return dot(x[i],x[j]);
	}
	double kernel_poly(int i, int j) const
	{
		return pow(gamma*dot(x[i],x[j])+coef0,degree);
	}
	double kernel_rbf(int i, int j) const
	{
		return exp(-gamma*(x_square[i]+x_square[j]-2*dot(x[i],x[j])));
	}
	double kernel_sigmoid(int i, int j) const
	{
		return tanh(gamma*dot(x[i],x[j])+coef0);
	}
public:
	Kernel(const svm_problem& prob, const svm_parameter& param);
	~Kernel();
	double *get_Q(int i) const;
};

Kernel::Kernel(const svm_problem& prob, const svm_parameter& param)
:l(prob.l),x(prob.x),y(prob.y),
 kernel_type(param.kernel_type),degree(param.degree),gamma(param.gamma),
 coef0(param.coef0)
{
	cache = new Cache(l,(int)min((double)l,(param.cache_size*(1<<20))/(sizeof(double)*l)));

	switch(kernel_type)
	{
		case LINEAR:
			kernel_function = &Kernel::kernel_linear;
			break;
		case POLY:
			kernel_function = &Kernel::kernel_poly;
			break;
		case RBF:
			kernel_function = &Kernel::kernel_rbf;
			break;
		case SIGMOID:
			kernel_function = &Kernel::kernel_sigmoid;
			break;
		default:
			fprintf(stderr,"unknown kernel function.\n");
			exit(1);
	}

	if(kernel_type == RBF)
	{
		x_square = new double[l];
		for(int i=0;i<l;i++)
			x_square[i] = dot(x[i],x[i]);
	}
	else
		x_square = 0;
}

Kernel::~Kernel()
{
	delete x_square;
	delete cache;
}

double *Kernel::get_Q(int i) const
{
	double *data;
	if(cache->get_data(i,&data)==0)
	{
		for(int j=0;j<l;j++)
			data[j] = y[i]*y[j]*(this->*kernel_function)(i,j);
	}
{'fraction_non_alphanumeric': 0.18137254901960784, 'fraction_numerical': 0.009681372549019608, 'mean_word_length': 3.803413772807534, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 83, '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': '4339644', 'n_tokens_mistral': 3814, 'n_tokens_neox': 3565, 'n_words': 768}