| /* 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; |
| } |
| |
