Trie.cpp

   1 // Implementation of CTrie methods
   2 // Copyright © 2009 The University of Chicago
   3 #include "Trie.h"
   4
   5 #include <memory>
   6 #include <vector>
   7 #include <algorithm>
   8 #include <functional>
   9 #include <QTextOStream>
  10 #include "linguisticamainwindow.h"
  11 #include "ui/Status.h"
  12 #include "StringSurrogate.h"
  13 #include "Parse.h"
  14 #include "Stem.h"
  15 #include "MorphemeCollection.h"
  16 #include "WordCollection.h"
  17 #include "CompareFunc.h"
  18 #include "Typedefs.h"
  19
  20 // CTrieListViewItem
  21 /////////////////////////////////////////////////////////////
  22
  23 CTrieListViewItem::CTrieListViewItem( Q3ListView *parent,
  24                     QString label1 )
  25 : Q3ListViewItem( parent, label1 )
  26 {}
  27
  28
  29 CTrieListViewItem::CTrieListViewItem( Q3ListViewItem *parent,
  30                     QString label1 )
  31 : Q3ListViewItem( parent, label1 )
  32 {}
  33
  34 QString CTrieListViewItem::key( int column, bool ascending ) const
  35 {
  36   //switch( column )
  37   //{
  38   //default:
  39     return Q3ListViewItem::key( column, ascending );
  40   //}
  41 }
  42
  43 QString CTrieListViewItem::text( int column ) const
  44 {
  45   //switch( column )
  46   //{
  47   //default:
  48     return Q3ListViewItem::text( column );
  49   //}
  50 }
  51
  52
  53 // CTrie
  54 /////////////////////////////////////////////////////////////
  55
  56 CTrie::CTrie(bool ReverseFlag)
  57         : m_Root(new CNode()),
  58         m_NodeArray(),
  59         m_ReverseFlag(ReverseFlag),
  60         m_AutoDelete(true),
  61         m_Count(0),
  62         m_NumberOfNodes(1),
  63         m_TrieHasChangedFlag(true),
  64         m_IsAlphabetized(false) { }
  65
  66 CTrie::~CTrie()
  67 {
  68         delete m_Root;
  69         delete[] m_NodeArray;
  70 }
  71
  72 void CTrie::ResetToEmpty()
  73 {
  74         delete m_Root;  // destructor deletes all child nodes
  75         m_Root = new CNode();
  76         m_Count = 0;
  77         m_NumberOfNodes = 1;
  78         m_TrieHasChangedFlag = true;
  79         m_IsAlphabetized = false;
  80         // m_NodeArray, m_ReverseFlag, and m_AutoDelete remain unchanged.
  81 }
  82
  83 CNode* CTrie::operator<< ( CStringSurrogate ssS )
  84 {
  85         return Insert(ssS);
  86 }
  87
  88
  89 CNode* CTrie::operator<< ( CParse* Parse )
  90 {
  91         CStringSurrogate ss = Parse->GetKey();
  92         return Insert( ss );
  93 }
  94
  95 void CTrie::ListDisplay(Q3ListView* List, LinguisticaMainWindow* doc,
  96         QMap<QString, QString>* filter, bool ReverseFlag)
  97 {
  98   int count = 0;
  99   // Remove all previous columns
 100   while( List->columns() ) List->removeColumn( 0 );
 101
 102   // Add column header
 103   if( m_ReverseFlag ) List->addColumn( "Reverse Trie" );
 104   else List->addColumn( "Forward Trie" );
 105
 106   if( doc )     // TODO: is doc set and if so are these functions below right
 107   {
 108     doc->status_display().major_operation = "Preparing trie for display";
 109     doc->status_display().progress.set_denominator(m_Count);
 110     m_Root->ListDisplay( List, doc, &count, filter, ReverseFlag );
 111     doc->status_display().major_operation.clear();
 112     doc->status_display().progress.clear();
 113   }
 114   else m_Root->ListDisplay( List, NULL, NULL, filter, ReverseFlag );
 115 }
 116
 117
 118 void CTrie::FindSFBumps( CMorphemeCollection& TempMorphemes, int SFThreshold )
 119 {
 120         m_Root->FindSFBumps ( TempMorphemes, SFThreshold );
 121 }
 122
 123
 124 void CTrie::MakeCutsWhereCountExceeds( int count, int start, int end )
 125 {
 126         m_Root->MakeCutsWhereCountExceeds( count, start, end );
 127 }
 128
 129 //----------------------------------------------------------------
 130 ////////////////////////////////////////////////////////////////
 131 //----------------------------------------------------------------
 132 //
 133 //      Insert
 134
 135 CNode* CTrie::Insert( CStringSurrogate ssS, int* pResult )
 136 {
 137   CNode* pNode = NULL;
 138
 139   m_Root->Insert(ssS, m_NumberOfNodes, &pNode, pResult);
 140
 141   if ( pResult && *pResult == 1 )
 142   {
 143     m_Count++;
 144   }
 145
 146   m_TrieHasChangedFlag  = TRUE;
 147   m_IsAlphabetized    = FALSE;
 148
 149   return pNode;
 150 }
 151
 152 CNode* CTrie::Insert(CStringSurrogate ssS)
 153 {
 154   int Result        = 0;
 155   int* pResult      = &Result;
 156   CNode* pNode      = NULL;
 157
 158   m_Root->Insert(ssS, m_NumberOfNodes, &pNode, pResult);
 159
 160   if ( pResult && *pResult == 1 )
 161   {
 162     m_Count++;
 163   }
 164
 165   m_TrieHasChangedFlag  = TRUE;
 166   m_IsAlphabetized    = FALSE;
 167
 168   return pNode;
 169 }
 170
 171
 172 //----------------------------------------------------------------
 173 ////////////////////////////////////////////////////////////////
 174 //----------------------------------------------------------------
 175 //
 176 //
 177
 178 void CTrie::MakeATerminalPointerArray( CNode** Array )
 179 {
 180   int Index = 0;
 181
 182   m_Root->MakeATerminalPointerArray( Array, Index );
 183   Q_ASSERT ( (int) Index == m_Count );
 184
 185 }
 186
 187
 188
 189 int CTrie::CountValidSubstrings( CStringSurrogate& ss )
 190 {
 191         return m_Root->CountValidSubstrings( ss );
 192 }
 193
 194
 195
 196 CNode*    CTrie::Find1 ( CStringSurrogate SS, bool PartialOK )
 197 {
 198   CNode* pNode = m_Root->Find1(SS, PartialOK);
 199   return pNode;
 200 }
 201
 202 bool   CTrie::RemoveFromTrie ( const CStringSurrogate string, bool RemovePointerFlag )
 203 {
 204   CNode*  pNode         = m_Root;
 205   CNode*  qNode         = NULL;
 206   m_TrieHasChangedFlag  = TRUE;
 207   while ( pNode )   {
 208     for (int i = pNode->m_StartPoint + 1; i < pNode->m_BreakPoint; i++ )     {
 209       if ( string[i] != pNode->m_Key [i] )       {
 210         return FALSE;
 211       }
 212     }
 213     QChar c             = string [ pNode->m_BreakPoint ];
 214     qNode               = pNode->FindLetter( c );
 215     if ( qNode == NULL )     {
 216       return FALSE;
 217     }
 218     if (qNode->GetKey() == string )        {
 219         Q_ASSERT ( qNode->m_Pointer );
 220         qNode->m_ExistenceFlag = FALSE;
 221
 222         if ( RemovePointerFlag && m_AutoDelete )   {
 223             delete qNode->m_Pointer;
 224         }
 225         qNode->m_Pointer = NULL;
 226
 227         if ( qNode->m_Letters == NULL )       {
 228             delete qNode;
 229             m_NumberOfNodes--;
 230
 231             QChar*  NewLetters      = new QChar [ pNode->GetNumberOfBranches() - 1 ];
 232             CNode**  NewPointers    = new CNode* [ pNode->GetNumberOfBranches() - 1 ];
 233             int k = 0;
 234                 for (int j = 0; j < (int)pNode->GetNumberOfBranches(); j++)        {
 235                     if ( c == pNode->m_Letters[j] ) { continue; }
 236                     NewLetters[k] = pNode->m_Letters[j];
 237                     NewPointers[k] = pNode->m_Pointers[j];
 238                     k++;
 239             }
 240             Q_ASSERT ( k == (int)pNode->GetNumberOfBranches()-1 );
 241             delete [] pNode->m_Letters;  pNode->m_Letters  = NewLetters;
 242             delete [] pNode->m_Pointers; pNode->m_Pointers = NewPointers;
 243             pNode->SetNumberOfBranches(k);
 244       }
 245       else      {
 246         qNode->DoesNotExist();
 247       }
 248       m_Count--;
 249       return TRUE;
 250     }
 251     else    {
 252       pNode = qNode;
 253       continue;
 254    }
 255   }
 256   Q_ASSERT (FALSE);
 257   return FALSE;
 258 }
 259
 260
 261 CNode* CTrie::SearchForPrefix(CStringSurrogate& CStringSurrogate, int& Result )
 262 {
 263   CNode* pNode = NULL;
 264   Result = 0;
 265    pNode = m_Root->SearchForPrefix (CStringSurrogate, Result );
 266
 267   return pNode;
 268
 269
 270 }
 271
 272
 273 //----------------------------------------------------------------
 274 ////////////////////////////////////////////////////////////////
 275 //----------------------------------------------------------------
 276 //
 277 //    Get At
 278
 279
 280 CNode* CTrie::GetRoot1()
 281 {
 282   return m_Root;
 283 }
 284
 285 //----------------------------------------------------------------
 286 ////////////////////////////////////////////////////////////////
 287 //----------------------------------------------------------------
 288 //
 289 //    Alphabetize
 290 void CTrie::Alphabetize()
 291 {
 292   if ( m_IsAlphabetized == FALSE)
 293   {
 294     m_Root->Alphabetize();
 295   }
 296   m_IsAlphabetized = TRUE;
 297 }
 298
 299 int CTrie::ComputeNumberOfEntries()
 300 {
 301   return m_Root->ComputeNumberOfEntries(0);
 302 }
 303
 304 void  CTrie::CreateNodeArray()
 305 {
 306         // XXX. avoid delete/new cycle if there’s room
 307         delete[] m_NodeArray;
 308         m_NodeArray = new CNode*[m_NumberOfNodes];
 309
 310         int Index = 0;
 311         m_Root->CreateNodeArray(m_NodeArray, Index);
 312
 313         Q_ASSERT(Index = GetCount());
 314 }
 315
 316 void CTrie::CreateSuffixSignatures(const CStringSurrogate& prefix, CParse* out)
 317 { CreateSuffixSignatures(&prefix, out); }
 318
 319 //----------------------------------------------------------------------------
 320 void CTrie::CreateSuffixSignatures ( const CStringSurrogate* Prefix, CParse* pSignature)
 321 {
 322   // This finds the location of Prefix in the Trie, and takes all of the
 323   // suffixes to it and creates a "signature" of them.
 324
 325   CNode*          pNode;
 326   int            nResult;
 327   CStringSurrogate    ssInitial;
 328   CStringSurrogate    ssPrefix = *Prefix;
 329
 330   Alphabetize();
 331
 332
 333   pNode = SearchForPrefix ( ssPrefix, nResult );
 334
 335   Q_ASSERT ( nResult != 0 );
 336
 337   if ( pNode && nResult == 2 )
 338   {
 339     ssInitial = pNode->GetKey().Mid( ssPrefix.GetLength() );
 340   }
 341
 342   int Offset  =  ssPrefix.GetLength();
 343   if( pNode ) pNode->FindAllTerminalsBelowHere( pSignature, Offset );
 344 }
 345
 346
 347 //------------------------------------------------------------------------------------
 348 // find the deepest node in the Trie whose count is more than half of m_Count
 349 CNode*  CTrie::FindLowestMajorityNode()
 350 {
 351   CNode* pNode = m_Root->FindLowestMajorityNode( m_Count );
 352
 353   if ( pNode == m_Root ) { return NULL; }
 354   else
 355   {
 356     return pNode;
 357   }
 358 }
 359
 360
 361
 362 void CTrie::MakeAllNodesVisible(bool Flag)
 363 {
 364   m_Root->MakeAllVisible(Flag);
 365 }
 366
 367
 368 bool CTrie::MakeVisible( const CStringSurrogate string )
 369 {
 370   return m_Root->MakeVisible(string);
 371
 372 }
 373
 374
 375 //----------------------------------------------------------------//
 376 ////////////////////////////////////////////////////////////////
 377 //----------------------------------------------------------------//
 378 //
 379 //    New functions added for FSA
 380
 381
 382 void CTrie::MakeMorphemeBoundariesAtThisWidth(int n, int MinimumStemLength)
 383 {
 384
 385   int    ThisLength = 0;
 386   m_Root->MakeMorphemeBoundariesAtThisWidth(n, MinimumStemLength, ThisLength);
 387
 388 }
 389
 390
 391
 392
 393 //----------------------------------------------------------------//
 394   ////////////////////////////////////////////////////////////////
 395 //----------------------------------------------------------------//
 396
 397 void CTrie::MakeCutsAtMorphemeBoundary()
 398 {
 399   int depth = 0;
 400   m_Root->MakeCutsAtMorphemeBoundary( depth );
 401 }
 402
 403
 404 void CTrie::SetAutoDelete( bool b )
 405 {
 406   m_AutoDelete = b;
 407   m_Root->SetAutoDelete(b);
 408 }
 409
 410
 411
 412 // CNode
 413 /////////////////////////////////////////////////////////////
 414
 415 CNode::CNode(QString s, int StartPoint, int BreakPoint)
 416         : m_Key(new QChar[s.length()]), // filled below
 417         m_KeyLength(s.length()),
 418         m_CorpusCount(0),
 419         m_Pointer(),
 420         m_Letters(),
 421         m_NumberOfBranches(0),
 422         m_Pointers(),
 423         m_CountBelow(0),
 424         m_Visible(false),
 425         m_AutoDelete(true),     // *this owns m_Pointer
 426         // public:
 427         m_StartPoint(StartPoint),
 428         m_BreakPoint(BreakPoint),
 429         m_ExistenceFlag(false),
 430         m_MorphemeBoundary(false)
 431 { LxStrCpy(s, m_Key, s.length()); }
 432
 433 CNode::CNode(const CStringSurrogate& SS, int StartPoint, int BreakPoint)
 434         : m_Key(new QChar[SS.GetLength()]),     // filled below
 435         m_KeyLength(SS.GetLength()),
 436         m_CorpusCount(0),
 437         m_Pointer(),
 438         m_Letters(),
 439         m_NumberOfBranches(0),
 440         m_Pointers(),
 441         m_CountBelow(0),
 442         m_Visible(false),
 443         m_AutoDelete(true),     // *this owns m_Pointer
 444         // public:
 445         m_StartPoint(StartPoint),
 446         m_BreakPoint(BreakPoint),
 447         m_ExistenceFlag(false),
 448         m_MorphemeBoundary(false)
 449 { LxStrCpy(&SS, m_Key, SS.GetLength()); }
 450
 451 CNode::CNode()
 452         : m_Key(),
 453         m_KeyLength(0),
 454         m_CorpusCount(0),
 455         m_Pointer(),
 456         m_Letters(),
 457         m_NumberOfBranches(0),
 458         m_Pointers(),
 459         m_CountBelow(0),
 460         m_Visible(false),
 461         m_AutoDelete(true),     // *this owns m_Pointer
 462         // public:
 463         m_StartPoint(0),
 464         m_BreakPoint(0),
 465         m_ExistenceFlag(false),
 466         m_MorphemeBoundary(false) { }
 467
 468 CNode::~CNode()
 469 {
 470         // Delete child nodes
 471         if (m_Letters != 0) {
 472                 for (int i=0; i < m_NumberOfBranches; ++i)
 473                         delete m_Pointers[i];
 474                 delete[] m_Pointers;
 475         }
 476
 477         // If we own it, delete data
 478         if (m_AutoDelete)
 479                 delete m_Pointer;
 480
 481         delete[] m_Key;
 482         delete[] m_Letters;
 483 }
 484
 485 void CNode::SetAutoDelete( bool b )
 486 {
 487   m_AutoDelete = b;
 488   for( int i=0; m_Letters && i < m_NumberOfBranches; i++ )
 489   {
 490     m_Pointers[i]->SetAutoDelete(b);
 491   }
 492 }
 493
 494
 495 int     CNode::CountValidSubstrings( CStringSurrogate& ss )
 496 {
 497         int count = 0;
 498
 499         if( m_ExistenceFlag ) count++;
 500
 501         CNode* pNode = FindLetter( ss[0] );
 502         if( pNode )
 503         {
 504                 int step = pNode->m_BreakPoint - m_BreakPoint;
 505                 CStringSurrogate ssMid = ss.Mid( step );
 506                 count += pNode->CountValidSubstrings( ssMid );
 507         }
 508
 509         return count;
 510 }
 511
 512
 513 void CNode::FindSFBumps ( CMorphemeCollection& TempMorphemes, int SFThreshold )
 514 {
 515   if ( GetWidth() > SFThreshold )
 516   {
 517     TempMorphemes << CStringSurrogate( m_Key, 0, m_KeyLength );
 518   }
 519
 520   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
 521   {
 522     m_Pointers[i]->FindSFBumps (  TempMorphemes, SFThreshold );
 523   }
 524 }
 525
 526
 527 void CNode::BreakAllWordsBelowHere(int BreakLocation, CWordCollection* Words )
 528 {
 529   CStem* pWord;
 530
 531   CStringSurrogate ssWord;
 532
 533   if (   m_KeyLength > 2 &&  m_KeyLength > BreakLocation + 1)
 534   {
 535     ssWord = CSS(m_Key, 0, m_KeyLength);
 536
 537     ssWord = ssWord.Mid(1, ssWord.GetLength() - 2 );// eliminate first and last #
 538     pWord = *Words ^= ssWord;
 539     if ( pWord )
 540       pWord->CutRightBeforeHere (BreakLocation  );
 541   }
 542 }
 543
 544
 545 CNode* CNode::Insert(CStringSurrogate& SS, int& NumberOfNodes,
 546                         CNode** ppNode, int* pResult)
 547 {
 548         using std::auto_ptr;
 549         using std::copy;
 550         using std::swap;
 551
 552         // The node that is returned is the node immediately down from
 553         // node that called this function in the first place.
 554         // It may be "This" or it may not.
 555         // ppNode is a pointer to the Terminal node that is eventually
 556         // identified or created for the string in question.
 557         CStringSurrogate ssKey = GetKey();
 558         auto_ptr<CNode> this_node(this);
 559
 560         // Result: 1: new node added
 561         //         2: node already existed
 562
 563         //-----------------------------------------------------------------------//
 564
 565         // 1: A difference before m_BreakPoint: it's definitely a new string.
 566         // should i be initialized as m_StartPoint + 1??
 567         int i = m_StartPoint;
 568         for (; i < m_BreakPoint && i < SS.GetLength(); ++i) {
 569                 // XXX. SS and ssKey could be backwards, hence the obscure test.
 570 //              if ( SS[i] != ssKey[i] )
 571                 if ( LxStrCmp( &SS, ssKey.GetKey(),1,1,SS.GetStart()+i,ssKey.GetStart()+i) ) {
 572                         // we create a new node that dominates *this and also
 573                         // dominates the other new node created, new_node.
 574
 575                         auto_ptr<CNode> prev(new CNode(ssKey.Left(i), m_StartPoint, i));
 576                         prev->GetLink(this_node.release());
 577                         ++NumberOfNodes;
 578                         m_StartPoint = i;
 579
 580                         auto_ptr<CNode> new_node(new CNode(SS, i, SS.GetLength()));
 581                         new_node->Exists();
 582                         CNode* inserted = new_node.get();
 583                         prev->GetLink(new_node.release());
 584                         ++NumberOfNodes;
 585
 586                         *ppNode = inserted;
 587
 588                         // Declare success.
 589                         if (pResult) *pResult = 1;
 590
 591                         prev->SetCountBelow((m_ExistenceFlag ? 0 : 1) + m_CountBelow + 1);
 592                         prev->SetCorpusCount(m_CorpusCount + 1);
 593                         inserted->SetCorpusCount(1);
 594
 595                         prev->SetAutoDelete(m_AutoDelete);
 596                         inserted->SetAutoDelete(m_AutoDelete);
 597
 598                         return prev.release();
 599                 }
 600         }
 601         // Now i == m_BreakPoint or i == SS.GetLength(),
 602         // and m_Key[j] == SS.m_Key[j] for all j < i
 603
 604         //-----------------------------------------------------------------------//
 605
 606         // 2. "s" is shorter than this node's Key:
 607         if (i < m_BreakPoint && i == SS.GetLength()) {
 608                 auto_ptr<CNode> prev(new CNode(ssKey.Left(i), m_StartPoint, i));
 609                 prev->GetLink(this_node.release());
 610                 prev->Exists();
 611                 ++NumberOfNodes;
 612                 m_StartPoint = i;
 613                 *ppNode = prev.get();
 614
 615                 // Declare success.
 616                 if (pResult) *pResult = 1;
 617
 618                 prev->SetCountBelow((m_ExistenceFlag ? 0 : 1) + m_CountBelow);
 619                 prev->SetCorpusCount(m_CorpusCount + 1);
 620                 prev->SetAutoDelete(m_AutoDelete);
 621
 622                 return prev.release();
 623         }
 624
 625         //-----------------------------------------------------------------------//
 626
 627         // 3. "s" is exactly this node's key:
 628         if (i == m_BreakPoint && i == SS.GetLength()) {
 629                 if (m_ExistenceFlag)
 630                         // Already present.
 631                         *pResult = 2;
 632                 else
 633                         // Success.
 634                         *pResult = 1;
 635
 636                 Exists();
 637                 SetCorpusCount(m_CorpusCount + 1);
 638
 639                 *ppNode = this;
 640
 641                 return this_node.release();
 642         }
 643
 644         //-----------------------------------------------------------------------//
 645         // 4. This node only takes us part way into the word:
 646         QChar Letter = SS[m_BreakPoint];
 647         for (int j = 0;  j < m_NumberOfBranches; ++j) {
 648                 if (m_Letters[j] == Letter) {
 649                         CNode* next = m_Pointers[j];
 650                         int result;
 651                         auto_ptr<CNode> new_node(next->Insert(SS, NumberOfNodes,
 652                                                         ppNode, &result));
 653                         if (pResult) *pResult = result;
 654                         m_Pointers[j] = new_node.release();
 655
 656                         if (result == 1)
 657                                 // new descendent
 658                                 ++m_CountBelow;
 659
 660                         ++m_CorpusCount;
 661                         return this_node.release();
 662                 }
 663         }
 664
 665         //-----------------------------------------------------------------------//
 666         // 5. the letter at BreakPoint is new:
 667         auto_ptr<CNode> new_node(new CNode(SS, m_BreakPoint, SS.GetLength()));
 668         new_node->Exists();
 669         new_node->SetCorpusCount(1);
 670         new_node->SetAutoDelete(m_AutoDelete);
 671         ++NumberOfNodes;
 672         *ppNode = new_node.get();
 673
 674         int length = m_NumberOfBranches;
 675
 676         // XXX. use realloc work-alike
 677         QChar* NewLetters = new QChar[length + 1];
 678         CNode** NewPointers = new CNode*[length + 1];
 679         copy(m_Letters, m_Letters + length, NewLetters);
 680         copy(m_Pointers, m_Pointers + length, NewPointers);
 681         NewLetters[length] = Letter;
 682         NewPointers[length] = new_node.release();
 683
 684         swap(m_Letters, NewLetters);
 685         swap(m_Pointers, NewPointers);
 686         ++m_NumberOfBranches;
 687
 688         delete[] NewLetters;
 689         delete[] NewPointers;
 690
 691         // Declare success.
 692         if (pResult) *pResult = 1;
 693
 694         ++m_CountBelow;
 695         ++m_CorpusCount;
 696
 697         return this_node.release();
 698
 699         //-----------------------------------------------------------------------//
 700         // end ///////////////////////
 701 }
 702
 703
 704 CNode** CNode::GetLink ( const CStringSurrogate s )
 705 {
 706   int i;
 707
 708   QChar c = s[m_BreakPoint];
 709   int length = 0;
 710
 711   if (m_Letters)
 712   {
 713     length = m_NumberOfBranches;
 714   }
 715   for ( i = 0;  i < length; i++)
 716   {
 717     if (m_Letters[i] == c) return &m_Pointers[i];
 718   }
 719
 720   QChar* NewLetters = new QChar[length + 1];
 721   CNode** NewPointers = new CNode*[length + 1];
 722   for ( i = 0; i < length; i++)
 723   {
 724     NewLetters[i] = m_Letters[i];
 725     NewPointers[i] = m_Pointers[i];
 726   }
 727   NewLetters[length] = c;
 728   m_NumberOfBranches++;
 729   delete m_Letters;
 730   m_Letters = NewLetters;
 731   delete m_Pointers;
 732   m_Pointers = NewPointers;
 733   m_Pointers[length] = new CNode(s, m_BreakPoint, m_BreakPoint);
 734   return &m_Pointers[length];
 735 }
 736
 737
 738 CNode* CNode::FindLetter (QChar c)
 739 {
 740
 741   int length = 0;
 742   if (m_Letters) { length = m_NumberOfBranches;}
 743   for (int i = 0;  i < length; i++)
 744   {
 745     if (m_Letters[i] == c) return m_Pointers[i];
 746   }
 747
 748   return NULL;
 749 }
 750
 751
 752 //int CNode::GetCount() const
 753 //{
 754 //  return m_Count;
 755 //}
 756
 757
 758 CNode** CNode::GetLink(CNode* pNode)
 759 {
 760         using std::copy;
 761         using std::swap;
 762
 763         int length = m_NumberOfBranches;
 764
 765         // case 1: pNode is terminal, has same Key as this:
 766         if (pNode->GetKeyLength() == m_BreakPoint)
 767                 return 0;
 768
 769         QChar c = pNode->GetKey()[m_BreakPoint];
 770
 771         for (int i = 0;  i < length; ++i)
 772                 if (m_Letters[i] == c)
 773                         return &m_Pointers[i];
 774
 775         // XXX. should use realloc workalike
 776         QChar* NewLetters = new QChar[length + 1];
 777         CNode** NewPointers = new CNode*[length + 1];
 778         copy(m_Letters, m_Letters + length, NewLetters);
 779         copy(m_Pointers, m_Pointers + length, NewPointers);
 780         NewLetters[length] = c;
 781         NewPointers[length] = pNode;
 782
 783         swap(m_Letters, NewLetters);
 784         swap(m_Pointers, NewPointers);
 785         delete[] NewLetters;
 786         delete[] NewPointers;
 787
 788         ++m_NumberOfBranches;
 789         return &m_Pointers[length];
 790 }
 791
 792 void CNode::MakeCutsWhereCountExceeds( int count, int start, int end )
 793 {
 794   CStringSurrogate ssKey(m_Key,0,m_KeyLength);
 795 //  QString spaces = "\n";
 796   int i;
 797
 798   if( start < m_KeyLength && end+1 >= m_KeyLength && m_NumberOfBranches >= count )
 799   {
 800 //    for( i=0; i < m_KeyLength; i++ ) spaces += " ";
 801     CutAllWordsHereAndBelow_AfterNLetters ( m_KeyLength );
 802   }
 803
 804   if( end+1 >= m_KeyLength )
 805   {
 806     for( i=0; m_Letters && i < m_NumberOfBranches; i++ )
 807     {
 808       m_Pointers[i]->MakeCutsWhereCountExceeds( count, start, end );
 809     }
 810   }
 811 }
 812
 813
 814 CStringSurrogate CNode::GetKey()
 815 {
 816   return CStringSurrogate(m_Key,0,m_KeyLength );
 817 }
 818
 819
 820 void  CNode::MakeATerminalPointerArray (CNode** Array, int& Index)
 821 {
 822
 823   if (m_ExistenceFlag)
 824   {
 825     Array[ Index ] = this;
 826     Index++;
 827   }
 828
 829   for (int i = 0 ; m_Letters && i < (int)m_NumberOfBranches; i++)
 830   {
 831     m_Pointers[i]->MakeATerminalPointerArray(Array, Index);
 832   }
 833
 834 }
 835
 836
 837 CNode* CNode::Find1(const CStringSurrogate string, bool PartialOK )
 838 {
 839   if (m_Key && LxStrCmp( &string, m_Key, string.GetLength(), m_KeyLength ) == 0 && ( PartialOK || m_ExistenceFlag ) )
 840   {
 841     return this;
 842   }
 843
 844   if( m_Key )
 845   {
 846     if( string.GetLength() < m_BreakPoint )
 847     {
 848       if( !PartialOK ) return NULL;
 849     }
 850
 851     for( int i = m_StartPoint; i < m_BreakPoint-1; i++ )
 852     {
 853       if( string[i] != m_Key[i] )
 854       {
 855         if( PartialOK && ( i > m_StartPoint ) ) return this;
 856                 else return NULL;
 857       }
 858     }
 859   }
 860
 861   QChar c = string[m_BreakPoint];
 862   for ( int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
 863   {
 864     if ( c == m_Letters[i] )
 865     {
 866       return m_Pointers[i] ->Find1 (string);
 867     }
 868   }
 869   return NULL;
 870 }
 871
 872
 873 CNode* CNode::SearchForPrefix ( CStringSurrogate& SS, int& Result, int Letterno )
 874 {
 875   CNode* pNode;
 876   Q_ASSERT ( Letterno == m_StartPoint);
 877   if ( Letterno < m_BreakPoint-1)
 878   {
 879     for (int i = Letterno + 1; i < m_BreakPoint; i++)
 880     {
 881       if ( i == SS.GetLength() )
 882       {
 883         Result = 2;
 884         return this;
 885         // Prefix is inside of this node, however!
 886       }
 887       if ( SS[i] != m_Key[i] )
 888       {
 889         Result = 0;
 890         return NULL;
 891         // Prefix not found!
 892       }
 893     }
 894
 895   }
 896
 897   Letterno = m_BreakPoint;
 898
 899   if ( m_Key && SS == CStringSurrogate( m_Key, 0, m_KeyLength ) )
 900   {
 901     Result = 1;
 902     return this;
 903   }
 904
 905   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
 906   {
 907       if ( SS[Letterno] == m_Letters[i] )
 908       {
 909         pNode = FindLetter ( SS[m_BreakPoint] );
 910         pNode = pNode->SearchForPrefix ( SS, Result, m_BreakPoint);
 911         return pNode;
 912       }
 913   }
 914   Result = 0;
 915   return NULL;
 916 }
 917
 918
 919 void CNode::ListDisplay(Q3ListView* List, LinguisticaMainWindow* doc,
 920         int* count, QMap<QString, QString>* filter, bool ReverseFlag)
 921 {
 922   QString Output;
 923   CStringSurrogate ssKey(m_Key,0,m_KeyLength);
 924   QString star = "*",
 925       width = "  Width: ",
 926       lt_curly = "  {",
 927       rt_curly = "}",
 928       below = " Count below: ";
 929       below += QString("%1").arg(m_CountBelow);
 930
 931   // Advance counter
 932   if( doc && count )
 933   {
 934     // Update on multiples of 100
 935     if( (*count) % 100 == 0 )
 936       doc->status_display().progress = *count;
 937     *count = *count + 1;
 938   }
 939
 940   if (m_Key)
 941   {
 942     Output.append ( ssKey.Display(filter) );
 943     if ( ReverseFlag == TRUE )
 944     {
 945       Output.append( " (" );
 946       QString reverse;
 947       LxStrCpy_R( ssKey.Display(filter),reverse,ssKey.GetLength(), ssKey.GetStart() );
 948       Output.append( reverse + ")" );
 949     }
 950   }
 951
 952
 953   if (m_ExistenceFlag )
 954   {
 955     Output.append (star);
 956   }
 957   Output.append ( width );
 958   Output += QString("%1").arg( GetWidth() );
 959   if ( m_Letters )
 960   {
 961     Output.append (lt_curly);
 962     Output.append ( CStringSurrogate( m_Letters, 0, m_NumberOfBranches ).Display(filter) );
 963     Output.append (rt_curly);
 964   }
 965
 966   Output.append ( below );
 967
 968   CTrieListViewItem* item = new CTrieListViewItem( List, Output );
 969   item->setSelectable(false);
 970   item->setOpen(true);
 971
 972   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
 973   {
 974     m_Pointers[i] ->ListDisplay (item, doc, count, filter, ReverseFlag);
 975   }
 976 }
 977
 978
 979 void CNode::ListDisplay(Q3ListViewItem* List, LinguisticaMainWindow* doc,
 980         int* count, QMap<QString, QString>* filter, bool ReverseFlag)
 981 {
 982   QString Output;
 983   CStringSurrogate ssKey(m_Key,0,m_KeyLength);
 984   QString star = "*",
 985       width = "  Width: ",
 986       lt_curly = "  {",
 987       rt_curly = "}",
 988       below = " Count below: ";
 989       below += QString("%1").arg(m_CountBelow);
 990
 991   // Advance counter
 992   if( doc && count )
 993   {
 994     // Update on multiples of 100
 995     if( (*count) % 100 == 0 )
 996       doc->status_display().progress = *count;
 997     *count = *count + 1;
 998   }
 999
1000   if (m_Key)
1001   {
1002     Output.append ( ssKey.Display(filter) );
1003     if ( ReverseFlag == TRUE )
1004     {
1005       Output.append( " (" );
1006       QString reverse;
1007       LxStrCpy_R( ssKey.Display(filter),reverse,ssKey.GetLength(), ssKey.GetStart() );
1008       Output.append( reverse + ")" );
1009     }
1010   }
1011
1012
1013   if (m_ExistenceFlag )
1014   {
1015     Output.append (star);
1016   }
1017   Output.append ( width );
1018   Output += QString("%1").arg( GetWidth() );
1019   if ( m_Letters )
1020   {
1021     Output.append (lt_curly);
1022     Output.append ( CStringSurrogate( m_Letters, 0, m_NumberOfBranches ).Display(filter) );
1023     Output.append (rt_curly);
1024   }
1025
1026   Output.append ( below );
1027
1028   CTrieListViewItem* item = new CTrieListViewItem( List, Output );
1029   item->setSelectable(false);
1030   item->setOpen(true);
1031
1032   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
1033   {
1034     m_Pointers[i] ->ListDisplay (item, doc, count, filter, ReverseFlag);
1035   }
1036 }
1037
1038
1039 int CNode::GetWidth()
1040 {
1041   int width = 0;
1042   if (m_ExistenceFlag) { width = 1;}
1043
1044   if (m_Pointers) { return m_NumberOfBranches + width; } else {return width; }
1045
1046 }
1047
1048 namespace {
1049         // helper for CNode::Alphabetize
1050         // index_in<char>("Hello")(0) == 'H'.
1051         template<class T> class index_in : public std::unary_function<int, T> {
1052                 const T* array;
1053         public:
1054                 index_in(const T* v) : array(v) { }
1055                 T operator()(int i) { return array[i]; }
1056         };
1057 }
1058
1059 void CNode::Alphabetize()
1060 {
1061         using std::copy;
1062         using std::swap;
1063         using std::transform;
1064         using std::mem_fun;
1065
1066         const int Length = m_NumberOfBranches;
1067
1068         if (Length == 0)
1069                 // nothing to do
1070                 return;
1071
1072         QChar* NewLetters = new QChar[Length];
1073         CNode** NewPointers  = new CNode*[Length];
1074
1075         std::vector<int> shuffle(Length);
1076         SortLetters(&shuffle[0], m_Letters, Length);
1077
1078         transform(shuffle.begin(), shuffle.end(),
1079                         NewLetters, index_in<QChar>(m_Letters));
1080         transform(shuffle.begin(), shuffle.end(),
1081                         NewPointers, index_in<CNode*>(m_Pointers));
1082         swap(m_Letters, NewLetters);
1083         swap(m_Pointers, NewPointers);
1084
1085         delete[] NewLetters;
1086         delete[] NewPointers;
1087
1088         std::for_each(m_Pointers, m_Pointers + Length,
1089                         mem_fun(&CNode::Alphabetize));
1090 }
1091
1092
1093 void* CNode::Get_T_Pointer()
1094 {
1095   if (m_ExistenceFlag)
1096   {
1097     return m_Pointer;
1098   }
1099   else
1100   {
1101     return NULL;
1102   }
1103 }
1104
1105
1106 int CNode::ComputeNumberOfEntries(int count)
1107 {
1108   if (m_ExistenceFlag)
1109   {
1110     count++;
1111   }
1112
1113   for (int i = 0 ; m_Letters && i < (int)m_NumberOfBranches; i++)
1114   {
1115     count = m_Pointers[i]->ComputeNumberOfEntries(count);
1116   }
1117   return count;
1118 }
1119
1120
1121 void CNode::CreateNodeArray(CNode** NodeArray, int& Index)
1122 {
1123
1124   NodeArray[Index] = this;
1125   Index++;
1126
1127   for (int i = 0 ; m_Letters && i < (int)m_NumberOfBranches; i++)
1128   {
1129     m_Pointers[i]->CreateNodeArray(NodeArray, Index);
1130   }
1131
1132 }
1133
1134
1135 void CNode::FindAllTerminalsBelowHere( CParse* pSuffixes, int Offset )
1136 {
1137   CStringSurrogate ssPiece;
1138   if( m_ExistenceFlag )
1139   {
1140     ssPiece = CStringSurrogate( m_Key,0,m_KeyLength );
1141     pSuffixes->Append( ssPiece.Mid( Offset ) );
1142   }
1143
1144   for( int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++ )
1145   {
1146     m_Pointers[i]->FindAllTerminalsBelowHere ( pSuffixes, Offset );
1147   }
1148
1149 }
1150
1151
1152 CNode* CNode::FindLowestMajorityNode(int Count)
1153 {
1154   bool  FoundFlag = FALSE;
1155   CNode*  pNode;
1156
1157
1158   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
1159   {
1160     if ( m_Pointers[i]->GetCountBelow() > Count / 2 )
1161     {
1162       FoundFlag = TRUE;
1163       return pNode = m_Pointers[i]->FindLowestMajorityNode( Count );
1164     }
1165
1166   }
1167
1168   if ( FoundFlag == FALSE )
1169   {
1170     if (m_CountBelow > Count / 2 ) { return this; }
1171     else
1172     {
1173       return NULL;
1174     }
1175   }
1176   else return NULL;
1177
1178 }
1179
1180
1181 void CNode::DumpVisibleToLogFile(QTextOStream* stream,  bool ReverseFlag)
1182 {
1183   if (m_Visible && m_ExistenceFlag )
1184   {
1185     if (ReverseFlag)
1186     {
1187       QChar* string = new QChar[ m_KeyLength + 1];
1188       LxStrCpy_R(m_Key, string, m_KeyLength );
1189       *stream << string << endl;
1190       delete string;
1191     }
1192     else
1193       *stream << m_Key << endl;
1194   }
1195   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
1196   {
1197     m_Pointers[i]->DumpVisibleToLogFile(stream, ReverseFlag);
1198   }
1199
1200
1201 }
1202
1203 /*
1204 void CNode::DumpVisibleWords ( CWordCollection* Words,  bool ReverseFlag )
1205 {
1206   if (m_Visible && m_ExistenceFlag )
1207   {
1208     if (ReverseFlag)
1209     {
1210        *Words << CStringSurrogate(m_Key, 0, m_KeyLength);
1211     }
1212     else
1213     {
1214       *Words << CStringSurrogate(m_Key, 0, m_KeyLength);
1215     }
1216   }
1217   for (int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
1218   {
1219     m_Pointers[i]->DumpVisibleWords(Words, ReverseFlag);
1220   }
1221
1222 }
1223 */
1224
1225 void CNode::MakeAllVisible(bool Flag)
1226 {
1227   m_Visible = Flag;
1228   for (int i = 0 ; m_Letters && i < (int)m_NumberOfBranches; i++)
1229   {
1230     m_Pointers[i]->MakeAllVisible(Flag);
1231   }
1232 }
1233
1234
1235 bool CNode::MakeVisible( const CStringSurrogate string )
1236 {
1237   if (m_Key && LxStrCmp( &string, m_Key, string.GetLength(), m_KeyLength ) == 0 && m_ExistenceFlag)
1238   {
1239     m_Visible = TRUE;
1240     return TRUE;
1241   }
1242
1243   if (m_Key)
1244   {
1245     if ( string.GetLength() < m_BreakPoint )
1246     {
1247       return FALSE;
1248     }
1249     for (int i = m_StartPoint; i < m_BreakPoint-1;i++)
1250     {
1251       if ( string[i] != m_Key[i] )
1252       {
1253         return FALSE;
1254       }
1255     }
1256   }
1257
1258
1259   QChar c = string[m_BreakPoint];
1260   for ( int i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
1261   {
1262     if ( c == m_Letters[i] )
1263     {
1264       return m_Pointers[i] ->MakeVisible (string);
1265     }
1266   }
1267   return FALSE;
1268 }
1269
1270
1271 bool CNode::MakeMorphemeBoundariesAtThisWidth(int n, int MinimumStemLength, int ThisLength)
1272 {
1273   bool val;
1274   bool bLowerIsBoundary = FALSE;
1275   int   KeyLen = 0;
1276   int  NumberOfBranches=0;
1277
1278 //  QString DebugString;
1279 //  const char*  DebugStringDisplay;
1280 //  int    DebugInt;
1281
1282
1283   if ( m_Key)
1284   {
1285     KeyLen = GetKeyLength();
1286     ThisLength = KeyLen;
1287
1288   //  DebugString = QString(m_Key, KeyLen);
1289   //  DebugStringDisplay = DebugString.ascii();
1290   //  DebugInt = 1;
1291   }
1292
1293   NumberOfBranches = GetNumberOfBranches();
1294
1295    for (int i = 0 ; m_Letters && i < NumberOfBranches; i++)
1296   {
1297     val = m_Pointers[i]->MakeMorphemeBoundariesAtThisWidth(n, MinimumStemLength, ThisLength );
1298     if (val) bLowerIsBoundary = TRUE;
1299   }
1300
1301    if ( ThisLength >= MinimumStemLength && GetWidth() >= n )
1302   {
1303     m_MorphemeBoundary = TRUE;
1304   }
1305   else
1306   {
1307     m_MorphemeBoundary = false;
1308   }
1309
1310   return m_MorphemeBoundary;
1311 }
1312
1313
1314 void CNode::CutAllWordsHereAndBelow_AfterNLetters ( int n )
1315 {
1316   int  NumberOfBranches=0;
1317
1318   if ( m_ExistenceFlag )
1319   {
1320     ((CStem*)m_Pointer)->CutRightBeforeHere (n);
1321   }
1322
1323   NumberOfBranches = GetNumberOfBranches();
1324
1325   for (int i = 0 ; m_Letters && i < NumberOfBranches; i++)
1326   {
1327     m_Pointers[i]->CutAllWordsHereAndBelow_AfterNLetters ( n );
1328   }
1329 }
1330
1331
1332 void CNode::MakeCutsAtMorphemeBoundary( int depth )
1333 {
1334   int ThisDepth = depth;
1335   int   KeyLen = 0;
1336   int  NumberOfBranches=0;
1337
1338   if (m_Key)
1339   {
1340     KeyLen = GetKeyLength();
1341     ThisDepth = KeyLen;
1342   }
1343
1344   if ( m_MorphemeBoundary )
1345   {
1346     CutAllWordsHereAndBelow_AfterNLetters ( ThisDepth );
1347   }
1348
1349   NumberOfBranches = GetNumberOfBranches();
1350
1351   for (int i = 0 ; m_Letters && i < NumberOfBranches; i++)
1352   {
1353     m_Pointers[i]->MakeCutsAtMorphemeBoundary(ThisDepth);
1354   }
1355 }
1356
1357 int CTrie::ProjectTrieStructureOntoWord( CParse* parse )
1358 {
1359         int status = 0;
1360
1361         parse->ClearParseStructure();
1362
1363
1364         if( m_ReverseFlag )
1365         {
1366                 parse->ReverseMe();
1367
1368
1369         }
1370
1371
1372         status = m_Root->ProjectTrieStructureOntoWord( parse );
1373
1374
1375         if( m_ReverseFlag )
1376         {
1377                 parse->ReverseMe();
1378
1379
1380         }
1381
1382         return status;
1383 }
1384
1385 int CNode::ProjectTrieStructureOntoWord( CParse* parse, int position )
1386 {
1387   CStringSurrogate ssKey = GetKey();
1388   CStringSurrogate SS = parse->GetKey();
1389
1390   int newPosition = position;
1391
1392
1393
1394   // Result: -1: word doesn't exist
1395   //       0: word existed
1396
1397   //-----------------------------------------------------------------------//
1398
1399   // 1: A difference before m_BreakPoint: it's definitely a new string.
1400   int i = m_StartPoint;
1401   for (; (SS.GetLength() > 0) && m_Key && i < m_BreakPoint && i < SS.GetLength(); i++)
1402   {
1403         newPosition++;
1404
1405 //    if ( SS[i] != ssKey[i] )
1406     if ( LxStrCmp( &SS, ssKey.GetKey(),1,1,SS.GetStart()+i,ssKey.GetStart()+i) )
1407     {
1408       return -1;
1409     }
1410   }
1411
1412   //-----------------------------------------------------------------------//
1413
1414   // 2. "s" is shorter than this node's Key:
1415   if ( i < m_BreakPoint && i == SS.GetLength() )
1416   {
1417       return -1;
1418   }
1419
1420   //-----------------------------------------------------------------------//
1421
1422   // 3. "s" is exactly this node's key:
1423   if ( m_Key && LxStrCmp ( &SS, m_Key, SS.GetLength(), m_KeyLength, SS.GetStart() ) == 0 )
1424   {
1425         parse->SetPieceValue( parse->Size(), (double) m_CorpusCount );
1426
1427     return 0;
1428   }
1429
1430
1431   //-----------------------------------------------------------------------//
1432   // 4. This node only takes us part way into the word:
1433   QChar Letter = SS[m_BreakPoint];
1434   for (int j = 0;  m_Letters && j < (int)m_NumberOfBranches; j++)
1435   {
1436     if ( m_Letters[j] == Letter )
1437     {
1438
1439
1440                 parse->SetPieceValue( parse->Size(), (double) m_CorpusCount );
1441                 parse->CutNFromTheLeft( newPosition );
1442
1443
1444         return m_Pointers[j]->ProjectTrieStructureOntoWord( parse, newPosition );
1445     }
1446   }
1447
1448
1449   //-----------------------------------------------------------------------//
1450   // 5. the letter at BreakPoint is new:
1451   return -1;
1452
1453   //-----------------------------------------------------------------------//
1454   // end ///////////////////////
1455 }
1456
1457 QString CTrie::Display()
1458 {
1459         return QString( m_Root->Display( 0, m_ReverseFlag ) + "=========================" );
1460 }
1461
1462 QString CNode::Display( int tabs, bool ReverseFlag )
1463 {
1464   QString Output = " ";
1465   QString star = "*",
1466       width = "  Width: ",
1467       lt_curly = "  {",
1468       rt_curly = "}",
1469       below = " Count below: ";
1470       below += QString("%1").arg(m_CountBelow);
1471
1472   CStringSurrogate ssKey(m_Key,0,m_KeyLength);
1473   int i;
1474
1475         for( i = 0; i < tabs; i++ )
1476         {
1477                 Output.append( "__" );
1478         }
1479         Output.append( " " );
1480
1481   if (m_Key)
1482   {
1483     Output.append ( ssKey.Display() );
1484     if ( ReverseFlag == TRUE )
1485     {
1486       Output.append( " (" );
1487       QString reverse;
1488       LxStrCpy_R( ssKey.Display(),reverse,ssKey.GetLength(), ssKey.GetStart() );
1489       Output.append( reverse + ")" );
1490     }
1491   }
1492
1493
1494   if (m_ExistenceFlag )
1495   {
1496     Output.append (star);
1497   }
1498 //  Output.append ( width );
1499 //  Output += QString("%1").arg( GetWidth() );
1500   if ( m_Letters )
1501   {
1502     Output.append (lt_curly);
1503     Output.append ( CStringSurrogate( m_Letters, 0, m_NumberOfBranches ).Display() );
1504     Output.append (rt_curly);
1505   }
1506
1507 //  Output.append ( below );
1508
1509   Output.append ( "\n" );
1510
1511   for (i = 0; m_Letters && i < (int)m_NumberOfBranches; i++)
1512   {
1513     Output.append( m_Pointers[i]->Display( tabs+1, ReverseFlag ) );
1514   }
1515
1516   return Output;
1517 }
1518