plugins/teamwork/sumsearch.h

   1 /***************************************************************************
   2   Copyright 2006 David Nolden <david.nolden.kdevelop@art-master.de>
   3 ***************************************************************************/
   4
   5 /***************************************************************************
   6  *                                                                         *
   7  *   This program is free software; you can redistribute it and/or modify  *
   8  *   it under the terms of the GNU General Public License as published by  *
   9  *   the Free Software Foundation; either version 2 of the License, or     *
  10  *   (at your option) any later version.                                   *
  11  *                                                                         *
  12  ***************************************************************************/
  13
  14 #ifndef SUMSEARCH_H
  15 #define SUMSEARCH_H
  16
  17 #include <cstdio>
  18 #include <cstdlib>
  19 #include <string>
  20 #include <vector>
  21
  22 ///For higher orders to work, the sum-type has to be signed
  23 #define DEFAULTSUMTYPE int
  24 #define DEFAULTORDER 2
  25
  26
  27 ///State-based-build can only nearly complete with extreme compiler-parameters set, although it should theoretically be faster, if the compile would optimize it the right way.
  28
  29 //#define STATEBASEDBUILD
  30
  31 namespace FuzzySearch {
  32
  33 /**
  34  * How should all the differences be weighed together to a compound difference?
  35  *
  36  * The weighting still needs some work.
  37  *
  38  * */
  39
  40 template < class Compare1, class Compare2, class Then, class Else >
  41 class IfEqual {
  42 public:
  43   typedef Else Result;
  44 };
  45
  46 template < class Compare, class Then, class Else >
  47 class IfEqual<Compare, Compare, Then, Else> {
  48 public:
  49   typedef Then Result;
  50 };
  51
  52 template <class Item>
  53 class PrimitiveVector {
  54     Item* data_;
  55     uint size_;
  56   public:
  57     PrimitiveVector() : data_( 0 ), size_( 0 ) {}
  58     ;
  59
  60     ~PrimitiveVector() {
  61       if ( data_ )
  62         delete[] data_;
  63     }
  64
  65     ///All data is lost when this is called
  66     void rawResize( unsigned int i ) {
  67       if ( size_ == i )
  68         return ;
  69       size_ = i;
  70       if ( data_ )
  71         delete[] data_;
  72       if ( !i ) {
  73         data_ = 0;
  74       } else {
  75         data_ = new Item[ i ];
  76       }
  77     };
  78
  79     Item& operator [] ( uint index ) {
  80       return data_[ index ];
  81     }
  82
  83     const Item& operator [] ( uint index ) const {
  84       return data_[ index ];
  85     }
  86
  87     uint size() const {
  88       return size_;
  89     }
  90 };
  91
  92 ///unsigned int is ok for document-sizes of up to about 16 Megabytes, 64-bit integers create problems here
  93 using namespace std;
  94 template <int maxDepth, class SumType = DEFAULTSUMTYPE>
  95 struct SumGroup {
  96   SumType sums[ maxDepth ];
  97
  98   SumGroup( SumType* _sums = 0 ) {
  99     if ( _sums ) {
 100       for ( int a = 0; a < maxDepth; a++ ) {
 101         sums[ a ] = _sums[ a ];
 102       }
 103     } else {
 104       for ( int a = 0; a < maxDepth; a++ )
 105         sums[ a ] = 0;
 106     }
 107   }
 108
 109   /*
 110   SumType sumDifference( const SumGroup& rhs ) const {
 111     SumType ret = 0;
 112     for( int a = 0; a < maxDepth; a++ ) {
 113       SumType dif;
 114       if( sums[a] > rhs.sums[a] )
 115         dif = sums[a] - rhs.sums[a];
 116       else
 117         dif = rhs.sums[a] - sums[a];
 118
 119       ret += ( dif * (maxDepth - a ) ) >> a;
 120     }
 121     return ret;
 122   };*/
 123
 124   struct VecSumGetter {
 125     SumType** sumVec;
 126     VecSumGetter() : sumVec( 0 ) {}
 127     VecSumGetter( SumType** vec ) : sumVec( vec ) {}
 128
 129     inline bool sumValid( const uint num ) const {
 130       return ( bool ) sumVec[ num ];
 131     }
 132
 133
 134     inline SumType sum( const uint num ) const {
 135       return * ( sumVec[ num ] );
 136     }
 137   };
 138
 139   struct ZeroGetter {
 140     inline bool sumValid( const uint num ) const {
 141       return false;
 142     }
 143     inline SumType sum( const uint num ) const {
 144       return 0;
 145     }
 146   };
 147
 148   struct GroupSumGetter {
 149     SumGroup& group;
 150     GroupSumGetter( SumGroup& grp ) : group( grp ) {}
 151
 152     inline bool sumValid( const uint num ) const {
 153       return true;
 154     }
 155
 156
 157     inline SumType sum( const uint num ) const {
 158       return group.sums[ num ];
 159     }
 160   };
 161
 162   template <class SumGetter>
 163   SumType sumDifference( const SumGetter& getter ) const {
 164     SumType ret = 0;
 165     for ( int a = 0; a < maxDepth; a++ ) {
 166       SumType dif;
 167       if ( getter.sumValid( a ) ) {
 168         if ( sums[ a ] > getter.sum( a ) )
 169           dif = sums[ a ] - getter.sum( a );
 170         else
 171           dif = getter.sum( a ) - sums[ a ];
 172       } else {
 173         dif = sums[ a ];
 174       }
 175
 176       ///The weighting is a bit primitive at the moment
 177       ret += ( dif * ( ( maxDepth - a ) + 1 ) ) /* >> a*/;
 178     }
 179     return ret;
 180   }
 181
 182   template <class Archive>
 183   void serialize( Archive& arch, const uint /*version*/ ) {
 184     arch & sums;
 185   }
 186 };
 187
 188 template < int Condition, class Then, class Else >
 189 struct IfThen {
 190   typedef Then Result;
 191 };
 192
 193 template < class Then, class Else >
 194 struct IfThen <0, Then, Else> {
 195   typedef Else Result;
 196 };
 197
 198
 199 template <int maxDepth, typename SumType, int order, bool dummy>
 200 class DifferenceSumReference {
 201   public:
 202     template <class Archive>
 203     void serialize( Archive& /*arch*/, const uint /*version*/ ) {}
 204 }
 205 ;
 206
 207 template <int maxDepth, class SumType = DEFAULTSUMTYPE, int order = DEFAULTORDER>
 208 class SumReference {
 209     bool valid_;
 210   public:
 211     SumGroup<maxDepth, SumType> leftMarker;
 212     SumGroup<maxDepth, SumType> rightMarker;
 213
 214     DifferenceSumReference < maxDepth, SumType, order - 1, ( order - 1 ) == 0 > nextOrder_;
 215
 216     SumReference() : valid_( false ) {}
 217
 218     template <class Archive>
 219     void serialize( Archive& arch, const uint /*version*/ ) {
 220       arch & valid_ & leftMarker & rightMarker;
 221       arch & nextOrder_;
 222     }
 223
 224     void setValid( bool valid ) {
 225       valid_ = valid;
 226     }
 227
 228     bool isValid() const {
 229       return valid_;
 230     }
 231 };
 232
 233
 234 template <int maxDepth, typename SumType, int order>
 235 struct DifferenceSumReference<maxDepth, SumType, order, false> {
 236   SumReference<maxDepth, SumType, order> reference_;
 237 public:
 238   template <class Archive>
 239   void serialize( Archive& arch, const uint /*version*/ ) {
 240     arch & reference_;
 241   }
 242 };
 243
 244 /** The problem with a single sum-search: 123456| is detected as exactly same as 124356|.
 245  * For that reason a parallel difference-sum-search can be used, which would look like 111111| in the first, and 112(-1)21| in the second case.
 246  * SumType must be signed for that to work.
 247  * */
 248
 249
 250 template <int maxDepth, typename SumType, int order, bool dummy>
 251 class DifferenceSumSearch {
 252   public:
 253     DifferenceSumSearch( const string& /*text*/ ) {}
 254     template <class Type>
 255     void fillReference( Type& /*t*/, int /*position*/ ) {}
 256
 257     template <class PrevType, class Evaluator>
 258     struct FindRefProgress {
 259       FindRefProgress( PrevType& /*t*/, const SumReference < maxDepth, SumType, order + 1 > & /*_ref*/, Evaluator& /*_eval*/ ) {}
 260       SumType leftDiff() {
 261         return 0;
 262       }
 263
 264       SumType rightDiff() {
 265         return 0;
 266       }
 267
 268       void next() {}
 269     }
 270     ;
 271 };
 272
 273
 274 template <class SumType, int Depth, int EndDepth>
 275 struct SumBuildState : public SumBuildState < SumType, Depth + 1, EndDepth > {
 276   typedef SumBuildState< SumType, Depth, EndDepth> Self;
 277   typedef SumBuildState < SumType, Depth + 1, EndDepth > Next;
 278   typedef SumBuildState< SumType, 0, EndDepth> Head;
 279   SumType* v;
 280
 281   uint tempSumC;
 282   SumType tempSum;
 283   const char* text;
 284   const char* ctext;
 285   uint offset;
 286
 287   //uint maxCount = 1<<b;
 288
 289   SumBuildState( PrimitiveVector<SumType>* sumVecs_, const char* tx ) : Next( sumVecs_, tx ), tempSumC( 0 ), tempSum( 0 ), text( tx ), ctext( tx ), offset( 0 ) {
 290     v = &( sumVecs_[ Depth ][ 0 ] );
 291   }
 292
 293   inline void go1( register const char* ctex, register const uint offset ) {
 294     Next::go1( ctex, offset );
 295     {
 296       if ( tempSumC == ( uint ) ( 1 << Depth ) ) {
 297         ///remove the first summand
 298         tempSum -= *( ctex - ( 1 << Depth ) );
 299       } else {
 300         tempSumC ++;
 301       }
 302
 303       tempSum += *ctex;
 304       ( * ( v + offset ) ) = tempSum;
 305     }
 306   }
 307
 308   /*  inline void go2( register uint offset ) {
 309       Next::go2( offset );
 310       //++v;
 311   }*/
 312
 313   inline void go() {
 314     go1( ctext, offset );
 315
 316     //go2( offset );
 317
 318     ++ctext;
 319     ++offset;
 320   }
 321 };
 322
 323 template <class SumType, int Depth>
 324 struct SumBuildState<SumType, Depth, Depth> {
 325   SumBuildState( PrimitiveVector<SumType>*, const char* ) {}
 326   ;
 327
 328   inline void go1( register const char* ctex, register const uint offset ) {}
 329   //  inline void go2() {
 330   //  }
 331 }
 332 ;
 333
 334
 335 template <int maxDepth, typename SumType = DEFAULTSUMTYPE, int order = DEFAULTORDER>
 336 class SumSearch {
 337     typedef SumSearch<maxDepth, SumType, order> SelfSumSearch;
 338     typedef PrimitiveVector< SumType > SumVector;
 339     string text_;
 340     SumVector sumVecs_[ maxDepth ];
 341     typedef DifferenceSumSearch < maxDepth, SumType, order - 1, ( order - 1 ) == 0 > NextOrderType;
 342
 343 #ifdef STATEBASEDBUILD
 344
 345     void buildSumGroups() {
 346       for ( int a = 0; a < maxDepth; a++ ) {
 347         sumVecs_[ a ].rawResize( text_.size() );
 348       }
 349
 350       SumBuildState< SumType, 0, maxDepth > state( sumVecs_, text_.c_str() );
 351
 352       uint textSize = text_.size();
 353
 354       for ( uint a = 0; a < textSize; a++ ) {
 355         state.go();
 356       }
 357     }
 358 #else
 359     void buildSumGroups() {
 360       for ( int a = 0; a < maxDepth; a++ ) {
 361         sumVecs_[ a ].rawResize( text_.size() );
 362       }
 363
 364       const char* text = text_.c_str();
 365       uint textSize = text_.size();
 366
 367       for ( uint b = 0; b < maxDepth; b++ ) {
 368
 369         SumType* v = &( sumVecs_[ b ][ 0 ] );
 370         uint tempSumC = 0;
 371         SumType tempSum = 0;
 372         uint maxCount = 1 << b;
 373
 374         const char* ctext = text;
 375
 376         for ( uint a = 0; a < textSize; a++ ) {
 377           if ( tempSumC == maxCount ) {
 378             ///remove the first summand
 379             tempSum -= *( ctext - maxCount );
 380           } else {
 381             tempSumC ++;
 382           }
 383
 384           tempSum += ( *ctext );
 385
 386           ( *v ) = tempSum;
 387           ++v;
 388           ++ctext;
 389         }
 390       }
 391     }
 392 #endif
 393
 394   public:
 395     NextOrderType nextOrder_;
 396
 397     SumSearch( const string& text ) : nextOrder_( text ) {
 398       text_ = text;
 399       buildSumGroups();
 400     }
 401
 402     ///position != 0
 403     SumReference<maxDepth, SumType, order> getReference( int position ) {
 404       SumReference<maxDepth, SumType, order> ret;
 405       fillReference( ret, position );
 406
 407       nextOrder_.fillReference( ret, position );
 408       return ret;
 409     }
 410
 411
 412     ///Should not be used from outside
 413     void fillReference( SumReference<maxDepth, SumType, order>& ret, int position ) {
 414       int leftPos = position - 1;
 415       SumType leftSums[ maxDepth ];
 416       SumType rightSums[ maxDepth ];
 417
 418       if ( leftPos >= 0 ) {
 419         for ( int a = 0; a < maxDepth; a++ )
 420           leftSums[ a ] = sumVecs_[ a ] [ leftPos ];
 421       } else {
 422         for ( int a = 0; a < maxDepth; a++ )
 423           leftSums[ a ] = 0;
 424       }
 425
 426       for ( int a = 0; a < maxDepth; a++ ) {
 427         uint pos = leftPos + ( 1 << a );
 428         if ( pos < sumVecs_[ 0 ].size() )
 429           rightSums[ a ] = sumVecs_[ a ][ pos ];
 430         else
 431           rightSums[ a ] = 0;
 432       }
 433
 434       ret.leftMarker = SumGroup<maxDepth, SumType>( leftSums );
 435       ret.rightMarker = SumGroup<maxDepth, SumType>( rightSums );
 436       ret.setValid( true );
 437     }
 438
 439
 440     struct SimpleEvaluator {
 441       SumType minDif;
 442       uint minDifPos;
 443
 444       SimpleEvaluator() : minDif( 100000 ), minDifPos( -1 ) {}
 445       /**This should return a new compound difference-value. In the end, the position with the lowest difference will be returned,
 446         *so this may be used to implement some weighting, maybe according to the position */
 447       inline void operator () ( const SumType leftDifference, const SumType rightDifference, const uint position ) {
 448         SumType dif = ( leftDifference + 1 ) * ( rightDifference + 1 );
 449
 450         if ( dif < minDif ) {
 451           //cout << "best dif: " << dif << endl;
 452           minDif = dif;
 453           minDifPos = position;
 454         }
 455       }
 456
 457       uint result() {
 458         return minDifPos;
 459       }
 460     };
 461
 462     SumVector* sumVecs() {
 463       return sumVecs_;
 464     }
 465
 466     template <class Evaluator>
 467     struct FindReferenceProgress {
 468       SumReference<maxDepth, SumType, order>& ref;
 469       Evaluator& eval;
 470
 471       typename NextOrderType::template FindRefProgress<SelfSumSearch, Evaluator>
 472       nextOrder_;
 473
 474       SumType* leftOffset[ maxDepth ];
 475       SumType* rightOffset[ maxDepth ];
 476
 477       SumType* firstItem;
 478       SumType* finalRight[ maxDepth ];
 479
 480       SumVector* sumVecs_;
 481
 482       typename SumGroup<maxDepth, SumType>::VecSumGetter leftGetter;
 483       typename SumGroup<maxDepth, SumType>::VecSumGetter rightGetter;
 484       typedef typename SumGroup<maxDepth, SumType>::ZeroGetter ZeroGetter;
 485
 486       FindReferenceProgress( SelfSumSearch& search, const SumReference<maxDepth, SumType, order>& _ref, Evaluator& _eval ) : ref( const_cast<SumReference<maxDepth, SumType, order>&>( _ref ) ), eval( _eval ), nextOrder_( search, ref, _eval ), sumVecs_( search.sumVecs() ) {
 487         for ( uint a = 0; a < maxDepth; a++ ) {
 488           leftOffset[ a ] = &( sumVecs_[ a ][ 0 - 1 ] );
 489
 490           if ( ( uint ) ( 1 << a ) < ( uint ) sumVecs_[ 0 ].size() ) {
 491             rightOffset[ a ] = &( sumVecs_[ a ][ ( 1 << a ) - 1 ] );
 492           } else {
 493             rightOffset[ a ] = 0;
 494           }
 495         }
 496
 497         firstItem = &sumVecs_[ 0 ][ 0 ];
 498
 499         for ( int a = 0; a < maxDepth; a++ )
 500           finalRight[ a ] = &( sumVecs_[ a ][ sumVecs_[ a ].size() - 1 ] );
 501
 502         leftGetter = typename SumGroup<maxDepth, SumType>::VecSumGetter( leftOffset );
 503         rightGetter = typename SumGroup<maxDepth, SumType>::VecSumGetter( rightOffset );
 504       }
 505
 506       operator bool() {
 507         return ( bool ) rightOffset[ 0 ];
 508       }
 509
 510       void next() {
 511         for ( int a = 0; a < maxDepth; a++ ) {
 512           ++leftOffset[ a ];
 513           if ( !rightOffset[ a ] )
 514             break;
 515           ++rightOffset[ a ];
 516           if ( rightOffset[ a ] > finalRight[ a ] )
 517             rightOffset[ a ] = 0;
 518         }
 519         nextOrder_.next();
 520       }
 521
 522       SumType leftDiff() {
 523         if ( leftOffset[ 0 ] < firstItem ) {
 524           return ref.leftMarker.sumDifference( ZeroGetter() ) + nextOrder_.leftDiff();
 525         }
 526         return ref.leftMarker.sumDifference( leftGetter ) + nextOrder_.leftDiff();
 527       }
 528
 529       SumType rightDiff() {
 530         return ref.rightMarker.sumDifference( rightGetter ) + nextOrder_.rightDiff();
 531       }
 532
 533       uint difPos() {
 534         return ( ((unsigned long)rightOffset[ 0 ] ) - (unsigned long)firstItem ) / sizeof( uint* );
 535       }
 536     };
 537
 538     template <class Evaluator>
 539     int findReference( const SumReference<maxDepth, SumType, order>& ref, Evaluator& eval ) {
 540       if ( !ref.isValid() )
 541         return -1;
 542       if ( sumVecs_[ 0 ].size() < 2 )
 543         return -1;
 544
 545       FindReferenceProgress<Evaluator> prog( *this, ref, eval );
 546
 547       while ( prog ) {
 548         SumType leftDif = 0; //prog.leftDiff();
 549         SumType rightDif = prog.rightDiff();
 550         uint difPos = prog.difPos();
 551
 552         eval( leftDif, rightDif, difPos );
 553
 554         prog.next();
 555       }
 556       return eval.result();
 557     }
 558
 559     ///This uses the default-evaluator
 560     inline int findReference( const SumReference<maxDepth, SumType, order>& ref ) {
 561       SimpleEvaluator eval;
 562       return findReference( ref, eval );
 563     }
 564 };
 565
 566
 567 template <int maxDepth, typename SumType, int order>
 568 class DifferenceSumSearch<maxDepth, SumType, order, false> {
 569     typedef SumSearch<maxDepth, SumType, order> MySearch;
 570     typedef SumSearch < maxDepth, SumType, order + 1 > MyPrevSearch;
 571     MySearch search_;
 572
 573     static string makeDifference( const string& str ) {
 574       string ret = str;
 575       uint len = ret.length();
 576       char last = 0;
 577       if ( !ret.empty() )
 578         last = ret[ 0 ];
 579
 580       for ( uint n = 0; n < len; n++ ) {
 581         char r = ret[ n ];
 582         ret[ n ] = r - last;
 583         last = r;
 584       }
 585       return ret;
 586     }
 587
 588   public:
 589     DifferenceSumSearch( const string& text ) : search_( makeDifference( text ) ) {}
 590
 591     template <class Type>
 592     void fillReference( Type& t, int position ) {
 593       search_.fillReference( t.nextOrder_.reference_, position );
 594     }
 595
 596     template <class PrevSearch, class Evaluator>
 597     struct FindRefProgress {
 598       typename MySearch:: template FindReferenceProgress<Evaluator>
 599       find;
 600
 601       FindRefProgress( PrevSearch& search, const SumReference < maxDepth, SumType, order + 1 > & _ref, Evaluator& _eval ) : find( search.nextOrder_.search_, _ref.nextOrder_.reference_, _eval )
 602       {}
 603
 604       SumType leftDiff() {
 605         return find.leftDiff();
 606       }
 607       SumType rightDiff() {
 608         return find.rightDiff();
 609       }
 610
 611       void next() {
 612         find.next();
 613       }
 614     };
 615 };
 616
 617
 618 } //FuzzySearch
 619
 620 using namespace FuzzySearch;
 621
 622 #endif
 623
 624 // kate: space-indent on; indent-width 2; tab-width 2; replace-tabs on