Thread portable class Gate portable class Timer class Pool class Terimber 2.0 About C++

Downloads Products & Services Support Clients Open Source About Home / Open source / Terimber 2.0 mst.h Go to the documentation of this file. /* * The Software License * ================================================================================= * Copyright (c) 2003-.The Terimber Corporation. All rights reserved. * ================================================================================= * Redistributions of source code must retain the above copyright notice, * this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, * this list of conditions and the following disclaimer in the documentation * and/or other materials provided with the distribution. * The end-user documentation included with the redistribution, if any, * must include the following acknowledgment: * "This product includes software developed by the Terimber Corporation." * ================================================================================= * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED WARRANTIES, * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE TERIMBER CORPORATION OR ITS CONTRIBUTORS BE LIABLE FOR * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * ================================================================================ */ #ifndef _terimber_mst_h_ #define _terimber_mst_h_ #include "base/vector.h" BEGIN_TERIMBER_NAMESPACE #pragma pack(4) typedef _vector< size_t > priority_queue_vec_t; template < class T > class priority_queue { public: inline priority_queue( byte_allocator& all, size_t N, const _vector< T >& pred, size_t dim = 3 ); inline bool empty() const; inline size_t size() const; inline void insert( size_t v ); inline size_t getmin(); inline void lower( size_t v ); private: inline void exchange( size_t i, size_t j ); inline void fixUp( size_t i ); inline void fixDown( size_t k, size_t N ); private: size_t _dim; size_t _Num; priority_queue_vec_t _pq; priority_queue_vec_t _qp; const _vector< T >& _pred; }; class mst_edge { public: mst_edge( size_t from, size_t to, double distance) : _from(from), _to(to), _distance(distance) { } inline bool operator<(const mst_edge& x) const { return _from != x._from ? _from < x._from : _to < x._to; } size_t _from; size_t _to; double _distance; }; typedef _map< size_t, size_t > mst_head_map_t; typedef mst_head_map_t::const_iterator mst_head_map_citer_t; class mst_head_compare_counts { public: inline bool operator()( mst_head_map_citer_t x, mst_head_map_citer_t y ) const { return *x > *y; } }; class cluster_info { public: cluster_info( size_t ident, double distance ) : _cluster_ident(ident), _cluster_distance(distance) { } size_t _cluster_ident; double _cluster_distance; }; typedef _vector< mst_edge > mst_vec_t; typedef _vector< double > mst_dist_t; template < class T, class N > class mst { public: mst( const T& container, const N& notifier, byte_allocator& all, byte_allocator& temp ); inline const mst_vec_t& get_mst() const; private: void pfs( size_t s, byte_allocator& tmp ); private: const T& _container; const N& _notifier; const size_t _length; mst_dist_t _wt; mst_vec_t _fr; mst_vec_t _mst; }; typedef _list< size_t > cluster_list_t; typedef _map< size_t, cluster_list_t > cluster_map_t; typedef _map< mst_edge, cluster_info > cluster_mst_map_t; template < class T, class N > class cluster_processor { public: cluster_processor(const T& container, const N& notifier, double max_vertex_distance, double max_cluster_distance, double avg_cluster_distance ); inline const cluster_map_t& get_clusters() const; private: void cut( double max_vertex_distance, double max_cluster_distance, double avg_cluster_distance ); inline double avg_distance( cluster_map_t::const_iterator citer, size_t index ) const; private: const T& _container; const N& _notifier; cluster_mst_map_t _mst_map; cluster_map_t _clusters; byte_allocator _all; }; #pragma pack() END_TERIMBER_NAMESPACE #endif

© Copyright Terimber 2003-.