nfa_NP

nfa_.h

#ifndef ushort
#define ushort unsigned short
#endif

using namespace std;
/* 6 bytes */
typedef struct state {
	ushort From;
	char On;
	ushort To;
} state;

typedef struct  link {
	state * L;
	state * R;
	link * ex;
} link;

/*  16 bytes */
typedef struct  frag {
	ushort handle;
	ushort offset;
	link * trans;
} frag;

inline ostream &operator<<(std::ostream &out, const state &p) {
	out << p.From << " " << p.On << (p.On == 0x0 ? "*" : "") << " " << p.To;
	return out;
}

state  _set(ushort f, char o, ushort t, double * hash) {
	state n;
	n.From = f;
	n.On = o;
	n.To = t;

	*hash = (*hash + f * 3 + o * 5 + t * 7) / 2;
	return n;
}

ushort code(char c) { return c; }
char code(ushort c) { return c; }

nfa_NP.cpp

//#include "stdafx.h"
/* notes
* an 'on' code of 0x0 (null) will represent an epsilon transition
* all the search algorithms are NOT optimized, i wrote this on a plane
*/
#include <iostream>
#include <string>
#include <cstdlib>
#include "nfa_NP.h"

#ifndef ushort
#define ushort unsigned short
#endif

using namespace std;

void subset(state * s, ushort f, int * pos);
void subset(state * s, ushort f, char o, int * pos);

const int entry = 2;
const int num_states = 8;
const ushort f[8] = { 2, 2, 2, 2, 4, 3, 3, 1 };
const char   o[8] = { 'a', 0x0, 'b', 'a', 'a', 'b', 'b', 0x0 };
const ushort t[8] = { 2, 4, 3, 1, 3, 3, 1, 2 };

bool contains(state *s1, state *s2)
{
	for (int i = 0; i < sizeof(s1); i++)
	for (int x = 0; x < sizeof(s2); x++)
	if (&s1[i] == &s2[x]) return true;
	return false;
}

int difference(state ** s1, state ** s2, state ** ret, int pos) {
	bool add = true;
	int p = 0;
	for (int i = 0; i < 8; i++) {
		for (int x = 0; x < pos + 1; x++)
			if (s1[i] == s2[x])
				add = false;

		if (add)
		{
			ret[p] = s1[i];
			add = true;
			p++;
		}
	}
	return p;
}



void subset(state ** s1, state ** s2, state * ctx, int * size1, int * size2) {
	for (int i = 0; i < *size1; i++)
	{
		if ((*s1)[i].From != ctx->To)
			continue;
		
		if( (*s1[i]).On != 0x0 )
		{	/* All non epsilon */
			s2[*size2] = s1[i];
			(*size2)++;
		}
		else
		{
			int length = *size2;
			state * result[num_states];
			state * compare[num_states];
			length = difference( s1, s2, result, *size2 );
			int x = 0;
			subset( result, compare, s1[i], &length, &x );
			cout << x << endl;
		}
	}
}


void inference( state ** s ) {
	//char * cursor = h, *offset = h;

	int l_size = num_states;
	
	for (int i = 0; i < num_states; i++)
	{
		/* search criteria */
		ushort from = (*s)[i].To;
		char on = (*s)[i].On;


		/* return data */
		state* set[num_states];
		int set_size = 0;

		/* create full closure */
		cout << "                          {" << *s[i] << "}" << endl;
		cout << "_________________________ " /*<< "(" << set_size << ")"*/ << '{' << from << ',' << on << (on == 0x0 ? "*" : "") << ",_}" << endl;

		subset(s, set, s[i], &l_size, &set_size);
		for(int x = 0; x < set_size; x++)
			cout << *set[x] << endl;

		cout << endl;
	}
}

int main(int argc, char const *argv[])
{
	/* set static table */
	state* core_ptr[num_states];
	static state core[num_states];

	double hash_id;

	for (int i = 0; i < num_states; i++)
	{
		core[i] = _set(f[i], o[i], t[i], &hash_id);
		core_ptr[i] = &(core[i]);
	}

	/* blob where all the fragments are held */
	/* covers size needed for quadratic, this could be linear(ish) */
	//const size_t max_alloc = (sizeof(frag)+sizeof(link)+sizeof(state)) * num_states * num_states;
	//char heap[max_alloc];

	//cout << "Inferring " <<  *(reinterpret_cast<long*>(&hash_id)) << " @ " << &heap << endl;
	//inference(heap, core_ptr);
	inference( core_ptr );


	//getchar();

	return 0;
}