/* * This is the Loris C++ Class Library, implementing analysis, * manipulation, and synthesis of digitized sounds using the Reassigned * Bandwidth-Enhanced Additive Sound Model. * * Loris is Copyright (c) 1999-2010 by Kelly Fitz and Lippold Haken * * 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 * * * Sieve.C * * Implementation of class Sieve. * * Lippold Haken, 20 Jan 2001 * loris@cerlsoundgroup.org * * http://www.cerlsoundgroup.org/Loris/ * */ #if HAVE_CONFIG_H #include "config.h" #endif #include "Sieve.h" #include "Breakpoint.h" #include "LorisExceptions.h" #include "Notifier.h" #include "Partial.h" #include "PartialList.h" #include "PartialUtils.h" #include // begin namespace namespace Loris { // --------------------------------------------------------------------------- // Sieve constructor // --------------------------------------------------------------------------- //! Construct a new Sieve using the specified partial fade //! time. If unspecified, the default fade time (same as the //! default fade time for the Distiller) is used. //! //! \param partialFadeTime is the extra time (in seconds) //! added to each end of a Partial to accomodate //! the fade to and from zero amplitude. Fade time //! must be non-negative. A default value is used //! if unspecified. //! \throw InvalidArgument if partialFadeTime is negative. // Sieve::Sieve( double partialFadeTime ) : _fadeTime( partialFadeTime ) { if ( _fadeTime < 0.0 ) { Throw( InvalidArgument, "the Partial fade time must be non-negative" ); } } // Definition of a comparitor for sorting a collection of pointers // to Partials by label (increasing) and duration (decreasing), so // that Partial ptrs are arranged by label, with the lowest labels // first, and then with the longest Partials having each label // before the shorter ones. struct SortPartialPtrs : public std::binary_function< const Partial *, const Partial *, bool > { bool operator()( const Partial * lhs, const Partial * rhs ) const { return ( lhs->label() != rhs->label() ) ? ( lhs->label() < rhs->label() ) : ( lhs->duration() > rhs->duration() ); } }; // Definition of predicate for finding the end of a Patial * // range having a common label. struct PartialPtrLabelNE : public std::unary_function< const Partial *, bool > { int label; PartialPtrLabelNE( int l ) : label(l) {} bool operator()( const Partial * p ) const { return p->label() != label; } }; // --------------------------------------------------------------------------- // find_overlapping (template function) // --------------------------------------------------------------------------- // Iterate over a range of Partials (presumably) with same labeling. // The range is specified by iterators over a collection of pointers // to Partials (not Partials themselves). Return the first position // in the specified range corresponding to a Partial that overlaps // (in time) the specified Partial, p, or the end of the range if // no Partials in the range overlap. // // Overlap is defined by the minimum time gap between Partials // (minGapTime), so Partials that have less then minGapTime // between them are considered overlapping. // template // Iter is the position of a Partial * Iter find_overlapping( Partial & p, double minGapTime, Iter start, Iter end) { for ( Iter it = start; it != end; ++it ) { // skip if other partial is already sifted out. if ( (*it)->label() == 0 ) continue; // skip the source Partial: // (identity test: compare addresses) // (this is a sanity check, should not happen since // src should be at position end) Assert( (*it) != &p ); // test for overlap: if ( p.startTime() < (*it)->endTime() + minGapTime && p.endTime() + minGapTime > (*it)->startTime() ) { // Does the overlapping Partial have longer duration? // (this should never be true, since the Partials // are sorted by duration) Assert( p.duration() <= (*it)->duration() ); #if Debug_Loris debugger << "Partial starting " << p.startTime() << ", " << p.begin().breakpoint().frequency() << " ending " << p.endTime() << ", " << (--p.end()).breakpoint().frequency() << " zapped by overlapping Partial starting " << (*it)->startTime() << ", " << (*it)->begin().breakpoint().frequency() << " ending " << (*it)->endTime() << ", " << (--(*it)->end()).breakpoint().frequency() << endl; #endif return it; } } // no overlapping Partial found: return end; } // --------------------------------------------------------------------------- // sift_ptrs (private helper) // --------------------------------------------------------------------------- //! Sift labeled Partials. If any two Partials having the same (non-zero) //! label overlap in time (where overlap includes the fade time at both //! ends of each Partial), then set the label of the Partial having the //! shorter duration to zero. Sifting is performed on a collection of //! pointers to Partials so that the it can be performed without changing //! the order of the Partials in the sequence. //! //! \param ptrs is a collection of pointers to the Partials in the //! sequence to be sifted. void Sieve::sift_ptrs( PartialPtrs & ptrs ) { // the minimum gap between Partials is twice the // specified fadeTime: double minGapTime = _fadeTime * 2.; // sort the collection of pointers to Partials: // (sort is by increasing label, then // decreasing duration) std::sort( ptrs.begin(), ptrs.end(), SortPartialPtrs() ); PartialPtrs::iterator sift_begin = ptrs.begin(); PartialPtrs::iterator sift_end = ptrs.end(); int zapped = 0; // iterate over labels and sift each one: PartialPtrs::iterator lowerbound = sift_begin; while ( lowerbound != sift_end ) { int label = (*lowerbound)->label(); // first the first element in l after sieve_begin // having a label not equal to 'label': PartialPtrs::iterator upperbound = std::find_if( lowerbound, sift_end, PartialPtrLabelNE(label) ); #ifdef Debug_Loris // don't want to compute this iterator distance unless debugging: debugger << "sifting Partials labeled " << label << endl; debugger << "Sieve found " << std::distance( lowerbound, upperbound ) << " Partials labeled " << label << endl; #endif // sift all partials with this label, unless the // label is 0: if ( label != 0 ) { PartialPtrs::iterator it; for ( it = lowerbound; it != upperbound; ++it ) { // find_overlapping only needs to consider Partials on the // half-open range [lowerbound, it), because all // Partials after it are shorter, thanks to the // sorting of the sift_set: if( it != find_overlapping( **it, minGapTime, lowerbound, it ) ) { (*it)->setLabel(0); ++zapped; } } } // advance Partial set iterator: lowerbound = upperbound; } #ifdef Debug_Loris debugger << "Sifted out (relabeled) " << zapped << " of " << ptrs.size() << "." << endl; #endif } } // end of namespace Loris