From b6bab4f8cfb7bd1d7276e2c194c44d8df67afea4 Mon Sep 17 00:00:00 2001
From: paul <paul@d708f5d6-7413-0410-9779-e7cbd77b26cf>
Date: Thu, 3 Jun 2010 15:58:15 +0000
Subject: [PATCH] Sequence::contains() and Sequence::overlaps() now use
 pitch-based indexing to speed things up in pathological cases

git-svn-id: http://subversion.ardour.org/svn/ardour2/ardour2/branches/3.0@7221 d708f5d6-7413-0410-9779-e7cbd77b26cf
---
 libs/evoral/evoral/Sequence.hpp | 34 +++++++++++++++++++--------
 libs/evoral/src/Sequence.cpp    | 52 ++++++++++++++++++++++++++---------------
 2 files changed, 57 insertions(+), 29 deletions(-)

diff --git a/libs/evoral/evoral/Sequence.hpp b/libs/evoral/evoral/Sequence.hpp
index acfe6970e..ae9ab0510 100644
--- a/libs/evoral/evoral/Sequence.hpp
+++ b/libs/evoral/evoral/Sequence.hpp
@@ -137,10 +137,6 @@ public:
 	inline       Notes& notes()       { return _notes; }
 	inline const Notes& notes() const { return _notes; }
 
-	typedef std::multiset<boost::shared_ptr< Note<Time> >, NoteNumberComparator>  Pitches;
-	inline       Pitches& pitches(uint8_t chan)       { return _pitches[chan&0xf]; }
-        inline const Pitches& pitches(uint8_t chan) const { return _pitches[chan&0xf]; }
-
         enum NoteOperator { 
                 PitchEqual,
                 PitchLessThan,
@@ -157,8 +153,19 @@ public:
         void get_notes (Notes&, NoteOperator, uint8_t val, int chan_mask = 0) const;
 
         void remove_overlapping_notes ();
+        void trim_overlapping_notes ();
         void remove_duplicate_notes ();
 
+        enum OverlapPitchResolution { 
+                LastOnFirstOff,
+                FirstOnFirstOff
+        };
+
+        bool overlapping_pitches_accepted() const { return _overlapping_pitches_accepted; }
+        void overlapping_pitches_accepted(bool yn)  { _overlapping_pitches_accepted = yn; }
+        OverlapPitchResolution overlap_pitch_resolution() const { return _overlap_pitch_resolution; }
+        void set_overlap_pitch_resolution(OverlapPitchResolution opr);
+
 	void set_notes (const Sequence<Time>::Notes& n);
 
 	typedef std::vector< boost::shared_ptr< Event<Time> > > SysExes;
@@ -224,8 +231,8 @@ public:
 	bool edited() const      { return _edited; }
 	void set_edited(bool yn) { _edited = yn; }
 
-        bool overlaps (const boost::shared_ptr< Note<Time> > ev) const;
-        bool contains (const boost::shared_ptr< Note<Time> > ev) const;
+        bool overlaps (const boost::shared_ptr< Note<Time> >& ev) const;
+        bool contains (const boost::shared_ptr< Note<Time> >& ev) const;
 
 	bool add_note_unlocked(const boost::shared_ptr< Note<Time> > note);
 	void remove_note_unlocked(const boost::shared_ptr< const Note<Time> > note);
@@ -233,15 +240,22 @@ public:
 	uint8_t lowest_note()  const { return _lowest_note; }
 	uint8_t highest_note() const { return _highest_note; }
 
+
 protected:
-	bool                 _edited;
-	mutable Glib::RWLock _lock;
+	bool                   _edited;
+        bool                   _overlapping_pitches_accepted;
+        OverlapPitchResolution _overlap_pitch_resolution;
+	mutable Glib::RWLock   _lock;
 
 private:
 	friend class const_iterator;
 
-        bool overlaps_unlocked (const boost::shared_ptr< Note<Time> > ev) const;
-        bool contains_unlocked (const boost::shared_ptr< Note<Time> > ev) const;
+	typedef std::multiset<boost::shared_ptr< Note<Time> >, NoteNumberComparator>  Pitches;
+	inline       Pitches& pitches(uint8_t chan)       { return _pitches[chan&0xf]; }
+        inline const Pitches& pitches(uint8_t chan) const { return _pitches[chan&0xf]; }
+
+        bool overlaps_unlocked (const boost::shared_ptr< Note<Time> >& ev) const;
+        bool contains_unlocked (const boost::shared_ptr< Note<Time> >& ev) const;
 
         void append_note_on_unlocked (boost::shared_ptr< Note<Time> >);
         void append_note_off_unlocked(boost::shared_ptr< Note<Time> >);
diff --git a/libs/evoral/src/Sequence.cpp b/libs/evoral/src/Sequence.cpp
index 0931ec785..4b9fed035 100644
--- a/libs/evoral/src/Sequence.cpp
+++ b/libs/evoral/src/Sequence.cpp
@@ -381,6 +381,8 @@ Sequence<Time>::const_iterator::operator=(const const_iterator& other)
 template<typename Time>
 Sequence<Time>::Sequence(const TypeMap& type_map)
 	: _edited(false)
+        , _overlapping_pitches_accepted (true)
+        , _overlap_pitch_resolution (FirstOnFirstOff)
 	, _type_map(type_map)
 	, _writing(false)
 	, _end_iter(*this, DBL_MAX)
@@ -397,6 +399,8 @@ template<typename Time>
 Sequence<Time>::Sequence(const Sequence<Time>& other)
 	: ControlSet (other)
         , _edited(false)
+        , _overlapping_pitches_accepted (other._overlapping_pitches_accepted)
+        , _overlap_pitch_resolution (other._overlap_pitch_resolution)
 	, _type_map(other._type_map)
 	, _writing(false)
 	, _end_iter(*this, DBL_MAX)
@@ -583,14 +587,10 @@ Sequence<Time>::add_note_unlocked(const boost::shared_ptr< Note<Time> > note)
 
 	DEBUG_TRACE (DEBUG::Sequence, string_compose ("%1 add note %2 @ %3\n", this, (int)note->note(), note->time()));
 
-        if (contains_unlocked (note)) {
+        if (!_overlapping_pitches_accepted && overlaps_unlocked (note)) {
                 return false;
 	}
 
-        if (overlaps_unlocked (note)) {
-                return false;
-        }
-
 	_edited = true;
 
 	if (note->note() < _lowest_note)
@@ -767,6 +767,8 @@ Sequence<Time>::remove_note_unlocked(const boost::shared_ptr< const Note<Time> >
             format.
          */
 
+         /* XXX use _overlap_pitch_resolution to determine FIFO/LIFO ... */
+
          for (typename WriteNotes::iterator n = _write_notes[note->channel()].begin(); n != _write_notes[note->channel()].end(); ++n) {
                  boost::shared_ptr< Note<Time> > nn = *n;
                  if (note->note() == nn->note() && nn->channel() == note->channel()) {
@@ -815,28 +817,33 @@ Sequence<Time>::remove_note_unlocked(const boost::shared_ptr< const Note<Time> >
 
  template<typename Time>
  bool
- Sequence<Time>::contains (const boost::shared_ptr< Note<Time> > note) const
+ Sequence<Time>::contains (const boost::shared_ptr< Note<Time> >& note) const
  {
          return contains_unlocked (note);
  }
 
  template<typename Time>
  bool
- Sequence<Time>::contains_unlocked (const boost::shared_ptr< Note<Time> > note) const
+ Sequence<Time>::contains_unlocked (const boost::shared_ptr< Note<Time> >& note) const
  {
-         for (typename Sequence<Time>::Notes::const_iterator i = note_lower_bound(note->time());
-                         i != _notes.end() && (*i)->time() == note->time(); ++i) {
-                 if (*i == note) {
+         const Pitches& p (pitches (note->channel()));
+         boost::shared_ptr< Note<Time> > search_note(new Note<Time>(0, 0, 0, 0, note->note()));
+
+         for (typename Pitches::const_iterator i = p.lower_bound (search_note); 
+              i != p.end() && (*i)->note() == note->note(); ++i) {
+
+                 if (**i == *note) {
                          cerr << "Existing note matches: " << *i << endl;
                          return true;
                  }
          }
+
          return false;
  }
 
  template<typename Time>
  bool
- Sequence<Time>::overlaps (const boost::shared_ptr< Note<Time> > note) const
+ Sequence<Time>::overlaps (const boost::shared_ptr< Note<Time> >& note) const
  {
          ReadLock lock (read_lock());
          return overlaps_unlocked (note);
@@ -844,17 +851,16 @@ Sequence<Time>::remove_note_unlocked(const boost::shared_ptr< const Note<Time> >
 
  template<typename Time>
  bool
- Sequence<Time>::overlaps_unlocked (const boost::shared_ptr< Note<Time> > note) const
+ Sequence<Time>::overlaps_unlocked (const boost::shared_ptr< Note<Time> >& note) const
  {
          Time sa = note->time();
          Time ea  = note->end_time();
+         
+         const Pitches& p (pitches (note->channel()));
+         boost::shared_ptr< Note<Time> > search_note(new Note<Time>(0, 0, 0, 0, note->note()));
 
-         for (typename Sequence<Time>::Notes::const_iterator i = note_lower_bound (note->time()); i != _notes.end(); ++i) {
-
-                 if ((note->note() != (*i)->note()) ||
-                     (note->channel() != (*i)->channel())) {
-                         continue;
-                 }
+         for (typename Pitches::const_iterator i = p.lower_bound (search_note); 
+              i != p.end() && (*i)->note() == note->note(); ++i) {
 
                  Time sb = (*i)->time();
                  Time eb = (*i)->end_time();
@@ -888,7 +894,6 @@ Sequence<Time>::remove_note_unlocked(const boost::shared_ptr< const Note<Time> >
          return i;
  }
 
-
 template<typename Time>
 void
 Sequence<Time>::get_notes (Notes& n, NoteOperator op, uint8_t val, int chan_mask) const
@@ -1012,6 +1017,15 @@ Sequence<Time>::get_notes_by_velocity (Notes& n, NoteOperator op, uint8_t val, i
         }
 }
 
+template<typename Time>
+void
+Sequence<Time>::set_overlap_pitch_resolution (OverlapPitchResolution opr)
+{
+        _overlap_pitch_resolution = opr;
+
+        /* XXX todo: clean up existing overlaps in source data? */
+}
+
 template class Sequence<Evoral::MusicalTime>;
 
 } // namespace Evoral
-- 
2.11.4.GIT