Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  
Public Types | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes

SgNode Class Reference

Node in tree. More...

#include <SgNode.h>

List of all members.

Public Types

enum  Direction {
  PREVIOUS, NEXT, NEXT_RIGHTMOST, PREV_DEPTHFIRST,
  NEXT_DEPTHFIRST, PREV_TERMINAL, NEXT_TERMINAL, PREV_BRANCH,
  NEXT_BRANCH, LEFT_BROTHER, RIGHT_BROTHER, MAIN_BRANCH,
  START_OF_GAME, END_OF_GAME
}

Public Member Functions

 SgNode ()
 ~SgNode ()
SgNodeCopyTree () const
 Return a newly allocated copy of this node and its subtree.
SgVector< SgPointVectorProp (SgPropID prop) const
bool HasFather () const
bool IsRoot () const
bool HasLeftBrother () const
bool HasRightBrother () const
bool HasSon () const
bool HasBrother () const
 HasLeftBrother(node) OR HasRightBrother(node).
bool IsOnMain () const
 True of the node is on the main branch of the tree, that is none of its ancestors has a left brother.
bool IsTerminal () const
 NOT HasSon(node).
bool IsBranchPoint () const
 NumSons(node) >= 2.
int NumSons () const
int NumLeftBrothers () const
SgNodeRoot () const
SgNodeFather () const
SgNodeLeftBrother () const
SgNodeRightBrother () const
SgNodeLeftMostSon () const
SgNodeRightMostSon () const
SgNodeNextDepthFirst () const
 Depth-first traversal of the tree.
SgNodePrevDepthFirst () const
 Inverse operation of NextDepthFirst.
SgNodeNodeInDirection (Direction dir) const
 Return the next node in the given direction.
bool ContainsText (const std::string &findText)
 Return whether this node contains a property that matches the given text.
void PathToRoot (SgVectorOf< SgNode > *path) const
 Returns all nodes on path from this node up to the root.
void ShortestPathTo (SgNode *node, int *numBack, SgVectorOf< SgNode > *path) const
 Find the closest common ancestor of the two nodes.
void PromoteNode ()
 Promote this node to first son.
void PromotePath ()
 The tree above this node is changed such that this node is on the main path.
void DeleteSubtree ()
 Deletes all nodes below this node, but not this node itself.
void DeleteBranches ()
 Deletes everything below the current node except the main branch.
void DeleteTree ()
 Deletes the tree that this node is part of.
SgNodeNewFather ()
SgNodeNewRightBrother ()
SgNodeNewLeftMostSon ()
SgNodeNewRightMostSon ()
 Insert a node at the appropriate place in the tree.
void AppendTo (SgNode *n)
 Append this tree to '*n'.
SgPropListProps ()
const SgPropListProps () const
void Add (const SgProp *prop)
SgPropGet (SgPropID id) const
bool HasProp (SgPropID id) const
 HasProp also handles abstract node properties like SG_PROP_TERMINAL and SG_PROP_BRANCH, while Get only returns real properties.
bool HasNodeMove () const
 has SG_PROP_MOVE_BLACK or SG_PROP_MOVE_WHITE
SgBlackWhite NodePlayer () const
 Player of move.
SgPoint NodeMove () const
SgNodeTopProp (SgPropID id) const
 Return the most recent node that has the given property, starting backwards from this node.
int GetIntProp (SgPropID id) const
 Return the value of the given property at this node.
bool GetIntProp (SgPropID id, int *value) const
 return if property exists.
double GetRealProp (SgPropID id) const
 Value of the given property at this node.
void SetIntProp (SgPropID id, int value)
 Set the value of the given property at this node to 'value'.
void SetRealProp (SgPropID id, double value, int precision=0)
 Set the value of the given property at this node.
void SetStringProp (SgPropID id, const std::string &value)
 Set the value of the given property at this node to 'value'.
bool GetStringProp (SgPropID id, std::string *value) const
 Return the value of the given property at this node.
void SetListProp (SgPropID id, const SgVector< SgPoint > &value)
 Set the value of the given property at this node to 'value'.
void SetListProp (SgPropID id, const SgPointSet &value)
void AddComment (const std::string &comment)
 Add comment to existing SG_PROP_COMMENT of this node, or create a new SG_PROP_COMMENT with this text.
SgPropCopyPropFrom (const SgNode &sourceNode, SgPropID id)
 If it exists, copy the property with the given 'id' from 'sourceNode' to this node, and return it.
void CopyAllPropsFrom (const SgNode &sourceNode)
 Copy all properties from 'sourceNode' to this node.
SgPropAddMoveProp (SgMove move, SgBlackWhite player)
 Add a move property to this node with 'move' played by 'player'.
SgBlackWhite Player () const
 Return the player, if explicitely set.
int CountNodes (bool fSetPropOnThisNode)
 Count the nodes in this subtree and sets SG_PROP_NUM_NODES for each interior node in the subtree that has at least two sons, plus for this node if 'fSetPropOnThisNode' is set.

Static Public Member Functions

static SgNodeLinkTrees (const SgVectorOf< SgNode > &roots)
 Add a new node and add all trees in 'roots' as subtrees of that node.
static void CopySubtree (const SgNode *node, SgNode *copy)
static void GetStatistics (int *numAlloc, int *numUsed)
 Total number of nodes allocated, still in use.
static void MemCheck ()
static std::string TreeIndex (const SgNode *node)
 Location of node in tree.

Private Member Functions

void LinkWithBrother (SgNode *node)
void Mark ()
void Unmark ()
bool IsMarked () const
 SgNode (const SgNode &)
 Not implemented.
SgNodeoperator= (const SgNode &)
 Not implemented.

Private Attributes

SgNodem_son
SgNodem_father
SgNodem_brother
SgPropList m_props
bool m_marked

Static Private Attributes

static int s_alloc = 0
static int s_free = 0

Detailed Description

Node in tree.

Procedures for moving around in the tree return 0 if the desti- nation doesn't exist. References to "left" and "right" picture the tree with the root at the top and the main line of play going down the left side.

Definition at line 40 of file SgNode.h.


Member Enumeration Documentation

Enumerator:
PREVIOUS 
NEXT 
NEXT_RIGHTMOST 
PREV_DEPTHFIRST 
NEXT_DEPTHFIRST 
PREV_TERMINAL 
NEXT_TERMINAL 
PREV_BRANCH 
NEXT_BRANCH 
LEFT_BROTHER 
RIGHT_BROTHER 
MAIN_BRANCH 
START_OF_GAME 
END_OF_GAME 

Definition at line 43 of file SgNode.h.


Constructor & Destructor Documentation

SgNode::SgNode (  ) 

Definition at line 26 of file SgNode.cpp.

References s_alloc.

Referenced by CopyTree(), LinkTrees(), NewFather(), NewLeftMostSon(), and NewRightBrother().

SgNode::~SgNode (  ) 
SgNode::SgNode ( const SgNode  )  [private]

Not implemented.


Member Function Documentation

void SgNode::Add ( const SgProp prop  ) 
void SgNode::AddComment ( const std::string &  comment  ) 

Add comment to existing SG_PROP_COMMENT of this node, or create a new SG_PROP_COMMENT with this text.

Definition at line 322 of file SgNode.cpp.

References Add(), SgPropText::AppendText(), Get(), and SG_PROP_COMMENT.

Referenced by SgSearchTracer::StartOfDepth(), and SgSearchTracer::TraceComment().

SgProp * SgNode::AddMoveProp ( SgMove  move,
SgBlackWhite  player 
)

Add a move property to this node with 'move' played by 'player'.

Returns:
the property added.
Warning:
Only for games which use SgMoveProp
Todo:
Too game dependent for a member of SgNode, move somewhere else

Definition at line 698 of file SgNode.cpp.

References Add(), SG_ASSERT_BW, SG_BLACK, SG_PROP_MOVE_BLACK, and SG_PROP_MOVE_WHITE.

Referenced by SgSearchTracer::AddMoveProp().

void SgNode::AppendTo ( SgNode n  ) 

Append this tree to '*n'.

Definition at line 529 of file SgNode.cpp.

References HasBrother(), HasFather(), HasSon(), m_brother, m_father, m_son, RightMostSon(), and SG_ASSERT.

Referenced by SgSearchTracer::AppendTrace().

bool SgNode::ContainsText ( const std::string &  findText  ) 

Return whether this node contains a property that matches the given text.

Doesn't handle text representing special properties.

Definition at line 314 of file SgNode.cpp.

References SgProp::ConvertFindTextToPropID(), SgPropList::GetPropContainingText(), m_props, SG_ASSERT, and SG_PROP_NONE.

void SgNode::CopyAllPropsFrom ( const SgNode sourceNode  ) 

Copy all properties from 'sourceNode' to this node.

Definition at line 676 of file SgNode.cpp.

References Add(), and Props().

Referenced by CopySubtree(), and CopyTree().

SgProp * SgNode::CopyPropFrom ( const SgNode sourceNode,
SgPropID  id 
)

If it exists, copy the property with the given 'id' from 'sourceNode' to this node, and return it.

If the property doesn't exist, return 0.

Definition at line 685 of file SgNode.cpp.

References Add(), SgProp::Duplicate(), and Get().

void SgNode::CopySubtree ( const SgNode node,
SgNode copy 
) [static]

Definition at line 75 of file SgNode.cpp.

References CopyAllPropsFrom(), LeftMostSon(), NewRightMostSon(), and RightBrother().

Referenced by CopyTree().

SgNode * SgNode::CopyTree (  )  const

Return a newly allocated copy of this node and its subtree.

Definition at line 86 of file SgNode.cpp.

References CopyAllPropsFrom(), CopySubtree(), and SgNode().

int SgNode::CountNodes ( bool  fSetPropOnThisNode  ) 

Count the nodes in this subtree and sets SG_PROP_NUM_NODES for each interior node in the subtree that has at least two sons, plus for this node if 'fSetPropOnThisNode' is set.

Return the number of nodes in the subtree, including this node.

Definition at line 714 of file SgNode.cpp.

References IsBranchPoint(), SetIntProp(), and SG_PROP_NUM_NODES.

void SgNode::DeleteBranches (  ) 

Deletes everything below the current node except the main branch.

Definition at line 443 of file SgNode.cpp.

References DeleteSubtree(), LeftMostSon(), and RightBrother().

void SgNode::DeleteSubtree (  ) 

Deletes all nodes below this node, but not this node itself.

Definition at line 435 of file SgNode.cpp.

References HasSon(), and LeftMostSon().

Referenced by DeleteBranches(), and DeleteTree().

void SgNode::DeleteTree (  ) 

Deletes the tree that this node is part of.

Same as:

        SgNode* root = Root();
        root->DeleteSubtree();
        delete root;
        

Definition at line 460 of file SgNode.cpp.

References DeleteSubtree(), and Root().

SgNode* SgNode::Father (  )  const
SgProp* SgNode::Get ( SgPropID  id  )  const
int SgNode::GetIntProp ( SgPropID  id  )  const

Return the value of the given property at this node.

Or 0 if there is no such property. The property must be of class SgPropInt (or a derived class).

Definition at line 553 of file SgNode.cpp.

References Get(), and SgPropInt::Value().

Referenced by SgTimeRecord::GetOTMovesFromTree(), SgGameWriter::HandleProps(), NodeMove(), SgNodeUtil::UpdateTime(), and SgGameWriter::WriteGame().

bool SgNode::GetIntProp ( SgPropID  id,
int *  value 
) const

return if property exists.

If true, return its value in *value

Definition at line 562 of file SgNode.cpp.

References Get(), and SgPropInt::Value().

double SgNode::GetRealProp ( SgPropID  id  )  const

Value of the given property at this node.

Returns 0 if there is no such property. The property must be of class SgPropReal.

Definition at line 597 of file SgNode.cpp.

References Get(), and SgPropReal::Value().

Referenced by SgTimeRecord::GetTimeFromTree(), and SgNodeUtil::UpdateTime().

void SgNode::GetStatistics ( int *  numAlloc,
int *  numUsed 
) [static]

Total number of nodes allocated, still in use.

Definition at line 730 of file SgNode.cpp.

References s_alloc, and s_free.

bool SgNode::GetStringProp ( SgPropID  id,
std::string *  value 
) const

Return the value of the given property at this node.

Or 0 if there is no such property. The property must be of class SgPropText (or a derived class).

Definition at line 632 of file SgNode.cpp.

References Get(), and SgPropText::Value().

bool SgNode::HasBrother (  )  const

HasLeftBrother(node) OR HasRightBrother(node).

Definition at line 95 of file SgNode.h.

References HasLeftBrother(), and HasRightBrother().

Referenced by AppendTo(), and NodeInDirection().

bool SgNode::HasFather (  )  const
bool SgNode::HasLeftBrother (  )  const
bool SgNode::HasNodeMove (  )  const

has SG_PROP_MOVE_BLACK or SG_PROP_MOVE_WHITE

Definition at line 573 of file SgNode.cpp.

References HasProp(), SG_PROP_MOVE_BLACK, and SG_PROP_MOVE_WHITE.

Referenced by NodePlayer().

bool SgNode::HasProp ( SgPropID  id  )  const

HasProp also handles abstract node properties like SG_PROP_TERMINAL and SG_PROP_BRANCH, while Get only returns real properties.

Definition at line 334 of file SgNode.cpp.

References Get(), IsBranchPoint(), IsTerminal(), SG_PROP_BRANCH, and SG_PROP_TERMINAL.

Referenced by SgNodeUtil::GetMoveNumber(), HasNodeMove(), NodePlayer(), SgNodeUtil::UpdateTime(), SgGameWriter::WriteGame(), and SgGameWriter::WriteNode().

bool SgNode::HasRightBrother (  )  const
bool SgNode::HasSon (  )  const
bool SgNode::IsBranchPoint (  )  const

NumSons(node) >= 2.

Definition at line 111 of file SgNode.h.

References m_brother, and m_son.

Referenced by CountNodes(), HasProp(), and NodeInDirection().

bool SgNode::IsMarked (  )  const [private]

Definition at line 371 of file SgNode.h.

References m_marked.

Referenced by ShortestPathTo().

bool SgNode::IsOnMain (  )  const

True of the node is on the main branch of the tree, that is none of its ancestors has a left brother.

Definition at line 102 of file SgNode.cpp.

References m_father, and m_son.

bool SgNode::IsRoot (  )  const

Definition at line 77 of file SgNode.h.

References m_father.

bool SgNode::IsTerminal (  )  const

NOT HasSon(node).

Definition at line 105 of file SgNode.h.

References m_son.

Referenced by HasProp(), and NodeInDirection().

SgNode * SgNode::LeftBrother (  )  const
SgNode* SgNode::LeftMostSon (  )  const
SgNode * SgNode::LinkTrees ( const SgVectorOf< SgNode > &  roots  )  [static]

Add a new node and add all trees in 'roots' as subtrees of that node.

Definition at line 511 of file SgNode.cpp.

References HasFather(), m_brother, m_father, m_son, SG_ASSERT, and SgNode().

void SgNode::LinkWithBrother ( SgNode node  )  [private]

Definition at line 120 of file SgNode.cpp.

References HasRightBrother(), m_brother, m_father, and RightBrother().

Referenced by ~SgNode().

void SgNode::Mark (  )  [private]

Definition at line 361 of file SgNode.h.

References m_marked.

Referenced by ShortestPathTo().

void SgNode::MemCheck (  )  [static]

Definition at line 737 of file SgNode.cpp.

References s_alloc, s_free, and SG_ASSERT.

Referenced by SgMemCheck().

SgNode * SgNode::NewFather (  ) 

Definition at line 467 of file SgNode.cpp.

References HasLeftBrother(), LeftBrother(), m_brother, m_father, m_son, and SgNode().

SgNode * SgNode::NewLeftMostSon (  ) 

Definition at line 494 of file SgNode.cpp.

References m_brother, m_father, m_son, and SgNode().

Referenced by NewRightMostSon().

SgNode * SgNode::NewRightBrother (  ) 

Definition at line 485 of file SgNode.cpp.

References m_brother, m_father, and SgNode().

Referenced by NewRightMostSon().

SgNode * SgNode::NewRightMostSon (  ) 

Insert a node at the appropriate place in the tree.

Definition at line 503 of file SgNode.cpp.

References HasSon(), NewLeftMostSon(), NewRightBrother(), and RightMostSon().

Referenced by SgSearchTracer::AddTraceNode(), CopySubtree(), SgGameReader::ReadSubtree(), and SgSearchTracer::StartOfDepth().

SgNode * SgNode::NextDepthFirst (  )  const

Depth-first traversal of the tree.

Definition at line 199 of file SgNode.cpp.

References Father(), HasFather(), HasRightBrother(), HasSon(), LeftMostSon(), and RightBrother().

Referenced by SgNodeConstIterator::Next(), SgNodeIterator::Next(), and NodeInDirection().

SgNode * SgNode::NodeInDirection ( Direction  dir  )  const
SgPoint SgNode::NodeMove (  )  const

Definition at line 586 of file SgNode.cpp.

References GetIntProp(), SG_NULLMOVE, SG_PROP_MOVE_BLACK, and SG_PROP_MOVE_WHITE.

SgBlackWhite SgNode::NodePlayer (  )  const

Player of move.

REQUIRES: HasNodeMove()

Definition at line 578 of file SgNode.cpp.

References HasNodeMove(), HasProp(), SG_ASSERT, SG_BLACK, SG_PROP_MOVE_BLACK, and SG_WHITE.

int SgNode::NumLeftBrothers (  )  const

Definition at line 154 of file SgNode.cpp.

References Father(), LeftMostSon(), and RightBrother().

int SgNode::NumSons (  )  const

Definition at line 138 of file SgNode.cpp.

References HasRightBrother(), HasSon(), LeftMostSon(), and RightBrother().

SgNode& SgNode::operator= ( const SgNode  )  [private]

Not implemented.

void SgNode::PathToRoot ( SgVectorOf< SgNode > *  path  )  const

Returns all nodes on path from this node up to the root.

Definition at line 229 of file SgNode.cpp.

References SgVector< void * >::Clear(), and SgVectorOf< T >::PushBack().

SgBlackWhite SgNode::Player (  )  const

Return the player, if explicitely set.

REQUIRES: Get(SG_PROP_PLAYER)

Definition at line 708 of file SgNode.cpp.

References Get(), SG_ASSERT, and SG_PROP_PLAYER.

SgNode * SgNode::PrevDepthFirst (  )  const

Inverse operation of NextDepthFirst.

Definition at line 214 of file SgNode.cpp.

References Father(), HasFather(), HasLeftBrother(), HasSon(), LeftBrother(), and RightMostSon().

Referenced by NodeInDirection().

void SgNode::PromoteNode (  ) 

Promote this node to first son.

Moves all its left brothers one position to the right.

Definition at line 411 of file SgNode.cpp.

References HasLeftBrother(), m_brother, m_father, and m_son.

Referenced by PromotePath().

void SgNode::PromotePath (  ) 

The tree above this node is changed such that this node is on the main path.

(first in depth-first search).

Definition at line 425 of file SgNode.cpp.

References Father(), and PromoteNode().

SgPropList& SgNode::Props (  ) 

Definition at line 206 of file SgNode.h.

References m_props.

Referenced by CopyAllPropsFrom(), SgNodeUtil::RemovePropInSubtree(), and SgGameWriter::WriteNode().

const SgPropList& SgNode::Props (  )  const

Definition at line 211 of file SgNode.h.

References m_props.

SgNode* SgNode::RightBrother (  )  const
SgNode * SgNode::RightMostSon (  )  const

Definition at line 188 of file SgNode.cpp.

References HasRightBrother(), LeftMostSon(), and RightBrother().

Referenced by AppendTo(), NewRightMostSon(), NodeInDirection(), and PrevDepthFirst().

SgNode * SgNode::Root (  )  const

Definition at line 170 of file SgNode.cpp.

References Father(), and HasFather().

Referenced by SgSearchTracer::AppendTrace(), DeleteTree(), NodeInDirection(), and SgGameReader::ReadGame().

void SgNode::SetIntProp ( SgPropID  id,
int  value 
)

Set the value of the given property at this node to 'value'.

Create such a property if it doesn't exist yet. The property must be of class SgPropInt (or a derived class).

Definition at line 606 of file SgNode.cpp.

References Add(), SgProp::CreateProperty(), Get(), and SgPropInt::SetValue().

Referenced by CountNodes(), SgTimeRecord::PlayedMove(), and SgSearchTracer::StartOfDepth().

void SgNode::SetListProp ( SgPropID  id,
const SgPointSet value 
)

Definition at line 669 of file SgNode.cpp.

References SetListProp(), and SgPointSet::ToVector().

void SgNode::SetListProp ( SgPropID  id,
const SgVector< SgPoint > &  value 
)

Set the value of the given property at this node to 'value'.

Create such a property if it doesn't exist yet. The property must be of class SgPropPointList (or a derived class).

Definition at line 656 of file SgNode.cpp.

References Add(), SgProp::CreateProperty(), Get(), and SgPropPointList::SetValue().

Referenced by SetListProp().

void SgNode::SetRealProp ( SgPropID  id,
double  value,
int  precision = 0 
)

Set the value of the given property at this node.

Create such a property if it doesn't exist yet. The property must be of class SgPropReal.

Parameters:
id 
value 
precision Precision; 0 means default precision (6)

Definition at line 619 of file SgNode.cpp.

References Add(), SgProp::CreateProperty(), Get(), and SgPropReal::SetValue().

Referenced by SgTimeRecord::PlayedMove(), SgTimeRecord::SetClock(), and SgTimeRecord::SetTimeInTree().

void SgNode::SetStringProp ( SgPropID  id,
const std::string &  value 
)

Set the value of the given property at this node to 'value'.

Create such a property if it doesn't exist yet. The property must be of class SgPropText (or a derived class).

Definition at line 643 of file SgNode.cpp.

References Add(), SgProp::CreateProperty(), Get(), and SgPropText::SetValue().

void SgNode::ShortestPathTo ( SgNode node,
int *  numBack,
SgVectorOf< SgNode > *  path 
) const

Find the closest common ancestor of the two nodes.

Returns the path from this node to 'node': how many times to go one node back, and a vector of the nodes to execute from there (excluding the common ancestor).

Definition at line 347 of file SgNode.cpp.

References SgVector< void * >::Clear(), IsMarked(), m_father, Mark(), SgVectorOf< T >::PushBack(), SgVector< void * >::Reverse(), SG_ASSERT, and Unmark().

SgNode * SgNode::TopProp ( SgPropID  id  )  const

Return the most recent node that has the given property, starting backwards from this node.

Return this node if it has the wanted property; return the root of the tree if no node with that property was found.

Definition at line 544 of file SgNode.cpp.

References Father(), Get(), and HasFather().

Referenced by SgTimeRecord::GetOTMovesFromTree(), and SgTimeRecord::GetTimeFromTree().

string SgNode::TreeIndex ( const SgNode node  )  [static]

Location of node in tree.

This function builds a unique string from the location of a node in the tree. It is a list of integers separated by dots, each integer represents the child index (counting from 1) for each node in the path from the root to the given node. For example

        root -- node1 -- node2
             |
             +- node3

        root  "1"
        node1 "1.1"
        node2 "1.1.1"
        node3 "1.2"
        

A null node pointer has the TreeIndex "NIL".

Definition at line 742 of file SgNode.cpp.

References Father(), LeftMostSon(), RightBrother(), and SG_ASSERT.

void SgNode::Unmark (  )  [private]

Definition at line 366 of file SgNode.h.

References m_marked.

Referenced by ShortestPathTo().

SgVector< SgPoint > SgNode::VectorProp ( SgPropID  prop  )  const
Todo:
: distinguish SgVector<SgPoint>, SgVector<int> etc.

Definition at line 130 of file SgNode.cpp.

References Get(), and SgPropPointList::Value().


Member Data Documentation

bool SgNode::m_marked [private]

Definition at line 357 of file SgNode.h.

Referenced by IsMarked(), Mark(), and Unmark().

Definition at line 355 of file SgNode.h.

Referenced by Add(), ContainsText(), Get(), and Props().

SgNode* SgNode::m_son [private]
int SgNode::s_alloc = 0 [static, private]

Definition at line 383 of file SgNode.h.

Referenced by GetStatistics(), MemCheck(), and SgNode().

int SgNode::s_free = 0 [static, private]

Definition at line 385 of file SgNode.h.

Referenced by GetStatistics(), MemCheck(), and ~SgNode().


The documentation for this class was generated from the following files:


Sun Mar 13 2011 Doxygen 1.7.1