source: branches/port5/PROBE_SET/ps_candidate.hxx

Last change on this file was 5428, checked in by westram, 17 years ago
  • fixed includes for gcc 4.3.1
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.6 KB
Line 
1#ifndef PS_CANDIDATE_HXX
2#define PS_CANDIDATE_HXX
3
4#ifndef PS_DEFS_HXX
5#include "ps_defs.hxx"
6#endif
7#ifndef PS_BITMAP_HXX
8#include "ps_bitmap.hxx"
9#endif
10#ifndef PS_FILEBUFFER_HXX
11#include "ps_filebuffer.hxx"
12#endif
13
14#ifndef _CPP_CLIMITS
15#include <climits>
16#endif
17
18using namespace std;
19
20class PS_Candidate;
21typedef PS_Candidate*                           PS_CandidatePtr;
22typedef SmartPtr<PS_Candidate>                  PS_CandidateSPtr;
23
24struct cmp_candidates
25{
26  bool operator()(const PS_CandidateSPtr &c1, const PS_CandidateSPtr &c2) const
27  {
28    return &(*c1) < &(*c2);
29  }
30};
31typedef set<PS_CandidateSPtr,cmp_candidates>    PS_CandidateSet;
32typedef PS_CandidateSet::iterator               PS_CandidateSetIter;
33typedef PS_CandidateSet::const_iterator         PS_CandidateSetCIter;
34typedef PS_CandidateSet::reverse_iterator       PS_CandidateSetRIter;
35typedef PS_CandidateSet::const_reverse_iterator PS_CandidateSetCRIter;
36
37typedef map<unsigned long,PS_CandidateSPtr>     PS_CandidateByGainMap;
38typedef PS_CandidateByGainMap::iterator               PS_CandidateByGainMapIter;
39typedef PS_CandidateByGainMap::const_iterator         PS_CandidateByGainMapCIter;
40typedef PS_CandidateByGainMap::reverse_iterator       PS_CandidateByGainMapRIter;
41typedef PS_CandidateByGainMap::const_reverse_iterator PS_CandidateByGainMapCRIter;
42
43// typedef map<float,PS_CandidateSPtr>              PS_CandidateByFillingMap;
44// typedef PS_CandidateByFillingMap::iterator               PS_CandidateByFillingMapIter;
45// typedef PS_CandidateByFillingMap::const_iterator         PS_CandidateByFillingMapCIter;
46// typedef PS_CandidateByFillingMap::reverse_iterator       PS_CandidateByFillingMapRIter;
47// typedef PS_CandidateByFillingMap::const_reverse_iterator PS_CandidateByFillingMapCRIter;
48
49typedef pair<SpeciesID,PS_BitSet::IndexSet>     ID2IndexSetPair;
50typedef set<ID2IndexSetPair>                    ID2IndexSetSet;
51typedef ID2IndexSetSet::iterator                ID2IndexSetSetIter;
52typedef ID2IndexSetSet::const_iterator          ID2IndexSetSetCIter;
53typedef ID2IndexSetSet::reverse_iterator        ID2IndexSetSetRIter;
54typedef ID2IndexSetSet::const_reverse_iterator  ID2IndexSetSetCRIter;
55
56class PS_Candidate {
57private:
58    PS_Candidate();
59    PS_Candidate( const PS_Candidate& );
60    explicit PS_Candidate( float _distance, unsigned long _gain, const PS_NodePtr _ps_node, IDSet &_path, PS_CandidatePtr _parent ) {
61        filling_level = 0.0;
62        depth         = ULONG_MAX;
63        distance      = _distance;
64        gain          = _gain;
65        passes_left   = MAX_PASSES;
66        parent        = _parent;
67        //source_set    = 0;
68        //target_set    = 0;
69        false_IDs     = 0;
70        one_false_IDs = 0;
71        one_false_IDs_matches = 0;
72        map           = 0;
73        node          = _ps_node;
74        path          = _path;
75    }
76
77public:
78    static const unsigned int MAX_PASSES = 3;
79    float                  filling_level;
80    unsigned long          depth;
81    float                  distance;
82    unsigned long          gain;
83    unsigned int           passes_left;
84    PS_Candidate          *parent;
85    //IDSet                 *source_set;
86    //IDSet                 *target_set;
87    //ID2IndexSetSet        *false_IDs;
88    unsigned long          false_IDs;
89    ID2IDSet              *one_false_IDs;
90    unsigned long          one_false_IDs_matches;
91    PS_BitMap_Counted     *map;
92    IDSet                  path;
93    PS_NodePtr             node;
94    PS_CandidateByGainMap  children;
95
96    unsigned long initFalseIDs( const SpeciesID  _min_id,
97                                const SpeciesID  _max_id,
98                                      SpeciesID &_min_sets_id,
99                                      SpeciesID &_max_sets_id ) {
100        // if i already have the set return its size
101        if (one_false_IDs) {
102//             for (ID2IndexSetSetCIter i = false_IDs->begin();
103//                  i != false_IDs->end();
104//                  ++i ) {
105//                 if (i->first < _min_sets_id) _min_sets_id = i->first;
106//                 if (i->first > _max_sets_id) _max_sets_id = i->first;
107//                 if (*i->second.begin()  < _min_sets_id) _min_sets_id = *i->second.begin();
108//                 if (*i->second.rbegin() > _max_sets_id) _max_sets_id = *i->second.rbegin();
109//                 countFalses += i->second.size();
110//                 //printf( "\n[%i] (%i)", i->first, i->second.size() );
111//             }
112            return one_false_IDs->size();
113        } else {
114            one_false_IDs = new ID2IDSet();
115            false_IDs     = 0;
116            //false_IDs     = new ID2IndexSetSet();
117            PS_BitSet::IndexSet falseIndices;       // temp. set to hold IDs of falses per ID
118            // iterate over _min_id .. _max_id range in map
119            for ( SpeciesID id1 = _min_id;
120                  id1 <= _max_id;
121                  ++id1) {
122                if (map->getCountFor( id1 ) == _max_id+1) continue; // skip ID if its already filled
123                if (id1 < _min_sets_id) _min_sets_id = id1;
124                if (id1 > _max_sets_id) _max_sets_id = id1;
125                map->getFalseIndicesFor( id1, falseIndices );
126                while ((*(falseIndices.begin()) < id1) &&
127                       !falseIndices.empty()) falseIndices.erase( *falseIndices.begin() );
128                if (falseIndices.empty()) continue;
129                if (*falseIndices.begin()  < _min_sets_id) _min_sets_id = *falseIndices.begin();
130                if (*falseIndices.rbegin() > _max_sets_id) _max_sets_id = *falseIndices.rbegin();
131                // store
132                false_IDs += falseIndices.size();
133                if (falseIndices.size() == 1) {
134                    one_false_IDs->insert( ID2IDPair(id1,*falseIndices.begin()) );
135                }
136                //false_IDs->insert( ID2IndexSetPair( id1,falseIndices ) );
137                // print
138//                 printf( "\n[%i] (%i) ", id1, falseIndices.size() );
139//                 for ( PS_BitSet::IndexSet::const_iterator i = falseIndices.begin();
140//                       i != falseIndices.end();
141//                       ++i ) {
142//                     printf( " %li", *i );
143//                 }
144            }
145        }
146        return one_false_IDs->size();
147    }
148
149    unsigned long matchPathOnOneFalseIDs( IDSet &_path ) {
150        unsigned long matches = 0;
151        IDSetCIter path_end = _path.end();
152        for ( ID2IDSetCIter p = one_false_IDs->begin();
153              p != one_false_IDs->end();
154              ++p ) {
155            if (_path.find( p->first ) == path_end) {
156                if (_path.find( p->second ) != path_end) ++matches;
157            } else {
158                if (_path.find( p->second ) == path_end) ++matches;
159            }
160        }
161        return matches;
162    }
163
164    void decreasePasses() {
165        --passes_left;
166        if (passes_left == 0) {
167            //if (source_set)    { delete source_set;    source_set = 0; }
168            //if (target_set)    { delete target_set;    target_set = 0; }
169            //if (false_IDs)     { delete false_IDs;     false_IDs  = 0; }
170            //if (one_false_IDs) { delete one_false_IDs; one_false_IDs  = 0; }
171        }
172    }
173
174    void getParentMap() {
175        if (!parent) return;
176        map = parent->map;      // grab parents version of the map
177        parent->map = 0;        // unbind parent from map
178    }
179
180    bool hasChild( PS_NodePtr _ps_node ) const {
181        PS_CandidateByGainMapCIter found = children.end();
182        for ( PS_CandidateByGainMapCIter child = children.begin();
183              (child != children.end()) && (found == children.end());
184              ++child ) {
185            if (child->second->node == _ps_node) found = child;
186        }
187        return (found != children.end());
188    }
189
190    bool alreadyUsedNode( const PS_NodePtr _ps_node ) const {
191        if (node.Null()) return false;
192        if (_ps_node == node) {
193            return true;
194        } else {
195            return parent->alreadyUsedNode( _ps_node );
196        }
197    }
198
199    int addChild( unsigned long     _distance,
200                  unsigned long     _gain,
201                  const PS_NodePtr  _node,
202                  IDSet            &_path ) {
203        PS_CandidateByGainMapIter found = children.find( _gain );
204        if (found == children.end()) {
205            PS_CandidateSPtr new_child( new PS_Candidate(_distance, _gain, _node, _path, this) );
206            children[ _gain ] = new_child;
207            return 2;
208        } else if (_distance < found->second->distance) {
209            children.erase( _gain );
210            PS_CandidateSPtr new_child( new PS_Candidate(_distance, _gain, _node, _path, this) );
211            children[ _gain ] = new_child;
212            return 1;
213        }
214        return 0;
215    }
216
217    bool updateBestChild( const unsigned long  _gain,
218                          const unsigned long  _one_false_IDs_matches,
219                          const float          _filling_level,
220                          const PS_NodePtr     _node, 
221                          IDSet               &_path ) {
222        if (children.size() == 0) {
223            // no child yet
224            PS_CandidateSPtr new_child( new PS_Candidate(0,_gain,_node,_path,this) );
225            new_child->depth = depth+1;
226            new_child->filling_level = _filling_level;
227            if (_filling_level >= 100.0) new_child->passes_left = 0;
228            children[ 0 ] = new_child;
229            one_false_IDs_matches = _one_false_IDs_matches;
230            return true;
231        }
232        // return false if new child matches less 'must matches' than best child so far
233        if (_one_false_IDs_matches < one_false_IDs_matches ) return false;
234        // return false if new child matches same 'must matches' but has less total gain
235        if ((_one_false_IDs_matches == one_false_IDs_matches) &&
236            (_gain <= children[ 0 ]->gain)) return false;
237               
238        children.clear();
239        PS_CandidateSPtr new_child( new PS_Candidate(0,_gain,_node,_path,this) );
240        new_child->depth = depth+1;
241        new_child->filling_level = _filling_level;
242        if (_filling_level >= 100.0) new_child->passes_left = 0;
243        children[ 0 ] = new_child;
244        one_false_IDs_matches = _one_false_IDs_matches;
245        return true;
246    }
247
248    void reduceChildren( const float _filling_level ) {
249        if (children.size() == 0) return;
250        // prepare
251        unsigned long best_gain   = children.rbegin()->first;
252        unsigned long worst_gain  = children.begin()->first;
253        unsigned long middle_gain = (best_gain + worst_gain) >> 1;
254        PS_CandidateByGainMapIter middle_child = children.find( middle_gain );
255        if (middle_child == children.end()) {
256            middle_child = children.lower_bound( middle_gain );
257            middle_gain  = middle_child->first;
258        }
259        PS_CandidateByGainMapIter to_delete = children.end();
260        // delete unwanted childs depending on filling level
261        if (_filling_level < 50.0) {
262            if (children.size() <= 3) return;
263            for ( PS_CandidateByGainMapIter c = children.begin();
264                  c != children.end();
265                  ++c ) {
266                if (to_delete != children.end()) {
267                    children.erase( to_delete );
268                    to_delete = children.end();
269                }
270                if ((c->first != worst_gain) &&
271                    (c->first != middle_gain) &&
272                    (c->first != best_gain)) {
273                    to_delete = c;
274                }
275            }
276        } else if (_filling_level < 75.0) {
277            if (children.size() <= 2) return;
278            for ( PS_CandidateByGainMapIter c = children.begin();
279                  c != children.end();
280                  ++c ) {
281                if (to_delete != children.end()) {
282                    children.erase( to_delete );
283                    to_delete = children.end();
284                }
285                if ((c->first != middle_gain) &&
286                    (c->first != best_gain)) {
287                    to_delete = c;
288                }
289            }
290        } else {
291            if (children.size() <= 1) return;
292            for ( PS_CandidateByGainMapIter c = children.begin();
293                  c != children.end();
294                  ++c ) {
295                if (to_delete != children.end()) {
296                    children.erase( to_delete );
297                    to_delete = children.end();
298                }
299                if (c->first != best_gain) {
300                    to_delete = c;
301                }
302            }
303        }
304        if (to_delete != children.end()) {
305            children.erase( to_delete );
306            to_delete = children.end();
307        }
308    }
309
310    void printProbes( const SpeciesID      _species_count,
311                      const unsigned long _depth = 0,
312                      const bool          _descend = true ) const {
313        for (unsigned long i = 0; i < _depth; ++i) {
314            printf( "|  " );
315        }
316        printf( "\n" );
317        if (node.Null()) {
318            for (unsigned long i = 0; i < _depth; ++i) {
319                printf( "|  " );
320            }
321            printf( "[%p] depth (%lu) no node\n", this, _depth );
322        } else if (node->countProbes() == 0) {
323            for (unsigned long i = 0; i < _depth; ++i) {
324                printf( "|  " );
325            }
326            printf( "[%p] depth (%lu)  node (%p)  no probes\n", this, _depth, &(*node) );
327        } else {
328            for ( PS_ProbeSetCIter probe = node->getProbesBegin();
329                  probe != node->getProbesEnd();
330                  ++probe ) {
331                for (unsigned long i = 0; i < _depth; ++i) {
332                    printf( "|  " );
333                }
334                printf( "[%p] depth (%lu)  node (%p)  matches (%zu)       %u   %u\n",
335                        this,
336                        _depth,
337                        &(*node),
338                        ((*probe)->quality > 0) ? path.size() : _species_count - path.size(),
339                        (*probe)->length,
340                        (*probe)->GC_content );
341            }
342        }
343        fflush( stdout );
344
345        if ( _descend) {
346            for ( PS_CandidateByGainMapCRIter child = children.rbegin();
347                  child != children.rend();
348                  ++child ) {
349                child->second->printProbes( _species_count, _depth+1 );
350            }
351        }
352
353    }
354
355    void print ( const unsigned long _depth = 0,
356                 const bool          _print_one_false_IDs = false,
357                 const bool          _descend = true ) const {
358        for (unsigned long i = 0; i < _depth; ++i) {
359            printf( "|  " );
360        }
361        printf( "[%p] passes left (%u)  filling level (%.5f)  distance (%6.2f)  gain (%6lu)  depth (%3lu)  path length (%4zu)  ",
362                this,
363                passes_left,
364                filling_level,
365                distance,
366                gain,
367                depth,
368                path.size() );
369        if (node.Null()) {
370            printf( "node (undefined)  children (%2zu)  ", children.size() );
371        } else {
372            printf( "node (%p)  children (%2zu)  ", &(*node), children.size() );
373        }
374//             unsigned long count = 0;
375//             for ( ID2IndexSetSetCIter i = false_IDs->begin();
376//                   i != false_IDs->end();
377//                   ++i ) {
378//                 count += i->second.size();
379//             }
380        printf( "(%4lu %4zu)/%lu", one_false_IDs_matches, (one_false_IDs) ? one_false_IDs->size() : 0, false_IDs );
381        if (_print_one_false_IDs) {
382            printf( "\n" );
383            for (unsigned long i = 0; i < _depth; ++i) {
384                printf( "|  " );
385            }
386            printf( "            one_false_IDs : " );
387            if (one_false_IDs) {
388                for ( ID2IDSetCIter p = one_false_IDs->begin();
389                      p != one_false_IDs->end();
390                      ++p ) {
391                    printf( "(%i %i)  ", p->first, p->second );
392                }
393            } else {
394                printf( "none" );
395            }
396        }
397        printf( "\n" ); fflush( stdout );
398        if (_descend) {
399            for ( PS_CandidateByGainMapCRIter child = children.rbegin();
400                  child != children.rend();
401                  ++child ) {
402                child->second->print(_depth+1);
403            }
404        }
405    }
406
407    void save( PS_FileBuffer       *_file,
408               const unsigned long  _bits_in_map ) {
409        unsigned long count;
410        // gain
411        _file->put_ulong( gain );
412        // passes_left
413        _file->put_uint( passes_left );
414        // false_IDs
415        _file->put_ulong( false_IDs );
416        // one_false_IDs
417        if (one_false_IDs) {
418            count = one_false_IDs->size();
419            _file->put_ulong( count );
420            for ( ID2IDSetCIter p = one_false_IDs->begin();
421                  p != one_false_IDs->end();
422                  ++p ) {
423                _file->put_int( p->first );
424                _file->put_int( p->second );
425            }
426        } else {
427            _file->put_ulong( 0 );
428        }
429        // one_false_IDs_matches
430        _file->put_ulong( one_false_IDs_matches );
431        // path
432        count = path.size();
433        _file->put_ulong( count );
434        for ( IDSetCIter id = path.begin();
435              id != path.end();
436              ++id ) {
437            _file->put_int( *id );
438        }
439        // children
440        count = children.size();
441        _file->put_ulong( count );
442        for ( PS_CandidateByGainMapIter child = children.begin();
443              child != children.end();
444              ++child ) {
445            child->second->save( _file, _bits_in_map );
446        }
447    }
448
449    void load( PS_FileBuffer       *_file,
450               const unsigned long  _bits_in_map,
451               const PS_NodePtr     _root_node ) {
452        unsigned long count;
453        // gain
454        _file->get_ulong( gain );
455        // passes_left
456        _file->get_uint( passes_left );
457        // false_IDs & filling_level
458        _file->get_ulong( false_IDs );
459        filling_level = (float)(_bits_in_map - false_IDs) / _bits_in_map * 100.0;
460        // one_false_IDs
461        SpeciesID id1;
462        SpeciesID id2;
463        _file->get_ulong( count );
464        one_false_IDs = (count) ? new ID2IDSet() : 0;
465        for ( ; count > 0; --count ) {
466            _file->get_int( id1 );
467            _file->get_int( id2 );
468            one_false_IDs->insert( ID2IDPair( id1,id2 ) );
469        }
470        // one_false_IDs_matches
471        _file->get_ulong( one_false_IDs_matches );
472        // path & node
473        _file->get_ulong( count );
474        if (count) node = _root_node;
475        for ( ; count > 0; --count ) {
476            _file->get_int( id1 );
477            path.insert( id1 );
478            node = node->getChild( id1 ).second;
479        }
480        // children
481        _file->get_ulong( count );
482        for ( ; count > 0; --count ) {
483            PS_CandidateSPtr new_child( new PS_Candidate( 0.0 ) );
484            new_child->depth  = depth+1;
485            new_child->parent = this;
486            new_child->load( _file, _bits_in_map, _root_node );
487            children[ new_child->gain ] = new_child;
488        }
489    }
490
491    explicit PS_Candidate( float _distance ) {
492        filling_level = 0.0;
493        depth         = 0;
494        distance      = _distance;
495        gain          = 0;
496        passes_left   = 0;
497        parent        = 0;
498        //source_set    = 0;
499        //target_set    = 0;
500        false_IDs     = 0;
501        one_false_IDs = 0;
502        one_false_IDs_matches = 0;
503        map           = 0;
504        node.SetNull();
505    }
506    ~PS_Candidate() {
507        if (map)           delete map;
508        if (one_false_IDs) delete one_false_IDs;
509        //if (false_IDs)     delete false_IDs;
510        //if (source_set)    delete source_set;
511        //if (target_set)    delete target_set;
512        if (path.size() > 0) path.clear();
513        if (children.size() > 0) children.clear();
514    }
515};
516
517#else
518#error ps_candidate.hxx included twice
519#endif
Note: See TracBrowser for help on using the repository browser.