Use set over vector for Sequence::Notes, for logarithmic search by time.

git-svn-id: svn://localhost/ardour2/branches/3.0@5798 d708f5d6-7413-0410-9779-e7cbd77b26cf

4 files changed, 37 insertions, 33 deletions

diff --git a/libs/evoral/evoral/Sequence.hpp b/libs/evoral/evoral/Sequence.hpp
index b4e11ba808..22d81b6948 100644
--- a/libs/evoral/evoral/Sequence.hpp
+++ b/libs/evoral/evoral/Sequence.hpp
@@ -61,7 +61,7 @@ public:
 template<typename Time>
 class Sequence : virtual public ControlSet {
 public:
-	Sequence(const TypeMap& type_map, size_t size=0);
+	Sequence(const TypeMap& type_map);
 
 	void write_lock();
 	void write_unlock();
@@ -78,12 +78,8 @@ public:
 	bool writing() const { return _writing; }
 	void end_write(bool delete_stuck=false);
 
-	/** Resizes vector if necessary (NOT realtime safe) */
 	void append(const Event<Time>& ev);
 
-	inline const boost::shared_ptr< const Note<Time> > note_at(size_t i) const { return _notes[i]; }
-	inline const boost::shared_ptr< Note<Time> >       note_at(size_t i)       { return _notes[i]; }
-
 	inline size_t n_notes() const { return _notes.size(); }
 	inline bool   empty()   const { return _notes.size() == 0 && ControlSet::controls_empty(); }
 
@@ -92,6 +88,20 @@ public:
 		return a->time() < b->time();
 	}
 
+	struct NoteNumberComparator {
+		inline bool operator()(const boost::shared_ptr< const Note<Time> > a,
+		                       const boost::shared_ptr< const Note<Time> > b) const {
+			return a->note() < b->note();
+		}
+	};
+
+	struct EarlierNoteComparator {
+		inline bool operator()(const boost::shared_ptr< const Note<Time> > a,
+		                       const boost::shared_ptr< const Note<Time> > b) const {
+			return a->time() < b->time();
+		}
+	};
+
 	struct LaterNoteComparator {
 		typedef const Note<Time>* value_type;
 		inline bool operator()(const boost::shared_ptr< const Note<Time> > a,
@@ -108,7 +118,7 @@ public:
 		}
 	};
 
-	typedef std::vector< boost::shared_ptr< Note<Time> > > Notes;
+	typedef std::set<boost::shared_ptr< Note<Time> >, EarlierNoteComparator> Notes;
 	inline       Notes& notes()       { return _notes; }
 	inline const Notes& notes() const { return _notes; }
 
@@ -199,7 +209,7 @@ private:
 	Notes   _notes;
 	SysExes _sysexes;
 
-	typedef std::vector<size_t> WriteNotes;
+	typedef std::set<boost::shared_ptr< Note<Time> >, NoteNumberComparator> WriteNotes;
 	WriteNotes _write_notes[16];
 	bool       _writing;
 
diff --git a/libs/evoral/src/Sequence.cpp b/libs/evoral/src/Sequence.cpp
index 124a0acd4c..81d515afbf 100644
--- a/libs/evoral/src/Sequence.cpp
+++ b/libs/evoral/src/Sequence.cpp
@@ -427,10 +427,9 @@ Sequence<Time>::const_iterator::operator=(const const_iterator& other)
 // Sequence
 
 template<typename Time>
-Sequence<Time>::Sequence(const TypeMap& type_map, size_t size)
+Sequence<Time>::Sequence(const TypeMap& type_map)
 	: _edited(false)
 	, _type_map(type_map)
-	, _notes(size)
 	, _writing(false)
 	, _end_iter(*this, DBL_MAX)
 	, _percussive(false)
@@ -569,14 +568,13 @@ Sequence<Time>::end_write(bool delete_stuck)
 
 	if (!_percussive && delete_stuck) {
 		for (typename Notes::iterator n = _notes.begin(); n != _notes.end() ;) {
+			typename Notes::iterator next = n;
+			++next;
 			if ((*n)->length() == 0) {
 				cerr << "WARNING: Stuck note lost: " << (*n)->note() << endl;
-				n = _notes.erase(n);
-				// we have to break here because erase invalidates the iterator
-				break;
-			} else {
-				++n;
+				_notes.erase(n);
 			}
+			n = next;
 		}
 	}
 
@@ -611,7 +609,7 @@ Sequence<Time>::append(const Event<Time>& event)
 
 	const MIDIEvent<Time>& ev = (const MIDIEvent<Time>&)event;
 
-	assert(_notes.empty() || ev.time() >= _notes.back()->time());
+	assert(_notes.empty() || ev.time() >= (*_notes.rbegin())->time());
 	assert(_writing);
 
 	if (!midi_event_is_valid(ev.buffer(), ev.size())) {
@@ -678,14 +676,14 @@ Sequence<Time>::append_note_on_unlocked(uint8_t chan, Time time, uint8_t note_nu
 		_highest_note = note_num;
 
 	boost::shared_ptr< Note<Time> > new_note(new Note<Time>(chan, time, 0, note_num, velocity));
-	_notes.push_back(new_note);
+	_notes.insert(new_note);
 	if (!_percussive) {
 		DUMP(format("Sustained: Appending active note on %1% channel %2%\n")
 				% (unsigned)(uint8_t)note_num % chan);
-		_write_notes[chan].push_back(_notes.size() - 1);
+		_write_notes[chan].insert(new_note);
 	} else {
-	 	DUMP("Percussive: NOT appending active note on\n");
-	 }
+		DUMP("Percussive: NOT appending active note on\n");
+	}
 }
 
 template<typename Time>
@@ -704,19 +702,15 @@ Sequence<Time>::append_note_off_unlocked(uint8_t chan, Time time, uint8_t note_n
 		return;
 	}
 
-	/* FIXME: make _write_notes fixed size (127 noted) for speed */
-
-	/* FIXME: note off velocity for that one guy out there who actually has
-	 * keys that send it */
+	// TODO: support note off velocity
 
 	bool resolved = false;
-
-	for (WriteNotes::iterator n = _write_notes[chan].begin(); n
-			!= _write_notes[chan].end(); ++n) {
-		Note<Time>& note = *_notes[*n].get();
-		if (note.note() == note_num) {
-			assert(time >= note.time());
-			note.set_length(time - note.time());
+	for (typename WriteNotes::iterator n = _write_notes[chan].begin();
+			n != _write_notes[chan].end(); ++n) {
+		boost::shared_ptr< Note<Time> > note = *n;
+		if (note->note() == note_num) {
+			assert(time >= note->time());
+			note->set_length(time - note->time());
 			_write_notes[chan].erase(n);
 			DUMP(format("resolved note, length: %1%\n") % note.length());
 			resolved = true;
diff --git a/libs/evoral/test/SMFTest.hpp b/libs/evoral/test/SMFTest.hpp
index cc5feb684c..77ccb54572 100644
--- a/libs/evoral/test/SMFTest.hpp
+++ b/libs/evoral/test/SMFTest.hpp
@@ -60,7 +60,7 @@ class SMFTest : public CppUnit::TestFixture
         void setUp() { 
            type_map = new DummyTypeMap();
            assert(type_map);
-           seq = new MySequence<Time>(*type_map, 0);
+           seq = new MySequence<Time>(*type_map);
            assert(seq);
         }
         
diff --git a/libs/evoral/test/SequenceTest.hpp b/libs/evoral/test/SequenceTest.hpp
index 9c6f084643..e5e5015bfc 100644
--- a/libs/evoral/test/SequenceTest.hpp
+++ b/libs/evoral/test/SequenceTest.hpp
@@ -54,7 +54,7 @@ public:
 template<typename Time>
 class MySequence : public Sequence<Time> {
 public:
-	MySequence(DummyTypeMap&map, int size) : Sequence<Time>(map, size) {}
+	MySequence(DummyTypeMap&map) : Sequence<Time>(map) {}
 	
 	boost::shared_ptr<Control> control_factory(const Parameter& param) {
 		
@@ -107,7 +107,7 @@ class SequenceTest : public CppUnit::TestFixture
         void setUp (void) { 
         	type_map = new DummyTypeMap();
            	assert(type_map);
-           	seq = new MySequence<Time>(*type_map, 0);
+           	seq = new MySequence<Time>(*type_map);
            	assert(seq);
            	
            	for(int i = 0; i < 12; i++) {