1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
/*
* TreeLib
* A library for manipulating phylogenetic trees.
* Copyright (C) 2001 Roderic D. M. Page <r.page@bio.gla.ac.uk>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
// $Id: lcaquery.h,v 1.1 2002/03/14 14:11:42 rdmp1c Exp $
/**
* @file lcaquery.h
*
* Classes to perform LCA queries on a tree
*
*/
#ifndef LCAQUERYH
#define LCAQUERYH
#ifdef __BORLANDC__
// Undefine __MINMAX_DEFINED so that min and max are correctly defined
#ifdef __MINMAX_DEFINED
#undef __MINMAX_DEFINED
#endif
// Ignore "Cannot create precompiled header: code in header" message
// generated when compiling string.cc
#pragma warn -pch
#endif
#include <vector>
#include "TreeLib.h"
#include "nodeiterator.h"
/**
* @class LCAQuery
* Base class for performing LCA queries. Descendants of this class must
* override the abstract member function LCA.
*/
class LCAQuery
{
public:
LCAQuery () { t = NULL; };
LCAQuery (Tree *tree);
virtual ~LCAQuery () {};
virtual NodePtr LCA (NodePtr i, NodePtr j) = 0;
virtual void SetTree (Tree *tree);
protected:
Tree *t;
virtual void Initialise () {};
};
/**
* @class SimpleLCAQuery
* Does naive LCA queries by going down the tree until we find the
* LCA.
*/
class SimpleLCAQuery : public LCAQuery
{
public:
SimpleLCAQuery () {};
SimpleLCAQuery (Tree *tree) : LCAQuery (tree) { Initialise (); };
/**
* Finds LCA by going down tree twowards root until we reach node
* with the same preorder number.
* @return LCA of nodes i and j
*/
virtual NodePtr LCA (NodePtr i, NodePtr j);
protected:
std::map<Node *, int, std::less<Node *> > depth;
/**
* Number the nodes in preorder (root = 0).
*/
virtual void Initialise ();
};
#if __BORLANDC__
// Redefine __MINMAX_DEFINED so Windows header files compile
#ifndef __MINMAX_DEFINED
#define __MINMAX_DEFINED
#endif
#endif
#endif
|
