Src/DasherCore/DasherModel.cpp

   1 // DasherModel.h
   2 //
   3 // Copyright (c) 2001-2005 David Ward
   4
   5 #include "../Common/Common.h"
   6 #include <iostream>
   7 #include "../Common/Random.h"
   8 #include "DasherModel.h"
   9
  10 using namespace Dasher;
  11 using namespace std;
  12
  13 #include "Event.h"
  14 #include "DasherInterfaceBase.h"
  15 #include "LanguageModelling/PPMLanguageModel.h"
  16 #include "LanguageModelling/WordLanguageModel.h"
  17 #include "LanguageModelling/DictLanguageModel.h"
  18 #include "LanguageModelling/MixtureLanguageModel.h"
  19
  20 #ifdef JAPANESE
  21 #include "LanguageModelling/JapaneseLanguageModel.h"
  22 #endif
  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, CDasherInterfaceBase *pDashIface)
  42 :CDasherComponent(pEventHandler, pSettingsStore), m_pDasherInterface(pDashIface), m_Root(0), total_nats(0.0),
  43 m_pLanguageModel(NULL), m_pcAlphabet(NULL), m_pGameMode(NULL), m_Rootmin(0), m_Rootmax(0), m_Rootmin_min(0),
  44 m_Rootmax_max(0), m_DasherY(0), m_DasherOX(0), m_DasherOY(0), m_dAddProb(0.0), m_dMaxRate(0.0), m_pControltree(NULL),
  45 m_Active(0, 0) {
  46
  47   // Set max bitrate in the FrameRate class
  48   m_dMaxRate = GetLongParameter(LP_MAX_BITRATE) / 100.0;
  49   m_fr.SetMaxBitrate(m_dMaxRate);
  50
  51   // Convert the full alphabet to a symbolic representation for use in the language model
  52   m_pcAlphabet = m_pDasherInterface->GetAlphabet();
  53   CSymbolAlphabet alphabet(m_pcAlphabet->GetNumberTextSymbols());
  54   alphabet.SetSpaceSymbol(m_pcAlphabet->GetSpaceSymbol());      // FIXME - is this right, or do we have to do some kind of translation?
  55   alphabet.SetAlphabetPointer(m_pcAlphabet);    // Horrible hack, but ignore for now.
  56
  57   // Create an appropriate language model;
  58
  59   // FIXME - return to using enum here
  60
  61
  62   switch (GetLongParameter(LP_LANGUAGE_MODEL_ID)) {
  63   case 0:
  64     m_pLanguageModel = new CPPMLanguageModel(m_pEventHandler, m_pSettingsStore, alphabet);
  65     break;
  66   case 2:
  67     m_pLanguageModel = new CWordLanguageModel(m_pEventHandler, m_pSettingsStore, alphabet);
  68     break;
  69   case 3:
  70     m_pLanguageModel = new CMixtureLanguageModel(m_pEventHandler, m_pSettingsStore, alphabet);
  71     break;
  72 #ifdef JAPANESE
  73   case 4:
  74     m_pLanguageModel = new CJapaneseLanguageModel(m_pEventHandler, m_pSettingsStore, alphabet);
  75     break;
  76 #endif
  77   default:
  78     // If there is a bogus value for the language model ID, we'll default
  79     // to our trusty old PPM language model.
  80     m_pLanguageModel = new CPPMLanguageModel(m_pEventHandler, m_pSettingsStore, alphabet);
  81     break;
  82   }
  83
  84   LearnContext = m_pLanguageModel->CreateEmptyContext();
  85
  86   // various settings
  87   int iShift = 12;
  88   m_DasherY = 1 << iShift;
  89   m_DasherOY = m_DasherY / 2;
  90   m_DasherOX = m_DasherY / 2;
  91   m_dAddProb = 0.003;
  92
  93   m_Active = CRange(0, m_DasherY);
  94
  95   int iNormalization = GetLongParameter(LP_NORMALIZATION);
  96   m_Rootmin_min = int64_min / iNormalization / 2;
  97   m_Rootmax_max = int64_max / iNormalization / 2;
  98
  99   // Initialize Game Mode object
 100   m_pGameMode = new CDasherGameMode(pEventHandler, pSettingsStore, m_pDasherInterface, this);
 101
 102   m_pAlphabetManagerFactory = new CAlphabetManagerFactory(this, m_pLanguageModel);
 103   m_pControlManagerFactory = new CControlManagerFactory(this, m_pLanguageModel);
 104
 105   m_bContextSensitive = true;
 106 }
 107
 108 CDasherModel::~CDasherModel() {
 109
 110   if(oldroots.size() > 0) {
 111     delete oldroots[0];
 112     oldroots.clear();
 113     // At this point we have also deleted the root - so better NULL pointer
 114     m_Root = NULL;
 115   }
 116
 117   delete m_Root;
 118
 119   delete m_pAlphabetManagerFactory;
 120   delete m_pControlManagerFactory;
 121
 122   if (m_pGameMode != NULL) {
 123     delete m_pGameMode;
 124     m_pGameMode = NULL;
 125   }
 126
 127   m_pLanguageModel->ReleaseContext(LearnContext);
 128   delete m_pLanguageModel;
 129
 130 }
 131
 132 void CDasherModel::HandleEvent(Dasher::CEvent *pEvent) {
 133
 134   if(pEvent->m_iEventType == 1) {
 135     Dasher::CParameterNotificationEvent * pEvt(static_cast < Dasher::CParameterNotificationEvent * >(pEvent));
 136
 137     switch (pEvt->m_iParameter) {
 138     case LP_MAX_BITRATE: // Delibarate fallthrough
 139     case LP_BOOSTFACTOR: // Deliberate fallthrough
 140     case LP_SPEED_DIVISOR:
 141       m_dMaxRate = GetLongParameter(LP_MAX_BITRATE) * GetLongParameter(LP_BOOSTFACTOR) / 100 / static_cast<double>(GetLongParameter(LP_SPEED_DIVISOR));
 142       m_fr.SetMaxBitrate(m_dMaxRate);
 143       break;
 144     default:
 145       break;
 146     }
 147   }
 148
 149 }
 150
 151 void CDasherModel::Make_root(CDasherNode *whichchild)
 152 // find a new root node
 153 {
 154
 155   symbol t = m_Root->Symbol();
 156   if(t < m_pDasherInterface->GetAlphabet()->GetNumberTextSymbols()) {
 157     // Only learn if we have adaptive behaviour enabled
 158
 159     // This was m_bAdaptive, which should be a setting for all dasher?
 160     if(true)
 161       // SYM0
 162       m_pLanguageModel->LearnSymbol(LearnContext, t);
 163   }
 164
 165   m_Root->DeleteNephews(whichchild);
 166
 167   oldroots.push_back(m_Root);
 168
 169   m_Root = whichchild;
 170
 171   while(oldroots.size() > 10) {
 172     oldroots[0]->OrphanChild(oldroots[1]);
 173     delete oldroots[0];
 174     oldroots.pop_front();
 175   }
 176
 177   myint range = m_Rootmax - m_Rootmin;
 178   m_Rootmax = m_Rootmin + (range * m_Root->Hbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 179   m_Rootmin = m_Rootmin + (range * m_Root->Lbnd()) / (int)GetLongParameter(LP_NORMALIZATION);
 180 }
 181
 182 void CDasherModel::Reparent_root(int lower, int upper) {
 183
 184   /* Change the root node to the parent of the existing node
 185      We need to recalculate the coordinates for the "new" root as the
 186      user may have moved around within the current root */
 187
 188   if(m_Root->Symbol() == 0)
 189     return; // Don't try to reparent the root symbol
 190
 191
 192   CDasherNode *pNewRoot;
 193
 194   if(oldroots.size() == 0) {
 195     CDasherNode *pCurrentNode(Get_node_under_crosshair());
 196     int iGenerations(0);
 197
 198     while(pCurrentNode != m_Root) {
 199       ++iGenerations;
 200       pCurrentNode = pCurrentNode->Parent();
 201     }
 202
 203     pNewRoot = m_Root->m_pNodeManager->RebuildParent(m_Root, iGenerations);
 204
 205     lower = m_Root->Lbnd();
 206     upper = m_Root->Hbnd();
 207
 208   }
 209   else {
 210     pNewRoot = oldroots.back();
 211     oldroots.pop_back();
 212   }
 213
 214   // Return if there's no existing parent and no way of recreating one
 215
 216   if(!pNewRoot) {
 217     return;
 218   }
 219
 220   /* Determine how zoomed in we are */
 221
 222   myint iRootWidth = m_Rootmax - m_Rootmin;
 223   myint iWidth = upper - lower;
 224 //  double scalefactor=(m_Rootmax-m_Rootmin)/static_cast<double>(upper-lower);
 225
 226   m_Root = pNewRoot;
 227
 228   m_Rootmax = m_Rootmax + (myint((GetLongParameter(LP_NORMALIZATION) - upper)) * iRootWidth / iWidth);
 229   m_Rootmin = m_Rootmin - (myint(lower) * iRootWidth / iWidth);
 230 }
 231
 232 /////////////////////////////////////////////////////////////////////////////
 233
 234 CDasherNode *CDasherModel::Get_node_under_crosshair() {
 235   return m_Root->Get_node_under(GetLongParameter(LP_NORMALIZATION), m_Rootmin, m_Rootmax, m_DasherOX, m_DasherOY);
 236 }
 237
 238 /////////////////////////////////////////////////////////////////////////////
 239
 240 CDasherNode *CDasherModel::Get_node_under_mouse(myint Mousex, myint Mousey) {
 241   return m_Root->Get_node_under(GetLongParameter(LP_NORMALIZATION), m_Rootmin, m_Rootmax, Mousex, Mousey);
 242 }
 243
 244 /////////////////////////////////////////////////////////////////////////////
 245
 246 void CDasherModel::Get_string_under_mouse(const myint Mousex, const myint Mousey, vector <symbol >&str) {
 247   m_Root->Get_string_under(GetLongParameter(LP_NORMALIZATION), m_Rootmin, m_Rootmax, Mousex, Mousey, str);
 248   return;
 249 }
 250
 251 /////////////////////////////////////////////////////////////////////////////
 252
 253 void CDasherModel::Start() {
 254
 255   // FIXME - re-evaluate this function and SetContext...
 256
 257 //              m_pEditbox->get_new_context(ContextString,5);
 258
 259   std::string strNewContext("");
 260
 261   SetContext(strNewContext);    // FIXME - REALLY REALLY broken!
 262
 263   CEditContextEvent oEvent(5);
 264
 265   InsertEvent(&oEvent);
 266
 267   // FIXME - what if we don't get a reply?
 268
 269 //      m_pLanguageModel->ReleaseNodeContext(therootcontext);
 270 //      ppmmodel->dump();
 271 //      dump();
 272
 273 }
 274
 275 void CDasherModel::SetContext(std::string &sNewContext) {
 276
 277
 278   if(oldroots.size() > 0) {
 279     delete oldroots[0];
 280     oldroots.clear();
 281     // At this point we have also deleted the root - so better NULL pointer
 282     m_Root = NULL;
 283   }
 284   delete m_Root;
 285
 286
 287   CLanguageModel::Context therootcontext = m_pLanguageModel->CreateEmptyContext();
 288
 289   if(sNewContext.size() == 0) {
 290     m_Root = m_pAlphabetManagerFactory->GetRoot(NULL, 0,GetLongParameter(LP_NORMALIZATION), NULL);
 291
 292     EnterText(therootcontext, ". ");
 293   }
 294   else {
 295     std::vector<symbol> vSymbols;
 296     m_pLanguageModel->SymbolAlphabet().GetAlphabetPointer()->GetSymbols(&vSymbols, &sNewContext, false);
 297
 298     int iRootSymbol(vSymbols[vSymbols.size()-1]);
 299
 300     m_Root = m_pAlphabetManagerFactory->GetRoot(NULL, 0,GetLongParameter(LP_NORMALIZATION), &iRootSymbol);
 301
 302     EnterText(therootcontext, sNewContext);
 303   }
 304
 305   m_pLanguageModel->ReleaseContext(LearnContext);
 306   LearnContext = m_pLanguageModel->CloneContext(therootcontext);
 307
 308   m_Root->SetContext(therootcontext);   // node takes control of the context
 309   Recursive_Push_Node(m_Root, 0);
 310
 311   double dFraction( 1 - (1 - m_Root->MostProbableChild() / static_cast<double>(GetLongParameter(LP_NORMALIZATION))) / 2.0 );
 312
 313   int iWidth( m_DasherY / (2.0*dFraction) );
 314
 315   m_Rootmin = m_DasherY / 2 - iWidth / 2;
 316   m_Rootmax = m_DasherY / 2 + iWidth / 2;
 317 }
 318
 319 /////////////////////////////////////////////////////////////////////////////
 320
 321 ///
 322 /// CDasherModel::Get_new_root_coords( myint Mousex,myint Mousey )
 323 ///
 324 /// Calculate the new co-ordinates for the root node after a single
 325 /// update step. For further information, see Doc/geometry.tex.
 326 ///
 327 /// \param Mousex x mouse co-ordinate measured right to left.
 328 /// \param Mousey y mouse co-ordinate measured top to bottom.
 329 /// \return Returns the number of nats entered
 330 ///
 331
 332 double CDasherModel::Get_new_root_coords(myint Mousex, myint Mousey) {
 333   // Comments refer to the code immedialtely before them
 334
 335   if(Mousex <= 0) {
 336     Mousex = 1;
 337   }
 338
 339   // Avoid Mousex=0, as this corresponds to infinite zoom
 340
 341   // If Mousex is too large we risk overflow errors, so make limit it
 342   // (this is a somewhat empirical limit - at some point we should
 343   // probably do it a little more scientifically)
 344
 345   if(Mousex > 60000000)
 346     Mousex = 60000000;
 347
 348   int iTargetMin(Mousey - (m_DasherY * Mousex) / (2 * m_DasherOX));
 349   int iTargetMax(Mousey + (m_DasherY * Mousex) / (2 * m_DasherOX));
 350
 351   // Calculate what the extremes of the viewport will be when the
 352   // point under the cursor is at the cross-hair. This is where
 353   // we want to be in iSteps updates
 354
 355   //  std::cout << iTargetMin << " " << iTargetMax << std::endl;
 356
 357   int iSteps = m_fr.Steps();
 358
 359   DASHER_ASSERT(iSteps > 0);
 360
 361   // iSteps is the number of update steps we need to get the point
 362   // under the cursor over to the cross hair. Calculated in order to
 363   // keep a constant bit-rate.
 364
 365   int iNewTargetMin;
 366   int iNewTargetMax;
 367
 368   iNewTargetMin = (iTargetMin * m_DasherY / (m_DasherY + (iSteps - 1) * (iTargetMax - iTargetMin)));
 369
 370   iNewTargetMax = ((iTargetMax * iSteps - iTargetMin * (iSteps - 1)) * m_DasherY) / (m_DasherY + (iSteps - 1) * (iTargetMax - iTargetMin));
 371
 372   iTargetMin = iNewTargetMin;
 373   iTargetMax = iNewTargetMax;
 374
 375   // Calculate the new values of iTargetMin and iTargetMax required to
 376   // perform a single update step. Note that the slightly awkward
 377   // expressions are in order to reproduce the behaviour of the old
 378   // algorithm
 379
 380   myint iMinSize(m_fr.MinSize(m_DasherY));
 381
 382   // Calculate the minimum size of the viewport corresponding to the
 383   // maximum zoom.
 384
 385   if((iTargetMax - iTargetMin) < iMinSize) {
 386
 387     iNewTargetMin = iTargetMin * (m_DasherY - iMinSize) / (m_DasherY - (iTargetMax - iTargetMin));
 388     iNewTargetMax = iNewTargetMin + iMinSize;
 389
 390     iTargetMin = iNewTargetMin;
 391     iTargetMax = iNewTargetMax;
 392
 393   }
 394
 395   // Check we're not going faster than the speed slider setting
 396   // allows, and adjust if necessary. Note that if we re-size the
 397   // target we need to be careful about where we centre the new range
 398   // (hence the slightly complicated expression above)
 399
 400   DoZoom(iTargetMin, iTargetMax);
 401
 402   // Actually do the zooming
 403
 404   return -1.0 * log((iTargetMax - iTargetMin) / static_cast < double >(m_DasherY));
 405
 406   // Return value is the zoom factor so we can keep track of bitrate.
 407 }
 408
 409 /// Zoom the display so that [iTargetMin,iTargetMax] (in current
 410 /// Dasher co-ordinates) are the new extremes of the viewport.
 411
 412 void CDasherModel::DoZoom(myint iTargetMin, myint iTargetMax) {
 413
 414   myint newRootmin(((m_Rootmin - iTargetMin) * m_DasherY) / (iTargetMax - iTargetMin));
 415   myint newRootmax(((m_Rootmax - iTargetMax) * m_DasherY) / (iTargetMax - iTargetMin) + m_DasherY);
 416
 417   // Update the max and min of the root node to make iTargetMin and iTargetMax the edges of the viewport.
 418
 419   if(newRootmin > m_DasherY / 2 - 1)
 420     newRootmin = m_DasherY / 2 - 1;
 421
 422   if(newRootmax < m_DasherY / 2 + 1)
 423     newRootmax = m_DasherY / 2 + 1;
 424
 425   // Check that we haven't drifted too far. The rule is that we're not
 426   // allowed to let the root max and min cross the midpoint of the
 427   // screen.
 428
 429   if(newRootmax < m_Rootmax_max && newRootmin > m_Rootmin_min && (newRootmax - newRootmin) > m_DasherY / 4) {
 430     // Only update if we're not making things big enough to risk
 431     // overflow. In theory we should have reparented the root well
 432     // before getting this far.
 433     //
 434     // Also don't allow the update if it will result in making the
 435     // root too small. Again, we should have re-generated a deeper
 436     // root in most cases, but the original root is an exception.
 437
 438     m_Rootmax = newRootmax;
 439     m_Rootmin = newRootmin;
 440   }
 441   else {
 442     // TODO - force a new root to be chosen, so that we get better
 443     // behaviour than just having Dasher stop at this point.
 444   }
 445 }
 446
 447 void CDasherModel::Get_new_goto_coords(double zoomfactor, myint MouseY)
 448                                        // this was mousex.
 449 {
 450   // First, we need to work out how far we need to zoom in
 451   //float zoomfactor=(m_DasherOX-MouseX)/(m_DasherOX*1.0);
 452
 453   // Then zoom in appropriately
 454   m_Rootmax = m_Rootmax + myint(zoomfactor * (m_Rootmax - m_DasherY / 2));
 455   m_Rootmin = m_Rootmin + myint(zoomfactor * (m_Rootmin - m_DasherY / 2));
 456
 457   // Afterwards, we need to take care of the vertical offset.
 458   myint up = (m_DasherY / 2) - MouseY;
 459   m_Rootmax = m_Rootmax + up;
 460   m_Rootmin = m_Rootmin + up;
 461 }
 462
 463 myint CDasherModel::PlotGoTo(myint MouseX, myint MouseY) {
 464   // First, we need to work out how far we need to zoom in
 465   double zoomfactor = (m_DasherOX - MouseX) / (m_DasherOX * 1.0);
 466   zoomfactor = pow(0.5, zoomfactor);
 467
 468   myint height = int (m_DasherY * zoomfactor / 2);
 469
 470   return height;
 471 }
 472
 473 void CDasherModel::Tap_on_display(myint miMousex,
 474                                   myint miMousey,
 475                                   unsigned long Time,
 476                                   Dasher::VECTOR_SYMBOL_PROB* pAdded,
 477                                   int* pNumDeleted)
 478         // work out the next viewpoint, opens some new nodes
 479 {
 480
 481   // Clear out parameters that might get passed in to track user activity
 482   if (pAdded != NULL)
 483           pAdded->clear();
 484   if (pNumDeleted != NULL)
 485           *pNumDeleted = 0;
 486
 487   // Find out the current node under the crosshair
 488   CDasherNode *old_under_cross = Get_node_under_crosshair();
 489
 490   // works out next viewpoint
 491   total_nats += Get_new_root_coords(miMousex, miMousey);
 492
 493   // opens up new nodes
 494
 495   if(false)
 496   {
 497
 498   // push node under mouse
 499   CDasherNode *pUnderMouse = Get_node_under_mouse(miMousex, miMousey);
 500
 501   Push_Node(pUnderMouse);
 502
 503   if(Framerate() > 4) {
 504     // push node under mouse but with x coord on RHS
 505     CDasherNode *pRight = Get_node_under_mouse(50, miMousey);
 506     Push_Node(pRight);
 507   }
 508
 509   if(Framerate() > 8) {
 510     // push node under the crosshair
 511     CDasherNode *pUnderCross = Get_node_under_crosshair();
 512     Push_Node(pUnderCross);
 513   }
 514
 515   int iRandom = RandomInt();
 516
 517   if(Framerate() > 8) {
 518     // add some noise and push another node
 519     CDasherNode *pRight = Get_node_under_mouse(50, miMousey + iRandom % 500 - 250);
 520     Push_Node(pRight);
 521   }
 522
 523   iRandom = RandomInt();
 524
 525   if(Framerate() > 15) {
 526     // add some noise and push another node
 527     CDasherNode *pRight = Get_node_under_mouse(50, miMousey + iRandom % 500 - 250);
 528     Push_Node(pRight);
 529   }
 530
 531   // only do this is Dasher is flying
 532   if(Framerate() > 30) {
 533     for(int i = 1; i < int (Framerate() - 30) / 3; i++) {
 534
 535       iRandom = RandomInt();
 536       // push at a random node on the RHS
 537       CDasherNode *pRight = Get_node_under_mouse(50, miMousey + iRandom % 1000 - 500);
 538       Push_Node(pRight);
 539
 540     }
 541   }
 542   }
 543 //      Update(m_Root,under_mouse,0);
 544
 545   CDasherNode *new_under_cross = Get_node_under_crosshair();
 546
 547   // FIXME - Reimplement
 548
 549   if(new_under_cross != old_under_cross) {
 550     DeleteCharacters(new_under_cross, old_under_cross, pNumDeleted);
 551   }
 552
 553   if(new_under_cross->isSeen() == true) {
 554 //     if(new_under_cross->ControlChild() != true) {
 555 //       SetBitrate(m_dMaxRate);
 556 //     }
 557      return;
 558    }
 559
 560
 561
 562
 563   // FIXME - Need to recurse up possibly unseen parents
 564
 565
 566   RecursiveOutput(new_under_cross, pAdded);
 567
 568   // FIXME - Reimplement
 569
 570 //   if(new_under_cross->ControlChild() == true) {
 571 //     //            m_pEditbox->outputcontrol(new_under_cross->GetControlTree()->pointer,new_under_cross->GetControlTree()->data,new_under_cross->GetControlTree()->type);
 572 //     OutputCharacters(new_under_cross);
 573 //     SetBitrate(m_dMaxRate / 3);
 574 //   }
 575 //   else {
 576 //     OutputCharacters(new_under_cross);
 577 //     SetBitrate(m_dMaxRate);
 578 //   }
 579   //      m_Root->Recursive_Push_Node(0);
 580 }
 581
 582
 583 void CDasherModel::RecursiveOutput(CDasherNode *pNode, Dasher::VECTOR_SYMBOL_PROB* pAdded) {
 584   if(pNode->Parent() && (!pNode->Parent()->isSeen()))
 585     RecursiveOutput(pNode->Parent(), pAdded);
 586
 587   if(pNode->Parent())
 588     pNode->Parent()->m_pNodeManager->Leave(pNode->Parent());
 589
 590   pNode->m_pNodeManager->Enter(pNode);
 591
 592   pNode->Seen(true);
 593   pNode->m_pNodeManager->Output(pNode, pAdded, GetLongParameter(LP_NORMALIZATION));
 594 }
 595
 596
 597 void CDasherModel::GoTo(double zoomfactor, myint miMousey)
 598         // work out the next viewpoint, opens some new nodes
 599 {
 600   // Find out the current node under the crosshair
 601   CDasherNode *old_under_cross = Get_node_under_crosshair();
 602
 603   // works out next viewpoint
 604   Get_new_goto_coords(zoomfactor, miMousey);
 605
 606   // push node under crosshair
 607
 608   CDasherNode *new_under_cross = Get_node_under_crosshair();
 609
 610   Push_Node(new_under_cross);
 611
 612   // push node under goto point
 613
 614   // We don't have a mousex, so "emulating" one.
 615   CDasherNode *node_under_goto = Get_node_under_mouse(50, miMousey);
 616
 617   Push_Node(node_under_goto);
 618
 619 //      Update(m_Root,new_under_cross,0);
 620
 621   if(new_under_cross != old_under_cross) {
 622     DeleteCharacters(new_under_cross, old_under_cross);
 623   }
 624
 625   if(new_under_cross->isSeen() == true)
 626     return;
 627
 628   new_under_cross->Seen(true);
 629
 630   OutputCharacters(new_under_cross);
 631 }
 632
 633 // This is similar to Get_new_goto_coords, but doesn't actually change Rootmax and Rootmin.
 634 // Instead it gives information for NewGoTo to make direct changes in the root coordinates.
 635 #define ZOOMDENOM (1<<10)
 636 #define STEPNUM   48
 637 #define STEPDENOM 64
 638 double CDasherModel::Plan_new_goto_coords(int iRxnew, myint mousey, int *iSteps, myint *o1, myint *o2 , myint *n1, myint *n2)
 639 {
 640   m_Stepnum = GetLongParameter(LP_ZOOMSTEPS);
 641   int iRxnew_dup = iRxnew;
 642   // note -- iRxnew is the zoom factor  in units of ZOOMDENOM
 643   *o1 = m_Rootmin ;
 644   *o2 = m_Rootmax ;
 645   DASHER_ASSERT(iRxnew > 0);
 646   if (iRxnew < ZOOMDENOM && m_Rootmax<m_DasherY && m_Rootmin>0 ) {
 647     // refuse to zoom backwards if the entire root node is visible.
 648     cout << "Refusing to zoom backwards." << endl;
 649     *iSteps = 0 ;
 650     *n1 = m_Rootmin;
 651     *n2 = m_Rootmax;
 652   }
 653   else {
 654     myint above=(mousey-*o1);
 655     myint below=(*o2-mousey);
 656
 657     myint miNewrootzoom= m_DasherY/2 ;
 658     myint newRootmax=miNewrootzoom+(below*iRxnew/ZOOMDENOM); // is there a risk of overflow in this multiply?
 659     myint newRootmin=miNewrootzoom-(above*iRxnew/ZOOMDENOM);
 660
 661     *n1 = newRootmin;
 662     *n2 = newRootmax;
 663
 664     *iSteps = 1;
 665
 666     // We might be moving at zoomfactor one vertically, in which case the below invention won't
 667     // come up with more than one step.  Look for a mousey difference and use an iSteps concordant
 668     // to that if it would be larger than the iSteps created by taking the log of the zoomfactor.
 669     int distance = mousey - (m_DasherY/2);
 670
 671     double s = (log(2.0) * 2 / log( (STEPDENOM*1.0)/(m_Stepnum*1.0)) ) / 4096;
 672
 673     double alpha = 2 * (2 * s);
 674     int alternateSteps = int(alpha * distance);
 675     // Take log of iRxnew to base ( STEPDENOM / STEPNUM ):
 676     if ( STEPDENOM > m_Stepnum && m_Stepnum > 0 ) { // check that the following loop will terminate.
 677       //cout << "iRxnew is " << iRxnew << " and ZOOMDENOM is" << ZOOMDENOM << endl;
 678       if ( iRxnew > ZOOMDENOM ) {
 679         while ( iRxnew > ZOOMDENOM ) {
 680           *iSteps += 1;
 681           iRxnew = iRxnew * m_Stepnum / STEPDENOM;
 682         }
 683       } else {
 684         while ( iRxnew < ZOOMDENOM ) {
 685           *iSteps += 1;
 686           iRxnew = iRxnew * STEPDENOM / m_Stepnum;
 687         }
 688       }
 689     }
 690     // Done taking log of iRxnew.
 691     if (alternateSteps > *iSteps) {
 692       *iSteps = alternateSteps;
 693     }
 694    }
 695
 696   double iRxnew_ratio = (double) iRxnew_dup / ZOOMDENOM;
 697   double iRxnew_log = log(iRxnew_ratio);
 698   return iRxnew_log;
 699 }
 700
 701 void CDasherModel::NewGoTo(myint n1 , myint n2 , int style) {
 702   // Find out the current node under the crosshair
 703   CDasherNode *old_under_cross=Get_node_under_crosshair();
 704
 705   // establish next viewpoint
 706   m_Rootmin = n1 ;
 707   m_Rootmax = n2 ;
 708
 709   // push node under crosshair
 710   CDasherNode* new_under_cross = Get_node_under_crosshair();
 711   Push_Node(new_under_cross);
 712
 713   if ( style >= 2 ) { // "2" means FINAL. "1" means STEP
 714         // Ugly hack  --
 715     // Push at all locations on the right hand side.
 716     int Hack=60 ; // was 20
 717     int hack ;
 718     int y1 , y2 , hackystep = 34 , mid=m_DasherY/2 , top=m_DasherY*1/20 , bot = m_DasherY*19/20 ;
 719     // y1 sweeps the top half of the screen; y2 sweeps the bottom half
 720     // choice of `random' hackystep intended to give fairly uniform coverage.
 721     for ( y1 = mid , y2 = mid+hackystep/2 , hack = 1 ; hack <= Hack ; hack ++ ) {
 722       // We don't have a mousex, so "emulating" one.
 723       CDasherNode* node_under_goto = Get_node_under_mouse(50, y1);
 724       Push_Node(node_under_goto);
 725       node_under_goto = Get_node_under_mouse(50, y2);
 726       Push_Node(node_under_goto);
 727
 728       y1 -= hackystep;
 729       if ( y1 < top ) { y1 += mid; }
 730
 731       y2 += hackystep;
 732       if ( y1 > bot ) { y2 -= mid; }
 733     }
 734     // end hack
 735   }
 736
 737   //Update(m_Root,new_under_cross,0);
 738
 739   if (new_under_cross!=old_under_cross) {
 740     DeleteCharacters(new_under_cross,old_under_cross);
 741   }
 742
 743   if (new_under_cross->isSeen()==true)
 744     return;
 745
 746   new_under_cross->Seen(true);
 747
 748   OutputCharacters(new_under_cross);
 749 }
 750
 751
 752
 753 void CDasherModel::OutputCharacters(CDasherNode *node) {
 754   if(node->Parent() != NULL && node->Parent()->isSeen() != true) {
 755     node->Parent()->Seen(true);
 756     OutputCharacters(node->Parent());
 757   }
 758   symbol t = node->Symbol();
 759   if(t)                         // SYM0
 760   {
 761     Dasher::CEditEvent oEvent(1, GetAlphabet().GetText(t));
 762     InsertEvent(&oEvent);
 763   }
 764   else if(node->ControlChild() == true) {
 765
 766     // FIXME - control events currently not implemented
 767 //        m_pEditbox->outputcontrol(node->GetControlTree()->pointer,node->GetControlTree()->data,node->GetControlTree()->type);
 768   }
 769 }
 770
 771 bool CDasherModel::DeleteCharacters(CDasherNode *newnode, CDasherNode *oldnode, int* pNumDeleted) {
 772
 773   // DJW cant see how either of these can ever be NULL
 774   DASHER_ASSERT_VALIDPTR_RW(newnode);
 775   DASHER_ASSERT_VALIDPTR_RW(oldnode);
 776
 777   if(newnode == NULL || oldnode == NULL)
 778     return false;
 779
 780   // This deals with the trivial instance - we're reversing back over
 781   // text that we've seen already
 782   if(newnode->isSeen() == true) {
 783     if(oldnode->Parent() == newnode) {
 784       oldnode->m_pNodeManager->Undo(oldnode);
 785       oldnode->Parent()->m_pNodeManager->Enter(oldnode->Parent());
 786       if (pNumDeleted != NULL)
 787         (*pNumDeleted)++;
 788       oldnode->Seen(false);
 789       return true;
 790     }
 791     if(DeleteCharacters(newnode, oldnode->Parent(), pNumDeleted) == true) {
 792       oldnode->m_pNodeManager->Undo(oldnode);
 793       oldnode->Parent()->m_pNodeManager->Enter(oldnode->Parent());
 794       if (pNumDeleted != NULL)
 795         (*pNumDeleted)++;
 796       oldnode->Seen(false);
 797       return true;
 798     }
 799   }
 800   else {
 801     // This one's more complicated - the user may have moved onto a new branch
 802     // Find the last seen node on the new branch
 803     CDasherNode *lastseen = newnode->Parent();
 804
 805     while(lastseen != NULL && lastseen->isSeen() == false) {
 806       lastseen = lastseen->Parent();
 807     };
 808     // Delete back to last seen node
 809     while(oldnode != lastseen) {
 810
 811       oldnode->Seen(false);
 812       if(oldnode->ControlChild() == true || oldnode->Symbol() == GetControlSymbol() || oldnode->Symbol() == 0) {
 813         oldnode = oldnode->Parent();
 814         continue;
 815       }
 816
 817       oldnode->m_pNodeManager->Undo(oldnode);
 818       oldnode->Parent()->m_pNodeManager->Enter(oldnode->Parent());
 819       if (pNumDeleted != NULL)
 820         (*pNumDeleted)++;
 821       oldnode = oldnode->Parent();
 822       if(oldnode == NULL) {
 823         return false;
 824       }
 825     }
 826   }
 827   return false;
 828 }
 829
 830 /////////////////////////////////////////////////////////////////////////////
 831
 832 // Diagnostic trace
 833 void CDasherModel::Trace() const {
 834   // OutputDebugString(TEXT(" ptr   symbol   context Next  Child    pushme pushed cscheme   lbnd  hbnd \n"));
 835   m_Root->Trace();
 836 }
 837
 838 ///////////////////////////////////////////////////////////////////
 839
 840 void CDasherModel::GetProbs(CLanguageModel::Context context, vector <symbol >&NewSymbols, vector <unsigned int >&Probs, int iNorm) const {
 841   // Total number of symbols
 842   int iSymbols = m_pcAlphabet->GetNumberSymbols();      // note that this includes the control node and the root node
 843
 844   // Number of text symbols, for which the language model gives the distribution
 845   // int iTextSymbols = m_pcAlphabet->GetNumberTextSymbols();
 846
 847   NewSymbols.resize(iSymbols);
 848 //      Groups.resize(iSymbols);
 849   for(int i = 0; i < iSymbols; i++) {
 850     NewSymbols[i] = i;          // This will be replaced by something that works out valid nodes for this context
 851     //      Groups[i]=m_pcAlphabet->get_group(i);
 852   }
 853
 854   // TODO - sort out size of control node - for the timebeing I'll fix the control node at 5%
 855
 856   int uniform_add;
 857   int nonuniform_norm;
 858   int control_space;
 859   int uniform = GetLongParameter(LP_UNIFORM);
 860
 861   if(!GetBoolParameter(BP_CONTROL_MODE)) {
 862     control_space = 0;
 863     uniform_add = ((iNorm * uniform) / 1000) / (iSymbols - 2);  // Subtract 2 from no symbols to lose control/root nodes
 864     nonuniform_norm = iNorm - (iSymbols - 2) * uniform_add;
 865   }
 866   else {
 867     control_space = int (iNorm * 0.05);
 868     uniform_add = (((iNorm - control_space) * uniform / 1000) / (iSymbols - 2));        // Subtract 2 from no symbols to lose control/root nodes
 869     nonuniform_norm = iNorm - control_space - (iSymbols - 2) * uniform_add;
 870   }
 871
 872   m_pLanguageModel->GetProbs(context, Probs, nonuniform_norm);
 873
 874 #if _DEBUG
 875   int iTotal = 0;
 876   for(int k = 0; k < Probs.size(); ++k)
 877     iTotal += Probs[k];
 878   DASHER_ASSERT(iTotal == nonuniform_norm);
 879 #endif
 880
 881   //  Probs.insert(Probs.begin(), 0);
 882
 883   for(unsigned int k(1); k < Probs.size(); ++k)
 884     Probs[k] += uniform_add;
 885
 886   Probs.push_back(control_space);
 887
 888 #if _DEBUG
 889   iTotal = 0;
 890   for(int k = 0; k < Probs.size(); ++k)
 891     iTotal += Probs[k];
 892 //      DASHER_ASSERT(iTotal == iNorm);
 893 #endif
 894
 895 }
 896
 897 void CDasherModel::LearnText(CLanguageModel::Context context, string *TheText, bool IsMore) {
 898   vector < symbol > Symbols;
 899
 900   m_pcAlphabet->GetSymbols(&Symbols, TheText, IsMore);
 901
 902   for(unsigned int i = 0; i < Symbols.size(); i++)
 903     m_pLanguageModel->LearnSymbol(context, Symbols[i]); // FIXME - conversion to symbol alphabet
 904 }
 905
 906 void CDasherModel::EnterText(CLanguageModel::Context context, string TheText) const {
 907   vector < symbol > Symbols;
 908   m_pcAlphabet->GetSymbols(&Symbols, &TheText, false);
 909   for(unsigned int i = 0; i < Symbols.size(); i++)
 910     m_pLanguageModel->EnterSymbol(context, Symbols[i]); // FIXME - conversion to symbol alphabet
 911 }
 912
 913 CDasherModel::CTrainer::CTrainer(CDasherModel &DasherModel)
 914 :m_DasherModel(DasherModel) {
 915   m_Context = m_DasherModel.m_pLanguageModel->CreateEmptyContext();
 916 }
 917
 918 void CDasherModel::CTrainer::Train(const std::vector <symbol >&vSymbols) {
 919   for(unsigned int i(0); i < vSymbols.size(); i++)
 920     m_DasherModel.m_pLanguageModel->LearnSymbol(m_Context, vSymbols[i]);
 921 }
 922
 923 CDasherModel::CTrainer::~CTrainer() {
 924   m_DasherModel.m_pLanguageModel->ReleaseContext(m_Context);
 925
 926 }
 927
 928 CDasherModel::CTrainer * CDasherModel::GetTrainer() {
 929   return new CDasherModel::CTrainer(*this);
 930 }
 931
 932 void CDasherModel::Push_Node(CDasherNode *pNode) {
 933   //    cerr << "In Push_Node, ChildCount is " << pNode->ChildCount() << ", HasAllChildren is " << pNode->HasAllChildren() << endl;
 934   if(pNode->HasAllChildren()) {
 935     DASHER_ASSERT(pNode->Children().size() > 0);
 936     // if there are children just give them a poke
 937     CDasherNode::ChildMap::iterator i;
 938     for(i = pNode->Children().begin(); i != pNode->Children().end(); i++)
 939       (*i)->Alive(true);
 940     return;
 941   }
 942
 943   pNode->Delete_children();
 944
 945   // This ASSERT seems to routinely fail
 946   //DASHER_ASSERT(pNode->Symbol()!=0);
 947
 948   // if we haven't got a context then derive it
 949
 950   if(!pNode->Context()) {
 951     CLanguageModel::Context cont;
 952     // sym0
 953     if(pNode->Symbol() < m_pcAlphabet->GetNumberTextSymbols() && pNode->Symbol() > 0) {
 954       CDasherNode *pParent = pNode->Parent();
 955       DASHER_ASSERT(pParent != NULL);
 956       // Normal symbol - derive context from parent
 957       cont = m_pLanguageModel->CloneContext(pParent->Context());
 958       m_pLanguageModel->EnterSymbol(cont, pNode->Symbol());
 959     } else {
 960       // For new "root" nodes (such as under control mode), we want to
 961       // mimic the root context
 962       cont = CreateEmptyContext();
 963       //      EnterText(cont, "");
 964     }
 965     pNode->SetContext(cont);
 966
 967   }
 968
 969   pNode->Alive(true);
 970
 971  //  if(pNode->Symbol() == GetControlSymbol() || pNode->ControlChild()) {
 972 //     ControlTree *pControlTreeChildren = pNode->GetControlTree();
 973
 974 //     ControlTree *test = new ControlTree;
 975 //     test->parent = test->next;
 976
 977 //     if(pControlTreeChildren == NULL) {
 978 //       // Root of the tree
 979 //       pControlTreeChildren = GetControlTree();
 980 //     } else {
 981 //       // some way down
 982 //       pControlTreeChildren = pControlTreeChildren->children;
 983 //     }
 984
 985 //     // Count total number of children
 986
 987 //     // Always 1 child for a root symbol
 988 //     int iChildCount = 1;
 989
 990 //     // Control children
 991 //     ControlTree *pTemp = pControlTreeChildren;
 992 //     while(pTemp != NULL) {
 993 //       iChildCount++;
 994 //       pTemp = pTemp->next;
 995 //     }
 996
 997 //     // Now we go back and build the node tree
 998 //     int quantum = int (GetLongParameter(LP_NORMALIZATION) / iChildCount);
 999
1000 //     ColorSchemes ChildScheme;
1001 //     if(pNode->ColorScheme() == Nodes1) {
1002 //       ChildScheme = Nodes2;
1003 //     } else {
1004 //       ChildScheme = Nodes1;
1005 //     }
1006
1007 //     int i = 0;
1008 //     // First a root node that takes up back to the text alphabet
1009 //     pNode->Children()[i] = new CDasherNode(*this, pNode, 0, 0, Opts::Nodes1, 0, int ((i + 1) * quantum), m_pLanguageModel, false, 240);
1010 //     i++;
1011
1012 //     // Now the control children
1013 //     pTemp = pControlTreeChildren;
1014 //     while(pTemp != NULL) {
1015 //       int colour;
1016 //       if(pTemp->colour != -1) {
1017 //         colour = pTemp->colour;
1018 //       } else {
1019 //         colour = (i % 99) + 11;
1020 //       }
1021 //       pNode->Children()[i] = new CDasherNode(*this, pNode, 0, i, ChildScheme, int (i * quantum), int ((i + 1) * quantum), m_pLanguageModel, true, colour, pTemp);
1022 //       i++;
1023 //       pTemp = pTemp->next;
1024 //     }
1025 //   }
1026 //   else {
1027     pNode->m_pNodeManager->PopulateChildren(pNode);
1028     //  }
1029   pNode->SetHasAllChildren(true);
1030 }
1031
1032 void CDasherModel::Recursive_Push_Node(CDasherNode *pNode, int iDepth) {
1033
1034   if(pNode->Range() < 0.1 * GetLongParameter(LP_NORMALIZATION)) {
1035     return;
1036   }
1037
1038   if(pNode->Symbol() == GetControlSymbol()) {
1039     return;
1040   }
1041
1042   Push_Node(pNode);
1043
1044   if(iDepth == 0)
1045     return;
1046
1047   for(unsigned int i(0); i < pNode->ChildCount(); i++) {
1048     Recursive_Push_Node(pNode->Children()[i], iDepth - 1);
1049   }
1050 }
1051