[dasher] Rename and extend NodeQueue to ExpansionPolicy, set by input filter (& reused)
- From: Patrick Welche <pwelche src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [dasher] Rename and extend NodeQueue to ExpansionPolicy, set by input filter (& reused)
- Date: Sat, 19 Dec 2009 22:20:14 +0000 (UTC)
commit 73982a1c9cf0fe81983322b4b4a48044b07dfd1f
Author: Alan Lawrence <acl33 inf phy cam ac uk>
Date: Mon Oct 26 23:58:38 2009 +0000
Rename and extend NodeQueue to ExpansionPolicy, set by input filter (& reused)
Now incorporates incorporate setting of costs (taken from DasherViewSquare)
and applying policy (i.e. expanding/collapsing nodes - taken from DasherModel).
Modified to use vector not priority_queue to allow more efficient amortization;
also changed to store costs/benefits inside policy, avoiding reads of m_dCost
after potential deallocation(!).
DasherModel::Push_Node renamed to ExpandNode
Src/DasherCore/ButtonMode.cpp | 4 +-
Src/DasherCore/ButtonMode.h | 2 +-
Src/DasherCore/ClickFilter.cpp | 2 +-
Src/DasherCore/ClickFilter.h | 3 +-
Src/DasherCore/DasherButtons.cpp | 2 +-
Src/DasherCore/DasherButtons.h | 2 +-
Src/DasherCore/DasherInterfaceBase.cpp | 34 +++---
Src/DasherCore/DasherInterfaceBase.h | 5 +-
Src/DasherCore/DasherModel.cpp | 62 ++-------
Src/DasherCore/DasherModel.h | 15 +--
Src/DasherCore/DasherNode.h | 1 -
Src/DasherCore/DasherView.cpp | 4 +-
Src/DasherCore/DasherView.h | 6 +-
Src/DasherCore/DasherViewSquare.cpp | 47 +++----
Src/DasherCore/DasherViewSquare.h | 6 +-
Src/DasherCore/DefaultFilter.cpp | 6 +-
Src/DasherCore/DefaultFilter.h | 2 +-
Src/DasherCore/DynamicFilter.cpp | 9 +-
Src/DasherCore/DynamicFilter.h | 4 +-
Src/DasherCore/ExpansionPolicy.cpp | 178 +++++++++++++++++++++++++++
Src/DasherCore/ExpansionPolicy.h | 73 +++++++++++
Src/DasherCore/InputFilter.h | 2 +-
Src/DasherCore/Makefile.am | 2 +
Src/DasherCore/NodeQueue.h | 92 --------------
Src/DasherCore/OneButtonDynamicFilter.cpp | 5 +-
Src/DasherCore/OneButtonDynamicFilter.h | 2 +-
Src/DasherCore/OneButtonFilter.cpp | 2 +-
Src/DasherCore/OneButtonFilter.h | 2 +-
Src/DasherCore/StylusFilter.cpp | 4 +-
Src/DasherCore/StylusFilter.h | 2 +-
Src/DasherCore/TwoButtonDynamicFilter.cpp | 6 +-
Src/DasherCore/TwoButtonDynamicFilter.h | 2 +-
Src/DasherCore/TwoPushDynamicFilter.cpp | 5 +-
Src/DasherCore/TwoPushDynamicFilter.h | 2 +-
Src/MacOSX/Dasher.xcodeproj/project.pbxproj | 12 ++-
35 files changed, 370 insertions(+), 237 deletions(-)
---
diff --git a/Src/DasherCore/ButtonMode.cpp b/Src/DasherCore/ButtonMode.cpp
index 89376fb..542816a 100644
--- a/Src/DasherCore/ButtonMode.cpp
+++ b/Src/DasherCore/ButtonMode.cpp
@@ -178,14 +178,14 @@ bool CButtonMode::DecorateView(CDasherView *pView) {
return bRV;
}
-bool CButtonMode::Timer(int Time, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
+bool CButtonMode::Timer(int Time, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
bool m_bOldHighlight(m_bHighlight);
m_bHighlight = (Time - m_iLastTime < 200);
if(m_bOldHighlight != m_bHighlight)
m_bDecorationChanged = true;
- return CDasherButtons::Timer(Time, pView, pModel, pAdded, pNumDeleted);
+ return CDasherButtons::Timer(Time, pView, pModel, pAdded, pNumDeleted, pol);
}
void CButtonMode::KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog, bool bPos, int iX, int iY)
diff --git a/Src/DasherCore/ButtonMode.h b/Src/DasherCore/ButtonMode.h
index fde8479..cd8ab67 100644
--- a/Src/DasherCore/ButtonMode.h
+++ b/Src/DasherCore/ButtonMode.h
@@ -26,7 +26,7 @@ class CButtonMode : public CDasherButtons
CButtonMode(Dasher::CEventHandler * pEventHandler, CSettingsStore * pSettingsStore, CDasherInterfaceBase *pInterface, bool bMenu, int iID, const char *szName);
virtual void HandleEvent(Dasher::CEvent * pEvent);
- bool Timer(int Time, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ bool Timer(int Time, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
bool DecorateView(CDasherView *pView);
//override to get mouse clicks/taps back again
diff --git a/Src/DasherCore/ClickFilter.cpp b/Src/DasherCore/ClickFilter.cpp
index c55347f..62230f2 100644
--- a/Src/DasherCore/ClickFilter.cpp
+++ b/Src/DasherCore/ClickFilter.cpp
@@ -13,7 +13,7 @@ bool CClickFilter::DecorateView(CDasherView *pView) {
return false;
}
-bool CClickFilter::Timer(int Time, CDasherView *pDasherView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
+bool CClickFilter::Timer(int Time, CDasherView *pDasherView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
return pModel->NextScheduledStep(Time, pAdded, pNumDeleted);
}
diff --git a/Src/DasherCore/ClickFilter.h b/Src/DasherCore/ClickFilter.h
index ff483c5..7898de6 100644
--- a/Src/DasherCore/ClickFilter.h
+++ b/Src/DasherCore/ClickFilter.h
@@ -14,10 +14,9 @@ class CClickFilter : public CInputFilter {
virtual void HandleEvent(Dasher::CEvent * pEvent);
virtual bool DecorateView(CDasherView *pView);
- virtual bool Timer(int Time, CDasherView *pDasherView, CDasherModel *pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool Timer(int Time, CDasherView *pDasherView, CDasherModel *pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void KeyDown(int iTime, int iId, CDasherView *pDasherView, CDasherModel *pModel, CUserLogBase *pUserLog, bool bPos, int iX, int iY);
virtual bool GetSettings(SModuleSettings **pSettings, int *iCount);
-
};
}
/// @}
diff --git a/Src/DasherCore/DasherButtons.cpp b/Src/DasherCore/DasherButtons.cpp
index 119765a..c082541 100644
--- a/Src/DasherCore/DasherButtons.cpp
+++ b/Src/DasherCore/DasherButtons.cpp
@@ -81,7 +81,7 @@ void CDasherButtons::DirectKeyDown(int iTime, int iId, CDasherView *pView, CDash
pModel->ScheduleZoom((m_pBoxes[iActiveBox].iBottom - m_pBoxes[iActiveBox].iTop)/2, (m_pBoxes[iActiveBox].iBottom + m_pBoxes[iActiveBox].iTop)/2);
}
-bool CDasherButtons::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
+bool CDasherButtons::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
if (m_bMenu && GetLongParameter(LP_BUTTON_SCAN_TIME) &&
Time > m_iScanTime) {
m_iScanTime = Time + GetLongParameter(LP_BUTTON_SCAN_TIME);
diff --git a/Src/DasherCore/DasherButtons.h b/Src/DasherCore/DasherButtons.h
index 5573ddb..39c0b08 100644
--- a/Src/DasherCore/DasherButtons.h
+++ b/Src/DasherCore/DasherButtons.h
@@ -30,7 +30,7 @@ class CDasherButtons : public CInputFilter
virtual bool DecorateView(CDasherView *pView)=0;
void KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog);
- bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
void Activate();
struct SBoxInfo {
diff --git a/Src/DasherCore/DasherInterfaceBase.cpp b/Src/DasherCore/DasherInterfaceBase.cpp
index b7388bf..0fa78fc 100644
--- a/Src/DasherCore/DasherInterfaceBase.cpp
+++ b/Src/DasherCore/DasherInterfaceBase.cpp
@@ -98,6 +98,7 @@ CDasherInterfaceBase::CDasherInterfaceBase() {
m_ColourIO = NULL;
m_pUserLog = NULL;
m_pNCManager = NULL;
+ m_defaultPolicy = NULL;
// Various state variables
m_bRedrawScheduled = false;
@@ -165,6 +166,8 @@ void CDasherInterfaceBase::Realize() {
CreateInput();
CreateInputFilter();
SetupActionButtons();
+ CParameterNotificationEvent oEvent(LP_NODE_BUDGET);
+ InterfaceEventHandler(&oEvent);
// Set up real orientation to match selection
if(GetLongParameter(LP_ORIENTATION) == Dasher::Opts::AlphabetDefault)
@@ -325,6 +328,9 @@ void CDasherInterfaceBase::InterfaceEventHandler(Dasher::CEvent *pEvent) {
case LP_MARGIN_WIDTH:
ScheduleRedraw();
break;
+ case LP_NODE_BUDGET:
+ delete m_defaultPolicy;
+ m_defaultPolicy = new AmortizedPolicy(GetLongParameter(LP_NODE_BUDGET));
default:
break;
}
@@ -495,7 +501,7 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
// return;
bool bChanged(false);
-
+ CExpansionPolicy *pol=m_defaultPolicy;
if(m_pDasherView != 0) {
if(!GetBoolParameter(BP_TRAINING)) {
if (m_pUserLog != NULL) {
@@ -506,7 +512,7 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
int iNumDeleted = 0;
if(m_pInputFilter) {
- bChanged = m_pInputFilter->Timer(iTime, m_pDasherView, m_pDasherModel, &vAdded, &iNumDeleted);
+ bChanged = m_pInputFilter->Timer(iTime, m_pDasherView, m_pDasherModel, &vAdded, &iNumDeleted, &pol);
}
#ifndef _WIN32_WCE
@@ -519,7 +525,7 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
}
else {
if(m_pInputFilter) {
- bChanged = m_pInputFilter->Timer(iTime, m_pDasherView, m_pDasherModel, 0, 0);
+ bChanged = m_pInputFilter->Timer(iTime, m_pDasherView, m_pDasherModel, 0, 0, &pol);
}
}
@@ -543,9 +549,7 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
bForceRedraw |= m_bLastChanged;
m_bLastChanged = bChanged; //will also be set in Redraw if any nodes were expanded.
- //limit the number of nodes we expand per frame...
- LimitedNodeQueue nq(max(1l,(500+GetLongParameter(LP_NODE_BUDGET))/1000)); //amortize over multiple frames
- Redraw(bChanged || m_bRedrawScheduled || bForceRedraw, nq);
+ Redraw(bChanged || m_bRedrawScheduled || bForceRedraw, *pol);
m_bRedrawScheduled = false;
@@ -557,7 +561,7 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
bReentered=false;
}
-void CDasherInterfaceBase::Redraw(bool bRedrawNodes, NodeQueue &nodeQueue) {
+void CDasherInterfaceBase::Redraw(bool bRedrawNodes, CExpansionPolicy &policy) {
// No point continuing if there's nothing to draw on...
if(!m_pDasherView)
return;
@@ -565,7 +569,7 @@ void CDasherInterfaceBase::Redraw(bool bRedrawNodes, NodeQueue &nodeQueue) {
// Draw the nodes
if(bRedrawNodes) {
m_pDasherView->Screen()->SendMarker(0);
- if (m_pDasherModel) m_bLastChanged |= m_pDasherModel->RenderToView(m_pDasherView,nodeQueue);
+ if (m_pDasherModel) m_bLastChanged |= m_pDasherModel->RenderToView(m_pDasherView,policy);
}
// Draw the decorations
@@ -642,14 +646,12 @@ void CDasherInterfaceBase::ChangeScreen(CDasherScreen *NewScreen) {
}
PositionActionButtons();
- UnlimitedNodeQueue nq; //maintain budget, but allow arbitrary amount of work.
- Redraw(true, nq); // (we're assuming resolution changes are occasional, i.e.
- // we don't need to worry about maintaining the frame rate - so we can do
- // as much work as necessary. We'll only do *any* if the new Screen somehow
- // allocates pixels to nodes in a different (rather than strictly more/less
- // generous) fashion - so this is probably more to do with the View changing
- // (it's behaviour), rather than the Screen. But I guess it allows for future
- // Views, and/or the View to behave differently on different aspect ratios...
+ BudgettingPolicy pol(GetLongParameter(LP_NODE_BUDGET)); //maintain budget, but allow arbitrary amount of work.
+ Redraw(true, pol); // (we're assuming resolution changes are occasional, i.e.
+ // we don't need to worry about maintaining the frame rate, so we can do
+ // as much work as necessary. However, it'd probably be better still to
+ // get a node queue from the input filter, as that might have a different
+ // policy / budget.
}
void CDasherInterfaceBase::ChangeView() {
diff --git a/Src/DasherCore/DasherInterfaceBase.h b/Src/DasherCore/DasherInterfaceBase.h
index 6c4fbf3..7446d24 100644
--- a/Src/DasherCore/DasherInterfaceBase.h
+++ b/Src/DasherCore/DasherInterfaceBase.h
@@ -437,6 +437,9 @@ protected:
private:
+ //The default expansion policy to use - an amortized policy depending on the LP_NODE_BUDGET parameter.
+ CExpansionPolicy *m_defaultPolicy;
+
/// @name Platform dependent utility functions
/// These functions provide various platform dependent functions
/// required by the core. A derived class is created for each
@@ -524,7 +527,7 @@ protected:
void ChangeAlphabet();
void ChangeColours();
void ChangeView();
- void Redraw(bool bRedrawNodes, NodeQueue &nodeQueue);
+ void Redraw(bool bRedrawNodes, CExpansionPolicy &policy);
void SetupActionButtons();
void DestroyActionButtons();
void PositionActionButtons();
diff --git a/Src/DasherCore/DasherModel.cpp b/Src/DasherCore/DasherModel.cpp
index 50e6e48..57a4da9 100644
--- a/Src/DasherCore/DasherModel.cpp
+++ b/Src/DasherCore/DasherModel.cpp
@@ -311,7 +311,7 @@ void CDasherModel::InitialiseAtOffset(int iOffset, CDasherView *pView) {
// TODO: What about parents?
if(m_Root->Range() >= 0.1 * GetLongParameter(LP_NORMALIZATION)) {
- Push_Node(m_Root);
+ ExpandNode(m_Root);
}
// Set the root coordinates so that the root node is an appropriate
@@ -436,10 +436,11 @@ bool CDasherModel::NextScheduledStep(unsigned long iTime, Dasher::VECTOR_SYMBOL_
iNewMax = m_deGotoQueue.front().iN2;
m_deGotoQueue.pop_front();
- return UpdateBounds(iNewMin, iNewMax, iTime, pAdded, pNumDeleted);
+ UpdateBounds(iNewMin, iNewMax, iTime, pAdded, pNumDeleted);
+ return true;
}
-bool CDasherModel::OneStepTowards(myint miMousex, myint miMousey, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
+void CDasherModel::OneStepTowards(myint miMousex, myint miMousey, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
//if (GetBoolParameter(BP_DASHER_PAUSED)) return false;
m_deGotoQueue.clear();
@@ -447,10 +448,10 @@ bool CDasherModel::OneStepTowards(myint miMousex, myint miMousey, unsigned long
// works out next viewpoint
Get_new_root_coords(miMousex, miMousey, iNewMin, iNewMax, iTime);
- return UpdateBounds(iNewMin, iNewMax, iTime, pAdded, pNumDeleted);
+ UpdateBounds(iNewMin, iNewMax, iTime, pAdded, pNumDeleted);
}
-bool CDasherModel::UpdateBounds(myint iNewMin, myint iNewMax, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
+void CDasherModel::UpdateBounds(myint iNewMin, myint iNewMax, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded, int* pNumDeleted) {
// Find out the current node under the crosshair
CDasherNode *old_under_cross=Get_node_under_crosshair();
@@ -462,15 +463,12 @@ bool CDasherModel::UpdateBounds(myint iNewMin, myint iNewMax, unsigned long iTim
// Check whether new nodes need to be created
CDasherNode* new_under_cross = Get_node_under_crosshair();
- Push_Node(new_under_cross);
+ ExpandNode(new_under_cross);
// TODO: Make this more efficient
new_under_cross = Get_node_under_crosshair();
HandleOutput(new_under_cross, old_under_cross, pAdded, pNumDeleted);
-
-
- return true;
}
void CDasherModel::NewFrame(unsigned long Time) {
@@ -631,7 +629,7 @@ bool CDasherModel::DeleteCharacters(CDasherNode *newnode, CDasherNode *oldnode,
return false;
}
-void CDasherModel::Push_Node(CDasherNode *pNode) {
+void CDasherModel::ExpandNode(CDasherNode *pNode) {
DASHER_ASSERT(pNode != NULL);
// TODO: Is NF_ALLCHILDREN any more useful/efficient than reading the map size?
@@ -681,7 +679,7 @@ void CDasherModel::Push_Node(CDasherNode *pNode) {
}
-bool CDasherModel::RenderToView(CDasherView *pView, NodeQueue &nodeQueue) {
+bool CDasherModel::RenderToView(CDasherView *pView, CExpansionPolicy &policy) {
DASHER_ASSERT(pView != NULL);
DASHER_ASSERT(m_Root != NULL);
@@ -694,7 +692,7 @@ bool CDasherModel::RenderToView(CDasherView *pView, NodeQueue &nodeQueue) {
// The Render routine will fill iGameTargetY with the Dasher Coordinate of the
// youngest node with NF_GAME set. The model is responsible for setting NF_GAME on
// the appropriate Nodes.
- pView->Render(m_Root, m_Rootmin + m_iDisplayOffset, m_Rootmax + m_iDisplayOffset, nodeQueue, true, &vGameTargetY);
+ pView->Render(m_Root, m_Rootmin + m_iDisplayOffset, m_Rootmax + m_iDisplayOffset, policy, true, &vGameTargetY);
/////////GAME MODE TEMP//////////////
if(m_bGameMode)
@@ -702,42 +700,6 @@ bool CDasherModel::RenderToView(CDasherView *pView, NodeQueue &nodeQueue) {
pTeacher->SetTargetY(vGameTargetY);
//////////////////////////////////////
- //ACL Off-screen nodes (zero collapse cost) will have been collapsed already.
- //Hence, here we act to maintain the node budget....
- //(however, note that doing this here will only expand one level per frame,
- //and won't really take effect until the *next* frame!)
- int iNodeBudget = GetLongParameter(LP_NODE_BUDGET);
-
- //first, make sure we are within our budget (probably only in case the budget's changed)
- while (nodeQueue.hasNodesToCollapse()
- && currentNumNodeObjects() > iNodeBudget)
- {
- nodeQueue.nodeToCollapse()->Delete_children();
- nodeQueue.popNodeToCollapse();
- }
-
- //ok. Since we're within budget, there's no point in doing anything if there aren't
- //nodes to expand (as zero-cost collapses have already been performed)
- while (nodeQueue.hasNodesToExpand())
- {
- if (currentNumNodeObjects() + nodeQueue.nodeToExpand()->ExpectedNumChildren() < iNodeBudget)
- {
- Push_Node(nodeQueue.nodeToExpand());
- nodeQueue.popNodeToExpand();
- bReturnValue = true;
- //...and loop.
- }
- else if (nodeQueue.hasNodesToCollapse()
- && nodeQueue.nodeToCollapse()->m_dCost < nodeQueue.nodeToExpand()->m_dCost)
- {
- //make room by performing collapse...
- nodeQueue.nodeToCollapse()->Delete_children();
- nodeQueue.popNodeToCollapse();
- //...and see how much room that makes
- }
- else break; //not enough room, nothing to collapse.
- }
-
CDasherNode *pNewNode = Get_node_under_crosshair();
// TODO: Fix up stats
@@ -745,6 +707,10 @@ bool CDasherModel::RenderToView(CDasherView *pView, NodeQueue &nodeQueue) {
if(pNewNode != pOldNode)
HandleOutput(pNewNode, pOldNode, NULL, NULL);
+ //ACL Off-screen nodes (zero collapse cost) will have been collapsed already.
+ //Hence, this acts to maintain the node budget....or whatever the queue's policy is!
+ if (policy.apply(m_pNodeCreationManager,this)) bReturnValue=true;
+
return bReturnValue;
}
diff --git a/Src/DasherCore/DasherModel.h b/Src/DasherCore/DasherModel.h
index b2006be..1412b0b 100644
--- a/Src/DasherCore/DasherModel.h
+++ b/Src/DasherCore/DasherModel.h
@@ -36,7 +36,7 @@
#include "DasherTypes.h"
#include "FrameRate.h"
#include "NodeCreationManager.h"
-#include "NodeQueue.h"
+#include "ExpansionPolicy.h"
namespace Dasher {
class CDasherModel;
@@ -76,7 +76,7 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
///
/// Update the root location with *one step* towards the specified
/// co-ordinates - used by timer callbacks (for non-button modes)
- bool OneStepTowards(myint, myint, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded = NULL, int* pNumDeleted = NULL);
+ void OneStepTowards(myint, myint, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB* pAdded = NULL, int* pNumDeleted = NULL);
///
/// Notify the framerate class that a new frame has occurred
@@ -126,7 +126,7 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
/// perform further expansion.
///
- bool RenderToView(CDasherView *pView, NodeQueue &nodeQueue);
+ bool RenderToView(CDasherView *pView, CExpansionPolicy &policy);
/// @}
@@ -193,13 +193,16 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
return 0;
};
+ /// Create the children of a Dasher node
+ void ExpandNode(CDasherNode * pNode);
+
void SetControlOffset(int iOffset);
private:
/// Common portion of OneStepTowards / NextScheduledStep, taking
/// bounds for the root node in the next frame.
- bool UpdateBounds(myint iNewMin, myint iNewMax, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ void UpdateBounds(myint iNewMin, myint iNewMax, unsigned long iTime, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
/// Struct representing intermediate stages in the goto queue
///
@@ -306,10 +309,6 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
/// Called from InitialiseAtOffset
void DeleteTree();
- /// Create the children of a Dasher node
- void Push_Node(CDasherNode * pNode);
-
-
///
/// Perform output on a node - recurse up the tree outputting any
/// symbols which have not been output so far. Neeed to check
diff --git a/Src/DasherCore/DasherNode.h b/Src/DasherCore/DasherNode.h
index b537589..fd4e7da 100644
--- a/Src/DasherCore/DasherNode.h
+++ b/Src/DasherCore/DasherNode.h
@@ -67,7 +67,6 @@ class Dasher::CDasherNode:private NoClones {
std::string strDisplayText;
};
CDasherNode *onlyChildRendered; //cache that only one child was rendered (as it filled the screen)
- double m_dCost; //to expand or collapse
/// Container type for storing children. Note that it's worth
/// optimising this as lookup happens a lot
diff --git a/Src/DasherCore/DasherView.cpp b/Src/DasherCore/DasherView.cpp
index daa01f1..41ee016 100644
--- a/Src/DasherCore/DasherView.cpp
+++ b/Src/DasherCore/DasherView.cpp
@@ -55,11 +55,11 @@ void CDasherView::ChangeScreen(CDasherScreen *NewScreen) {
/////////////////////////////////////////////////////////////////////////////
-void CDasherView::Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY) {
+void CDasherView::Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, CExpansionPolicy &policy, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY) {
m_iRenderCount = 0;
Screen()->SetLoadBackground(false);
- RenderNodes(pRoot, iRootMin, iRootMax, nodeQueue, pvGameTargetY);
+ RenderNodes(pRoot, iRootMin, iRootMax, policy, pvGameTargetY);
}
int CDasherView::GetCoordinateCount() {
diff --git a/Src/DasherCore/DasherView.h b/Src/DasherCore/DasherView.h
index 9b7b1eb..a421bc8 100644
--- a/Src/DasherCore/DasherView.h
+++ b/Src/DasherCore/DasherView.h
@@ -17,7 +17,7 @@ namespace Dasher {
#include "DasherTypes.h"
#include "DasherComponent.h"
#include "View/DelayedDraw.h"
-#include "NodeQueue.h"
+#include "ExpansionPolicy.h"
/// \defgroup View Visualisation of the model
/// @{
@@ -122,7 +122,7 @@ public:
/// Renders Dasher with mouse-dependent items
/// \todo Clarify relationship between Render functions and probably only expose one
- virtual void Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY);
+ virtual void Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, CExpansionPolicy &policy, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY);
/// @}
@@ -193,7 +193,7 @@ private:
CDasherInput *m_pInput; // Input device abstraction
/// Renders the Dasher node structure
- virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer) = 0;
+ virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, CExpansionPolicy &policy, std::vector<std::pair<myint,bool> > *pvGamePointer) = 0;
/// Get the co-ordinates from the input device
diff --git a/Src/DasherCore/DasherViewSquare.cpp b/Src/DasherCore/DasherViewSquare.cpp
index a5d4e87..82e1263 100644
--- a/Src/DasherCore/DasherViewSquare.cpp
+++ b/Src/DasherCore/DasherViewSquare.cpp
@@ -112,7 +112,7 @@ void CDasherViewSquare::HandleEvent(Dasher::CEvent *pEvent) {
}
void CDasherViewSquare::RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax,
- NodeQueue &nodeQueue,
+ CExpansionPolicy &policy,
std::vector<std::pair<myint,bool> > *pvGamePointer) {
DASHER_ASSERT(pRoot != 0);
myint iDasherMinX;
@@ -163,8 +163,7 @@ void CDasherViewSquare::RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iR
// 0, -1, Nodes1, false, true, 1);
// Render the root node (and children)
- pRoot->m_dCost = std::numeric_limits<double>::infinity();
- RecursiveRender(pRoot, iRootMin, iRootMax, iDasherMaxX, nodeQueue, pvGamePointer,iDasherMaxX,0,0);
+ RecursiveRender(pRoot, iRootMin, iRootMax, iDasherMaxX, policy, std::numeric_limits<double>::infinity(), pvGamePointer,iDasherMaxX,0,0);
// Labels are drawn in a second parse to get the overlapping right
m_pDelayDraw->Draw(Screen());
@@ -179,7 +178,7 @@ void CDasherViewSquare::RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iR
#define MIN_SIZE 2
bool CDasherViewSquare::CheckRender(CDasherNode *pRender, myint y1, myint y2,
- int mostleft, NodeQueue &nodeQueue,
+ int mostleft, CExpansionPolicy &policy, double dMaxCost,
std::vector<std::pair<myint,bool> > *pvGamePointer,
myint parent_width, int parent_color, int iDepth)
{
@@ -207,12 +206,7 @@ bool CDasherViewSquare::CheckRender(CDasherNode *pRender, myint y1, myint y2,
{
//node should be rendered!
- //hence, is potentially collapsible/expandable - set it's cost
- dasherint iDasherYDist = (y1 > 2048) ? y1 - 2048 : (y2 < 2048) ? 2048-y2 : 0; //minimum dist - better in pixels...?
- pRender->m_dCost = (y2-y1) / (iDasherYDist / + 50.0 + iDepth);
- DASHER_ASSERT(!pRender->Parent() || pRender->m_dCost < pRender->Parent()->m_dCost);
-
- RecursiveRender(pRender, y1, y2, mostleft, nodeQueue, pvGamePointer, parent_width, parent_color, iDepth);
+ RecursiveRender(pRender, y1, y2, mostleft, policy, dMaxCost, pvGamePointer, parent_width, parent_color, iDepth);
return true;
}
}
@@ -231,7 +225,7 @@ bool CDasherViewSquare::CheckRender(CDasherNode *pRender, myint y1, myint y2,
}
void CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2,
- int mostleft, NodeQueue &nodeQueue,
+ int mostleft, CExpansionPolicy &policy, double dMaxCost,
std::vector<std::pair<myint,bool> > *pvGamePointer,
myint parent_width,int parent_color, int iDepth)
{
@@ -290,14 +284,16 @@ void CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2
DasherDrawRectangle(std::min(y2-y1,iDasherMaxX), std::min(y2,iDasherMaxY),0, std::max(y1,iDasherMinY), pRender->GetDisplayInfo()->iColour, -1, Nodes1, false, true, 1);
}
//also allow it to be expanded, it's big enough.
- nodeQueue.pushNodeToExpand(pRender);
+ policy.pushNode(pRender, y1, y2, true, dMaxCost);
return;
}
- //Node has children. It can therefore be collapsed...
- if (!pRender->GetFlag(NF_GAME)
- && pRender->m_dCost!=std::numeric_limits<double>::infinity()) //don't collapse a node covering the screen!!
- nodeQueue.pushNodeToCollapse(pRender);
+ //Node has children. It can therefore be collapsed...however,
+ // we don't allow a node covering the crosshair to be collapsed
+ // (at best this'll mean there's nowhere useful to go forwards;
+ // at worst, all kinds of crashes trying to do text output!)
+ if (!pRender->GetFlag(NF_GAME) && !pRender->GetFlag(NF_SEEN))
+ dMaxCost = policy.pushNode(pRender, y1, y2, false, dMaxCost);
// Render children
int norm = (myint)GetLongParameter(LP_NORMALIZATION);
@@ -319,15 +315,15 @@ void CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2
myint newy2 = y1 + (Range * (myint)pChild->Hbnd()) / (myint)norm;
if (newy1 < iDasherMinY && newy2 > iDasherMaxY) {
//still covers entire screen. Parent should too...
- DASHER_ASSERT(pRender->m_dCost == std::numeric_limits<double>::infinity());
- //set cost (in a way that prevents collapse) before recursion
- pChild->m_dCost = std::numeric_limits<double>::infinity();
+ DASHER_ASSERT(dMaxCost == std::numeric_limits<double>::infinity());
+
//don't inc iDepth, meaningless when covers the screen
RecursiveRender(pChild, newy1, newy2, mostleft,
- nodeQueue, pvGamePointer,
- temp_parentwidth, temp_parentcolor, iDepth);
+ policy, dMaxCost, pvGamePointer,
+ temp_parentwidth, temp_parentcolor, iDepth);
//leave pRender->onlyChildRendered set, so remaining children are skipped
- } else
+ }
+ else
pRender->onlyChildRendered = NULL;
}
@@ -341,15 +337,14 @@ void CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2
myint newy1 = y1 + (Range * (myint)pChild->Lbnd()) / (myint)norm;/// norm and lbnd are simple ints
myint newy2 = y1 + (Range * (myint)pChild->Hbnd()) / (myint)norm;
if (newy1 < iDasherMinY && newy2 > iDasherMaxY) {
+ DASHER_ASSERT(dMaxCost == std::numeric_limits<double>::infinity());
pRender->onlyChildRendered = pChild;
- //set cost (in a way that prevents collapse), and recurse
- pChild->m_dCost = std::numeric_limits<double>::infinity();
- RecursiveRender(pChild, newy1, newy2, mostleft, nodeQueue, pvGamePointer, temp_parentwidth, temp_parentcolor, iDepth);
+ RecursiveRender(pChild, newy1, newy2, mostleft, policy, dMaxCost, pvGamePointer, temp_parentwidth, temp_parentcolor, iDepth);
//ensure we don't blank over this child in "finishing off" the parent (!)
lasty=newy2;
break; //no need to render any more children!
}
- if (CheckRender(pChild, newy1, newy2, mostleft, nodeQueue,
+ if (CheckRender(pChild, newy1, newy2, mostleft, policy, dMaxCost,
pvGamePointer, temp_parentwidth, temp_parentcolor, iDepth+1))
{
diff --git a/Src/DasherCore/DasherViewSquare.h b/Src/DasherCore/DasherViewSquare.h
index b19b168..712c0e2 100644
--- a/Src/DasherCore/DasherViewSquare.h
+++ b/Src/DasherCore/DasherViewSquare.h
@@ -109,17 +109,17 @@ private:
///
/// Render the current state of the model.
///
- virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer);
+ virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, CExpansionPolicy &policy, std::vector<std::pair<myint,bool> > *pvGamePointer);
///
/// Recursively render all nodes in a tree. Responsible for all the Render_node calls
///
- void RecursiveRender(CDasherNode * Render, myint y1, myint y2, int mostleft, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer, myint parent_width,int parent_color, int iDepth);
+ void RecursiveRender(CDasherNode * Render, myint y1, myint y2, int mostleft, CExpansionPolicy &policy, double dMaxCost, std::vector<std::pair<myint,bool> > *pvGamePointer, myint parent_width,int parent_color, int iDepth);
///Check that a node is large enough, and onscreen, to render;
///calls RecursiveRender if so, or collapses the node immediately if not
- bool CheckRender(CDasherNode * Render, myint y1, myint y2, int mostleft, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer, myint parent_width,int parent_color, int iDepth);
+ bool CheckRender(CDasherNode * Render, myint y1, myint y2, int mostleft, CExpansionPolicy &policy, double dMaxCost, std::vector<std::pair<myint,bool> > *pvGamePointer, myint parent_width,int parent_color, int iDepth);
/// Render a single node
/// \param Color The colour to draw it
diff --git a/Src/DasherCore/DefaultFilter.cpp b/Src/DasherCore/DefaultFilter.cpp
index 7af5d83..80a7550 100644
--- a/Src/DasherCore/DefaultFilter.cpp
+++ b/Src/DasherCore/DefaultFilter.cpp
@@ -42,7 +42,7 @@ bool CDefaultFilter::DecorateView(CDasherView *pView) {
return bDidSomething;
}
-bool CDefaultFilter::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
+bool CDefaultFilter::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
bool bDidSomething = false;
if (!GetBoolParameter(BP_DASHER_PAUSED))
{
@@ -66,8 +66,8 @@ bool CDefaultFilter::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m
return false;
}
- bDidSomething = m_pDasherModel->OneStepTowards(iDasherX,iDasherY, Time, pAdded, pNumDeleted);
- DASHER_ASSERT (bDidSomething);
+ m_pDasherModel->OneStepTowards(iDasherX,iDasherY, Time, pAdded, pNumDeleted);
+ bDidSomething = true;
m_pAutoSpeedControl->SpeedControl(iDasherX, iDasherY, m_pDasherModel->Framerate(), m_pDasherView);
}
diff --git a/Src/DasherCore/DefaultFilter.h b/Src/DasherCore/DefaultFilter.h
index 116b44c..b4a8826 100644
--- a/Src/DasherCore/DefaultFilter.h
+++ b/Src/DasherCore/DefaultFilter.h
@@ -16,7 +16,7 @@ class CDefaultFilter : public CInputFilter {
virtual void HandleEvent(Dasher::CEvent * pEvent);
virtual bool DecorateView(CDasherView *pView);
- virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void KeyDown(int iTime, int iId, CDasherView *pDasherView, CDasherModel *pModel, CUserLogBase *pUserLog);
protected:
diff --git a/Src/DasherCore/DynamicFilter.cpp b/Src/DasherCore/DynamicFilter.cpp
index 538dc40..453745c 100644
--- a/Src/DasherCore/DynamicFilter.cpp
+++ b/Src/DasherCore/DynamicFilter.cpp
@@ -30,7 +30,7 @@ CDynamicFilter::CDynamicFilter(Dasher::CEventHandler * pEventHandler, CSettingsS
pause();
}
-bool CDynamicFilter::Timer(int iTime, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted)
+bool CDynamicFilter::Timer(int iTime, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol)
{
if(m_bKeyDown && !m_bKeyHandled && ((iTime - m_iKeyDownTime) > GetLongParameter(LP_HOLD_TIME))) {
Event(iTime, m_iHeldId, 1, m_pDasherModel, m_pUserLog);
@@ -38,7 +38,10 @@ bool CDynamicFilter::Timer(int iTime, CDasherView *m_pDasherView, CDasherModel *
//return true; //ACL although that's what old DynamicFilter did, surely we should progress normally?
}
if (isPaused()) return false;
- if (isReversing()) return m_pDasherModel->OneStepTowards(41943,2048, iTime, pAdded, pNumDeleted);
+ if (isReversing()) {
+ m_pDasherModel->OneStepTowards(41943,2048, iTime, pAdded, pNumDeleted);
+ return true;
+ }
//moving forwards. Check auto speed control...
unsigned int uTime = static_cast<unsigned int>(iTime);
if (GetBoolParameter(BP_AUTO_SPEEDCONTROL) && m_uSpeedControlTime < uTime)
@@ -47,7 +50,7 @@ bool CDynamicFilter::Timer(int iTime, CDasherView *m_pDasherView, CDasherModel *
SetLongParameter(LP_MAX_BITRATE, GetLongParameter(LP_MAX_BITRATE) * (1.0 + GetLongParameter(LP_DYNAMIC_SPEED_INC)/100.0));
m_uSpeedControlTime = uTime + 1000*GetLongParameter(LP_DYNAMIC_SPEED_FREQ);
}
- return TimerImpl(iTime, m_pDasherView, m_pDasherModel, pAdded, pNumDeleted);
+ return TimerImpl(iTime, m_pDasherView, m_pDasherModel, pAdded, pNumDeleted, pol);
}
void CDynamicFilter::KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog) {
diff --git a/Src/DasherCore/DynamicFilter.h b/Src/DasherCore/DynamicFilter.h
index f42b78c..c0580bc 100644
--- a/Src/DasherCore/DynamicFilter.h
+++ b/Src/DasherCore/DynamicFilter.h
@@ -32,7 +32,7 @@ class CDynamicFilter : public CInputFilter {
CDynamicFilter(Dasher::CEventHandler * pEventHandler, CSettingsStore *pSettingsStore, CDasherInterfaceBase *pInterface, ModuleID_t iID, int iType, const char *szName);
///when reversing, backs off; when paused, does nothing; when running, delegates to TimerImpl
- virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog);
virtual void KeyUp(int iTime, int iId, CDasherView *pView, CDasherModel *pModel);
@@ -52,7 +52,7 @@ class CDynamicFilter : public CInputFilter {
virtual void reverse();
virtual void run();
- virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) = 0;
+ virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) = 0;
private:
int m_iState; // 0 = paused, 1 = reversing, >=2 = running (extensible by subclasses)
diff --git a/Src/DasherCore/ExpansionPolicy.cpp b/Src/DasherCore/ExpansionPolicy.cpp
new file mode 100644
index 0000000..62b8a1d
--- /dev/null
+++ b/Src/DasherCore/ExpansionPolicy.cpp
@@ -0,0 +1,178 @@
+/*
+ * ExpansionPolicy.cpp
+ * Dasher
+ *
+ * Created by Alan Lawrence on 26/10/2009.
+ * Copyright 2009 Cavendish Laboratory. All rights reserved.
+ *
+ */
+
+#include "ExpansionPolicy.h"
+#include "DasherModel.h"
+#include <algorithm>
+
+using namespace Dasher;
+using namespace std;
+
+bool Less(pair<double,CDasherNode *> x, pair<double, CDasherNode *> y) {return x.first < y.first;}
+bool More(pair<double,CDasherNode *> x, pair<double, CDasherNode *> y) {return x.first > y.first;}
+
+BudgettingPolicy::BudgettingPolicy(unsigned int iNodeBudget) : m_iNodeBudget(iNodeBudget) {}
+
+double BudgettingPolicy::pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dParentCost) {
+ double dRes = getCost(pNode, iMin, iMax);
+ if (dRes >= dParentCost) {
+ double eps = min(1.0, abs(dParentCost));
+ while (dParentCost - (eps/2.0) < dParentCost) eps/=2.0;
+ dRes = dParentCost - eps;
+ }
+ vector<pair<double, CDasherNode*> > &target = (bExpand) ? sExpand : sCollapse;
+ target.push_back(pair<double, CDasherNode *>(dRes,pNode));
+ return dRes;
+}
+
+///Expand one level per frame; note this won't really take effect until the *next* frame!
+bool BudgettingPolicy::apply(CNodeCreationManager *pMgr, CDasherModel *pModel) {
+ //firstly, sort the nodes...
+ sort(sExpand.begin(), sExpand.end(), Less);
+ //sExpand now in < order: [0] < [1] < ... < [size()-1] - so last element will have highest (cost=)benefit
+ sort(sCollapse.begin(), sCollapse.end(),More);
+ //sCollapse now in > order: [0] > ... > [size()-1] - so last element will have lowest cost(=benefit)
+
+ //did we expand anything? (if so, there may be more opportunities for expansion next frame)
+ bool bReturnValue = false;
+
+ //maintain record of the highest cost we've incurred by collapsing a node;
+ // avoid expanding anything LESS beneficial than that, as (even if we've room)
+ // it'll be better to instead wait until next frame (and possibly re-expand the
+ // collapsed node! Sadly we can't rely on trading one-for-one as different nodes
+ // may have different numbers of children...)
+ double collapseCost = -std::numeric_limits<double>::infinity();
+
+ //first, make sure we are within our budget (probably only in case the budget's changed)
+ while (!sCollapse.empty()
+ && currentNumNodeObjects() > m_iNodeBudget)
+ {
+ pair<double,CDasherNode *> node = sCollapse.back();
+ DASHER_ASSERT(node.first >= collapseCost);
+ collapseCost = node.first;
+ node.second->Delete_children();
+ sCollapse.pop_back();
+ }
+
+ //ok, we're now within budget. However, we may still wish to "trade off" nodes
+ // against each other, in case there are any unimportant (low-cost) nodes we could collapse
+ // to make room to expand other more important (high-benefit) nodes.
+ while (!sExpand.empty() && sExpand.back().first > collapseCost)
+ {
+ if (currentNumNodeObjects()+sExpand.back().second->ExpectedNumChildren() < m_iNodeBudget)
+ {
+ pModel->ExpandNode(sExpand.back().second);
+ sExpand.pop_back();
+ bReturnValue = true;
+ //...and loop.
+ }
+ else if (!sCollapse.empty()
+ && sCollapse.back().first < sExpand.back().first)
+ {
+ //could be a beneficial trade - make room by performing collapse...
+ pair<double,CDasherNode *> node = sCollapse.back();
+ DASHER_ASSERT(node.first >= collapseCost);
+ collapseCost = node.first;
+ node.second->Delete_children();
+ sCollapse.pop_back();
+ //...and see how much room that makes
+ }
+ else break; //not enough room, nothing to collapse.
+ }
+ sExpand.clear();
+ sCollapse.clear();
+ return bReturnValue;
+}
+
+int BudgettingPolicy::getRange(int y1, int y2, int iMin, int iMax) {
+ if (y1>iMax || y2 < iMin) return 0;
+ return min(y2, iMax) - max(y1, iMin);
+}
+
+double BudgettingPolicy::getCost(CDasherNode *pNode, int iDasherMinY, int iDasherMaxY) {
+ return getRange(iDasherMinY, iDasherMaxY, 0, 4096);
+}
+
+AmortizedPolicy::AmortizedPolicy(unsigned int iNodeBudget) : BudgettingPolicy(iNodeBudget), m_iMaxExpands(std::max(1u,500+(iNodeBudget/1000))) {}
+
+AmortizedPolicy::AmortizedPolicy(unsigned int iNodeBudget, unsigned int iMaxExpands) : BudgettingPolicy(iNodeBudget), m_iMaxExpands(iMaxExpands) {}
+
+double AmortizedPolicy::pushNode(CDasherNode *node, int iMin, int iMax, bool bExpand, double dParentCost) {
+ double dRes = BudgettingPolicy::pushNode(node,iMin,iMax,bExpand,dParentCost);
+ if (bExpand && sExpand.size() > 2*m_iMaxExpands) trim();
+ return dRes;
+}
+
+bool AmortizedPolicy::apply(CNodeCreationManager *pMgr, CDasherModel *pModel) {
+ trim();
+ return BudgettingPolicy::apply(pMgr,pModel);
+}
+
+void AmortizedPolicy::trim() {
+ if (sExpand.size() <= m_iMaxExpands) return;
+ //ok - repeatedly find a pivot element, and place it dividing all elements into
+ //those more than it (in lower indices) and those less than it (in higher indices),
+ // until we have separated off the <m_iMaxExpands> elements with greatest benefit
+#ifdef DEBUG_TRIM
+ vector<pair<double,CDasherNode *> > backup = sExpand; //yep, copy the lot
+#endif
+ unsigned int start = 0, stop = sExpand.size()-1;
+ while (true) {
+ //at this point, we assume we know only that elements [start - stop] need examining....
+ unsigned int low = start, high = stop;
+ pair<double,CDasherNode *> &pivot = sExpand[low++];
+ while (true) {
+ while (low <= high && !Less(sExpand[low],pivot)) low++;
+ //all elements (start-low) can stay on left of pivot.
+ if (low <= high) {
+ //element <low> needs to be on R of pivot.
+ while (high >= low && !More(sExpand[high],pivot)) high--;
+ if (high >= low) {
+ //element <high> needs to be on L of pivot
+ pair<double,CDasherNode *> temp = sExpand[low];
+ sExpand[low++] = sExpand[high];
+ sExpand[high--]=temp;
+ continue;
+ } //else, fall through to break -> place pivot
+ }
+ break;
+ }
+ //place pivot at index (low-1) - if that's not where it is already!
+ low--;
+ if (start!=low) {
+ pair<double,CDasherNode *> temp = sExpand[start];
+ sExpand[start]=sExpand[low];
+ sExpand[low] = temp;
+ }
+ //if (low == m_iMaxExpands), elements [0 - low-1] are all <= pivot
+ //if (low == m_iMaxExpands-1), elements [0 - low] are all <= pivot (as pivot<=pivot!)
+ //finish in both cases.
+ if (low < m_iMaxExpands-1)
+ start=low+1;
+ else if (low>m_iMaxExpands)
+ stop=low-1;
+ else break;
+ }
+ //truncate array
+ sExpand.resize(m_iMaxExpands);
+#ifdef DEBUG_TRIM
+ //now compare with the brute-force method...
+ sort(sExpand.begin(), sExpand.end(), Less);
+ sort(backup.begin(), backup.end(), Less);
+ backup.erase(backup.begin(), backup.end()-m_iMaxExpands);
+ //now compare. note we _don't_ require the node pointers to be the same;
+ // where the cut-off point falls within a group of nodes with the same cost,
+ // the two vectors could have different nodes from that group.
+ double dFirstCost = sExpand[sExpand.size()-1].first;
+ for (vector<pair<double, CDasherNode *> >::iterator it1=sExpand.begin(), it2=backup.begin(); it1!=sExpand.end(); it1++, it2++)
+ if (*it1 == *it2) continue;
+ else if (it1->first == dFirstCost && it2->first==dFirstCost) continue;
+ else cout << "trim not equal!\n";
+#endif
+}
\ No newline at end of file
diff --git a/Src/DasherCore/ExpansionPolicy.h b/Src/DasherCore/ExpansionPolicy.h
new file mode 100644
index 0000000..e5aaa9f
--- /dev/null
+++ b/Src/DasherCore/ExpansionPolicy.h
@@ -0,0 +1,73 @@
+/*
+ * ExpansionPolicy.h
+ * Dasher
+ *
+ * Created by Alan Lawrence on 03/06/2009.
+ * Copyright 2009 Cavendish Laboratory. All rights reserved.
+ *
+ */
+
+#ifndef __ExpansionPolicy_h__
+#define __ExpansionPolicy_h__
+
+#include <vector>
+#include <queue>
+#include <limits>
+#include <algorithm>
+#include "DasherNode.h"
+
+class CNodeCreationManager;
+
+namespace Dasher {
+ class CDasherModel;
+class CExpansionPolicy
+{
+public:
+ ///dMaxCost should be the value returned by pushNode from the call for the node most closely enclosing pNode (that was pushed!)
+ ///for the first (outermost) node, i.e. when no enclosing node has been passed, (+ive) INFINITY should be passed in.
+ virtual double pushNode(CDasherNode *pNode, int iDasherMinY, int iDasherMaxY, bool bExpand, double dMaxCost)=0;
+ ///Return TRUE if another frame should be forced.
+ virtual bool apply(CNodeCreationManager *pMgr, CDasherModel *model)=0;
+};
+
+class NoExpansions : public CExpansionPolicy
+{
+public:
+ double pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dMaxCost) {return dMaxCost;}
+ bool apply(CNodeCreationManager *pMgr, CDasherModel *model) {return false;}
+};
+
+///A policy that expands/collapses nodes to maintain a given node budget.
+///Also ascribes uniform costs, according to size within the range 0-4096.
+class BudgettingPolicy : public CExpansionPolicy
+{
+public:
+ BudgettingPolicy(unsigned int iNodeBudget);
+ ///sets cost according to getCost(pNode,iMin,iMax);
+ ///then assures node is cheaper (less important) than its parent;
+ ///then adds to relevant queue
+ double pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dParentCost);
+ bool apply(CNodeCreationManager *pMgr, CDasherModel *pModel);
+protected:
+ virtual double getCost(CDasherNode *pNode, int iDasherMinY, int iDasherMaxY);
+ ///return the intersection of the ranges (y1-y2) and (iMin-iMax)
+ int getRange(int y1, int y2, int iMin, int iMax);
+ std::vector<std::pair<double,CDasherNode *> > sExpand, sCollapse;
+ unsigned int m_iNodeBudget;
+};
+
+///limits expansion to a few nodes (per instance i.e. per frame)
+///(collapsing is at present unlimited, have to test this...)
+class AmortizedPolicy : public BudgettingPolicy
+{
+public:
+ AmortizedPolicy(unsigned int iNodeBudget);
+ AmortizedPolicy(unsigned int iNodeBudget, unsigned int iMaxExpands);
+ bool apply(CNodeCreationManager *pMgr, CDasherModel *pModel);
+ double pushNode(CDasherNode *pNode, int iMin, int iMax, bool bExpand, double dParentCost);
+private:
+ unsigned int m_iMaxExpands;
+ void trim();
+};
+}
+#endif /*defined __ExpansionPolicy_h__*/
diff --git a/Src/DasherCore/InputFilter.h b/Src/DasherCore/InputFilter.h
index 3eb6649..25a704a 100644
--- a/Src/DasherCore/InputFilter.h
+++ b/Src/DasherCore/InputFilter.h
@@ -29,7 +29,7 @@ class CInputFilter : public CDasherModule {
KeyUp(Time, iId, pDasherView, pModel);
};
- virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) { return false; };
+ virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol)=0;// { return false; };
virtual void Activate() {};
virtual void Deactivate() {};
diff --git a/Src/DasherCore/Makefile.am b/Src/DasherCore/Makefile.am
index 0d5aa82..3fc85b8 100644
--- a/Src/DasherCore/Makefile.am
+++ b/Src/DasherCore/Makefile.am
@@ -98,6 +98,8 @@ libdashercore_a_SOURCES = \
NodeCreationManager.cpp \
NodeCreationManager.h \
NodeManager.h \
+ ExpansionPolicy.cpp \
+ ExpansionPolicy.h \
OneButtonDynamicFilter.cpp \
OneButtonDynamicFilter.h \
OneButtonFilter.cpp \
diff --git a/Src/DasherCore/OneButtonDynamicFilter.cpp b/Src/DasherCore/OneButtonDynamicFilter.cpp
index 93a681e..69983e5 100644
--- a/Src/DasherCore/OneButtonDynamicFilter.cpp
+++ b/Src/DasherCore/OneButtonDynamicFilter.cpp
@@ -115,8 +115,9 @@ void COneButtonDynamicFilter::KeyUp(int Time, int iId, CDasherView *pDasherView,
CInputFilter::KeyUp(Time, iId, pDasherView, pModel, bPos, iX, iY);
}
-bool COneButtonDynamicFilter::TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
- return m_pDasherModel->OneStepTowards(m_iTargetX[m_iTarget], m_iTargetY[m_iTarget], Time, pAdded, pNumDeleted);
+bool COneButtonDynamicFilter::TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
+ m_pDasherModel->OneStepTowards(m_iTargetX[m_iTarget], m_iTargetY[m_iTarget], Time, pAdded, pNumDeleted);
+ return true;
}
void COneButtonDynamicFilter::ActionButton(int iTime, int iButton, int iType, CDasherModel *pModel, CUserLogBase *pUserLog) {
diff --git a/Src/DasherCore/OneButtonDynamicFilter.h b/Src/DasherCore/OneButtonDynamicFilter.h
index 0bb9b72..8d084d6 100644
--- a/Src/DasherCore/OneButtonDynamicFilter.h
+++ b/Src/DasherCore/OneButtonDynamicFilter.h
@@ -41,7 +41,7 @@ class COneButtonDynamicFilter : public CButtonMultiPress {
private:
unsigned int maxClickCount() {return 2;} //double-click to reverse
- virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void ActionButton(int iTime, int iButton, int iType, CDasherModel *pModel, CUserLogBase *pUserLog);
int m_iTarget;
diff --git a/Src/DasherCore/OneButtonFilter.cpp b/Src/DasherCore/OneButtonFilter.cpp
index 77550f9..a4f93cf 100644
--- a/Src/DasherCore/OneButtonFilter.cpp
+++ b/Src/DasherCore/OneButtonFilter.cpp
@@ -47,7 +47,7 @@ bool COneButtonFilter::DecorateView(CDasherView *pView) {
return true;
}
-bool COneButtonFilter::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
+bool COneButtonFilter::Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
if(bStarted) {
iLocation = (Time - iStartTime) * 4096 / GetLongParameter(LP_STATIC1B_TIME);
diff --git a/Src/DasherCore/OneButtonFilter.h b/Src/DasherCore/OneButtonFilter.h
index 45c6f02..3163bca 100644
--- a/Src/DasherCore/OneButtonFilter.h
+++ b/Src/DasherCore/OneButtonFilter.h
@@ -12,7 +12,7 @@ class COneButtonFilter : public CInputFilter {
~COneButtonFilter();
virtual bool DecorateView(CDasherView *pView);
- virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool Timer(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog);
bool GetSettings(SModuleSettings **pSettings, int *iCount);
private:
diff --git a/Src/DasherCore/StylusFilter.cpp b/Src/DasherCore/StylusFilter.cpp
index 272a593..7844292 100644
--- a/Src/DasherCore/StylusFilter.cpp
+++ b/Src/DasherCore/StylusFilter.cpp
@@ -9,7 +9,7 @@ CStylusFilter::CStylusFilter(Dasher::CEventHandler *pEventHandler, CSettingsStor
: CDefaultFilter(pEventHandler, pSettingsStore, pInterface, iID, szName) {
}
-bool CStylusFilter::Timer(int iTime, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted)
+bool CStylusFilter::Timer(int iTime, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol)
{
if (GetBoolParameter(BP_DASHER_PAUSED))
{
@@ -19,7 +19,7 @@ bool CStylusFilter::Timer(int iTime, CDasherView *pView, CDasherModel *pModel, D
//however, given we're paused, this is only the Start Handler,
//which we're not using anyway.
}
- return CDefaultFilter::Timer(iTime, pView, pModel, pAdded, pNumDeleted);
+ return CDefaultFilter::Timer(iTime, pView, pModel, pAdded, pNumDeleted, pol);
}
void CStylusFilter::KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog) {
diff --git a/Src/DasherCore/StylusFilter.h b/Src/DasherCore/StylusFilter.h
index adc9e0a..8b9ea79 100644
--- a/Src/DasherCore/StylusFilter.h
+++ b/Src/DasherCore/StylusFilter.h
@@ -10,7 +10,7 @@ class CStylusFilter : public CDefaultFilter {
public:
CStylusFilter(Dasher::CEventHandler * pEventHandler, CSettingsStore *pSettingsStore, CDasherInterfaceBase *pInterface, ModuleID_t iID, const char *szName);
- virtual bool Timer(int Time, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool Timer(int Time, CDasherView *pView, CDasherModel *pModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void KeyDown(int iTime, int iId, CDasherView *pView, CDasherModel *pModel, CUserLogBase *pUserLog);
virtual void KeyUp(int iTime, int iId, CDasherView *pView, CDasherModel *pModel);
private:
diff --git a/Src/DasherCore/TwoButtonDynamicFilter.cpp b/Src/DasherCore/TwoButtonDynamicFilter.cpp
index da1bc2a..9607d23 100644
--- a/Src/DasherCore/TwoButtonDynamicFilter.cpp
+++ b/Src/DasherCore/TwoButtonDynamicFilter.cpp
@@ -111,9 +111,9 @@ void CTwoButtonDynamicFilter::KeyUp(int Time, int iId, CDasherView *pDasherView,
CInputFilter::KeyUp(Time, iId, pDasherView, pModel, bPos, iX, iY);
}
-
-bool CTwoButtonDynamicFilter::TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted) {
- return m_pDasherModel->OneStepTowards(100,2048, Time, pAdded, pNumDeleted);
+bool CTwoButtonDynamicFilter::TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol) {
+ m_pDasherModel->OneStepTowards(100,2048, Time, pAdded, pNumDeleted);
+ return true;
}
void CTwoButtonDynamicFilter::Activate() {
diff --git a/Src/DasherCore/TwoButtonDynamicFilter.h b/Src/DasherCore/TwoButtonDynamicFilter.h
index aca5a80..8a62103 100644
--- a/Src/DasherCore/TwoButtonDynamicFilter.h
+++ b/Src/DasherCore/TwoButtonDynamicFilter.h
@@ -55,7 +55,7 @@ class CTwoButtonDynamicFilter : public CButtonMultiPress {
private:
unsigned int maxClickCount() {return GetBoolParameter(BP_2B_INVERT_DOUBLE) ? 3 : 2;}
- virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void ActionButton(int iTime, int iButton, int iType, CDasherModel *pModel, CUserLogBase *pUserLog);
double m_dLagMul;
diff --git a/Src/DasherCore/TwoPushDynamicFilter.cpp b/Src/DasherCore/TwoPushDynamicFilter.cpp
index 6e739c9..0db4494 100644
--- a/Src/DasherCore/TwoPushDynamicFilter.cpp
+++ b/Src/DasherCore/TwoPushDynamicFilter.cpp
@@ -211,7 +211,7 @@ bool doSet(int &var, const int val)
return true;
}
-bool CTwoPushDynamicFilter::TimerImpl(int iTime, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted)
+bool CTwoPushDynamicFilter::TimerImpl(int iTime, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol)
{
DASHER_ASSERT(isRunning());
if (m_dNatsSinceFirstPush > -std::numeric_limits<double>::infinity()) // first button has been pushed
@@ -247,7 +247,8 @@ bool CTwoPushDynamicFilter::TimerImpl(int iTime, CDasherView *m_pDasherView, CDa
m_bDecorationChanged |= doSet(m_iActiveMarker, 1 /*down*/);
else m_bDecorationChanged |= doSet(m_iActiveMarker, -1 /*in middle (neither/both) or too short*/);
}
- return m_pDasherModel->OneStepTowards(100, 2048, iTime, pAdded, pNumDeleted);
+ m_pDasherModel->OneStepTowards(100, 2048, iTime, pAdded, pNumDeleted);
+ return true;
}
void CTwoPushDynamicFilter::Activate() {
diff --git a/Src/DasherCore/TwoPushDynamicFilter.h b/Src/DasherCore/TwoPushDynamicFilter.h
index e6db1c3..4682343 100644
--- a/Src/DasherCore/TwoPushDynamicFilter.h
+++ b/Src/DasherCore/TwoPushDynamicFilter.h
@@ -42,7 +42,7 @@ class CTwoPushDynamicFilter : public CDynamicFilter /*long push, but do our own
virtual void KeyUp(int Time, int iId, CDasherView *pDasherView, CDasherModel *pModel, bool bPos, int iX, int iY);
protected:
- virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted);
+ virtual bool TimerImpl(int Time, CDasherView *m_pDasherView, CDasherModel *m_pDasherModel, Dasher::VECTOR_SYMBOL_PROB *pAdded, int *pNumDeleted, CExpansionPolicy **pol);
virtual void ActionButton(int iTime, int iButton, int iType, CDasherModel *pModel, CUserLogBase *pUserLog);
virtual void HandleEvent(Dasher::CEvent * pEvent);
diff --git a/Src/MacOSX/Dasher.xcodeproj/project.pbxproj b/Src/MacOSX/Dasher.xcodeproj/project.pbxproj
index 230e8eb..bb22718 100755
--- a/Src/MacOSX/Dasher.xcodeproj/project.pbxproj
+++ b/Src/MacOSX/Dasher.xcodeproj/project.pbxproj
@@ -346,6 +346,8 @@
19F8C7E60C858A2800276B4F /* I18n.h in Headers */ = {isa = PBXBuildFile; fileRef = 19F8C7E50C858A2800276B4F /* I18n.h */; };
19F8C7F90C858E9900276B4F /* TrainingHelper.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 19F8C7F70C858E9900276B4F /* TrainingHelper.cpp */; };
19F8C7FA0C858E9900276B4F /* TrainingHelper.h in Headers */ = {isa = PBXBuildFile; fileRef = 19F8C7F80C858E9900276B4F /* TrainingHelper.h */; };
+ 3300115210A2EA7700D31B1D /* ExpansionPolicy.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 3300115010A2EA7700D31B1D /* ExpansionPolicy.cpp */; };
+ 3300115310A2EA7700D31B1D /* ExpansionPolicy.h in Headers */ = {isa = PBXBuildFile; fileRef = 3300115110A2EA7700D31B1D /* ExpansionPolicy.h */; };
3306E0220FFD1CE60017324C /* PPMPYLanguageModel.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 3306E0200FFD1CE60017324C /* PPMPYLanguageModel.cpp */; };
3306E0230FFD1CE60017324C /* PPMPYLanguageModel.h in Headers */ = {isa = PBXBuildFile; fileRef = 3306E0210FFD1CE60017324C /* PPMPYLanguageModel.h */; };
3306E1F70FFE6CAD0017324C /* Trainer.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 3306E1F50FFE6CAD0017324C /* Trainer.cpp */; };
@@ -362,7 +364,6 @@
335DB0FB100B332C006DB155 /* alphabet.spyDict.xml in Resources */ = {isa = PBXBuildFile; fileRef = 335DB0FA100B332C006DB155 /* alphabet.spyDict.xml */; };
335DB101100B3358006DB155 /* training_spyDict.txt in Resources */ = {isa = PBXBuildFile; fileRef = 335DB100100B3358006DB155 /* training_spyDict.txt */; };
335DB122100B3606006DB155 /* PinYinConversionHelper.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1948BE760C226CFD001DFA32 /* PinYinConversionHelper.cpp */; };
- 336C2D13101A31EE00CCD70D /* NodeQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 336C2D12101A31EE00CCD70D /* NodeQueue.h */; };
33ABFEC60FC379EA00EA2BA5 /* ButtonMultiPress.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 33ABFEC40FC379EA00EA2BA5 /* ButtonMultiPress.cpp */; };
33ABFEC70FC379EA00EA2BA5 /* ButtonMultiPress.h in Headers */ = {isa = PBXBuildFile; fileRef = 33ABFEC50FC379EA00EA2BA5 /* ButtonMultiPress.h */; };
33E173C70F3E0B6400D19B38 /* Makefile.am in Resources */ = {isa = PBXBuildFile; fileRef = 33E173A70F3E0B6400D19B38 /* Makefile.am */; };
@@ -764,6 +765,8 @@
29B97319FDCFA39411CA2CEA /* English */ = {isa = PBXFileReference; lastKnownFileType = wrapper.nib; name = English; path = English.lproj/MainMenu.nib; sourceTree = "<group>"; };
29B97324FDCFA39411CA2CEA /* AppKit.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = AppKit.framework; path = /System/Library/Frameworks/AppKit.framework; sourceTree = "<absolute>"; };
29B97325FDCFA39411CA2CEA /* Foundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Foundation.framework; path = /System/Library/Frameworks/Foundation.framework; sourceTree = "<absolute>"; };
+ 3300115010A2EA7700D31B1D /* ExpansionPolicy.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ExpansionPolicy.cpp; sourceTree = "<group>"; };
+ 3300115110A2EA7700D31B1D /* ExpansionPolicy.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ExpansionPolicy.h; sourceTree = "<group>"; };
3306E0200FFD1CE60017324C /* PPMPYLanguageModel.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PPMPYLanguageModel.cpp; sourceTree = "<group>"; };
3306E0210FFD1CE60017324C /* PPMPYLanguageModel.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PPMPYLanguageModel.h; sourceTree = "<group>"; };
3306E1F50FFE6CAD0017324C /* Trainer.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Trainer.cpp; sourceTree = "<group>"; };
@@ -779,7 +782,6 @@
335901B31009E5A900821255 /* ConversionHelper.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ConversionHelper.cpp; sourceTree = "<group>"; };
335DB0FA100B332C006DB155 /* alphabet.spyDict.xml */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.xml; path = alphabet.spyDict.xml; sourceTree = "<group>"; };
335DB100100B3358006DB155 /* training_spyDict.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = training_spyDict.txt; sourceTree = "<group>"; };
- 336C2D12101A31EE00CCD70D /* NodeQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NodeQueue.h; sourceTree = "<group>"; };
33ABFEC40FC379EA00EA2BA5 /* ButtonMultiPress.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ButtonMultiPress.cpp; sourceTree = "<group>"; };
33ABFEC50FC379EA00EA2BA5 /* ButtonMultiPress.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ButtonMultiPress.h; sourceTree = "<group>"; };
33E173A70F3E0B6400D19B38 /* Makefile.am */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = Makefile.am; sourceTree = "<group>"; };
@@ -923,7 +925,6 @@
3313534C102C6D8E00E28220 /* CompassMode.h */,
3313534D102C6D8E00E28220 /* ButtonMode.cpp */,
3313534E102C6D8E00E28220 /* ButtonMode.h */,
- 336C2D12101A31EE00CCD70D /* NodeQueue.h */,
3306E1F50FFE6CAD0017324C /* Trainer.cpp */,
3306E1F60FFE6CAD0017324C /* Trainer.h */,
33FC93420FEFA2FB00A9F08D /* FrameRate.cpp */,
@@ -986,6 +987,8 @@
1948BE3B0C226CFD001DFA32 /* DefaultFilter.cpp */,
1948BE3C0C226CFD001DFA32 /* DefaultFilter.h */,
1948BE3D0C226CFD001DFA32 /* DelayedDraw.cpp */,
+ 3300115010A2EA7700D31B1D /* ExpansionPolicy.cpp */,
+ 3300115110A2EA7700D31B1D /* ExpansionPolicy.h */,
1948BE3E0C226CFD001DFA32 /* DynamicFilter.cpp */,
1948BE3F0C226CFD001DFA32 /* DynamicFilter.h */,
1948BE400C226CFD001DFA32 /* Event.h */,
@@ -1504,10 +1507,10 @@
3306E0230FFD1CE60017324C /* PPMPYLanguageModel.h in Headers */,
3306E1F80FFE6CAD0017324C /* Trainer.h in Headers */,
3306E33E0FFFB9880017324C /* MandarinAlphMgr.h in Headers */,
- 336C2D13101A31EE00CCD70D /* NodeQueue.h in Headers */,
33135352102C6D8E00E28220 /* AlternatingDirectMode.h in Headers */,
33135354102C6D8E00E28220 /* CompassMode.h in Headers */,
33135356102C6D8E00E28220 /* ButtonMode.h in Headers */,
+ 3300115310A2EA7700D31B1D /* ExpansionPolicy.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -1856,6 +1859,7 @@
33135351102C6D8E00E28220 /* AlternatingDirectMode.cpp in Sources */,
33135353102C6D8E00E28220 /* CompassMode.cpp in Sources */,
33135355102C6D8E00E28220 /* ButtonMode.cpp in Sources */,
+ 3300115210A2EA7700D31B1D /* ExpansionPolicy.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]