00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "WHierarchicalTree.h"
00026
00027 WHierarchicalTree::WHierarchicalTree() :
00028 m_clusterCount( 0 ),
00029 m_leafCount( 0 ),
00030 m_maxLevel( 0 ),
00031 m_leafesLocked( false )
00032 {
00033 }
00034
00035 WHierarchicalTree::~WHierarchicalTree()
00036 {
00037 }
00038
00039 std::vector< size_t > WHierarchicalTree::findXBiggestClusters( size_t cluster, size_t number )
00040 {
00041
00042
00043 if( number > m_containsLeafes[cluster].size() )
00044 {
00045 number = m_containsLeafes[cluster].size();
00046 }
00047
00048
00049 std::list<size_t>worklist;
00050 worklist.push_back( cluster );
00051
00052 while( worklist.size() < number )
00053 {
00054 size_t current = worklist.front();
00055 worklist.pop_front();
00056 if( m_containsLeafes[current].size() > 1 )
00057 {
00058 size_t left = m_children[current].first;
00059 size_t right = m_children[current].second;
00060 worklist.push_back( left );
00061 worklist.push_back( right );
00062 }
00063 else
00064 {
00065 worklist.push_back( current );
00066 }
00067 }
00068
00069 worklist.sort( compSize( this ) );
00070
00071 bool newSplit = true;
00072
00073 while( newSplit )
00074 {
00075 newSplit = false;
00076 size_t current = worklist.front();
00077
00078 if( m_containsLeafes[current].size() > 1 )
00079 {
00080 size_t left = m_children[current].first;
00081 size_t right = m_children[current].second;
00082 size_t last = worklist.back();
00083
00084 if( m_containsLeafes[left].size() > m_containsLeafes[last].size() )
00085 {
00086 worklist.pop_front();
00087 worklist.push_back( left );
00088 worklist.sort( compSize( this ) );
00089 newSplit = true;
00090 }
00091
00092 last = worklist.back();
00093 if( m_containsLeafes[right].size() > m_containsLeafes[last].size() )
00094 {
00095 if( !newSplit )
00096 {
00097 worklist.pop_front();
00098 }
00099 if( worklist.size() == number )
00100 {
00101 worklist.pop_back();
00102 }
00103 worklist.push_back( right );
00104 worklist.sort( compSize( this ) );
00105 newSplit = true;
00106 }
00107 }
00108 }
00109
00110 std::vector<size_t>returnVector;
00111 std::list<size_t>::iterator it;
00112 for( it = worklist.begin(); it != worklist.end(); ++it )
00113 {
00114 size_t current = *it;
00115
00116 returnVector.push_back( current );
00117 }
00118
00119 return returnVector;
00120 }
00121
00122 std::vector< size_t > WHierarchicalTree::downXLevelsFromTop( size_t level, bool hideOutliers )
00123 {
00124 if( level > m_maxLevel )
00125 {
00126 level = m_maxLevel -1;
00127 }
00128
00129 std::vector<size_t>returnVector;
00130
00131 std::list<size_t>worklist;
00132 worklist.push_back( m_clusterCount - 1 );
00133
00134 for( size_t i = 0; i < level; ++i )
00135 {
00136 std::list<size_t>newChildList;
00137 while( !worklist.empty() )
00138 {
00139 size_t current = worklist.front();
00140 worklist.pop_front();
00141 if( m_containsLeafes[current].size() > 1 )
00142 {
00143 size_t left = m_children[current].first;
00144 size_t right = m_children[current].second;
00145
00146 if( hideOutliers )
00147 {
00148 if( m_containsLeafes[left].size() > 1 )
00149 {
00150 newChildList.push_back( left );
00151 }
00152 if( m_containsLeafes[right].size() > 1 )
00153 {
00154 newChildList.push_back( right );
00155 }
00156 }
00157 else
00158 {
00159 newChildList.push_back( left );
00160 newChildList.push_back( right );
00161 }
00162 }
00163 }
00164 worklist = newChildList;
00165 }
00166
00167 worklist.sort( compSize( this ) );
00168
00169 std::list<size_t>::iterator it;
00170 for( it = worklist.begin(); it != worklist.end(); ++it )
00171 {
00172 size_t current = *it;
00173 returnVector.push_back( current );
00174 }
00175
00176 return returnVector;
00177 }
00178
00179 void WHierarchicalTree::colorCluster( size_t cluster, WColor color )
00180 {
00181 m_colors[cluster] = color;
00182 if( m_containsLeafes[cluster].size() > 1 )
00183 {
00184 colorCluster( m_children[cluster].first, color );
00185 colorCluster( m_children[cluster].second, color );
00186 }
00187 }
00188