/* FILE: sub_supp.cpp
* DATE MODIFIED: 31-Aug-07
* DESCRIPTION: Part of the SREC graph compiler project source files.
*
* Copyright 2007, 2008 Nuance Communciations, Inc. *
* *
* Licensed under the Apache License, Version 2.0 (the 'License'); *
* you may not use this file except in compliance with the License. *
* *
* You may obtain a copy of the License at *
* http://www.apache.org/licenses/LICENSE-2.0 *
* *
* Unless required by applicable law or agreed to in writing, software *
* distributed under the License is distributed on an 'AS IS' BASIS, *
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
* See the License for the specific language governing permissions and *
* limitations under the License. *
* *
*---------------------------------------------------------------------------*/
#include <iostream>
#include <string>
#include <assert.h>
#include <cstdio>
#include "sub_grph.h"
#define ARC_COMPARE(x,y) (arc[x]->Compare(arc[y]))
#define ARC_COMPARE_REV(x,y) (arc[x]->CompareReverse(arc[y]))
#define ARC_COMPARE_MIN(x,y) (arc[x]->CompareForMin(arc[y]))
void SubGraph::SortLanguage ()
{
int *sortList;
if (numArc <= 1) {
sortList= new int [numArc+2];
sortList[0]= 0;
if (forwardList)
delete [] forwardList;
forwardList= sortList;
sortNum= numArc;
return;
}
SortLanguageAtIndices (-1, -1);
return;
}
void SubGraph::SortLanguageAtIndices (int begIx, int endIx)
{
int ii, jj, hired, retd;
int holdArc, *sortList;
if (begIx < 0)
begIx= 0;
if (endIx < 0)
endIx= numArc;
if (endIx <= begIx)
return;
sortList= new int [numArc+2];
for (ii= 0; ii < sortNum && ii < numArc; ii++)
sortList[ii]= forwardList[ii];
for (ii= begIx; ii < endIx; ii++)
sortList[ii]= ii;
sortList--;
/* Hiring
*/
hired= (numArc >> 1)+1;
while (hired-- > 1) {
holdArc= sortList[hired];
ii= hired;
jj= hired << 1;
while (jj <= numArc) {
if (jj < numArc && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0 )
jj++;
if (ARC_COMPARE (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
/* Retiring
*/
retd= numArc;
while (retd > 0) {
holdArc= sortList[retd];
sortList[retd]= sortList[1];
if (--retd == 1) {
sortList[1]= holdArc;
break;
}
ii= 1;
jj= 2;
while (jj <= retd) {
if (jj < retd && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0)
jj++;
if (ARC_COMPARE (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
sortList++;
if (forwardList)
delete [] forwardList;
forwardList= sortList;
sortNum= numArc;
/* Now carry out some checks
*/
assert(CheckSort());
return;
}
void SubGraph::SortLanguageAtSortIndices (int begIx, int endIx)
{
int ii, jj, hired, retd;
int holdArc, *sortList;
if (begIx < 0)
begIx= 0;
if (endIx < 0)
endIx= numArc;
if (endIx <= begIx)
return;
sortList= forwardList;
sortList--;
/* Hiring
*/
hired= (numArc >> 1)+1;
while (hired-- > 1) {
holdArc= sortList[hired];
ii= hired;
jj= hired << 1;
while (jj <= numArc) {
if (jj < numArc && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0 )
jj++;
if (ARC_COMPARE (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
/* Retiring
*/
retd= numArc;
while (retd > 0) {
holdArc= sortList[retd];
sortList[retd]= sortList[1];
if (--retd == 1) {
sortList[1]= holdArc;
break;
}
ii= 1;
jj= 2;
while (jj <= retd) {
if (jj < retd && ARC_COMPARE (sortList[jj], sortList[jj+1]) <= 0)
jj++;
if (ARC_COMPARE (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
sortList++;
forwardList= sortList;
/* Now carry out some checks
*/
assert(CheckSort());
return;
}
int SubGraph::FindFromIndex (int element)
{
int rix, rix_low, rix_high, direction;
rix_low= -1;
rix_high= sortNum;
while ((rix_high - rix_low) > 1) {
rix= (rix_high + rix_low) >> 1;
direction= element - arc[forwardList[rix]]->GetFromId();
if (direction < 0)
rix_high= rix;
else if (direction > 0)
rix_low= rix;
else {
assert (arc[forwardList[rix]]->GetFromId() == element);
while (rix > 0 && arc[forwardList[rix-1]]->GetFromId() == element)
rix--;
assert (arc[forwardList[rix]]->GetFromId() == element);
assert (rix < sortNum);
return (rix);
}
}
return (-1);
}
void SubGraph::SortLanguageReverse ()
{
int ii, jj, hired, retd;
int holdArc, *sortList;
if (numArc <= 1) {
sortList= new int [numArc+2];
sortList[0]= 0;
if (backwardList)
delete [] backwardList;
backwardList= sortList;
sortRevNum= numArc;
return;
}
sortList= new int [numArc+2];
for (ii= 0; ii < numArc; ii++)
sortList[ii]= ii;
sortList--;
/* Hiring
*/
hired= (numArc >> 1)+1;
while (hired-- > 1) {
holdArc= sortList[hired];
ii= hired;
jj= hired << 1;
while (jj <= numArc) {
if (jj < numArc && ARC_COMPARE_REV (sortList[jj], sortList[jj+1]) <= 0 )
jj++;
if (ARC_COMPARE_REV (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
/* Retiring
*/
retd= numArc;
while (retd > 0) {
holdArc= sortList[retd];
sortList[retd]= sortList[1];
if (--retd == 1) {
sortList[1]= holdArc;
break;
}
ii= 1;
jj= 2;
while (jj <= retd) {
if (jj < retd && ARC_COMPARE_REV (sortList[jj], sortList[jj+1]) <= 0)
jj++;
if (ARC_COMPARE_REV (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
sortList++;
if (backwardList)
delete [] backwardList;
backwardList= sortList;
sortRevNum= numArc;
/* Now carry out some checks
*/
assert(CheckSortReverse());
return;
}
int SubGraph::FindToIndex (int element)
{
int rix, rix_low, rix_high, direction;
rix_low= -1;
rix_high= sortRevNum;
while ((rix_high - rix_low) > 1) {
rix= (rix_high + rix_low) >> 1;
direction= element - arc[backwardList[rix]]->GetToId();
if (direction < 0)
rix_high= rix;
else if (direction > 0)
rix_low= rix;
else {
assert (arc[backwardList[rix]]->GetToId() == element);
while (rix > 0 && arc[backwardList[rix-1]]->GetToId() == element)
rix--;
assert (arc[backwardList[rix]]->GetToId() == element);
assert (rix < sortRevNum);
return (rix);
}
}
return (-1);
}
void SubGraph::UpdateSortForLanguage ()
{
SortLanguageAtIndices (sortNum, numArc);
}
bool SubGraph::CheckSort ()
{
for (int ii= 1; ii < numArc; ii++) {
if (ARC_COMPARE (forwardList[ii-1], forwardList[ii]) > 0)
return false;
}
return true;
}
bool SubGraph::CheckSortReverse ()
{
for (int ii= 1; ii < numArc; ii++) {
if (ARC_COMPARE_REV (backwardList[ii-1], backwardList[ii]) > 0) {
printf ("Failed at %d\n", ii);
return false;
}
}
return true;
}
void SubGraph::ClearDuplicateArcs ()
{
int currId;
SortLanguage();
currId= 0;
for (int ii= 1; ii < numArc; ii++) {
if (arc[forwardList[ii]]->GetInput() != DISCARD_LABEL)
if (ARC_COMPARE (forwardList[currId], forwardList[ii]) == 0)
arc[forwardList[ii]]->AssignInput (DISCARD_LABEL);
else
currId= ii;
}
return;
}
void SubGraph::RenumberNodes ()
{
int ii, id, count;
UpdateVertexCount (0);
if (numVertex > 0) {
int *mapList= new int [numVertex];
for (ii= 0; ii < numVertex; ii++)
mapList[ii]= -1;
for (ii= 0; ii < numArc; ii++) {
id= arc[ii]->GetFromId();
mapList[id]= 1;
id= arc[ii]->GetToId();
if (id >= 0)
mapList[id]= 1;
}
count= 0;
for (ii= 0; ii < numVertex; ii++)
if (mapList[ii] > 0) {
mapList[ii]= count;
count++;
}
for (ii= 0; ii < numArc; ii++) {
id= arc[ii]->GetFromId();
arc[ii]->AssignFromId(mapList[id]);
id= arc[ii]->GetToId();
if (id >= 0)
arc[ii]->AssignToId(mapList[id]);
}
startId= mapList[startId];
if (lastId >= 0)
lastId= mapList[lastId];
delete [] mapList;
}
else {
startId= 0;
lastId= -1;
endId= -1;
}
return;
}
void SubGraph::RemoveDuplicatesAtNode (int rixBegin, int rixEnd)
// Works only within one node/vertex
{
int rix, lastRix;
bool needSort;
SortLanguageAtSortIndices (rixBegin, rixEnd);
// Check for duplicate transitions
needSort= false;
lastRix= rixBegin;
for (rix= rixBegin+1; rix < rixEnd; rix++) {
assert (arc[forwardList[lastRix]]->GetFromId() == arc[forwardList[rix]]->GetFromId());
if (ARC_COMPARE (forwardList[lastRix], forwardList[rix]) == 0) {
arc[forwardList[rix]]->AssignInput (DISCARD_LABEL);
needSort= true;
}
else
lastRix= rix;
}
// Resort
if (needSort)
SortLanguageAtSortIndices (rixBegin, rixEnd);
return;
}
void SubGraph::SortLanguageForMin ()
{
int *sortList;
if (numArc <= 1) {
sortList= new int [numArc+2];
sortList[0]= 0;
if (forwardList)
delete [] forwardList;
forwardList= sortList;
sortNum= numArc;
return;
}
SortLanguageAtIndicesForMin (-1, -1);
return;
}
void SubGraph::SortLanguageAtIndicesForMin (int begIx, int endIx)
{
int ii, jj, hired, retd;
int holdArc, *sortList;
if (begIx < 0)
begIx= 0;
if (endIx < 0)
endIx= numArc;
if (endIx <= begIx)
return;
sortList= new int [numArc+2];
for (ii= 0; ii < sortNum && ii < numArc; ii++)
sortList[ii]= forwardList[ii];
for (ii= begIx; ii < endIx; ii++)
sortList[ii]= ii;
sortList--;
/* Hiring
*/
hired= (numArc >> 1)+1;
while (hired-- > 1) {
holdArc= sortList[hired];
ii= hired;
jj= hired << 1;
while (jj <= numArc) {
if (jj < numArc && ARC_COMPARE_MIN (sortList[jj], sortList[jj+1]) <= 0 )
jj++;
if (ARC_COMPARE_MIN (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
/* Retiring
*/
retd= numArc;
while (retd > 0) {
holdArc= sortList[retd];
sortList[retd]= sortList[1];
if (--retd == 1) {
sortList[1]= holdArc;
break;
}
ii= 1;
jj= 2;
while (jj <= retd) {
if (jj < retd && ARC_COMPARE_MIN (sortList[jj], sortList[jj+1]) <= 0)
jj++;
if (ARC_COMPARE_MIN (holdArc, sortList[jj]) < 0) {
sortList[ii]= sortList[jj];
ii= jj;
jj <<= 1;
}
else
break;
}
sortList[ii]= holdArc;
}
sortList++;
if (forwardList)
delete [] forwardList;
forwardList= sortList;
sortNum= numArc;
/* Now carry out some checks
*/
int checkSort = CheckSort();
if(checkSort == 0) {
// printf("assert(0) in SubGraph::CheckSort %d\n", checkSort);
// hmm .. this seems harmless but ...!
// assert(checkSort);
}
return;
}