item.cc

来自「This is a resource based on j2me embedde」· CC 代码 · 共 1,241 行 · 第 1/2 页

	rulelist_iterator	rl_i;
	rule *			r;
	item		i;
	item		cookie_max;
	item_cost *		item_costset_set;
	int			changed; // Boolean
	unsigned		sum_cost;
	int			n_instances;

	// allocate a item_costset array: fill it with absent elements.
	cookie_max = ptp->n()-1;
	item_costset_set = allocate_item_costset_array( ptp->n() );

	/*
	 * start the item_costset_set with all items in which the symbol
	 * appears on the rhs.
	 */
	rl_i = symp->rhs();
	n_instances = 0;
	while( (r = rl_i.next() ) != 0 ){
		n_instances +=
		    find_instance( item_costset_set, symp, r, ptp, 0 );
	}

	if ( n_instances == 0 ){
		/*
		 * this is very boring: there is nothin in the core
		 * set. Give back the storage. Return smaller,
		 * empty sets.
		 */
		free_item_costset_space( item_costset_set );
		if ( core_set_p != 0 ){
			*core_set_p = item_costset( ptp, 0 );
		}
		return item_costset( ptp, 0 );
	}

	if ( core_set_p != 0 ){
		item_cost * core_p = allocate_item_costset_space( ptp->n());
		memcpy(core_p, item_costset_set, ptp->n()*sizeof( item_cost ));
		*core_set_p = item_costset( ptp, core_p );
	}

	changed = 1;
	while( changed ){
		changed = 0;
		/*
		 * for every item in the item_costset_set corresponding
		 * to a fullmatch of a rule, r,
		 * add to the set all items where r's lhs appear
		 * in the (new) item's rhs. Cost is cost of matching r
		 * plus r's cost.
		 * Of course, consider that the set is changed only
		 * if (a) the new item wasn't in the set, or
		 * (b) if it was but at greater cost.
		 */
		for ( i = 0; i <= cookie_max; i++ ){
			if (item_costset_set[i] != item_cost_none
			    && ptp->item_subpart(i)==item_table::fullmatch){
				r = ptp->item_rule(i);
				sum_cost = item_costset_set[i]+r->principle_cost();
				assert( sum_cost <= item_cost_max );
				symp = r->lhs();
				rl_i = symp->rhs();
				while( (r = rl_i.next() ) != 0 ){
					changed += find_instance(
						item_costset_set,
						symp,
						r,
						ptp,
						sum_cost );
				}
			}
		}
	}
	return item_costset( ptp, item_costset_set );
}

/*
 * Manipulate item_costsets:
 * first: add a new item with cost to a item_costset.
 */
int
item_costset::cost_add( item cook, item_cost c )
{
	if ( c == item_cost_none )
		return 0; // not the best move.
	if (item_costset_p == 0 ){
		// instantiate it.
		item_costset_p = allocate_item_costset_array( item_costset_table->n() );
	}
	assert( cook < item_costset_table->n() );
	if ( item_costset_p[cook] == item_cost_none
	||   item_costset_p[cook] > c ){
		item_costset_p[cook] = c;
		return 1;
	} else {
		return 0;
	}
}


/*
 * cost_bias: add a constant +/- item_cost c to the cost of
 * every item in the set. Absent items, and ininstantiated sets
 * are uneffected.
 */
void 
item_costset::cost_bias( int c )
{
	item i, cookie_max = item_costset_table->n()-1;
	item_cost * cp;

	if ( c == 0 )
		return;
	if (item_costset_p == 0 )
		return;
	for( i = 0, cp = item_costset_p ; i <= cookie_max ; i++, cp++ ){
		if ( *cp != item_cost_none ){
			*cp += c;
		}
	}
}

/*
 * normalize: find the least item_cost, and subtract it from the
 * cost of all present items. Works in place.
 */
void 
item_costset::normalize()
{
	unsigned ncosts;
	int lowcost = item_cost_none;
	register unsigned i;
	register item_cost * cp;
	register int v;

	ncosts = item_costset_table->n();
	cp = item_costset_p;
	if ( cp == 0 )
		return;
	for( i = 0; i < ncosts ; i++ ){
		v = cp[i];
		if ( v < lowcost ){
			lowcost = v;
		}
	}
	if ( lowcost != item_cost_none )
		cost_bias( -lowcost );
}

/*
 * Union together two item_costsets, with cost bias
 */
void
item_costset::cost_union( const item_costset & other, item_cost bias )
{
	unsigned i, maxp1;
	unsigned sumcost;
	int	is_it_empty;

	if ( other.item_costset_p == 0 ){
		// other set empty. Nothing to do.
		return;
	}
	if (item_costset_p == 0 ){
		// instantiate it.
		item_costset_p = allocate_item_costset_array( item_costset_table->n() );
	}
	is_it_empty = 1;
	assert( bias <= item_cost_max );
	maxp1 = item_costset_table->n();
	for ( i = 0; i < maxp1; i++){
		if ( (sumcost=other.item_costset_p[i]) != item_cost_none ){	
			sumcost += bias;
			if ( item_costset_p[i] == item_cost_none
			||   item_costset_p[i] > sumcost ){
				item_costset_p[i] = sumcost;
			}
			is_it_empty = 0;
		} else if (item_costset_p[i] != item_cost_none){
			is_it_empty = 0;
		}
	}
	if (is_it_empty!=0){
		/*
		 * its an empty set.
		 * deallocate storage.
		 */
		free_item_costset_space( item_costset_p );
		item_costset_p = 0;
	}
	return;
}


/*
 * Intersect two item_costsets, with cost bias
 */
void
item_costset::cost_intersect( const item_costset & other, item_cost bias )
{
	unsigned i, maxp1;
	unsigned sumcost;
	int is_it_empty;

	if (item_costset_p == 0 ){
		// this set empty. Intersection is empty.
		return;
	}
	assert( bias <= item_cost_max );
	maxp1 = item_costset_table->n();

	if ( other.item_costset_p == 0 ){
		// other set empty. Intersection is empty.
		free_item_costset_space( item_costset_p );
		item_costset_p = 0;
		return;
	}
	// away we go
	is_it_empty = 1;
	for ( i = 0; i < maxp1; i++){
		if ( (sumcost=other.item_costset_p[i]) == item_cost_none ){	
			// not in other set: not in intersection.
			item_costset_p[i] = item_cost_none;
		} else {
			sumcost += bias;
			if ( item_costset_p[i] != item_cost_none ){
				item_costset_p[i] += sumcost;
				is_it_empty = 0;
			}
		}
	}
	if (is_it_empty != 0 ){
		/*
		 * empty result.
		 */
		free_item_costset_space( item_costset_p );
		item_costset_p = 0;
	}
	return;
}

int
item_costset::n()
const
{
	// count items present in item_costset
	unsigned i, maxp1;
	int nmembers;

	if (item_costset_p == 0 ){
		// empty set
		return 0;
	} else {
		nmembers = 0;
		maxp1 = item_costset_table->n();
		for( i = 0; i < maxp1; i++ )
			if ( item_costset_p[i] != item_cost_none )
				nmembers += 1;
		return nmembers;
	}
}
/*
 * A cheaper test if all you need to know is existance:
 *     1=> empty set
 *     0=> non empty set
 */
int
item_costset::private_is_empty() const
{
	unsigned i, maxp1;

	if (item_costset_p != 0 ){
		maxp1 = item_costset_table->n();
		for( i = 0; i < maxp1; i++ )
			if ( item_costset_p[i] != item_cost_none )
				return 0;
	}
	return 1;
}

item_costset
item_costset::copy()
const
{
	item_costset result( item_costset_table );
	unsigned ncosts;
	if (item_costset_p == 0 ){
		// empty set
		return result;
	} else {
		// allocate array. Bcopy.
		ncosts = item_costset_table->n();
		result.item_costset_p = allocate_item_costset_space( ncosts );
		memcpy(result.item_costset_p, item_costset_p, ncosts*sizeof(item_cost));
		return result;
	}
}

/* 
 * For prt == parent_table::leftpart
 * construct a item_costset of all cookies "b", such that
 *	item "a" is a member of item_costset l;
 *	and  "a" is of the form [ x -> alpha s < treeL > beta ; c ]
 *					for unary symbol s or 
 *				[ x -> alpha s < treeL > treeR  beta ; c ]
 *					for binary s
 *      then "b" is		[ x -> alpha < s treeL > beta; c]
 *			     or [ x-> alpha <s treeL treeR > beta; c ]
 *      correspondingly.
 */

item_costset
item_costset::parent_allmatch(
	item_table::subgraph_part prt,
	symbol *s ) const
{
	register item_table *t = item_costset_table;
	register item_cost * p;
	register item v, vmaxp1;
	item vparent;
	item_cost c;
	item_costset result(t);

	p = item_costset_p;
	if ( p == 0 ){
		// empty set in, empty set out.
		return result;
	}
	vmaxp1 = t->n();
	for( v = 0; v < vmaxp1; v++ ){
		if ( (c = p[v] ) == item_cost_none ){
			// v not in set.
			continue;
		}
		if (t->item_subpart(v) == prt ){
			vparent = t->item_parent( v );
			if ( t->item_subtree(vparent)->node == s )
				result.cost_add( vparent, c );
		}
	}
	return result;
}

int 
item_costset_equal( const item_costset &a, const item_costset &b )
{
	// look for the special cases:
	// expanded and unexpanded empty sets.
	if ( a.item_costset_p == 0 ){
		// "a" is empty.
		return ( b.is_empty() );
	} else if ( b.item_costset_p == 0 ){
		// "b" is empty, and even though "a" is allocated,
		// it might be empty anyway.
		// this case is unlikely.
		return ( a.is_empty() );
	}
	// else neither is empty.
	// do byte-by-byte equality check.
	return memcmp( a.item_costset_p, b.item_costset_p, a.item_costset_table->n()*sizeof(item_cost) ) == 0;
}

/*
 * funky comparison: would this set be equal to the other
 * if both were normalized. Thus ignoring differences of a 
 * constant cost bias, as this will wash out after minimization.
 * This costs lots and lots more than operator==, but if applied
 * earlier in the state building process, may shortcut other
 * more expensive operations.
 */

int
item_costset_normalized_equal( const item_costset &a, const item_costset &b )
{
	// look for the special cases:
	// expanded and unexpanded empty sets.
	// (starts like item_costset_equal, doesn't it?)
	if ( a.item_costset_p == 0 ){
		return ( b.n() == 0 );
	} else if ( b.item_costset_p == 0 ){
		// other is empty
		return ( a.n() == 0 );
	}

	register unsigned i, maxp1;
	register int  bias = item_cost_none;
	register item_cost this_v, other_v;
	register item_cost * this_p, * other_p;
	maxp1 = a.item_costset_table->n();
	this_p = a.item_costset_p;
	other_p = b.item_costset_p;
	// first, compare as much of the set as possible
	// for simple emptyness.
	for (i=0; i<maxp1; i++ ){
		if (this_p[i] != item_cost_none )
			break;
		if (other_p[i] != item_cost_none )
			break;
	}
	if ( i >= maxp1 ){
		// both entirely empty
		return 1;
	}
	// found the first case where one or the other is not missing.
	this_v = this_p[i];
	other_v = other_p[i];
	if ( this_v == item_cost_none || other_v == item_cost_none ){
		// one not missing, but one is missing.
		return 0;
	}
	// neither missing. Compute the bias only once.
	bias = this_v - other_v;

	// continue comparison more carefully.
	for (i=i+1; i<maxp1; i++ ){
		this_v = this_p[i];
		other_v = other_p[i];
		if ( this_v == item_cost_none ){
			if ( other_v == item_cost_none ){
				// element i is missing from both
				continue;
			} else {
				// element i is missing from this
				// but in other: not equal
				return 0;
			}
		} else if ( other_v == item_cost_none ) {
			// element i is missing from other
			return 0;
		} else {
			// make sure cost difference is same.
			if ( this_v - other_v != bias )
					return 0;
		}
	}
	// end of for loop: found no unequal elements
	return 1;
}

// how to get rid of one:
// only deallocates the allocated array:
// does not deallocate the item_costset struct itself.
void
item_costset::destruct()
{
	if ( item_costset_p != 0 ){
		free_item_costset_space( item_costset_p);
		item_costset_p = 0;
	}
}

/*
 * Operations on sparse item cost sets. These are used in 
 * "compute_parental_matchsets", where even the non-empty sets have,
 * generally, < 3 things in them. These are lots smaller, and can
 * easily support the operational subset required.
 */

int
sparse_item_costset::cost_add( item p, item_cost c )
{
	register unsigned	i;
	register item_pair *	pp;

	assert( p < item_costset_table->n() );
	if ( c == item_cost_none )
		return 0; // very dopy thing to do.
	if (max_pairs <= SPARSE_ITEM_COSTSET_ARRAY_SIZE)
		pp = stuff;
	else
		pp = pair_array;
	/*
	 * iterate through table, looking for match.
	 */
	for ( i = 0 ; i < n_pairs ; i ++ ){
		if ( pp[i].ino == p ){
			// found
			if ( c < pp[i].c ){
				pp[i].c = c;
				return 1;
			} else
				return 0; // was already there cheaper.
		}
	}
	/*
	 * didn't find. add at end.
	 */
	if ( max_pairs <= SPARSE_ITEM_COSTSET_ARRAY_SIZE ){
		// allocate at end of builtin array if it fits...
		max_pairs = SPARSE_ITEM_COSTSET_ARRAY_SIZE;
		if ( n_pairs < SPARSE_ITEM_COSTSET_ARRAY_SIZE ){
			// will fit
			pp = &stuff[n_pairs];
		} else { 
			// won't fit. Will allocate and copy.
			max_pairs *=2;
			pair_array = (item_pair *) malloc(
			    max_pairs*sizeof(item_pair) );
			DID_SPARSEALLOC( max_pairs );
			assert( pair_array != 0 );
			memcpy(pair_array, stuff, (SPARSE_ITEM_COSTSET_ARRAY_SIZE)*sizeof(item_pair) );
			pp = &pair_array[n_pairs];
		}
	} else {
		// allocate at end of allocated array if it fits...
		if ( n_pairs >= max_pairs ){
			// must reallocate.
			max_pairs *=2;
			pair_array = (item_pair *) realloc(
			    (char*)pair_array, max_pairs*sizeof(item_pair) );
			DID_SPARSE_REALLOC( max_pairs );
			assert( pair_array != 0 );
		}
		pp = &pair_array[n_pairs];
	} 
	pp->ino = p;
	pp->c = c;
	n_pairs +=1;
	return 1;
}

item_costset
sparse_item_costset::get() const
{
	item_costset v( item_costset_table ); // construct an empty one.
	register unsigned		i;
	register const item_pair *	pp;

	if (max_pairs <= SPARSE_ITEM_COSTSET_ARRAY_SIZE)
		pp = stuff;
	else
		pp = pair_array;
	for ( i = 0 ; i < n_pairs ; i += 1 ){
		v.cost_add( pp[i].ino, pp[i].c );
	}
	return v;
}

void
sparse_item_costset::private_destruct()
{
	if ( max_pairs > SPARSE_ITEM_COSTSET_ARRAY_SIZE ){
		// free allocated memory
		free( (char *)pair_array );
		DID_SPARSEFREE( max_pairs );
	}
	n_pairs = 0;
	max_pairs = 0;
}

void
sparse_item_costset::print( FILE * out ) const
{
	unsigned i;

	for( i = 0; i <= n_pairs; i++ ){
		fputs( "\t[ ", out);
		item_costset_table->item_print( pair_array[i].ino, out );
		fprintf( out, " ; %d ]\n", pair_array[i].c );
	}
}

/****************************************************************************/

void
close_symbols()
{
	symbollist_iterator sl_i = all_symbols;
	symbol * sp;
	item_costset core_set;

	/*
	 * compute item_costset for nonterminals. And while we're at it,
	 * compute itemsets for leaf terminals. Others should have
	 * empty item_costset sets.
	 */
	while( ( sp = sl_i.next() ) != 0 ){
		switch( sp->type() ){
		case symbol::binaryop:
		case symbol::unaryop:
			// build an empty one.
			sp->add_closure( item_costset( &all_items ) );
			break;
		case symbol::terminal:
		case symbol::nonterminal:
			sp->add_closure(
			    item_costset::compute_item_costset( sp, &all_items, &core_set ) );
			sp->add_core_set( core_set );
		}
	}
}

void
print_closures( int print_core_sets )
{
	symbollist_iterator sl_i = all_symbols;
	symbol *s;
	puts("\nCLOSURE SETS");

	while( (s=sl_i.next() ) != 0 ){
		printf("%s: {\n", s->name());
		s->get_closure().print(stdout);
		puts("}");
		if (print_core_sets ){
			printf("core of %s: {\n", s->name());
			s->get_core_set().print(stdout);
			puts("}");
		}
	}
}

void
print_item_costset( const item_costset * cp )
{
	cp->print( stdout );
	fflush(stdout);
}