Chris@181: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
Chris@181: 
Chris@181: /*
Chris@181:   Silvet
Chris@181: 
Chris@181:   A Vamp plugin for note transcription.
Chris@181:   Centre for Digital Music, Queen Mary University of London.
Chris@181:   This file Copyright 2012 Chris Cannam.
Chris@181:     
Chris@181:   This program is free software; you can redistribute it and/or
Chris@181:   modify it under the terms of the GNU General Public License as
Chris@181:   published by the Free Software Foundation; either version 2 of the
Chris@181:   License, or (at your option) any later version.  See the file
Chris@181:   COPYING included with this distribution for more information.
Chris@181: */
Chris@181: 
Chris@181: #ifndef AGENT_FEEDER_POLY_H
Chris@181: #define AGENT_FEEDER_POLY_H
Chris@181: 
Chris@181: #include "AgentFeeder.h"
Chris@181: 
Chris@181: #include <cassert>
Chris@184: #include <stdexcept>
Chris@181: 
Chris@188: //#define DEBUG_FEEDER 1
Chris@181: 
Chris@181: /**
Chris@181:  * Take a series of observations or estimates (one at a time) and feed
Chris@181:  * them to a set of agent hypotheses, creating a new candidate agent
Chris@181:  * for each observation and also testing the observation against the
Chris@181:  * existing set of hypotheses.
Chris@181:  *
Chris@181:  *!!! -- todo: document poly-ness of it
Chris@181:  *
Chris@181:  * Call feed() to provide a new observation. Call finish() when all
Chris@181:  * observations have been provided. The set of hypotheses returned by
Chris@181:  * getAcceptedHypotheses() will not be complete unless finish() has
Chris@181:  * been called.
Chris@181:  */
Chris@181: template <typename Hypothesis>
Chris@181: class AgentFeederPoly : public AgentFeeder
Chris@181: {
Chris@181: private:
Chris@184:     typedef std::vector<Hypothesis> Hypotheses;
Chris@184: 
Chris@181:     struct State {
Chris@181:         Hypotheses provisional;
Chris@181:         Hypotheses satisfied;
Chris@181:         Hypotheses completed;
Chris@181:     };
Chris@181:     State m_state;
Chris@181: 
Chris@181: public:
Chris@181:     AgentFeederPoly() { }
Chris@181: 
Chris@181:     virtual void feed(AgentHypothesis::Observation o) {
Chris@181: #ifdef DEBUG_FEEDER        
Chris@184:         std::cerr << "\nfeed: have observation [value = " << o.value << ", time = " << o.time << "]" << std::endl;
Chris@181: #endif
Chris@181: 
Chris@184:         m_state = update(m_state, o);
Chris@181:     }
Chris@181: 
Chris@181:     virtual void finish() {
Chris@181: #ifdef DEBUG_FEEDER        
Chris@181:         std::cerr << "finish: satisfied count == " << m_state.satisfied.size() << std::endl;
Chris@181: #endif
Chris@181:         for (typename Hypotheses::const_iterator i = m_state.satisfied.begin();
Chris@181:              i != m_state.satisfied.end(); ++i) {
Chris@184:             m_state.completed.push_back(*i);
Chris@181:         }
Chris@181:     }
Chris@181: 
Chris@187:     std::set<Hypothesis> retrieveAcceptedHypotheses() {
Chris@184:         std::set<Hypothesis> hs;
Chris@184:         for (typename Hypotheses::const_iterator i = m_state.completed.begin();
Chris@184:              i != m_state.completed.end(); ++i) {
Chris@190:             Hypothesis h(*i);
Chris@190: #ifdef DEBUG_FEEDER
Chris@190:             std::cerr << "returning accepted hypothesis: strengths: ";
Chris@190:             for (typename Hypothesis::Observations::const_iterator j = 
Chris@190:                      h.getAcceptedObservations().begin(); 
Chris@190:                  j != h.getAcceptedObservations().end(); ++j) {
Chris@190:                 std::cerr << j->confidence << " ";
Chris@190:             }
Chris@190:             std::cerr << std::endl;
Chris@190: #endif
Chris@190:             hs.insert(h);
Chris@184:         }
Chris@187:         m_state.completed.clear();
Chris@184:         return hs;
Chris@181:     }
Chris@181: 
Chris@181: private:
Chris@184:     State update(State s, AgentHypothesis::Observation o) {
Chris@181: 
Chris@181:         /*
Chris@181:           An observation can "belong" to any number of provisional
Chris@181:           hypotheses, but only to one satisfied hypothesis.
Chris@181: 
Chris@181:           A new observation is first offered to the hypotheses that
Chris@181:           have already been satisfied. If one of these accepts it, it
Chris@181:           gets to keep it and no other hypothesis can have it.
Chris@181:          
Chris@181:           Any observation not accepted by a hypothesis in satisfied
Chris@181:           state is then offered to the provisional hypotheses; any
Chris@181:           number of these may accept it. Also, every observation that
Chris@181:           belongs to no satisfied hypothesis is used as the first
Chris@181:           observation in its own new hypothesis (regardless of how
Chris@181:           many other provisional hypotheses have accepted it).
Chris@181: 
Chris@181:           When a hypothesis subsequently becomes satisfied, all other
Chris@181:           provisional hypotheses containing any of its observations
Chris@181:           must be discarded.
Chris@181:         */
Chris@181: 
Chris@184:         State newState;
Chris@184: 
Chris@181:         // We only ever add to the completed hypotheses, never remove
Chris@181:         // anything from them. But we may remove from provisional (if
Chris@181:         // rejected or transferred to satisfied) and satisfied (when
Chris@181:         // completed).
Chris@184:         
Chris@184:         newState.completed = s.completed;
Chris@181:         
Chris@181:         bool swallowed = false;
Chris@181: 
Chris@181:         for (typename Hypotheses::iterator i = s.satisfied.begin();
Chris@181:              i != s.satisfied.end(); ++i) {
Chris@181: 
Chris@181:             Hypothesis h = *i;
Chris@181: 
Chris@181:             assert(h.getState() == Hypothesis::Satisfied);
Chris@181: 
Chris@181:             if (swallowed) {
Chris@181: 
Chris@181:                 // An observation that has already been accepted by a
Chris@181:                 // hypothesis cannot be offered to any other, because
Chris@181:                 // it can only belong to one satisfied hypothesis. Any
Chris@181:                 // subsequent satisfied hypotheses are retained
Chris@181:                 // unchanged in our updated state. We can't test them
Chris@181:                 // for expiry, because the state is only updated when
Chris@181:                 // accept() is called.
Chris@181:                 //!!! That looks like a limitation in the Hypothesis API
Chris@184:                 newState.satisfied.push_back(h);
Chris@181: 
Chris@181:             } else { // !swallowed
Chris@181: 
Chris@181:                 if (h.accept(o)) {
Chris@181: #ifdef DEBUG_FEEDER        
Chris@181:                     std::cerr << "accepted by satisfied hypothesis " << &(*i) << ", state is " << h.getState() << std::endl;
Chris@181: #endif
Chris@181:                     swallowed = true;
Chris@184:                     newState.satisfied.push_back(h);
Chris@181:                 } else if (h.getState() == Hypothesis::Expired) {
Chris@184:                     newState.completed.push_back(h);
Chris@184:                 } else {
Chris@184:                     newState.satisfied.push_back(h);
Chris@181:                 }
Chris@181:             }
Chris@181:         }
Chris@181: 
Chris@181:         if (swallowed) {
Chris@181: 
Chris@181: #ifdef DEBUG_FEEDER        
Chris@181:             std::cerr << "was swallowed by satisfied hypothesis" << std::endl;
Chris@181: #endif
Chris@181:             // no provisional hypotheses have become satisfied, no new
Chris@181:             // ones have been introduced
Chris@184:             newState.provisional = s.provisional;
Chris@181: 
Chris@181:         } else {
Chris@181: 
Chris@181: #ifdef DEBUG_FEEDER        
Chris@181:             std::cerr << "remained unswallowed by " << newState.satisfied.size() << " satisfied hypotheses" << std::endl;
Chris@181: #endif
Chris@181: 
Chris@181:             // not swallowed by any satisfied hypothesis
Chris@181: 
Chris@181:             Hypothesis promoted;
Chris@181:         
Chris@181:             for (typename Hypotheses::iterator i = s.provisional.begin();
Chris@181:                  i != s.provisional.end(); ++i) {
Chris@181: 
Chris@181:                 Hypothesis h = *i;
Chris@181: 
Chris@181:                 assert(h.getState() == Hypothesis::Provisional);
Chris@181: 
Chris@181:                 // can only have one satisfied hypothesis for each
Chris@181:                 // observation, so try this only if promoted has not been
Chris@181:                 // set to something else yet
Chris@181:                 if (promoted == Hypothesis() &&
Chris@181:                     h.accept(o) &&
Chris@181:                     h.getState() == Hypothesis::Satisfied) {
Chris@184:                     newState.satisfied.push_back(h);
Chris@181: #ifdef DEBUG_FEEDER        
Chris@181:                     std::cerr << "promoting a hypothesis to satisfied, have " << newState.satisfied.size() << " satisfied now" << std::endl;
Chris@181: #endif
Chris@181:                     promoted = h;
Chris@181:                 } else if (h.getState() != Hypothesis::Rejected) {
Chris@184:                     newState.provisional.push_back(h);
Chris@181:                 }
Chris@181:             }
Chris@181: 
Chris@181:             if (promoted == Hypothesis()) {
Chris@181: 
Chris@181:                 // No provisional hypothesis has become satisfied
Chris@181: 
Chris@181:                 Hypothesis h;
Chris@181:                 h.accept(o);
Chris@181: 
Chris@181:                 if (h.getState() == Hypothesis::Provisional) {
Chris@184:                     newState.provisional.push_back(h);
Chris@181:                 } else if (h.getState() == Hypothesis::Satisfied) {
Chris@184:                     newState.satisfied.push_back(h);
Chris@181:                 }
Chris@181: 
Chris@181: #ifdef DEBUG_FEEDER        
Chris@181:                 std::cerr << "update: new hypothesis of state " << h.getState() << ", provisional count -> " << newState.provisional.size() << std::endl;
Chris@181: #endif
Chris@184:             } else {
Chris@181: 
Chris@184: #ifdef DEBUG_FEEDER        
Chris@184:                 std::cerr << "a hypothesis became satisfied, reaping its observations" << std::endl;
Chris@184: #endif
Chris@184:                 newState = reap(newState);
Chris@181:             }
Chris@181:         }
Chris@181: 
Chris@184:         return newState;
Chris@181:     }
Chris@181: 
Chris@184:     State reap(State s) {
Chris@181: 
Chris@181:         // "When a hypothesis subsequently becomes satisfied, all
Chris@181:         // other provisional hypotheses containing any of its
Chris@181:         // observations must be discarded."
Chris@181: 
Chris@184:         if (s.provisional.empty()) return s;
Chris@181: 
Chris@181:         int reaped = 0;
Chris@181: 
Chris@184:         Hypotheses prior = s.provisional;
Chris@184:         s.provisional = Hypotheses();
Chris@181: 
Chris@184:         for (typename Hypotheses::const_iterator hi = prior.begin();
Chris@184:              hi != prior.end(); ++hi) {
Chris@181:                     
Chris@181:             const AgentHypothesis::Observations obs =
Chris@181:                 hi->getAcceptedObservations();
Chris@181: 
Chris@181:             bool keep = true;
Chris@181: 
Chris@181:             for (AgentHypothesis::Observations::const_iterator oi = obs.begin();
Chris@181:                  oi != obs.end(); ++oi) {
Chris@181: 
Chris@181:                 for (typename Hypotheses::const_iterator si = s.satisfied.end();
Chris@181:                      si != s.satisfied.begin(); ) {
Chris@181:                 
Chris@181:                     --si;
Chris@181: 
Chris@181:                     const AgentHypothesis::Observations sobs = 
Chris@181:                         si->getAcceptedObservations();
Chris@181: 
Chris@181:                     if (sobs.find(*oi) != sobs.end()) {
Chris@181:                         keep = false;
Chris@181:                         break;
Chris@181:                     }
Chris@181:                 }
Chris@181: 
Chris@181:                 if (!keep) {
Chris@181:                     break;
Chris@181:                 }
Chris@181:             }
Chris@181: 
Chris@184:             if (keep) {
Chris@184:                 s.provisional.push_back(*hi);
Chris@184:             } else {
Chris@181:                 ++reaped;
Chris@181:             }
Chris@181:         }
Chris@181: 
Chris@181: #ifdef DEBUG_FEEDER
Chris@181:         std::cerr << "reap: have "
Chris@181:                   << s.satisfied.size() << " satisfied, "
Chris@181:                   << s.provisional.size() << " provisional, "
Chris@181:                   << s.completed.size() << " completed, reaped "
Chris@181:                   << reaped << std::endl;
Chris@181: #endif
Chris@184: 
Chris@184:         return s;
Chris@181:     }
Chris@181: };
Chris@181: 
Chris@181: #endif