<commit_before>/*************************************************************************/
/* Copyright (c) 2012, 2013 <NAME> <<EMAIL>>       */
/* All rights reserved                                                   */
/*                                                                       */
/* Use of the Viterbi parsing system is subject to the terms of the      */
/* license set forth in the LICENSE file included with this software.    */
/* This license allows free redistribution and use in source and binary  */
/* forms, with or without modification, subject to certain conditions.   */
/*                                                                       */
/*************************************************************************/

#include <ctype.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include "utilities.h" // From base link-grammar

#include "atom.h"
#include "compress.h"
#include "connect.h"
#include "connector-utils.h"

using namespace std;

#define DBG(X) X;

namespace link_grammar {
namespace viterbi {

/**
 * constructor: argument is a connector set (typically, for a single
 * word) that will be used to try connections. This connector set is
 * assumed to be to the right of the argument to the try_connect()
 * method.
 *
 * To be precise, the right_wconset is presumed to be of the form:
 *	WORD_CSET :
 *    WORD : blah-blah.v
 *	   OR :
 *       CONNECTOR : Wd-
 *       CONNECTOR : Abc+ etc...
 *
 * In particular, it is assumed to be in DNF (disjunctive normal form).
 */
Connect::Connect(WordCset* right_wconset)
	: _right_cset(right_wconset)
{
	assert(_right_cset, "Unexpected NULL dictionary entry!");
	_rcons = _right_cset->get_cset();
cout<<"------------------------- duuude rwcset=\n"<<_right_cset<<endl;
}

/// Unite two states into one. 
///
/// This is needed to implement zippering properly: The old set of
/// states is the collection of as-yet unconnected connectors; the 
/// new set of states is the collection that remains after connecting.
/// We have to peel off and discard some certain number of the old
/// states (as these are now connected), ad append in their place
/// the new states.  We also typically peel off one new one, as that
/// one will be used for trying new onnections.
static StatePair* unite(StatePair* old_sp, size_t old_peel_off,
                        StatePair* new_sp, size_t new_peel_off)
{
	OutList united_states;
	Seq* old_state = old_sp->get_state();
	Seq* new_state = new_sp->get_state();

	const OutList& oo = old_state->get_outgoing_set();
	united_states.insert(united_states.end(), 
	                     oo.begin() + old_peel_off, oo.end());

	const OutList& no = new_state->get_outgoing_set();
	united_states.insert(united_states.end(), 
	                     no.begin() + new_peel_off, no.end());

	// Unite the outputs too ... 
	// This is easy, just concatenate old and append new.
	OutList united_outputs;
	Seq* old_output = old_sp->get_output();
	Seq* new_output = new_sp->get_output();

	const OutList& ooo = old_output->get_outgoing_set();
	united_outputs.insert(united_outputs.end(), ooo.begin(), ooo.end());

	const OutList& noo = new_output->get_outgoing_set();
	united_outputs.insert(united_outputs.end(), noo.begin(), noo.end());

	return new StatePair(new Seq(united_states), new Seq(united_outputs));
}

/**
 * Try connecting this connector set sequence, from the left, to what
 * was passed in ctor.  It is preseumed that left_sp is a single parse
 * state: it should contain no left-pointing connectors whatsoever.  This
 * routine will attempt to attach the right-pointing connectors to the
 * left-pointers passed in the ctor.  A connection is considered to be
 * successful if *all* left-pointers in the ctor were attached (except
 * possibly for optionals).  The returned value is a set of all possible
 * alternative state pairs for which there is a connnection.
 *
 * Connectors must be satisfied sequentially: that is, the first connector
 * set in the sequence must be fully satisfied before a connection is made
 * to the second one in the sequence, etc. (counting from zero).
 */
// XXX most of this should probably be moved to State class
Set* Connect::try_connect(StatePair* left_sp)
{
	// Zipper up the zipper.
	// The left state can the thought of as a strand of zipper teeth,
	// or half of a strand of DNA, if you wish. Each of the zipper teeth
	// are right-pointing connectors.  These must be mated with the
	// left-pointing connectors from the right cset.  The reason its
	// zipper-like is that the right cset might connect to multiple csets
	// on the left.  The connectins must be made in order, and so we loop
	// through the left state, first trying to satisfy all connectors in
	// the first cset, then the second, and so on, until all of the
	// left-pointing connectors in the right cset have been connected,
	// or they're optional, or there is a failure to connect. 
	Seq* left_state = left_sp->get_state();
	Atom* a = left_state->get_outgoing_atom(0);
	WordCset* lwc = dynamic_cast<WordCset*>(a);
	Set* alternatives = next_connect(lwc);
cout<<"wtfffff got alts"<<alternatives<<endl;

	size_t lsz = left_state->get_arity();
	size_t lnext = 1;

	// OK, so do any of the alternatives include state with
	// left-pointing connectors?  If not, then we are done. If so,
	// then these need to be mated to the next word cset on the left.
	// If they can't be mated, then fail, and we are done.
	OutList filtered_alts;
	size_t sz = alternatives->get_arity();
cout<<"wtffff got arity="<<sz<<endl;
	for (size_t i=0; i<sz; i++)
	{
cout<<"wtffff enter i="<<i<<endl;
		Atom* a = alternatives->get_outgoing_atom(i);
		StatePair* new_sp = dynamic_cast<StatePair*>(a);
		Seq* new_state = new_sp->get_state();

		if (0 < new_state->get_arity())
		{
			a = new_state->get_outgoing_atom(0);
			WordCset* new_cset = dynamic_cast<WordCset*>(a);
			if (new_cset->has_left_pointers())
			{
				// The left-pointers are either mandatory or optional.
				// If they're mandatory and there is no state to zipper with,
				// then its a parse fail. Otherwise recurse.
// XX check for optional...
				if (lnext < lsz)
				{
					Atom* a = left_state->get_outgoing_atom(lnext);
				
cout <<"rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrecurse"<<endl;
cout << "old sp, rm "<<lnext<<": " << left_sp<<endl;
cout << "new sp rm 1:" << new_sp<<endl;
					// Recurse
					StatePair* united_sp = unite(left_sp, lnext, new_sp, 1);
cout << "United states:" << united_sp<<endl;
					Connect recurse(new_cset);
					Set* new_alts = recurse.try_connect(united_sp);
cout << "woot got this:" << new_alts<<endl;

					size_t nsz = new_alts->get_arity();
					for (size_t k = 0; k < nsz; k++)
					{
						Atom* a = new_alts->get_outgoing_atom(k);
						StatePair* asp = dynamic_cast<StatePair*>(a);
						StatePair* mrg = unite(united_sp, 1, asp, 0);
						filtered_alts.push_back(mrg);
cout << "mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmerge result="<<mrg<<endl;
					}
					continue;
				}
			}
		}
		
		// Append old and new output and state, before pushing back.
		// XXX I think the below is correct, its untested.
cout<<"mooooooooooooooooooooooooooooooooooooooooooooore"<<endl;
		StatePair* mrg = unite(left_sp, lnext, new_sp, 0);
cout<<"left sp was "<<left_sp<<endl;
cout<<"new sp was "<<new_sp<<endl;
cout<<"mrg is "<<mrg<<endl;
		filtered_alts.push_back(mrg);<commit_msg>fix 13 unit tests, correctly, this time.<commit_after>/*************************************************************************/
/* Copyright (c) 2012, 2013 <NAME> <<EMAIL>>       */
/* All rights reserved                                                   */
/*                                                                       */
/* Use of the Viterbi parsing system is subject to the terms of the      */
/* license set forth in the LICENSE file included with this software.    */
/* This license allows free redistribution and use in source and binary  */
/* forms, with or without modification, subject to certain conditions.   */
/*                                                                       */
/*************************************************************************/

#include <ctype.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include "utilities.h" // From base link-grammar

#include "atom.h"
#include "compress.h"
#include "connect.h"
#include "connector-utils.h"

using namespace std;

#define DBG(X) X;

namespace link_grammar {
namespace viterbi {

/**
 * constructor: argument is a connector set (typically, for a single
 * word) that will be used to try connections. This connector set is
 * assumed to be to the right of the argument to the try_connect()
 * method.
 *
 * To be precise, the right_wconset is presumed to be of the form:
 *	WORD_CSET :
 *    WORD : blah-blah.v
 *	   OR :
 *       CONNECTOR : Wd-
 *       CONNECTOR : Abc+ etc...
 *
 * In particular, it is assumed to be in DNF (disjunctive normal form).
 */
Connect::Connect(WordCset* right_wconset)
	: _right_cset(right_wconset)
{
	assert(_right_cset, "Unexpected NULL dictionary entry!");
	_rcons = _right_cset->get_cset();
cout<<"------------------------- duuude rwcset=\n"<<_right_cset<<endl;
}

/// Unite two states into one. 
///
/// This is needed to implement zippering properly: The old set of
/// states is the collection of as-yet unconnected connectors; the 
/// new set of states is the collection that remains after connecting.
/// We have to peel off and discard some certain number of the old
/// states (as these are now connected), ad append in their place
/// the new states.  We also typically peel off one new one, as that
/// one will be used for trying new onnections.
static StatePair* unite(StatePair* old_sp, size_t old_peel_off,
                        StatePair* new_sp, size_t new_peel_off)
{
	OutList united_states;
	Seq* old_state = old_sp->get_state();
	Seq* new_state = new_sp->get_state();

	const OutList& oo = old_state->get_outgoing_set();
	united_states.insert(united_states.end(), 
	                     oo.begin() + old_peel_off, oo.end());

	const OutList& no = new_state->get_outgoing_set();
	united_states.insert(united_states.end(), 
	                     no.begin() + new_peel_off, no.end());

	// Unite the outputs too ... 
	// This is easy, just concatenate old and append new.
	OutList united_outputs;
	Seq* old_output = old_sp->get_output();
	Seq* new_output = new_sp->get_output();

	const OutList& ooo = old_output->get_outgoing_set();
	united_outputs.insert(united_outputs.end(), ooo.begin(), ooo.end());

	const OutList& noo = new_output->get_outgoing_set();
	united_outputs.insert(united_outputs.end(), noo.begin(), noo.end());

	return new StatePair(new Seq(united_states), new Seq(united_outputs));
}

/**
 * Try connecting this connector set sequence, from the left, to what
 * was passed in ctor.  It is preseumed that left_sp is a single parse
 * state: it should contain no left-pointing connectors whatsoever.  This
 * routine will attempt to attach the right-pointing connectors to the
 * left-pointers passed in the ctor.  A connection is considered to be
 * successful if *all* left-pointers in the ctor were attached (except
 * possibly for optionals).  The returned value is a set of all possible
 * alternative state pairs for which there is a connnection.
 *
 * Connectors must be satisfied sequentially: that is, the first connector
 * set in the sequence must be fully satisfied before a connection is made
 * to the second one in the sequence, etc. (counting from zero).
 */
// XXX most of this should probably be moved to State class
Set* Connect::try_connect(StatePair* left_sp)
{
	// Zipper up the zipper.
	// The left state can the thought of as a strand of zipper teeth,
	// or half of a strand of DNA, if you wish. Each of the zipper teeth
	// are right-pointing connectors.  These must be mated with the
	// left-pointing connectors from the right cset.  The reason its
	// zipper-like is that the right cset might connect to multiple csets
	// on the left.  The connectins must be made in order, and so we loop
	// through the left state, first trying to satisfy all connectors in
	// the first cset, then the second, and so on, until all of the
	// left-pointing connectors in the right cset have been connected,
	// or they're optional, or there is a failure to connect. 
	Seq* left_state = left_sp->get_state();
	Atom* a = left_state->get_outgoing_atom(0);
	WordCset* lwc = dynamic_cast<WordCset*>(a);
	Set* alternatives = next_connect(lwc);
cout<<"wtfffff got alts"<<alternatives<<endl;

	size_t lsz = left_state->get_arity();
	size_t lnext = 1;

	// OK, so do any of the alternatives include state with
	// left-pointing connectors?  If not, then we are done. If so,
	// then these need to be mated to the next word cset on the left.
	// If they can't be mated, then fail, and we are done.
	OutList filtered_alts;
	size_t sz = alternatives->get_arity();
cout<<"wtffff got arity="<<sz<<endl;
	for (size_t i=0; i<sz; i++)
	{
cout<<"wtffff enter i="<<i<<endl;
		Atom* a = alternatives->get_outgoing_atom(i);
		StatePair* new_sp = dynamic_cast<StatePair*>(a);
		Seq* new_state = new_sp->get_state();

		if (0 < new_state->get_arity())
		{
			a = new_state->get_outgoing_atom(0);
			WordCset* new_cset = dynamic_cast<WordCset*>(a);
			if (new_cset->has_left_pointers())
			{
				// The left-pointers are either mandatory or optional.
				// If they're mandatory and there is no state to zipper with,
				// then its a parse fail. Otherwise recurse.
// XX check for optional...
				if (lnext < lsz)
				{
					Atom* a = left_state->get_outgoing_atom(lnext);
				
cout <<"rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrecurse"<<endl;
cout << "old sp, rm "<<lnext<<": " << left_sp<<endl;
cout << "new sp rm 1:" << new_sp<<endl;
					// Recurse -- zipper up the next unconnected left-pointer.
					StatePair* united_sp = unite(left_sp, lnext, new_sp, 1);
					// zero out output before continuing... we want only
					// the fresh output just minted by the recurse
					StatePair* usp = new StatePair(united_sp->get_state(), new Seq());
cout << "United states:" << united_sp<<endl;
					Connect recurse(new_cset);
					Set* new_alts = recurse.try_connect(usp);
cout << "woot got this:" << new_alts<<endl;

					size_t nsz = new_alts->get_arity();
					for (size_t k = 0; k < nsz; k++)
					{
						Atom* a = new_alts->get_outgoing_atom(k);
						StatePair* asp = dynamic_cast<StatePair*>(a);
						StatePair* mrg = unite(united_sp, 1, asp, 0);
						filtered_alts.push_back(mrg);
cout << "mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmerge result="<<mrg<<endl;
					}
					continue;
				}
// XXX we need to increment lnext at some point ...  if there are more
// than one lefty that is undone.
			}
		}
		
		// Append old and new output and state, before pushing back.
		// XXX I think the below is correct, its untested.
cout<<"mooooooooooooooooooooooooooooooooooooooooooooore"<<endl;
		StatePair* mrg = unite(left_sp, lnext, new_sp, 0);
cout<<"left sp was "<<left_sp<<endl;
cout<<"new sp was "<<new_sp<<endl;
cout<<"mrg is "<<mrg<<endl;
		filtered_alts.push_back(mrg);
{'fraction_non_alphanumeric': 0.13206056616194864, 'fraction_numerical': 0.0026333113890717576, 'mean_word_length': 3.267134831460674, 'pattern_counts': {'":': 2, '<': 203, '<?xml version=': 0, '>': 70, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 6, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5130788', 'n_tokens_mistral': 5088, 'n_tokens_neox': 4690, 'n_words': 1674}