haskell-igraph-0.8.0: igraph/include/hrg_splittree_eq.h
/* -*- mode: C++ -*- */
/*
IGraph library.
Copyright (C) 2011-2012 Gabor Csardi <csardi.gabor@gmail.com>
334 Harvard street, Cambridge, MA 02139 USA
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 Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
// ****************************************************************************************************
// *** COPYRIGHT NOTICE *******************************************************************************
// splittree_eq.h - a binary search tree data structure for storing dendrogram split frequencies
// Copyright (C) 2006-2008 Aaron Clauset
//
// 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
// See http://www.gnu.org/licenses/gpl.txt for more details.
//
// ****************************************************************************************************
// Author : Aaron Clauset ( aaronc@santafe.edu | http://www.santafe.edu/~aaronc/ )
// Collaborators: Cristopher Moore and Mark E.J. Newman
// Project : Hierarchical Random Graphs
// Location : University of New Mexico, Dept. of Computer Science AND Santa Fe Institute
// Created : 19 April 2006
// Modified : 19 May 2007
// : 20 May 2008 (cleaned up for public consumption)
//
// ***********************************************************************
//
// Data structure for storing the split frequences in the sampled
// dendrograms. Data is stored efficiently as a red-black binary
// search tree (this is a modified version of the rbtree.h file).
//
// ***********************************************************************
#ifndef IGRAPH_HRG_SPLITTREE
#define IGRAPH_HRG_SPLITTREE
#include <iostream>
using namespace std;
namespace fitHRG {
// ******** Basic Structures *********************************************
#ifndef IGRAPH_HRG_SLIST
#define IGRAPH_HRG_SLIST
class slist {
public:
string x; // stored elementd in linked-list
slist* next; // pointer to next elementd
slist(): x(""), next(0) { }
~slist() { }
};
#endif
class keyValuePairSplit {
public:
string x; // elementsp split (string)
double y; // stored weight (double)
int c; // stored count (int)
keyValuePairSplit* next; // linked-list pointer
keyValuePairSplit(): x(""), y(0.0), c(0), next(0) { }
~keyValuePairSplit() { }
};
// ******** Tree elementsp Class *****************************************
class elementsp {
public:
string split; // split represented as a string
double weight; // total weight of this split
int count; // number of observations of this split
bool color; // F: BLACK, T: RED
short int mark; // marker
elementsp *parent; // pointer to parent node
elementsp *left; // pointer for left subtree
elementsp *right; // pointer for right subtree
elementsp(): split(""), weight(0.0), count(0), color(false), mark(0),
parent(0), left(0), right(0) { }
~elementsp() { }
};
// ******** Red-Black Tree Class *****************************************
// This vector implementation is a red-black balanced binary tree data
// structure. It provides find a stored elementsp in time O(log n),
// find the maximum elementsp in time O(1), delete an elementsp in
// time O(log n), and insert an elementsp in time O(log n).
//
// Note that the split="" is assumed to be a special value, and thus
// you cannot insert such an item. Beware of this limitation.
//
class splittree {
private:
elementsp* root; // binary tree root
elementsp* leaf; // all leaf nodes
int support; // number of nodes in the tree
double total_weight; // total weight stored
int total_count; // total number of observations stored
// left-rotation operator
void rotateLeft(elementsp*);
// right-rotation operator
void rotateRight(elementsp*);
// house-keeping after insertion
void insertCleanup(elementsp*);
// house-keeping after deletion
void deleteCleanup(elementsp*);
keyValuePairSplit* returnSubtreeAsList(elementsp*, keyValuePairSplit*);
// delete subtree rooted at z
void deleteSubTree(elementsp*);
// returns minimum of subtree rooted at z
elementsp* returnMinKey(elementsp*);
// returns successor of z's key
elementsp* returnSuccessor(elementsp*);
public:
// default constructor/destructor
splittree(); ~splittree();
// returns value associated with searchKey
double returnValue(const string);
// returns T if searchKey found, and points foundNode at the
// corresponding node
elementsp* findItem(const string);
// update total_count and total_weight
void finishedThisRound();
// insert a new key with stored value
bool insertItem(string, double);
void clearTree();
// delete a node with given key
void deleteItem(string);
// delete the entire tree
void deleteTree();
// return array of keys in tree
string* returnArrayOfKeys();
// return list of keys in tree
slist* returnListOfKeys();
// return the tree as a list of keyValuePairSplits
keyValuePairSplit* returnTreeAsList();
// returns the maximum key in the tree
keyValuePairSplit returnMaxKey();
// returns the minimum key in the tree
keyValuePairSplit returnMinKey();
// returns number of items in tree
int returnNodecount();
// returns list of splits with given number of Ms
keyValuePairSplit* returnTheseSplits(const int);
// returns sum of stored values
double returnTotal();
};
} // namespace fitHRG
#endif