Repository: cuthbertLab/music21 (python)

Issue:
Prevent so many gaps from quantizing durations
**Feature request**
A MIDI note with a duration of, say, 0.385 QL will, with the default quantization units of 0.25 and 0.33QL, have its duration shortened to 0.33QL. Later, a 0.16QL rest will be needed to fill the gap from 0.33 to 0.5. This is likely not what users want.


**Steps to reproduce**

```
s = stream.Stream()
n1 = note.Note(quarterLength=0.385)
n2 = note.Note(quarterLength=0.385)
s.insert(0, n1)
s.insert(0.5, n2)
s.quantize(inPlace=True)
s.makeRests(fillGaps=True, inPlace=True)
s.show('t')
```

**Result**
{0.0} <music21.note.Note C>
{0.3333} <music21.note.Rest 23/100ql>
{0.5} <music21.note.Note C>

**What should be done?**

- Unlike offsets, should durations only round up rather than up or down? Or only when there is a gap to be filled?

Pull request description:
Avoid gaps that don't fit quantization scheme
Fixes #811

Avoid gaps that don't fit quantization scheme (1/6 QL rests, etc.) by looking ahead to see the divisor that will be used to quantize the subsequent offset.

***

Example file: https://github.com/cuthbertLab/music21/blob/master/music21/midi/testPrimitive/test01.mid

**Finale (reference)**
![Screen Shot 2021-07-14 at 12 49 42 PM](https://user-images.githubusercontent.com/38668450/125661180-f9e48679-405b-466b-8e1b-7268b1f88893.png)


**m21 roundtrip Before**
![Screen Shot 2021-07-14 at 12 48 01 PM](https://user-images.githubusercontent.com/38668450/125660994-8fa875aa-0532-4267-9cfc-98e83910e6be.png)

**m21 roundtrip After**

![Screen Shot 2021-07-14 at 12 47 52 PM](https://user-images.githubusercontent.com/38668450/125660983-5fa649b3-cc02-4c37-be1c-d634f9b68f29.png)


Patch:
diff --git a/music21/_version.py b/music21/_version.py
index 7651c8d0c..b4949ae8b 100644
--- a/music21/_version.py
+++ b/music21/_version.py
@@ -42,7 +42,7 @@ When changing, update the single test case in base.py.
 Changing this number invalidates old pickles -- do it if the old pickles create a problem.
 '''
 
-__version_info__ = (7, 0, 7, 'b1')  # can be 4-tuple: (7, 0, 5, 'a2')
+__version_info__ = (7, 0, 8)  # can be 4-tuple: (7, 0, 5, 'a2')
 
 v = '.'.join(str(x) for x in __version_info__[0:3])
 if len(__version_info__) > 3 and __version_info__[3]:
diff --git a/music21/base.py b/music21/base.py
index 3330d787c..1c930b143 100644
--- a/music21/base.py
+++ b/music21/base.py
@@ -28,7 +28,7 @@ available after importing `music21`.
 <class 'music21.base.Music21Object'>
 
 >>> music21.VERSION_STR
-'7.0.7b1'
+'7.0.8'
 
 Alternatively, after doing a complete import, these classes are available
 under the module "base":
diff --git a/music21/converter/__init__.py b/music21/converter/__init__.py
index 7be27c3f9..94598cd43 100644
--- a/music21/converter/__init__.py
+++ b/music21/converter/__init__.py
@@ -1978,5 +1978,3 @@ if __name__ == '__main__':
     # sys.arg test options will be used in mainTest()
     import music21
     music21.mainTest(Test)  # , runTest='testConverterFromPath')
-
-
diff --git a/music21/stream/base.py b/music21/stream/base.py
index 6356ed065..823baba5f 100644
--- a/music21/stream/base.py
+++ b/music21/stream/base.py
@@ -29,6 +29,7 @@ import pathlib
 import unittest
 import sys
 
+from collections import namedtuple
 from fractions import Fraction
 from math import isclose
 from typing import Union, List, Optional, Set, Tuple, Sequence
@@ -70,6 +71,8 @@ environLocal = environment.Environment('stream')
 StreamException = exceptions21.StreamException
 ImmutableStreamException = exceptions21.ImmutableStreamException
 
+BestQuantizationMatch = namedtuple('BestQuantizationMatch',
+    ['error', 'tick', 'match', 'signedError', 'divisor'])
 
 class StreamDeprecationWarning(UserWarning):
     # Do not subclass Deprecation warning, because these
@@ -8905,7 +8908,9 @@ class Stream(core.StreamCoreMixin, base.Music21Object):
         If `recurse` is True, then all substreams are also quantized.
         If False (default), then only the highest level of the Stream is quantized.
 
-        Changed in v.7 -- recurse defaults False
+        Changed in v.7:
+           - `recurse` defaults False
+           - look-ahead approach to choosing divisors to avoid gaps when processing durations
 
         >>> n = note.Note()
         >>> n.quarterLength = 0.49
@@ -8953,6 +8958,29 @@ class Stream(core.StreamCoreMixin, base.Music21Object):
         >>> [e.offset for e in myPart.measure(1).notes]
         [0.0, 0.0, 0.25, Fraction(1, 3)]
 
+        New in v.7: if both `processDurations` and `processOffsets` are True, then
+        the next note's quantized offset is taken into account when quantizing the
+        duration of the current note. This is to prevent unnecessary gaps from applying
+        different quantization units to adjacent notes:
+
+        >>> s2 = stream.Stream()
+        >>> nOddLength = note.Note(quarterLength=0.385)
+        >>> s2.repeatInsert(nOddLength, [0, 0.5, 1, 1.5])
+        >>> s2.show('t', addEndTimes=True)
+            {0.0 - 0.385} <music21.note.Note C>
+            {0.5 - 0.885} <music21.note.Note C>
+            {1.0 - 1.385} <music21.note.Note C>
+            {1.5 - 1.885} <music21.note.Note C>
+
+        Before v.7, this would have yielded four triplet-eighths (separated by 1/6 QL rests):
+
+        >>> s2.quantize(processOffsets=True, processDurations=True, inPlace=True)
+        >>> s2.show('text', addEndTimes=True)
+            {0.0 - 0.5} <music21.note.Note C>
+            {0.5 - 1.0} <music21.note.Note C>
+            {1.0 - 1.5} <music21.note.Note C>
+            {1.5 - 1.8333} <music21.note.Note C>
+
         OMIT_FROM_DOCS
 
         Test changing defaults, running, and changing back...
@@ -8988,7 +9016,8 @@ class Stream(core.StreamCoreMixin, base.Music21Object):
             found = []
             for div in divisors:
                 match, error, signedErrorInner = common.nearestMultiple(target, (1 / div))
-                found.append((error, match, signedErrorInner))  # reverse match, error for sorting
+                # Sort by unsigned error, then "tick" (divisor expressed as QL, e.g. 0.25)
+                found.append(BestQuantizationMatch(error, 1 / div, match, signedErrorInner, div))
             # get first, and leave out the error
             bestMatchTuple = sorted(found)[0]
             return bestMatchTuple
@@ -8996,50 +9025,67 @@ class Stream(core.StreamCoreMixin, base.Music21Object):
         # if we have a min of 0.25 (sixteenth)
         # quarterLengthMin = quarterLengthDivisors[0]
 
-        # TODO: Use new filters...
         if inPlace is False:
             returnStream = self.coreCopyAsDerivation('quantize')
-
         else:
             returnStream = self
 
         useStreams = [returnStream]
         if recurse is True:
-            for obj in returnStream.recurse():
-                if 'Stream' in obj.classes:
-                    useStreams.append(obj)
+            useStreams = returnStream.recurse(streamsOnly=True, includeSelf=True)
 
+        rests_lacking_durations: List[note.Rest] = []
         for useStream in useStreams:
-            for e in useStream._elements:
+            for i, e in enumerate(useStream._elements):
                 if processOffsets:
                     o = useStream.elementOffset(e)
                     sign = 1
                     if o < 0:
                         sign = -1
                         o = -1 * o
-                    unused_error, oNew, signedError = bestMatch(float(o), quarterLengthDivisors)
-                    useStream.coreSetElementOffset(e, oNew * sign)
-                    if (hasattr(e, 'editorial')
-                            and signedError != 0):
-                        e.editorial.offsetQuantizationError = signedError * sign
+                    o_matchTuple = bestMatch(float(o), quarterLengthDivisors)
+                    useStream.coreSetElementOffset(e, o_matchTuple.match * sign)
+                    if (hasattr(e, 'editorial') and o_matchTuple.signedError != 0):
+                        e.editorial.offsetQuantizationError = o_matchTuple.signedError * sign
                 if processDurations:
                     ql = e.duration.quarterLength
                     ql = max(ql, 0)  # negative ql possible in buggy MIDI files?
-                    unused_error, qlNew, signedError = bestMatch(
-                        float(ql), quarterLengthDivisors)
+                    d_matchTuple = bestMatch(float(ql), quarterLengthDivisors)
+                    # Check that any gaps from this quantized duration to the next onset
+                    # are at least as large as the smallest quantization unit (largest divisor)
+                    # If not, then re-quantize this duration with the divisor
+                    # that will be used to quantize the next element's offset
+                    if processOffsets and i + 1 < len(useStream._elements):
+                        next_element = useStream._elements[i + 1]
+                        next_offset = useStream.elementOffset(next_element)
+                        look_ahead_result = bestMatch(float(next_offset), quarterLengthDivisors)
+                        next_offset = look_ahead_result.match
+                        next_divisor = look_ahead_result.divisor
+                        if (0 < next_offset - (e.offset + d_matchTuple.match)
+                                < 1 / max(quarterLengthDivisors)):
+                            # Overwrite the earlier matchTuple with a better result
+                            d_matchTuple = bestMatch(float(ql), (next_divisor,))
                     # Enforce nonzero duration for non-grace notes
-                    if qlNew == 0 and 'GeneralNote' in e.classes and not e.duration.isGrace:
-                        qlNew = 1 / max(quarterLengthDivisors)
-                        signedError = ql - qlNew
-                    e.duration.quarterLength = qlNew
-                    if (hasattr(e, 'editorial')
-                            and signedError != 0):
-                        e.editorial.quarterLengthQuantizationError = signedError
+                    if (d_matchTuple.match == 0
+                            and 'NotRest' in e.classes
+                            and not e.duration.isGrace):
+                        e.quarterLength = 1 / max(quarterLengthDivisors)
+                        if hasattr(e, 'editorial'):
+                            e.editorial.quarterLengthQuantizationError = ql - e.quarterLength
+                    elif d_matchTuple.match == 0 and 'Rest' in e.classes:
+                        rests_lacking_durations.append(e)
+                    else:
+                        e.duration.quarterLength = d_matchTuple.match
+                        if (hasattr(e, 'editorial') and d_matchTuple.signedError != 0):
+                            e.editorial.quarterLengthQuantizationError = d_matchTuple.signedError
 
             # end for e in ._elements
             # ran coreSetElementOffset
             useStream.coreElementsChanged(updateIsFlat=False)
 
+            for rest_to_remove in rests_lacking_durations:
+                useStream.remove(rest_to_remove)
+
         if inPlace is False:
             return returnStream
 


Test patch:
diff --git a/music21/stream/tests.py b/music21/stream/tests.py
index 58eb22af6..fe90dc1ee 100644
--- a/music21/stream/tests.py
+++ b/music21/stream/tests.py
@@ -3817,16 +3817,25 @@ class Test(unittest.TestCase):
 
     def testQuantizeMinimumDuration(self):
         '''
-        Notes of nonzero duration should retain a nonzero
-        duration after quantizing.
+        Notes (not rests!) of nonzero duration should retain a nonzero
+        duration after quantizing. Zero duration rests should be removed.
         '''
         from music21 import converter
 
         dirLib = common.getSourceFilePath() / 'midi' / 'testPrimitive'
         fp = dirLib / 'test15.mid'  # 3 16ths, 2 32nds
         s = converter.parse(fp, quarterLengthDivisors=[2])
-        self.assertEqual(s.flat.notes[-1].duration.quarterLength, 0.5)
-        self.assertEqual(s.flat.notes[-1].editorial.quarterLengthQuantizationError, .125 - .5)
+        last_note = s.flat.notes[-1]
+        self.assertEqual(last_note.duration.quarterLength, 0.5)
+        self.assertEqual(last_note.editorial.quarterLengthQuantizationError, .125 - .5)
+
+        # build up the same score from scratch and show
+        # minimum duration constraint does not apply to rests
+        s2 = Stream()
+        s2.repeatAppend(note.Note(type='16th'), 3)
+        s2.repeatAppend(note.Rest(type='32nd'), 2)
+        s2.quantize(inPlace=True, quarterLengthDivisors=[2])
+        self.assertEqual(len(s2.notesAndRests), 3)
 
     def testAnalyze(self):