RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/tree__algo_8hpp_source.html below:

NCBI C++ ToolKit: include/algo/tree/tree_algo.hpp Source File

1 #ifndef ALGO___TREE__ALGO_HPP 2 #define ALGO___TREE__ALGO_HPP 61 template

class

TTreeNode,

class

TCompFun>

62 bool TreeCompare

(

const

TTreeNode& tree1,

const

TTreeNode& tree2, TCompFun func)

65 const

TTreeNode* t1 = &tree1;

66 const

TTreeNode* t2 = &tree2;

67 if

(!func(t1->GetValue(), t2->GetValue()))

69 if

(t1->IsLeaf() && t2->IsLeaf())

72 typedef typename

TTreeNode::TNodeList_CI CTreeNodeIterator;

74

CTreeNodeIterator it1 = t1->SubNodeBegin();

75

CTreeNodeIterator it1_end = t1->SubNodeEnd();

76

CTreeNodeIterator it2 = t2->SubNodeBegin();

77

CTreeNodeIterator it2_end = t2->SubNodeEnd();

79

queue<CTreeNodeIterator> t1_queue;

80

queue<CTreeNodeIterator> t2_queue;

85 while

(it1 != it1_end) {

90 while

(it2 != it2_end) {

96 if

(children1 != children2)

100 while

(!t1_queue.empty() && !t2_queue.empty()) {

103

it1 = t1_queue.front();

105

it2 = t2_queue.front();

112 if

(!func(t1->GetValue(), t2->GetValue()))

117

it1 = t1->SubNodeBegin();

118

it1_end = t1->SubNodeEnd();

119 while

(it1 != it1_end) {

120

t1_queue.push(it1++);

126

it2 = t2->SubNodeBegin();

127

it2_end = t2->SubNodeEnd();

128 while

(it2 != it2_end) {

129

t2_queue.push(it2++);

133 if

(children1 != children2)

140 if

(t1_queue.empty() && t2_queue.empty())

155 template

class

TTreeNode,

class

TFunc>

158 bool

skip_self =

false

)

160 const

TTreeNode* node_ptr = &tree_node;

162

node_ptr = node_ptr->GetParent();

164 for

( ;node_ptr; node_ptr = node_ptr->GetParent()) {

174 template

class

TTreeNode,

class

TTraceContainer>

204 template

class

TTreeNode,

class

TTraceContainer>

216 template

class

TTreeNode>

219

vector<const TTreeNode*>

trace

;

221

TTreeNode* local_root = &new_root_node;

222 ITERATE

(

typename

vector<const TTreeNode*>, it,

trace

) {

223

TTreeNode* node =

const_cast<

TTreeNode*

>

(*it);

224

TTreeNode* parent = node->GetParent();

226

parent->DetachNode(node);

227 if

(local_root != node)

228

local_root->AddNode(node);

243 template

class

TTreeNode>

245 const

TTreeNode& tree_node_b)

247 typedef

vector<const TTreeNode*> TTraceVector;

249

TTraceVector trace_a;

250

TTraceVector trace_b;

257 const

TTreeNode* node_candidate = 0;

264 const

TTraceVector& ctr_a = trace_a;

265 const

TTraceVector& ctr_b = trace_b;

267 typename

TTraceVector::const_reverse_iterator it_a = ctr_a.rbegin();

268 typename

TTraceVector::const_reverse_iterator it_b = ctr_b.rbegin();

270 typename

TTraceVector::const_reverse_iterator it_a_end = ctr_a.rend();

271 typename

TTraceVector::const_reverse_iterator it_b_end = ctr_b.rend();

273 for

(;it_a != it_a_end || it_b != it_b_end; ++it_a, ++it_b) {

274 const

TTreeNode* node_a = *it_a;

275 const

TTreeNode* node_b = *it_b;

277 if

(node_a != node_b) {

280

node_candidate = node_a;

283 return

node_candidate;

289 template

class

TTreeNode,

class

TConverter>

306 const typename

TTreeNode::TValueType& v = tr.GetValue();

307 const string

& node_str =

m_Conv

(v);

311

"["

"0x"

hex

<< &tr <<

"]=> 0x"

<< tr.GetParent()

312

" ( "

<< node_str <<

" ) "

<< endl;

347 template

class

TTreeNode,

class

TConverter>

349 const

TTreeNode& tree_node,

351 bool

print_ptr =

false

)

355

TTreeNode* non_c_tr =

const_cast<

TTreeNode*

>

(&tree_node);

374 template

class

TPairTree,

class

TValue>

376 const

TValue& search_id)

378 const

TPairTree* ptr = &tr;

381 const

TValue& node_value = ptr->GetValue().value;

383 if

(search_id == node_value) {

387 typename

TPairTree::TNodeList_CI it = ptr->SubNodeBegin();

388 typename

TPairTree::TNodeList_CI it_end = ptr->SubNodeEnd();

390 for

(;it != it_end; ++it) {

391 const

TPairTree* node = *it;

392 const typename

TPairTree::TValueType& node_pair = node->GetValue();

394 if

(search_id == node_pair.id) {

400

ptr = ptr->GetParent();

411 template

class

TPairTree,

class

TPathList>

416 const

TPairTree* ptr = &tr;

417 const

TPairTree* pfnd = 0;

419 typename

TPathList::const_iterator last_it = node_path.end();

423 ITERATE

(

typename

TPathList, sit, node_path) {

424 const typename

TPairTree::TKeyType& search_id = *sit;

425 bool

sub_level_found =

false

;

427 typename

TPairTree::TNodeList_CI it = ptr->SubNodeBegin();

428 typename

TPairTree::TNodeList_CI it_end = ptr->SubNodeEnd();

430 for

(;it != it_end; ++it) {

431 const

TPairTree* node = *it;

432 const typename

TPairTree::TValueType& node_pair = node->GetValue();

435 if

(node_pair.id == search_id) {

436

ptr = (TPairTree*) node;

437

sub_level_found =

true

;

440 if

(node_pair.id == last_search_id) {

441

pfnd = (TPairTree*) node;

442

sub_level_found =

true

;

450 if

(!sub_level_found) {

463 template

class

TNodeListIt,

class

TBackInsert>

465

TNodeListIt node_list_last,

466

TBackInsert back_ins)

468 for

(;node_list_first != node_list_last; ++node_list_first)

470 unsigned

uid = (unsigned)(*node_list_first)->GetValue().GetId();

481 template

class

TNodeList,

class

TBackInsert>

484 typename

TNodeList::const_iterator it = node_list.begin();

485 typename

TNodeList::const_iterator it_end = node_list.end();

495 template

class

TTreeNode,

class

TBackInsert>

506 if

(delta_level >= 0) {

525 template

class

TNode,

class

TBackInsert>

540 template

class

TNode,

class

TBackInsert>

543

TNode* node =

const_cast<

TNode*

>

(&tree_node);

555 template

class

TNode,

class

TBackInsert>

558 typename

TNode::TNodeList_CI it = tree_node.SubNodeBegin();

559 typename

TNode::TNodeList_CI it_end = tree_node.SubNodeEnd();

561 for

(;it != it_end; ++it) {

562 const

TNode* node = *it;

563

*back_ins = node->GetValue().GetId();

573 template

class

TTreeNode,

class

TSet,

class

TNodeList>

585 if

(delta_level >= 0) {

586 unsigned id

= node.GetValue().GetId();

608 template

class

TNode,

class

TSet,

class

TNodeList>

610 const

TSet& node_set,

613

TNode* node =

const_cast<

TNode*

>

(&tree_node);

626 template

class

TNode,

class

TSet,

class

TNodeList>

631

TNodeList& dst_nlist)

638 ITERATE

(

typename

TNodeList, it, src_nlist) {

641

ancestor_set.clear();

645

ancestor_set &= src_set;

646 unsigned cnt

= ancestor_set.count();

650

dst_nlist.push_back(snode);

664 template

class

TNode,

class

TSet,

class

TNodeList>

679

TNodeList& dst_nlist,

680 const

TSet* ignore_set = 0)

682 MinimalSet

(src_nlist, dst_nlist, ignore_set);

690

TNodeList& dst_nlist,

691 const

TSet* ignore_set = 0)

704

src_set, tmp_set, child_set, ignore_set);

709

src_set, tmp_set, child_set, ignore_set);

718 unsigned id

= snode->GetValue().GetId();

721 bool b

= src_set[id];

729 ITERATE

(

typename

TNodeList, it, src_nlist) {

731 unsigned id

= snode->GetValue().GetId();

733 bool b

= src_set[id];

735

dst_nlist.push_back(snode);

743

TNodeList& dst_nlist,

747 const

TSet* ignore_set)

751 bool

promo_flag =

false

;

753 ITERATE

(

typename

TNodeList, it, nlist) {

756 unsigned id

= snode->GetValue().GetId();

757

TNode* parent = snode->GetParent();

760 bool b

= src_set[id];

761 if

|| (parent == 0))

764 unsigned

parent_id = parent->GetValue().GetId();

773

tmp_set -= *ignore_set;

776 if

(tmp_set.none()) {

781

src_set -= child_set;

783 bool

parent_in = src_set[parent_id];

786

src_set[parent_id] =

true

;

792 if

(&nlist != &dst_nlist) {

793

dst_nlist.push_back(parent);

795

tmp_nlist.push_back(parent);

805 ITERATE

(

typename

TNodeList, it, tmp_nlist) {

807

dst_nlist.push_back(snode);

815 template

class

TNode,

class

TSet,

class

TNodeList>

833 const

TNodeList& src_nlist_b,

834 const

TSet& mask_set,

841 unsigned

dst_count = dst_set.count();

842 unsigned

src_count = mask_set.count();

844 if

(src_count != dst_count) {

852 const

TSet& mask_set,

856 ITERATE

(

typename

TNodeList, it, src_nlist) {

857 unsigned id

= (*it)->GetValue().GetId();

858 bool

exists = mask_set[id];

860

exists = dst_set[id];

862

dst_list.push_back(*it);

873 template

class

TNode,

class

TSet,

class

TNodeList>

878 const

TNodeList& src_nlist_b,

879

TNodeList& dst_nlist)

882

this->

operator()

(src_nlist_a, src_nlist_b, dst_nlist, tmp_set);

886 const

TNodeList& src_nlist_b,

887

TNodeList& dst_nlist,

901

merge_func.

JoinNodeList

(src_nlist_a, src_nlist_b, set_a,

908 template

class

TNode,

class

TSet,

class

TNodeList>

913 const

TNodeList& src_nlist_b,

914

TNodeList& dst_nlist)

917

this->

operator()

(src_nlist_a, src_nlist_b, dst_nlist, tmp_set);

921 const

TNodeList& src_nlist_b,

922

TNodeList& dst_nlist,

936

merge_func.

JoinNodeList

(src_nlist_a, src_nlist_b, set_a,

Utility to join to node lists according to a set of ids.

Functor to trace node pointers to root and create set of parents (TreeForEachParent)

Functor takes a single nodelist as an argument and tries to push that nodelist as high as it can.

Node list AND (set intersection)

Class-algorithm to compute Non Redundant Set.

Functor to trace node pointers to root (TreeForEachParent)

Tree print functor used as a tree traversal payload.

Functor to convert tree to a nodelist by the set pattern.

#define ITERATE(Type, Var, Cont)

ITERATE macro to sequence through container elements.

#define NON_CONST_ITERATE(Type, Var, Cont)

Non constant version of ITERATE macro.

#define END_NCBI_SCOPE

End previously defined NCBI scope.

#define BEGIN_NCBI_SCOPE

Define ncbi namespace.

IO_PREFIX::ostream CNcbiOstream

Portable alias for ostream.

void operator()(const TNodeList &src_nlist_a, const TNodeList &src_nlist_b, TNodeList &dst_nlist, TSet &dst_set)

void operator()(const TNodeList &src_nlist_a, const TNodeList &src_nlist_b, TNodeList &dst_nlist)

ETreeTraverseCode operator()(const TTreeNode &node, int delta_level=0)

void operator()(const TNodeList &src_nlist, TNodeList &dst_nlist)

CTreeIdToSetFunc(TBackInsert back_ins)

Fun TreeDepthFirstTraverse(TTreeNode &tree_node, Fun func)

Depth-first tree traversal algorithm.

TTraceContainer * m_Trace

ETreeTraverseCode

Tree traverse code returned by the traverse predicate function.

void operator()(const TNodeList &src_nlist_a, const TNodeList &src_nlist_b, TNodeList &dst_nlist, TSet &dst_set)

const TTreeNode * TreeFindCommonParent(const TTreeNode &tree_node_a, const TTreeNode &tree_node_b)

Check if two nodes have the same common root.

CTreeSet2NodeListFunc(const TSet &node_set, TNodeList *node_list)

bool TreeCompare(const TTreeNode &tree1, const TTreeNode &tree2, TCompFun func)

Compare two trees using comparison functor where order of children matters.

TFunc TreeForEachParent(const TTreeNode &tree_node, TFunc func, bool skip_self=false)

Visit every parent of the specified node.

CTreePrintFunc(CNcbiOstream &os, TConverter &conv, bool print_ptr)

void TreeMakeParentsSet(const TNode &tree_node, TBackInsert back_ins)

Traverses all ancestors and add their ids to a set.

void MinimalSet(const TNodeList &src_nlist, TNodeList &dst_nlist, const TSet *ignore_set=0)

void operator()(const TNodeList &src_nlist_a, const TNodeList &src_nlist_b, TNodeList &dst_nlist)

void operator()(const TNodeList &src_nlist, TNodeList &dst_nlist, const TSet *ignore_set=0)

Compute minimal set.

void MaskCopyNodes(const TNodeList &src_nlist, const TSet &mask_set, TNodeList &dst_list, TSet &dst_set)

Copy nodes from the source node list to destination if nodes are in the mask set and not yet in the d...

void TreeMakeSubNodesSet(const TNode &tree_node, TBackInsert back_ins)

Create set of all immediate sub-nodes (one level down from the root)

bool CheckNodeList(const TNodeList &nlist, TNodeList &dst_nlist, TSet &src_set, TSet &tmp_set, TSet &child_set, const TSet *ignore_set)

void TreeListToSet(TNodeListIt node_list_first, TNodeListIt node_list_last, TBackInsert back_ins)

Convert list of node pointers to set of ids Input set is represented by input forward iterators Outpu...

ETreeTraverseCode operator()(const TTreeNode &node, int delta_level=0)

const TPairTree * PairTreeTraceNode(const TPairTree &tr, const TPathList &node_path)

Algorithm to trace the pair tree and find specified leaf along the node path.

void TreeReRoot(TTreeNode &new_root_node)

Change tree root (tree rotation)

void TreeMakeSet(const TNode &tree_node, TBackInsert back_ins)

Create set of all sub-nodes (recursively)

void JoinNodeList(const TNodeList &src_nlist_a, const TNodeList &src_nlist_b, const TSet &mask_set, TNodeList &dst_list, TSet &dst_set)

Join two node lists.

void TreeSetToNodeList(const TNode &tree_node, const TSet &node_set, TNodeList &nlist)

Convert set of node ids to list of nodes.

void TreeTraceToRoot(const TTreeNode &tree_node, TTraceContainer &trace)

Trace from the specified node to to the tree root.

const TPairTree * PairTreeBackTraceNode(const TPairTree &tr, const TValue &search_id)

Algorithm to to search for a node with specified id.

void TreePrint(CNcbiOstream &os, const TTreeNode &tree_node, TConverter conv, bool print_ptr=false)

Tree printing (use for debugging purposes)

CTreeParentTraceFunc(TTraceContainer *trace)

ETreeTraverseCode operator()(const TTreeNode &tr, int delta)

void operator()(const TTreeNode &node)

@ eTreeTraverse

Keep traversal.

static void hex(unsigned char c)

double value_type

The numeric datatype used by the parser.

Int4 delta(size_t dimension_, const Int4 *score_)

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4