Src/DasherCore/DasherModel.cpp

   1 // DasherModel.h
   2 //
   3 // Copyright (c) 2001-2005 David Ward
   4
   5 #include "../Common/Common.h"
   6
   7 #include <iostream>
   8 #include "../Common/Random.h"
   9 #include "DasherModel.h"
  10 #include "DasherView.h"
  11 #include "Parameters.h"
  12
  13 using namespace Dasher;
  14 using namespace std;
  15
  16 #include "Event.h"
  17 #include "DasherInterfaceBase.h"
  18 #include "LanguageModelling/PPMLanguageModel.h"
  19 #include "LanguageModelling/WordLanguageModel.h"
  20 #include "LanguageModelling/DictLanguageModel.h"
  21 #include "LanguageModelling/MixtureLanguageModel.h"
  22 #include "NodeCreationManager.h"
  23
  24 using namespace Dasher;
  25 using namespace std;
  26
  27 // Track memory leaks on Windows to the line that new'd the memory
  28 #ifdef _WIN32
  29 #ifdef _DEBUG
  30 #define DEBUG_NEW new( _NORMAL_BLOCK, THIS_FILE, __LINE__ )
  31 #define new DEBUG_NEW
  32 #undef THIS_FILE
  33 static char THIS_FILE[] = __FILE__;
  34 #endif
  35 #endif
  36
  37 // FIXME - need to get node deletion working properly and implement reference counting
  38
  39 // CDasherModel
  40
  41 CDasherModel::CDasherModel(CEventHandler *pEventHandler, CSettingsStore *pSettingsStore, CNodeCreationManager *pNCManager, CDasherInterfaceBase *pDashIface, CDasherView *pView, int iOffset, bool bGameMode, const std::string &strGameModeText)
  42 :CDasherComponent(pEventHandler, pSettingsStore), m_pDasherInterface(pDashIface) {
  43
  44   m_Root = 0;
  45   //  m_pLanguageModel =NULL;
  46
  47   m_Rootmin = 0;
  48   m_Rootmax = 0;
  49   m_Rootmin_min = 0;
  50   m_Rootmax_max = 0;
  51   m_dAddProb = 0.0;
  52   m_dMaxRate = 0.0;
  53   m_iTargetOffset = 0;
  54   m_dTotalNats = 0.0;
  55   m_bGameMode = bGameMode;
  56
  57   m_iOffset = iOffset;
  58
  59   // TODO: Need to rationalise the require conversion methods
  60
  61 #ifdef JAPANESE
  62   m_bRequireConversion = true;
  63 #else
  64   m_bRequireConversion = false;
  65 #endif
  66
  67   SetBoolParameter(BP_CONVERSION_MODE, m_bRequireConversion);
  68
  69   // Set max bitrate in the FrameRate class
  70   m_dMaxRate = GetLongParameter(LP_MAX_BITRATE) / 100.0;
  71   m_fr.SetMaxBitrate(m_dMaxRate);
  72   m_dAddProb = 0.003;
  73
  74   int iNormalization = GetLongParameter(LP_NORMALIZATION);
  75   m_Rootmin_min = int64_min / iNormalization / 2;
  76   m_Rootmax_max = int64_max / iNormalization / 2;
  77
  78   m_pNodeCreationManager = pNCManager;
  79
  80   //  m_pLanguageModel = m_pNodeCreationManager->GetLanguageModel();
  81   //  LearnContext = m_pNodeCreationManager->GetLearnContext();
  82
  83   //  m_bContextSensitive = true;
  84
  85   // TODO: Do something sensible here
  86   //  Start();
  87
  88   InitialiseAtOffset(iOffset, pView);
  89 }
  90
  91 CDasherModel::~CDasherModel() {
  92
  93   if(oldroots.size() > 0) {
  94     delete oldroots[0];
  95     oldroots.clear();
  96     // At this point we have also deleted the root - so better NULL pointer
  97     m_Root = NULL;
  98   }
  99
 100   if(m_Root)
 101     delete m_Root;
 102 }
 103
 104 void CDasherModel::HandleEvent(Dasher::CEvent *pEvent) {
 105
 106   if(pEvent->m_iEventType == 1) {
 107     Dasher::CParameterNotificationEvent * pEvt(static_cast < Dasher::CParameterNotificationEvent * >(pEvent));
 108
 109     switch (pEvt->m_iParameter) {
 110     case LP_MAX_BITRATE: // Delibarate fallthrough
 111     case LP_BOOSTFACTOR: // Deliberate fallthrough
 112     case LP_SPEED_DIVISOR:
 113       m_dMaxRate = GetLongParameter(LP_MAX_BITRATE) * GetLongParameter(LP_BOOSTFACTOR) / 100 / static_cast<double>(GetLongParameter(LP_SPEED_DIVISOR));
 114       m_fr.SetMaxBitrate(m_dMaxRate);
 115       break;
 116     case BP_CONTROL_MODE: // Rebuild the model if control mode is switched on/off
 117       RebuildAroundNode(Get_node_under_crosshair());
 118       break;
 119     case BP_DELAY_VIEW:
 120       MatchTarget(GetBoolParameter(BP_DELAY_VIEW));
 121       break;
 122     case BP_DASHER_PAUSED:
 123       if(GetBoolParameter(BP_SLOW_START))
 124         m_iStartTime = 0;
 125       else
 126         m_iStartTime = 1;
 127       break;
 128     default:
 129       break;
 130     }
 131   }
 132   else if(pEvent->m_iEventType == 2) {
 133     // Keep track of where we are in the buffer
 134     CEditEvent *pEditEvent(static_cast < CEditEvent * >(pEvent));
 135
 136     if(pEditEvent->m_iEditType == 1) {
 137       m_iOffset += pEditEvent->m_sText.size();
 138     }
 139     else if(pEditEvent->m_iEditType == 2) {
 140       m_iOffset -= pEditEvent->m_sText.size();
 141     }
 142   }
 143 }
 144
 145 void CDasherModel::Make_root(CDasherNode *pNewRoot) {
 146   if(!pNewRoot->NodeIsParent(m_Root))
 147     return;
 148
 149   m_Root->SetFlag(NF_COMMITTED, true);
 150
 151   // Remove all children of current root other than the new root and
 152   // push the new root onto the stack
 153
 154   // TODO: Is the stack necessary at all? We may as well just keep the
 155   // existing data structure?
 156
 157   //  m_Root->DeleteNephews(pNewRoot);
 158
 159   oldroots.push_back(m_Root);
 160
 161   while((oldroots.size() > 10) && (!m_bRequireConversion || (oldroots[0]->GetFlag(NF_CONVERTED)))) {
 162     oldroots[0]->OrphanChild(oldroots[1]);
 163     delete oldroots[0];
 164     oldroots.pop_front();
 165   }
 166
 167   m_Root = pNewRoot;
 168
 169   // Update the root coordinates, as well as any currently scheduled locations
 170   myint range = m_Rootmax - m_Rootmin;
 171   m_Rootmax = m_Rootmin + (range * m_Root->Hbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 172   m_Rootmin = m_Rootmin + (range * m_Root->Lbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 173
 174   for(std::deque<SGotoItem>::iterator it(m_deGotoQueue.begin()); it != m_deGotoQueue.end(); ++it) {
 175     myint r = it->iN2 - it->iN1;
 176     it->iN2 = it->iN1 + (r * m_Root->Hbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 177     it->iN1 = it->iN1 + (r * m_Root->Lbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 178   }
 179 }
 180
 181 void CDasherModel::RecursiveMakeRoot(CDasherNode *pNewRoot) {
 182   // TODO: Macros for this kind of thing
 183   if(!pNewRoot)
 184     return;
 185
 186   // TODO: we really ought to check that pNewRoot is actually a
 187   // descendent of the root, although that should be guaranteed
 188
 189   if(!pNewRoot->NodeIsParent(m_Root))
 190     RecursiveMakeRoot(pNewRoot->Parent());
 191
 192   // Don't try to reparent subnodes
 193   //  if(!pNewRoot->GetFlag(NF_SUBNODE))
 194     Make_root(pNewRoot);
 195 }
 196
 197 void CDasherModel::RebuildAroundNode(CDasherNode *pNode) {
 198   RecursiveMakeRoot(pNode);
 199   ClearRootQueue();
 200   m_Root->Delete_children();
 201   m_Root->m_pNodeManager->PopulateChildren(m_Root);
 202 }
 203
 204 // TODO: Need to make this do the right thing with subnodes
 205 void CDasherModel::Reparent_root(int lower, int upper) {
 206   // Change the root node to the parent of the existing node. We need
 207   // to recalculate the coordinates for the "new" root as the user may
 208   // have moved around within the current root
 209
 210   CDasherNode *pNewRoot;
 211
 212   if(oldroots.size() == 0) {
 213     // Figure out how many nodes are between the crosshair and the
 214     // current root. This is used to figure out the cursor position of
 215     // the current root in order to obtain context.
 216
 217     // TODO: store cursor position in the node itself. This would make
 218     // life a lot easier in several ways
 219     //    CDasherNode *pCurrentNode(Get_node_under_crosshair());
 220     int iGenerations(0);
 221
 222     // TODO: This was failing - figure out why
 223
 224 //     while(pCurrentNode != m_Root) {
 225 //       ++iGenerations;
 226 //       pCurrentNode = pCurrentNode->Parent();
 227 //     }
 228
 229     // Tell the node manager to rebuild the parent
 230
 231     pNewRoot = m_Root->m_pNodeManager->RebuildParent(m_Root, iGenerations);
 232
 233   }
 234   else {
 235     pNewRoot = oldroots.back();
 236     oldroots.pop_back();
 237
 238     while((oldroots.size() > 0) && pNewRoot->GetFlag(NF_SUBNODE)) {
 239       pNewRoot = oldroots.back();
 240       oldroots.pop_back();
 241     }
 242   }
 243
 244   // Return if there's no existing parent and no way of recreating one
 245   if(!pNewRoot) {
 246     return;
 247   }
 248
 249   pNewRoot->SetFlag(NF_COMMITTED, false);
 250
 251   CDasherNode *pCurrent = m_Root;
 252
 253   // Need to iterate through group pseudo-nodes
 254   while(pCurrent != pNewRoot) {
 255
 256     lower = pCurrent->Lbnd();
 257     upper = pCurrent->Hbnd();
 258
 259     pCurrent = pCurrent->Parent();
 260
 261     myint iWidth = upper - lower;
 262     myint iRootWidth = m_Rootmax - m_Rootmin;
 263
 264     // Fail and undo root creation if the new root is bigger than allowed by normalisation
 265     if(!(pNewRoot->GetFlag(NF_SUBNODE)) && (((myint((GetLongParameter(LP_NORMALIZATION) - upper)) / static_cast<double>(iWidth))
 266         > (m_Rootmax_max - m_Rootmax)/static_cast<double>(iRootWidth)) ||
 267        ((myint(lower) / static_cast<double>(iWidth))
 268         > (m_Rootmin - m_Rootmin_min) / static_cast<double>(iRootWidth)))) {
 269       pNewRoot->OrphanChild(m_Root);
 270       delete pNewRoot;
 271       return;
 272     }
 273
 274     //Update the root coordinates to reflect the new root
 275     m_Root = pNewRoot;
 276
 277     m_Rootmax = m_Rootmax + (myint((GetLongParameter(LP_NORMALIZATION) - upper)) * iRootWidth / iWidth);
 278     m_Rootmin = m_Rootmin - (myint(lower) * iRootWidth / iWidth);
 279
 280     for(std::deque<SGotoItem>::iterator it(m_deGotoQueue.begin()); it != m_deGotoQueue.end(); ++it) {
 281       iRootWidth = it->iN2 - it->iN1;
 282       it->iN2 = it->iN2 + (myint((GetLongParameter(LP_NORMALIZATION) - upper)) * iRootWidth / iWidth);
 283       it->iN1 = it->iN1 - (myint(lower) * iRootWidth / iWidth);
 284     }
 285   }
 286 }
 287
 288 void CDasherModel::ClearRootQueue() {
 289   while(oldroots.size() > 0) {
 290     if(oldroots.size() > 1) {
 291       oldroots[0]->OrphanChild(oldroots[1]);
 292     }
 293     else {
 294       oldroots[0]->OrphanChild(m_Root);
 295     }
 296     delete oldroots[0];
 297     oldroots.pop_front();
 298   }
 299 }
 300
 301 CDasherNode *CDasherModel::Get_node_under_crosshair() {
 302     return m_Root->Get_node_under(GetLongParameter(LP_NORMALIZATION), m_Rootmin + m_iTargetOffset, m_Rootmax + m_iTargetOffset, GetLongParameter(LP_OX), GetLongParameter(LP_OY));
 303 }
 304
 305 CDasherNode *CDasherModel::Get_node_under_mouse(myint Mousex, myint Mousey) {
 306   return m_Root->Get_node_under(GetLongParameter(LP_NORMALIZATION), m_Rootmin + m_iTargetOffset, m_Rootmax + m_iTargetOffset, Mousex, Mousey);
 307 }
 308
 309 // void CDasherModel::Start() {
 310
 311 //   // FIXME - re-evaluate this function and SetContext...
 312
 313 // //              m_pEditbox->get_new_context(ContextString,5);
 314
 315 //   std::cout << "Called CDasherModel::Start()" << std::endl;
 316
 317 //   std::string strNewContext("");
 318
 319 //   SetContext(strNewContext);    // FIXME - REALLY REALLY broken!
 320
 321 //   CEditContextEvent oEvent(5);
 322
 323 //   InsertEvent(&oEvent);
 324
 325 //   // FIXME - what if we don't get a reply?
 326
 327 // //      m_pLanguageModel->ReleaseNodeContext(therootcontext);
 328 // //      ppmmodel->dump();
 329 // //      dump();
 330
 331 // }
 332
 333 void CDasherModel::DeleteTree() {
 334   if(oldroots.size() > 0) {
 335     delete oldroots[0];
 336     oldroots.clear();
 337     m_Root = NULL;
 338   }
 339
 340   delete m_Root;
 341 }
 342
 343 void CDasherModel::InitialiseAtOffset(int iOffset, CDasherView *pView) {
 344   DeleteTree();
 345
 346   if(iOffset == 0)
 347     m_Root = GetRoot(0, NULL, 0,GetLongParameter(LP_NORMALIZATION), NULL);
 348   else {
 349     // Get the most recent character
 350     std::string strContext = m_pDasherInterface->GetContext(iOffset - 1, 1);
 351
 352     CAlphabetManager::SRootData oData;
 353
 354     oData.szContext = new char[strContext.size() + 1];
 355     strcpy(oData.szContext, strContext.c_str());
 356
 357     oData.iOffset = iOffset;
 358
 359     m_Root = GetRoot(0, NULL, 0, GetLongParameter(LP_NORMALIZATION), &oData);
 360
 361     delete[] oData.szContext;
 362   }
 363
 364   // Create children of the root
 365   // TODO: What about parents?
 366
 367   Recursive_Push_Node(m_Root, 0);
 368
 369   // Set the root coordinates so that the root node is an appropriate
 370   // size and we're not in any of the children
 371
 372   double dFraction( 1 - (1 - m_Root->MostProbableChild() / static_cast<double>(GetLongParameter(LP_NORMALIZATION))) / 2.0 );
 373
 374   int iWidth( static_cast<int>( (GetLongParameter(LP_MAX_Y) / (2.0*dFraction)) ) );
 375
 376   m_Rootmin = GetLongParameter(LP_MAX_Y) / 2 - iWidth / 2;
 377   m_Rootmax = GetLongParameter(LP_MAX_Y) / 2 + iWidth / 2;
 378
 379   m_iTargetOffset = 0;
 380
 381   if(pView) {
 382     while(pView->IsNodeVisible(m_Rootmin,m_Rootmax)) {
 383       CDasherNode *pOldRoot = m_Root;
 384       Reparent_root(m_Root->Lbnd(), m_Root->Hbnd());
 385       if(m_Root == pOldRoot)
 386         break;
 387     }
 388   }
 389
 390   // TODO: See if this is better positioned elsewhere
 391   m_pDasherInterface->ScheduleRedraw();
 392
 393
 394 }
 395
 396 // void CDasherModel::SetContext(std::string &sNewContext) {
 397
 398 //   std::cout << "Called CDasherModel::SetContext()" << std::endl;
 399
 400 //   // TODO: This is probably the area most significantly in need of a
 401 //   // rethink. Get the language model out of here!
 402 //   m_deGotoQueue.clear();
 403
 404 //   DeleteTree();
 405
 406 //   // CLanguageModel::Context therootcontext = m_pLanguageModel->CreateEmptyContext();
 407
 408 //   if(sNewContext.size() == 0) {
 409 //     m_Root = GetRoot(0, NULL, 0,GetLongParameter(LP_NORMALIZATION), NULL);
 410
 411 //     //    EnterText(therootcontext, ". ");
 412 //   }
 413 //   else {
 414 //     std::vector<symbol> vSymbols;
 415 //     //    m_pLanguageModel->SymbolAlphabet().GetAlphabetPointer()->GetSymbols(&vSymbols, &sNewContext, false);
 416
 417 //     int iRootSymbol(vSymbols[vSymbols.size()-1]);
 418
 419 //     m_Root = GetRoot(0, NULL, 0,GetLongParameter(LP_NORMALIZATION), &iRootSymbol);
 420
 421 //     //    EnterText(therootcontext, sNewContext);
 422 //   }
 423
 424 //   // TODO: Reimplement
 425 //   //  m_pLanguageModel->ReleaseContext(LearnContext);
 426 //   // LearnContext = m_pLanguageModel->CloneContext(therootcontext);
 427
 428 //   // TODO: Reimplement
 429 //   //  m_Root->SetContext(therootcontext);   // node takes control of the context
 430 //   Recursive_Push_Node(m_Root, 0);
 431
 432 //   double dFraction( 1 - (1 - m_Root->MostProbableChild() / static_cast<double>(GetLongParameter(LP_NORMALIZATION))) / 2.0 );
 433
 434 //   int iWidth( static_cast<int>( (GetLongParameter(LP_MAX_Y) / (2.0*dFraction)) ) );
 435
 436 //   m_Rootmin = GetLongParameter(LP_MAX_Y) / 2 - iWidth / 2;
 437 //   m_Rootmax = GetLongParameter(LP_MAX_Y) / 2 + iWidth / 2;
 438
 439 //   m_iTargetOffset = 0;
 440
 441 // //   m_iTargetMin = m_Rootmin;
 442 // //   m_iTargetMax = m_Rootmax;
 443 // }
 444
 445 void CDasherModel::Get_new_root_coords(myint Mousex, myint Mousey, myint &iNewMin, myint &iNewMax, unsigned long iTime) {
 446
 447   // Avoid Mousex == 0, as this corresponds to infinite zoom
 448   if(Mousex <= 0) {
 449     Mousex = 1;
 450   }
 451
 452   if(m_iStartTime == 0)
 453     m_iStartTime = iTime;
 454
 455   int iSteps = m_fr.Steps();
 456
 457   double dFactor;
 458
 459   if(IsSlowdown(iTime))
 460     dFactor = 0.1 * (1 + 9 * ((iTime - m_iStartTime) / static_cast<double>(GetLongParameter(LP_SLOW_START_TIME))));
 461   else
 462     dFactor = 1.0;
 463
 464   iSteps = static_cast<int>(iSteps / dFactor);
 465
 466   // If Mousex is too large we risk overflow errors, so limit it
 467   int iMaxX = (1 << 29) / iSteps;
 468
 469   if(Mousex > iMaxX)
 470     Mousex = iMaxX;
 471
 472   // Cache some results so we don't do a huge number of parameter lookups
 473
 474   myint iMaxY(GetLongParameter(LP_MAX_Y));
 475   myint iOX(GetLongParameter(LP_OX));
 476   myint iOY(GetLongParameter(LP_OY));
 477
 478   // Calculate what the extremes of the viewport will be when the
 479   // point under the cursor is at the cross-hair. This is where
 480   // we want to be in iSteps updates
 481
 482   int iTargetMin(Mousey - ((myint)iMaxY * Mousex) / (2 * (myint)iOX));
 483   int iTargetMax(Mousey + ((myint)iMaxY * Mousex) / (2 * (myint)iOY));
 484
 485   // iSteps is the number of update steps we need to get the point
 486   // under the cursor over to the cross hair. Calculated in order to
 487   // keep a constant bit-rate.
 488
 489   DASHER_ASSERT(iSteps > 0);
 490
 491   // Calculate the new values of iTargetMin and iTargetMax required to
 492   // perform a single update step. Note that the slightly awkward
 493   // expressions are in order to reproduce the behaviour of the old
 494   // algorithm
 495
 496   int iNewTargetMin;
 497   int iNewTargetMax;
 498
 499   iNewTargetMin = (iTargetMin * iMaxY / (iMaxY + (iSteps - 1) * (iTargetMax - iTargetMin)));
 500
 501   iNewTargetMax = ((iTargetMax * iSteps - iTargetMin * (iSteps - 1)) * iMaxY) / (iMaxY + (iSteps - 1) * (iTargetMax - iTargetMin));
 502
 503   iTargetMin = iNewTargetMin;
 504   iTargetMax = iNewTargetMax;
 505
 506   // Calculate the minimum size of the viewport corresponding to the
 507   // maximum zoom.
 508
 509   myint iMinSize(m_fr.MinSize(iMaxY, dFactor));
 510
 511   if((iTargetMax - iTargetMin) < iMinSize) {
 512     iNewTargetMin = iTargetMin * (iMaxY - iMinSize) / (iMaxY - (iTargetMax - iTargetMin));
 513     iNewTargetMax = iNewTargetMin + iMinSize;
 514
 515     iTargetMin = iNewTargetMin;
 516     iTargetMax = iNewTargetMax;
 517   }
 518
 519   iNewMin = (((m_Rootmin - iTargetMin) * (myint)GetLongParameter(LP_MAX_Y)) / (iTargetMax - iTargetMin));
 520   iNewMax = (((m_Rootmax - iTargetMax) * (myint)GetLongParameter(LP_MAX_Y)) / (iTargetMax - iTargetMin) + (myint)GetLongParameter(LP_MAX_Y));
 521 }
 522
 523 bool CDasherModel::UpdatePosition(myint miMousex, myint miMousey, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
 524   // Clear out parameters that might get passed in to track user activity
 525   if (pAdded != NULL)
 526     pAdded->clear();
 527   if (pNumDeleted != NULL)
 528     *pNumDeleted = 0;
 529
 530   if(GetBoolParameter(BP_DASHER_PAUSED) && (m_deGotoQueue.size() == 0))
 531      return false;
 532
 533   myint iNewMin;
 534   myint iNewMax;
 535
 536   if(m_deGotoQueue.size() == 0) {
 537     // works out next viewpoint
 538     Get_new_root_coords(miMousex, miMousey, iNewMin, iNewMax, iTime);
 539
 540     if(GetBoolParameter(BP_OLD_STYLE_PUSH))
 541       OldPush(miMousex, miMousey);
 542   }
 543   else {
 544     iNewMin = m_deGotoQueue.front().iN1;
 545     iNewMax = m_deGotoQueue.front().iN2;
 546     m_deGotoQueue.pop_front();
 547   }
 548
 549   m_dTotalNats += log((iNewMax - iNewMin) / static_cast<double>(m_Rootmax - m_Rootmin));
 550
 551   // Now actually zoom to the new location
 552   NewGoTo(iNewMin, iNewMax, pAdded, pNumDeleted);
 553
 554   return true;
 555 }
 556
 557 void CDasherModel::OldPush(myint iMousex, myint iMousey) {
 558   // push node under mouse
 559   CDasherNode *pUnderMouse = Get_node_under_mouse(iMousex, iMousey);
 560
 561   Push_Node(pUnderMouse);
 562
 563   if(Framerate() > 4) {
 564     // push node under mouse but with x coord on RHS
 565     CDasherNode *pRight = Get_node_under_mouse(50, iMousey);
 566     Push_Node(pRight);
 567   }
 568
 569   if(Framerate() > 8) {
 570     // push node under the crosshair
 571     CDasherNode *pUnderCross = Get_node_under_crosshair();
 572     Push_Node(pUnderCross);
 573   }
 574
 575   int iRandom = RandomInt();
 576
 577   if(Framerate() > 8) {
 578     // add some noise and push another node
 579     CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 500 - 250);
 580     Push_Node(pRight);
 581   }
 582
 583   iRandom = RandomInt();
 584
 585   if(Framerate() > 15) {
 586     // add some noise and push another node
 587     CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 500 - 250);
 588     Push_Node(pRight);
 589   }
 590
 591   // only do this is Dasher is flying
 592   if(Framerate() > 30) {
 593     for(int i = 1; i < int (Framerate() - 30) / 3; i++) {
 594
 595       int iRandom = RandomInt();
 596
 597       if(Framerate() > 8) {
 598               // add some noise and push another node
 599         CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 500 - 250);
 600               Push_Node(pRight);
 601       }
 602
 603       iRandom = RandomInt();
 604       // push at a random node on the RHS
 605       CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 1000 - 500);
 606       Push_Node(pRight);
 607
 608     }
 609   }
 610 }
 611
 612 void CDasherModel::RecursiveOutput(CDasherNode *pNode, Dasher::VECTOR_SYMBOL_PROB* pAdded) {
 613   if(pNode->Parent() && (!pNode->Parent()->GetFlag(NF_SEEN)))
 614     RecursiveOutput(pNode->Parent(), pAdded);
 615
 616   if(pNode->Parent())
 617     pNode->Parent()->m_pNodeManager->Leave(pNode->Parent());
 618
 619   pNode->m_pNodeManager->Enter(pNode);
 620
 621   pNode->SetFlag(NF_SEEN, true);
 622   pNode->m_pNodeManager->Output(pNode, pAdded, GetLongParameter(LP_NORMALIZATION));
 623 }
 624
 625
 626 // This is similar to Get_new_goto_coords, but doesn't actually change Rootmax and Rootmin.
 627 // Instead it gives information for NewGoTo to make direct changes in the root coordinates.
 628 // #define ZOOMDENOM (1<<10)
 629 // #define STEPNUM   48
 630 // #define STEPDENOM 64
 631 // double CDasherModel::Plan_new_goto_coords(int iRxnew, myint mousey, int *iSteps, myint *o1, myint *o2 , myint *n1, myint *n2)
 632 // {
 633 //   m_Stepnum = GetLongParameter(LP_ZOOMSTEPS);
 634 //   int iRxnew_dup = iRxnew;
 635 //   // note -- iRxnew is the zoom factor  in units of ZOOMDENOM
 636 //   *o1 = m_Rootmin ;
 637 //   *o2 = m_Rootmax ;
 638 //   DASHER_ASSERT(iRxnew > 0);
 639 //   if (iRxnew < ZOOMDENOM && m_Rootmax<(myint)GetLongParameter(LP_MAX_Y) && m_Rootmin>0 ) {
 640 //     // refuse to zoom backwards if the entire root node is visible.
 641 //     *iSteps = 0 ;
 642 //     *n1 = m_Rootmin;
 643 //     *n2 = m_Rootmax;
 644 //   }
 645 //   else {
 646 //     myint above=(mousey-*o1);
 647 //     myint below=(*o2-mousey);
 648
 649 //     myint miNewrootzoom= GetLongParameter(LP_MAX_Y)/2 ;
 650 //     myint newRootmax=miNewrootzoom+(below*iRxnew/ZOOMDENOM); // is there a risk of overflow in this multiply?
 651 //     myint newRootmin=miNewrootzoom-(above*iRxnew/ZOOMDENOM);
 652
 653 //     *n1 = newRootmin;
 654 //     *n2 = newRootmax;
 655
 656 //     *iSteps = 1;
 657
 658 //     // We might be moving at zoomfactor one vertically, in which case the below invention won't
 659 //     // come up with more than one step.  Look for a mousey difference and use an iSteps concordant
 660 //     // to that if it would be larger than the iSteps created by taking the log of the zoomfactor.
 661 //     int distance = mousey - ((myint)GetLongParameter(LP_MAX_Y)/2);
 662
 663 //     double s = (log(2.0) * 2 / log( (STEPDENOM*1.0)/(m_Stepnum*1.0)) ) / 4096;
 664
 665 //     double alpha = 2 * (2 * s);
 666 //     int alternateSteps = int(alpha * abs(distance));
 667
 668 //     // Take log of iRxnew to base ( STEPDENOM / STEPNUM ):
 669 //     if ( STEPDENOM > m_Stepnum && m_Stepnum > 0 ) { // check that the following loop will terminate.
 670 //       //cout << "iRxnew is " << iRxnew << " and ZOOMDENOM is" << ZOOMDENOM << endl;
 671 //       if ( iRxnew > ZOOMDENOM ) {
 672 //         while ( iRxnew > ZOOMDENOM ) {
 673 //           *iSteps += 1;
 674 //           iRxnew = iRxnew * m_Stepnum / STEPDENOM;
 675 //         }
 676 //       } else {
 677 //         while ( iRxnew < ZOOMDENOM ) {
 678 //           *iSteps += 1;
 679 //           iRxnew = iRxnew * STEPDENOM / m_Stepnum;
 680 //         }
 681 //       }
 682 //     }
 683
 684 //     // Done taking log of iRxnew.
 685 //     if (alternateSteps > *iSteps) {
 686 //       *iSteps = alternateSteps;
 687 //     }
 688 //    }
 689
 690 //   double iRxnew_ratio = (double) iRxnew_dup / ZOOMDENOM;
 691 //   double iRxnew_log = log(iRxnew_ratio);
 692 //   return iRxnew_log;
 693 // }
 694
 695 void CDasherModel::NewGoTo(myint newRootmin, myint newRootmax, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
 696   // Find out the current node under the crosshair
 697   CDasherNode *old_under_cross=Get_node_under_crosshair();
 698
 699   // Update the max and min of the root node to make iTargetMin and
 700   // iTargetMax the edges of the viewport.
 701
 702   if(newRootmin + m_iTargetOffset > (myint)GetLongParameter(LP_MAX_Y) / 2 - 1)
 703     newRootmin = (myint)GetLongParameter(LP_MAX_Y) / 2 - 1 - m_iTargetOffset;
 704
 705   if(newRootmax + m_iTargetOffset < (myint)GetLongParameter(LP_MAX_Y) / 2 + 1)
 706     newRootmax = (myint)GetLongParameter(LP_MAX_Y) / 2 + 1 - m_iTargetOffset;
 707
 708   // Check that we haven't drifted too far. The rule is that we're not
 709   // allowed to let the root max and min cross the midpoint of the
 710   // screen.
 711
 712   if(newRootmax < m_Rootmax_max && newRootmin > m_Rootmin_min && (newRootmax - newRootmin) > (myint)GetLongParameter(LP_MAX_Y) / 4) {
 713     // Only update if we're not making things big enough to risk
 714     // overflow. In theory we should have reparented the root well
 715     // before getting this far.
 716     //
 717     // Also don't allow the update if it will result in making the
 718     // root too small. Again, we should have re-generated a deeper
 719     // root in most cases, but the original root is an exception.
 720
 721     m_Rootmax = newRootmax;
 722     m_Rootmin = newRootmin;
 723
 724     m_iTargetOffset = (m_iTargetOffset * 90) / 100;
 725   }
 726   else {
 727     // TODO - force a new root to be chosen, so that we get better
 728     // behaviour than just having Dasher stop at this point.
 729   }
 730
 731   // Check whether new nodes need to be created
 732   CDasherNode* new_under_cross = Get_node_under_crosshair();
 733   Push_Node(new_under_cross);
 734
 735   HandleOutput(new_under_cross, old_under_cross, pAdded, pNumDeleted);
 736 }
 737
 738 void CDasherModel::HandleOutput(CDasherNode *pNewNode, CDasherNode *pOldNode, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
 739   if(pNewNode != pOldNode)
 740     DeleteCharacters(pNewNode, pOldNode, pNumDeleted);
 741
 742   if(pNewNode->GetFlag(NF_SEEN))
 743     return;
 744
 745   RecursiveOutput(pNewNode, pAdded);
 746 }
 747
 748 bool CDasherModel::DeleteCharacters(CDasherNode *newnode, CDasherNode *oldnode, int* pNumDeleted) {
 749   // DJW cant see how either of these can ever be NULL
 750   DASHER_ASSERT_VALIDPTR_RW(newnode);
 751   DASHER_ASSERT_VALIDPTR_RW(oldnode);
 752
 753   if(newnode == NULL || oldnode == NULL)
 754     return false;
 755
 756   // This deals with the trivial instance - we're reversing back over
 757   // text that we've seen already
 758   if(newnode->GetFlag(NF_SEEN)) {
 759     if(oldnode->Parent() == newnode) {
 760       oldnode->m_pNodeManager->Undo(oldnode);
 761       oldnode->Parent()->m_pNodeManager->Enter(oldnode->Parent());
 762       if (pNumDeleted != NULL)
 763         (*pNumDeleted)++;
 764       oldnode->SetFlag(NF_SEEN, false);
 765       return true;
 766     }
 767     if(DeleteCharacters(newnode, oldnode->Parent(), pNumDeleted) == true) {
 768       oldnode->m_pNodeManager->Undo(oldnode);
 769       oldnode->Parent()->m_pNodeManager->Enter(oldnode->Parent());
 770       if (pNumDeleted != NULL)
 771         (*pNumDeleted)++;
 772       oldnode->SetFlag(NF_SEEN, false);
 773       return true;
 774     }
 775   }
 776   else {
 777     // This one's more complicated - the user may have moved onto a new branch
 778     // Find the last seen node on the new branch
 779     CDasherNode *lastseen = newnode->Parent();
 780
 781     while(lastseen != NULL && !(lastseen->GetFlag(NF_SEEN))) {
 782       lastseen = lastseen->Parent();
 783     };
 784     // Delete back to last seen node
 785     while(oldnode != lastseen) {
 786
 787       oldnode->SetFlag(NF_SEEN, false);
 788
 789       oldnode->m_pNodeManager->Undo(oldnode);
 790
 791       if(oldnode->Parent())
 792         oldnode->Parent()->m_pNodeManager->Enter(oldnode->Parent());
 793
 794       if (pNumDeleted != NULL)
 795         (*pNumDeleted)++;
 796       oldnode = oldnode->Parent();
 797       if(oldnode == NULL) {
 798         return false;
 799       }
 800     }
 801   }
 802   return false;
 803 }
 804
 805 // void CDasherModel::LearnText(CLanguageModel::Context context, string *TheText, bool IsMore) {
 806 //   m_pNodeCreationManager->LearnText(context, TheText, IsMore);
 807 // }
 808
 809 // void CDasherModel::EnterText(CLanguageModel::Context context, string TheText) const {
 810 //   m_pNodeCreationManager->EnterText(context, TheText);
 811 // }
 812
 813 void CDasherModel::Push_Node(CDasherNode *pNode) {
 814
 815   // TODO: Fix this and make an assertion again
 816   if(pNode->GetFlag(NF_SUBNODE))
 817     return;
 818
 819   if(pNode->GetFlag(NF_ALLCHILDREN)) {
 820     DASHER_ASSERT(pNode->Children().size() > 0);
 821     // if there are children just give them a poke
 822     CDasherNode::ChildMap::iterator i;
 823     for(i = pNode->Children().begin(); i != pNode->Children().end(); i++)
 824       (*i)->SetFlag(NF_ALIVE, true);
 825     return;
 826   }
 827
 828   // TODO: Do we really need to delete all of the children at this point?
 829   pNode->Delete_children();
 830
 831   pNode->SetFlag(NF_ALIVE, true);
 832
 833   pNode->m_pNodeManager->PopulateChildren(pNode);
 834   pNode->SetFlag(NF_ALLCHILDREN, true);
 835 }
 836
 837 void CDasherModel::Recursive_Push_Node(CDasherNode *pNode, int iDepth) {
 838
 839   if(pNode->Range() < 0.1 * GetLongParameter(LP_NORMALIZATION)) {
 840     return;
 841   }
 842
 843   Push_Node(pNode);
 844
 845   if(iDepth == 0)
 846     return;
 847
 848   for(unsigned int i(0); i < pNode->ChildCount(); i++) {
 849     Recursive_Push_Node(pNode->Children()[i], iDepth - 1);
 850   }
 851 }
 852
 853 bool CDasherModel::RenderToView(CDasherView *pView, bool bRedrawDisplay) {
 854   std::vector<CDasherNode *> vNodeList;
 855   std::vector<CDasherNode *> vDeleteList;
 856
 857   bool bReturnValue;
 858
 859   bReturnValue = pView->Render(m_Root, m_Rootmin + m_iTargetOffset, m_Rootmax + m_iTargetOffset, vNodeList, vDeleteList, bRedrawDisplay, m_bGameMode);
 860
 861   if(!GetBoolParameter(BP_OLD_STYLE_PUSH)) {
 862   for(std::vector<CDasherNode *>::iterator it(vNodeList.begin()); it != vNodeList.end(); ++it)
 863     Push_Node(*it);
 864   }
 865
 866   // TODO: Fix this
 867   for(std::vector<CDasherNode *>::iterator it(vDeleteList.begin()); it != vDeleteList.end(); ++it) {
 868     if(!((*it)->GetFlag(NF_SUBNODE)))
 869       (*it)->Delete_children();
 870   }
 871
 872   return bReturnValue;
 873 }
 874
 875 // Return true to indicate zero or one nodes found, false for more than one
 876 bool CDasherModel::RecursiveCheckRoot(CDasherNode *pNode, CDasherNode **pNewNode, bool &bFound) {
 877   CDasherNode::ChildMap & children = pNode->Children();
 878
 879   for(CDasherNode::ChildMap::iterator it(children.begin()); it != children.end(); ++it) {
 880     if((*it)->GetFlag(NF_SUBNODE)) {
 881       if(!RecursiveCheckRoot(*it, pNewNode, bFound))
 882         return false;
 883     }
 884     else if((*it)->GetFlag(NF_SUPER)) {
 885       if(bFound) // TODO: This should be an error (and probably isn't worth checking for)
 886         return false;
 887       else {
 888         *pNewNode = *it;
 889         bFound = true;
 890       }
 891     }
 892   }
 893
 894   return true;
 895 }
 896
 897 bool CDasherModel::CheckForNewRoot(CDasherView *pView) {
 898   // TODO: Check for non-subnode on return
 899
 900   //  if(m_deGotoQueue.size() > 0)
 901   //   return false;
 902
 903   CDasherNode *root(m_Root);
 904   CDasherNode::ChildMap & children = m_Root->Children();
 905
 906   //  if(pView->IsNodeVisible(m_Rootmin,m_Rootmax)) {
 907   if(!(m_Root->GetFlag(NF_SUPER))) {
 908     Reparent_root(root->Lbnd(), root->Hbnd());
 909
 910     DASHER_ASSERT(!(m_Root->GetFlag(NF_SUBNODE)));
 911
 912     return(m_Root != root);
 913   }
 914
 915   CDasherNode *pNewRoot = NULL;
 916
 917   bool bFound = false;
 918
 919   if(RecursiveCheckRoot(m_Root, &pNewRoot, bFound)) {
 920     if(bFound) {
 921       // We now have a new root, but it's not necessarily a direct
 922       // descentent of the current root, so loop:
 923
 924       m_Root->DeleteNephews(pNewRoot);
 925
 926       RecursiveMakeRoot(pNewRoot);
 927     }
 928   }
 929
 930   DASHER_ASSERT(!(m_Root->GetFlag(NF_SUBNODE)));
 931
 932
 933 //   if(children.size() == 0)
 934 //     return false;
 935
 936 //   int alive = 0;
 937 //   CDasherNode *theone = 0;
 938
 939 //   // Find whether there is exactly one alive child; if more, we don't care.
 940 //   CDasherNode::ChildMap::iterator i;
 941 //   for(i = children.begin(); i != children.end(); i++) {
 942 //     if((*i)->GetFlag(NF_ALIVE)) {
 943 //       alive++;
 944 //       theone = *i;
 945 //       if(alive > 1)
 946 //         break;
 947 //     }
 948 //   }
 949
 950 //   if(alive == 1) {
 951 //     // We must have zoomed sufficiently that only one child of the root node
 952 //     // is still alive.  Let's make it the root.
 953
 954 //     myint y1 = m_Rootmin;
 955 //     myint y2 = m_Rootmax;
 956 //     myint range = y2 - y1;
 957
 958 //     myint newy1 = y1 + (range * theone->Lbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 959 //     myint newy2 = y1 + (range * theone->Hbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 960 //     if(!pView->IsNodeVisible(newy1, newy2)) {
 961 //         Make_root(theone);
 962 //         return false;
 963 //     }
 964 //   }
 965
 966   return false;
 967 }
 968
 969 double CDasherModel::CorrectionFactor(int dasherx, int dashery) {
 970   double dX = 1 - dasherx/2048.0;
 971   double dY = dashery/2048.0 - 1;
 972
 973   double dR = sqrt(pow(dX, 2.0) + pow(dY, 2.0));
 974
 975   if(fabs(dX) < 0.1)
 976     return dR * (1 + dX /2.0+ pow(dX, 2.0) / 3.0 + pow(dX, 3.0) / 4.0 + pow(dX, 4.0) / 5.0);
 977   else
 978     return -dR * log(1 - dX) / dX;
 979 }
 980
 981 void CDasherModel::ScheduleZoom(int dasherx, int dashery) {
 982
 983    // TODO: What is the following line for?
 984    if (dasherx < 2) { dasherx = 100; }
 985
 986    double dCFactor(CorrectionFactor(dasherx, dashery));
 987
 988    int iSteps = static_cast<int>(GetLongParameter(LP_ZOOMSTEPS) * dCFactor);
 989   // myint iRxnew = ((GetLongParameter(LP_OX)/2) * GetLongParameter(LP_OX)) / dasherx;
 990    myint n1, n2, iTarget1, iTarget2;
 991    //Plan_new_goto_coords(iRxnew, dashery, &iSteps, &o1,&o2,&n1,&n2);
 992
 993    iTarget1 = dashery - dasherx;
 994    iTarget2 = dashery + dasherx;
 995
 996    double dZ = 4096 / static_cast<double>(iTarget2 - iTarget1);
 997
 998    n1 = static_cast<int>((m_Rootmin - iTarget1) * dZ);
 999    n2 = static_cast<int>((m_Rootmax - iTarget2) * dZ + 4096);
1000
1001    m_deGotoQueue.clear();
1002    SGotoItem sNewItem;
1003
1004    for(int s(1); s < iSteps; ++s) {
1005      // use simple linear interpolation. Really should do logarithmic interpolation, but
1006      // this will probably look fine.
1007
1008      sNewItem.iN1 = (s * n1 + (iSteps-s) * m_Rootmin) / iSteps;
1009      sNewItem.iN2 = (s * n2 + (iSteps-s) * m_Rootmax) / iSteps;
1010      sNewItem.iStyle = 1;
1011
1012      m_deGotoQueue.push_back(sNewItem);
1013    }
1014
1015    sNewItem.iN1 = n1;
1016    sNewItem.iN2 = n2;
1017    sNewItem.iStyle = 2;
1018
1019    m_deGotoQueue.push_back(sNewItem);
1020 }
1021
1022 void CDasherModel::Offset(int iOffset) {
1023   m_Rootmin += iOffset;
1024   m_Rootmax += iOffset;
1025
1026   m_iTargetOffset -= iOffset;
1027 }
1028
1029 void CDasherModel::MatchTarget(bool bReverse) {
1030   // TODO: Does anything need to happen wrt bReverse here?
1031
1032   m_Rootmin += m_iTargetOffset;
1033   m_Rootmax += m_iTargetOffset;
1034
1035   m_iTargetOffset = 0;
1036 }
1037
1038 void CDasherModel::LimitRoot(int iMaxWidth) {
1039   m_Rootmin = GetLongParameter(LP_MAX_Y) / 2 - iMaxWidth / 2;
1040   m_Rootmax = GetLongParameter(LP_MAX_Y) / 2 + iMaxWidth / 2;
1041 }
1042
1043 void CDasherModel::SetOffset(int iLocation, CDasherView *pView) {
1044   if(iLocation == m_iOffset)
1045     return; // We're already there
1046
1047   // TODO: Special cases, ie this can be done without rebuilding the
1048   // model
1049
1050   m_iOffset = iLocation;
1051
1052   // Now actually rebuild the model
1053   InitialiseAtOffset(iLocation, pView);
1054
1055 }