# -*- coding: utf-8 -*- # ------------------------------------------------------------------------------ # Name: sieve.py # Purpose: sieve operations, after Iannis Xenakis. # # Authors: Christopher Ariza # # Copyright: Copyright © 2003, 2010 Christopher Ariza # Copyright © 2010-2012, 19 Michael Scott Asato Cuthbert # License: BSD, see license.txt # ------------------------------------------------------------------------------ ''' A comprehensive, object model of the Xenakis Sieve. :class:`music21.sieve.Sieve` objects can be created from high-level string notations, and used to generate line segments in various representation. Additional functionality is available through associated objects. The :class:`music21.sieve.Sieve` class permits generation segments in four formats. >>> a = sieve.Sieve('3@2|7@1') >>> a.segment() [1, 2, 5, 8, 11, 14, 15, 17, 20, 22, 23, 26, 29, 32, 35, 36, 38, 41, 43, 44, 47, 50, 53, 56, 57, 59, 62, 64, 65, 68, 71, 74, 77, 78, 80, 83, 85, 86, 89, 92, 95, 98, 99] >>> a.segment(segmentFormat='binary') [0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1] >>> a.segment(segmentFormat='width') [1, 3, 3, 3, 3, 1, 2, 3, 2, 1, 3, 3, 3, 3, 1, 2, 3, 2, 1, 3, 3, 3, 3, 1, 2, 3, 2, 1, 3, 3, 3, 3, 1, 2, 3, 2, 1, 3, 3, 3, 3, 1] >>> len(a.segment(segmentFormat='unit')) 43 A :class:`music21.sieve.CompressionSegment` can be used to derive a Sieve from a ny sequence of integers. >>> a = sieve.CompressionSegment([3, 4, 5, 6, 7, 8, 13, 19]) >>> str(a) '6@1|7@6|8@5|9@4|10@3|11@8' The :class:`music21.sieve.PitchSieve` class provides a quick generation of :class:`music21.pitch.Pitch` lists from Sieves. >>> a = sieve.PitchSieve('13@3|13@6|13@9', 'c1', 'c10', 'f#4') >>> pitches = a() >>> ', '.join([str(p) for p in pitches]) 'F#1, A1, C2, G2, B-2, C#3, G#3, B3, D4, A4, C5, E-5, B-5, C#6, E6, B6, D7, F7, C8, E-8, F#8, C#9, E9, G9' ''' from __future__ import annotations from ast import literal_eval from collections.abc import Iterable import copy from math import gcd, lcm import random import string import typing as t import unittest from music21 import common from music21 import environment from music21 import exceptions21 from music21 import interval from music21 import pitch environLocal = environment.Environment('sieve') # ------------------------------------------------------------------------------ class UnitException(exceptions21.Music21Exception): pass class ResidualException(exceptions21.Music21Exception): pass class SieveException(exceptions21.Music21Exception): pass class CompressionSegmentException(exceptions21.Music21Exception): pass class PitchSieveException(exceptions21.Music21Exception): pass LGROUP = '{' RGROUP = '}' AND = '&' OR = '|' XOR = '^' BOUNDS = [LGROUP, RGROUP, AND, OR, XOR] NEG = '-' RESIDUAL = list(string.digits) + ['@'] # ------------------------------------------------------------------------------ # from # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117119 # David Eppstein, UC Irvine, 28 Feb 2002 # Alex Martelli # other implementations # http://c2.com/cgi-bin/wiki?SieveOfEratosthenesInManyProgrammingLanguages # http://www.mycgiserver.com/~gpiancastelli/blog/archives/000042.html def eratosthenes(firstCandidate=2): ''' Yields the sequence of prime numbers via the Sieve of Eratosthenes. rather than creating a fixed list of a range (z) and crossing out multiples of sequential candidates, this algorithm stores primes under their next possible candidate, thus allowing the generation of primes in sequence without storing a complete range (z). Create a dictionary. Each entry in the dictionary is a key:item pair of (key) the largest multiple of this prime so far found and (item) the prime. The dictionary only has as many entries as found primes. If a candidate is not a key in the dictionary, it is not a multiple of any already-found prime; it is thus a prime. a new entry is added to the dictionary, with the square of the prime as the key. The square of the prime is the next possible multiple to be found. To use this generator, create an instance and then call the .next() method on the instance. >>> a = sieve.eratosthenes() >>> next(a) 2 >>> next(a) 3 We can also specify a starting value for the sequence, skipping over initial primes smaller than this number: >>> a = sieve.eratosthenes(95) >>> next(a) 97 >>> next(a) 101 ''' D = {} # map composite integers to primes witnessing their compositeness # D stores largest composite: prime, pairs q = 2 # candidate, first integer to test for primality while True: # get item from dict by key; remove from dict # p is the prime, if already found # q is the candidate, the running integer list p = D.pop(q, None) # returns item for key, None if not in dict # if candidate (q) is already in dict, not a prime if p is not None: # key (prime candidate) in dictionary # update dictionary w/ the next multiple of this prime not already # in dictionary nextMult = p + q # prime prime plus the candidate; next multiple while nextMult in D: # incr x by p until it is a unique key nextMult = nextMult + p # re-store the prime under a key of the next multiple D[nextMult] = p # x is now the next unique multiple to be found # candidate (q) not already in dictionary; q is prime else: # value not in dictionary nextMult = q * q # square is next multiple tt will be found D[nextMult] = q if q >= firstCandidate: yield q # return prime q = q + 1 # incr. candidate def rabinMiller(n): ''' Returns True if an integer is likely prime or False if it is likely composite using the Rabin Miller primality test. See also here: http://www.4dsolutions.net/ocn/numeracy2.html >>> sieve.rabinMiller(234) False >>> sieve.rabinMiller(5) True >>> sieve.rabinMiller(4) False >>> sieve.rabinMiller(97 * 2) False >>> sieve.rabinMiller(6 ** 4 + 1) # prime True >>> sieve.rabinMiller(123986234193) # divisible by 3, runs fast False ''' n = abs(n) if n in (2, 3): return True m = n % 6 # if n (except 2 and 3) mod 6 is not 1 or 5, then n isn't prime if m not in (1, 5): return False # primes up to 100; 2, 3 handled by mod 6 primes = [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] if n <= 100: if n in primes: return True # must include 2, 3 return False for prime in primes: if n % prime == 0: return False s, r = n - 1, 1 while not s & 1: s >>= 1 r = r + 1 for i in range(10): # random tests # calculate a^s mod n, where "a" is a random number y = pow(random.randint(1, n - 1), s, n) if y == 1: # pragma: no cover continue # n passed test, is composite # try values of j from 1 to r - 1 for j in range(1, r): if y == n - 1: break # if y = n - 1, n passed the test this time y = pow(y, 2, n) # a^((2^j)*s) mod n else: # pragma: no cover return False # y never equaled n - 1, then n is composite # n passed all the tests, it is very likely prime return True # ------------------------------------------------------------------------------ # list processing and unit interval routines # possible move to common.py if used elsewhere def discreteBinaryPad(series: Iterable[int], fixRange=None) -> list[int]: ''' Treat a sequence of integers as defining contiguous binary integers, where provided values are 1's and excluded values are zero. For instance, running [3, 10, 12] through this method gives a 1 for the first entry (signifying 3), 0s for the next six entries (signifying 4-9), a 1 (for 10), a 0 (for 11), and a 1 (for 12). >>> sieve.discreteBinaryPad([3, 10, 12]) [1, 0, 0, 0, 0, 0, 0, 1, 0, 1] >>> sieve.discreteBinaryPad([3, 4, 5]) [1, 1, 1] ''' # make sure these are ints for x in series: if not common.isNum(x): raise UnitException('non-integer value found') discrete = [] if fixRange is not None: fixRange.sort() # make sure sorted minVal = fixRange[0] maxVal = fixRange[-1] else: # find max and min from values seriesAlt = list(copy.deepcopy(series)) seriesAlt.sort() minVal = seriesAlt[0] maxVal = seriesAlt[-1] for x in range(minVal, maxVal + 1): if x in series: discrete.append(1) else: # not in series discrete.append(0) return discrete def unitNormRange(series, fixRange=None): ''' Given a list of numbers, create a proportional spacing across the unit interval. The first entry will always be 0 and the last 1, other entries will be spaced according to their distance between these two units. For instance, for 0, 3, 4 the middle entry will be 0.75 since 3 is 3/4 of the distance between 0 and 4: >>> sieve.unitNormRange([0, 3, 4]) [0.0, 0.75, 1.0] but for [1, 3, 4], it will be 0.666... because 3 is 2/3 of the distance between 1 and 4 >>> sieve.unitNormRange([1, 3, 4]) [0.0, 0.666..., 1.0] ''' if fixRange is not None: fixRange.sort() minFound = fixRange[0] maxFound = fixRange[-1] else: # find maxFound and minFound from values minFound = min(series) maxFound = max(series) span = maxFound - minFound unit = [] if len(series) > 1: for val in series: dif = val - minFound if common.isNum(dif): dif = float(dif) if span != 0: unit.append(dif / span) else: # fill value if span is zero unit.append(0) else: # if one element, return 0 (could be 1, or 0.5) unit.append(0) return unit def unitNormEqual(parts): ''' Given a certain number of parts, return a list unit-interval values between 0 and 1, with as many divisions as parts; 0 and 1 are always inclusive. >>> sieve.unitNormEqual(3) [0.0, 0.5, 1] If parts is 0 or 1, then a single entry of [0] is given: >>> sieve.unitNormEqual(1) [0] ''' if parts <= 1: return [0] elif parts == 2: return [0, 1] else: unit = [] step = 1 / (parts - 1) for y in range(parts - 1): # one less value tn needed unit.append(y * step) unit.append(1) # make last an integer, add manually return unit def unitNormStep(step, a=0, b=1, normalized=True): ''' Given a step size and an a/b min/max range, calculate number of parts to fill step through inclusive a,b, then return a unit interval list of values necessary to cover region. Note that returned values are, by default, normalized within the unit interval. >>> sieve.unitNormStep(0.5, 0, 1) [0.0, 0.5, 1] >>> sieve.unitNormStep(0.5, -1, 1) [0.0, 0.25, 0.5, 0.75, 1] >>> sieve.unitNormStep(0.5, -1, 1, normalized=False) [-1, -0.5, 0.0, 0.5, 1.0] >>> post = sieve.unitNormStep(0.25, 0, 20) >>> len(post) 81 >>> post = sieve.unitNormStep(0.25, 0, 20, normalized=False) >>> len(post) 81 ''' if a == b: return [] # no range, return boundary if a < b: minVal = a maxVal = b else: minVal = b maxVal = a # find number of parts necessary count = 0 # will count last, so do not count min at beginning values = [] x = minVal while x <= maxVal: values.append(x) # do before incrementing x += step count += 1 if normalized: return unitNormEqual(count) else: return values # ------------------------------------------------------------------------------ # note: some of these methods are in common, though they are slightly different algorithms; # need to test for compatibility def _meziriac(c1, c2): # Bachet de Meziriac (1624) # in order for x and y to be two coprimes, it is necessary and sufficient # that there exist two relative whole numbers, e, g such that # 1 + (g * x) = e * y or # y' * x = (e' * y) + 1 # where e and g come from the recursive equations # (e * c2) % c1 == 1 and # (g'* c1) % c2 == 1 ### this is version used here # while letting e, g' run through values 0, 1, 2, 3... # except if c1 == 1 and c2 == 1 g = 0 if c2 == 1: g = 1 elif c1 == c2: g = 0 # if equal, causes infinite loop of 0 else: while g < 10000: val = (g * c1) % c2 if val == 1: break g = g + 1 return g # ------------------------------------------------------------------------------ class PrimeSegment: def __init__(self, start, length): ''' A generator of prime number segments, given a start value and desired length of primes. >>> ps = sieve.PrimeSegment(3, 20) >>> ps() [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73] ''' self.seg = [] self.start = start self.length = length # fill the segment self._fillRange() def _fillRabinMiller(self, start, length, stop=None, direction='up'): ''' scan all number in range and return a list of primes provide a max to force stoppage at certain point before the maximum length direction determines which way things go. ''' seg = [] _oddBoundary = 4 # number above which only odd primes are found if start % 2 == 0 and start > _oddBoundary: # if even if direction == 'up': n = start + 1 else: # if down n = start - 1 else: n = start while 1: if rabinMiller(n): seg.append(n) if len(seg) >= length: break if n == stop: break if n > _oddBoundary: # after 5, no even primes if direction == 'up': n = n + 2 # only test odd numbers else: n = n - 2 else: # n is less than 5, add 1 if direction == 'up': n = n + 1 # must increment by 1 else: n = n - 1 return seg def _fillRange(self): ''' fill positive and negative range ''' if self.start < 0: # create the negative portion of the segment segNeg = self._fillRabinMiller(abs(self.start), self.length, 0, 'down') segNeg = [-x for x in segNeg] # make negative if len(segNeg) < self.length: segPos = self._fillRabinMiller(0, self.length - len(segNeg), None, 'up') self.seg = segNeg + segPos else: # add positive values self.seg = segNeg else: # start from zero alone self.seg = self._fillRabinMiller(self.start, self.length, None, 'up') def __call__(self, segmentFormat=None): ''' assumes that min and max values are derived from found primes means that primes will always be at boundaries ''' z = [self.seg[0], self.seg[-1]] if segmentFormat in ('bin', 'binary'): return discreteBinaryPad(self.seg, z) elif segmentFormat == 'unit': return unitNormRange(self.seg, z) elif segmentFormat in ('wid', 'width'): wid = [] for i in range(len(self.seg) - 1): wid.append((self.seg[i + 1] - self.seg[i])) return wid else: # int, integer return self.seg # ------------------------------------------------------------------------------ class Residual: ''' object that represents a modulus and a start point each object stores a range of integers (self._z) from which sections are drawn this range of integers can be changed whenever the section os drawn >>> residual = sieve.Residual(3, 2) ''' def __init__(self, m, shift=0, neg=0, z=None): # get a default range, can be changed later # is an actual range and not start/end points b/c when producing a not (-) # it is easy to remove the mod,n from the range if z is None: # supply default if necessary z = list(range(100)) self._z = z # print('residual init self._z', self._z) self._m = m if neg not in (0, 1): raise ResidualException('negative value must be 0, 1, or a Boolean') self._neg = neg # negative, complement boolean if self._m == 0: # 0 mode causes ZeroDivisionError self._shift = shift else: self._shift = shift % self._m # do mod on shift self._segmentFormatOptions = ['int', 'bin', 'unit', 'wid'] self._segmentFormat = 'int' # -------------------------------------------------------------------------- # utility functions def setZ(self, z): ''' z is the range of integers to use when generating a list ''' self._z = z def setZRange(self, minInt, maxInt): ''' z is the range of integers to use when generating a list convenience function that fixes max ''' self._z = list(range(minInt, maxInt + 1)) def setSegmentFormat(self, fmt): # fmt = drawer.strScrub(fmt, 'l') fmt = fmt.strip().lower() if fmt in self._segmentFormatOptions: raise ResidualException(f'format not in format options: {fmt}') self._segmentFormat = fmt # -------------------------------------------------------------------------- def segment(self, n=0, z=None, segmentFormat=None): ''' get a residual subset of this modulus at this n within the integer range provided by z format can be 'int' or 'bin', for integer or binary >>> a = sieve.Residual(3, 2) >>> a.segment(3) [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98] >>> a.segment(3, range(3, 15)) [5, 8, 11, 14] ''' if z is None: # z is temporary; if none z = self._z # assign to local if segmentFormat is None: segmentFormat = self._segmentFormat subset = [] if self._m == 0: return subset # empty n = (n + self._shift) % self._m # check for n >= m for value in z: if n == value % self._m: subset.append(value) if self._neg: # find opposite compSet = copy.deepcopy(z) for value in subset: compSet.remove(value) seg = compSet else: seg = subset if segmentFormat in ('bin', 'binary'): return discreteBinaryPad(seg, z) elif segmentFormat == 'unit': return unitNormRange(seg, z) elif segmentFormat in ('wid', 'width'): # difference always equal to m wid = [self._m] * (len(seg) - 1) # one shorter than segment return wid elif segmentFormat in ('int', 'integer'): # int, integer return seg else: raise ResidualException(f'{segmentFormat} not a valid sieve segmentFormat string.') def period(self) -> int: ''' period is M; obvious, but nice for completeness >>> a = sieve.Residual(3, 2) >>> a.period() 3 ''' return self._m # -------------------------------------------------------------------------- def copy(self): # TODO: replace with deepcopy method m = copy.copy(self._m) shift = copy.copy(self._shift) neg = copy.copy(self._neg) # provide ref, not copy, to z return Residual(m, shift, neg, self._z) def __call__(self, n=0, z=None, segmentFormat=None): ''' calls self.segment(); uses _segmentFormat >>> a = sieve.Residual(3, 2) >>> a() [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98] ''' # if z is None, uses self._z return self.segment(n, z, segmentFormat) def represent(self, style=None): ''' does not show any logical operator but unary negation ''' if style == 'classic': # mathematical style if self._shift != 0: repStr = f'{self._m}(n+{self._shift})' else: repStr = f'{self._m}(n)' if self._neg: repStr = f'-{repStr}' else: # do evaluatable type repStr = f'{self._m}@{self._shift}' # show w/ @ if self._neg: repStr = f'-{repStr}' return repStr def __str__(self): ''' str representation using M(n + shift) style notation >>> a = sieve.Residual(3, 2) >>> str(a) '3@2' ''' return self.represent() # default style def __eq__(self, other): ''' ==, compare residual classes in terms of m and shift ''' if other is None: return 0 if (self._m == other._m and self._shift == other._shift and self._neg == other._neg): return 1 else: return 0 def __cmp__(self, other): ''' allow comparison based on m and shift; if all equal look at neg Still being used internally even though __cmp__ is not used in Python 3 ''' # return neg if self < other, zero if self == other, # a positive integer if self > other. if self._m < other._m: return -1 elif self._m > other._m: return 1 # if equal compare shift elif self._m == other._m: if self._shift < other._shift: return -1 elif self._shift > other._shift: return 1 else: # shifts are equal if self._neg != other._neg: if self._neg == 1: # its negative, then less return -1 else: return 1 else: return 0 def __lt__(self, other): if self.__cmp__(other) == -1: return True else: return False def __gt__(self, other): if self.__cmp__(other) == 1: return True else: return False def __neg__(self): ''' unary neg operators; return neg object ''' if self._neg: # if 1 neg = 0 else: # if 0 neg = 1 return Residual(self._m, self._shift, neg, self._z) def __and__(self, other): ''' &, produces an intersection of two Residual classes returns a new Residual class cannot be done if R under complementation >>> a = sieve.Residual(3, 2) >>> b = sieve.Residual(5, 1) >>> c = a & b >>> str(c) '15@11' ''' if other._neg or self._neg: raise ResidualException('complemented Residual objects cannot be intersected') m, n = self._cmpIntersection(self._m, other._m, self._shift, other._shift) # get the union of both z zSet = set(self._z) | set(other._z) z = list(zSet) # neg = 0 # most not be complemented return Residual(m, n, 0, z) def __or__(self, other): ''' |, not sure if this can be implemented i.e., a union of two Residual classes can not be expressed as a single Residual, that is intersections can always be reduced, whereas unions cannot be reduced. ''' pass # -------------------------------------------------------------------------- def _cmpIntersection(self, m1, m2, n1, n2): ''' compression by intersection find m,n such that the intersection of two Residuals can be reduced to one Residual. Xenakis p 273. ''' d = gcd(m1, m2) c1 = m1 // d # not sure if we need floats here c2 = m2 // d n3 = 0 m3 = 0 if m1 != 0 and m2 != 0: n1 = n1 % m1 n2 = n2 % m2 else: # one of the mods is equal to 0 return n3, m3 # no intersection if d != 1 and ((n1 - n2) % d != 0): return n3, m3 # no intersection elif d != 1 and ((n1 - n2) % d == 0) and (n1 != n2) and (c1 == c2): m3 = d # for real? n3 = n1 return m3, n3 else: # d == 1, or ... m3 = c1 * c2 * d g = _meziriac(c1, c2) # c1,c2 must be co-prime may produce a loop n3 = (n1 + (g * (n2 - n1) * c1)) % m3 return m3, n3 # ------------------------------------------------------------------------------ class CompressionSegment: ''' Utility to convert from a point sequence to sieve. A z range can be supplied to explicitly provide the complete sieve segment, both positive and negative values. all values in the z range not in the segment are interpreted as negative values. thus, there is an essential dependency on the z range and the realized sieve. No matter the size of the z range, there is a modulus at which one point in the segment can be found. As such, any segment can be reduced to, at a minimum, a residual for each point in the segment, each, for the supplied z, providing a segment with one point. The same segment can then have multiplied logical string representations, depending on the provided z. >>> a = sieve.CompressionSegment([3, 4, 5, 6, 7, 8, 13, 19]) >>> str(a) '6@1|7@6|8@5|9@4|10@3|11@8' >>> b = sieve.CompressionSegment([0, 2, 4, 6, 8]) >>> str(b) '2@0' >>> c = sieve.CompressionSegment([0, 2, 4, 5, 7, 9, 11, 12]) >>> str(c) '5@2|5@4|6@5|7@0' ''' def __init__(self, src, z=None): # The supplied list of values is only the positive values of a sieve segment # we do not know what the negative values are; we can assume they are between # the min and max of the list, but this may not be true in all cases. src = list(copy.deepcopy(src)) src.sort() self._match = [] # already sorted from src for num in src: # remove redundancies if num not in self._match: self._match.append(num) if len(self._match) <= 1: raise CompressionSegmentException('segment must have more than one element') self._zUpdate(z) # sets self._z # max mod should always be the max of z; this is b/c at for any segment # if the mod == max of seg, at least one point can be found in the segment # mod is the step size, so only one step will happen in the sequence self._maxMod = len(self._z) # set maximum mod tried # assign self._residuals and do analysis try: self._process() except AssertionError: raise CompressionSegmentException('no Residual classes found for this z range') def _zUpdate(self, z=None): # z must at least be a superset of match if z is not None: # it is a list if not self._subset(self._match, z): raise CompressionSegmentException( 'z range must be a superset of desired segment') self._z = z zMin, zMax = self._z[0], self._z[-1] # z is range from max to min, unless provided at init else: # range from min, max; add 1 for range() to max zMin, zMax = self._match[0], self._match[-1] self._z = list(range(zMin, (zMax + 1))) # -------------------------------------------------------------------------- def __call__(self): ''' >>> a = sieve.CompressionSegment([3, 4, 5, 6, 7, 8]) >>> b = a() >>> str(b[0]) '1@0' ''' return self._residuals def __str__(self): resStr = [] if len(self._residuals) == 1: # single union must have an or resStr = str(self._residuals[0]) else: for resObj in self._residuals: resStr.append(str(resObj)) resStr = '|'.join(resStr) return resStr # -------------------------------------------------------------------------- def _subset(self, sub, thisSet): ''' True if sub is part of set; assumes no redundancies in each ''' commonNum = 0 for x in sub: if x in thisSet: commonNum = commonNum + 1 if commonNum == len(sub): return 1 else: return 0 def _find(self, n, part, whole): ''' given a point, and SieveSegment, find a modulus and shift that match. ''' m = 1 # could start at one, but only pertains to the single case of 1@0 while m < self._maxMod: # search m for max obj = Residual(m, n, 0, self._z) seg = obj() # n, z is set already # check first to see if it is a member of the part if self._subset(seg, part): return obj, seg elif self._subset(seg, whole): return obj, seg m = m + 1 # a mod will always be found, at least 1 point; should never happen raise SieveException(f'a mod was not found less than {self._maxMod}') def _process(self): ''' take a copy of match; move through each value of this list as if it were n; for each n test each modulo (from 1 to len(z) + 1) to find a residual. when found (one will be found), keep it; remove the found segments from the match, and repeat. ''' # process residuals self._residuals = [] # list of objects match = copy.copy(self._match) # scratch to work on maxToRun = 10000 while maxToRun: # loop over whatever is left in the match copy maxToRun -= 1 n = match[0] # always get first item obj, seg = self._find(n, match, self._match) if obj is None: # no residual found; should never happen raise CompressionSegmentException('_find() returned a None object') if obj not in self._residuals: # b/c __eq__ defined self._residuals.append(obj) for x in seg: # clean found values from match if x in match: match.remove(x) if not match: break self._residuals.sort() # ------------------------------------------------------------------------------ # http://docs.python.org/lib/set-objects.html # set object precedence: & before | # >>> a = set([3, 4]) # >>> b = set([4, 5]) # >>> c = set([3, 4, 5]) # >>> a & b & c # Set([4]) # >>> a & b | c # Set([3, 4, 5]) # >>> a & (b | c) # Set([3, 4]) # >>> (a & b) | c # Set([3, 4, 5]) # >>> b = sieve.SieveBound('2&4&8|5') # &&| # >>> str(b) # '2&4&8|5' # >>> b(0, range(20)) # [0, 5, 8, 10, 15, 16] # >>> b = sieve.SieveBound('2&4&(8|5)') # &&(|) # >>> b(0, range(20)) # [0, 8, 16] # >>> b = sieve.SieveBound('5|2&4&8') # |&& # >>> b(0, range(20)) # [0, 5, 8, 10, 15, 16] # >>> b = sieve.SieveBound('(5|2)&4&8') # (|)&& # >>> b(0, range(20)) # [0, 8, 16] # >>> # precedence is -, &, | class Sieve: ''' Create a sieve segment from a sieve logical string of any complexity. >>> a = sieve.Sieve('3@11') >>> b = sieve.Sieve('2&4&8|5') >>> c = sieve.Sieve('(5|2)&4&8') ''' def __init__(self, usrStr: str|list[str], z: list[int]|None = None): # note: this z should only be used if usrStr is a str, and not a list if z is None and isinstance(usrStr, str): z = list(range(100)) elif z is None and common.isListLike(usrStr): # if a list pass self._z = z # may be none; will be handled in self._load self._state: t.Literal['exp', 'cmp'] = 'exp' # default start state self._expType = None # either 'simple' or 'complex'; set w/ load self._segmentFormat = 'int' self._segmentFormatOptions = ['int', 'bin', 'unit', 'wid'] self._nonCompressible = False # if current z provides a nullSeg; no compression # variables will re-initialize w/ dedicated methods self._resLib: dict[int, Residual] = {} # store id and object self._resId = 0 # used to calculate residual ids # expanded, compressed form self._expTree = '' # string that stores representation self._expPeriod = -1 # only set if called self._cmpTree = '' # string that stores representation self._cmpPeriod = -1 # only set if called; may not be same as exp self._usrStr = usrStr # store user string, may be None if self._usrStr is not None: self._load() # -------------------------------------------------------------------------- def _load(self): if common.isListLike(self._usrStr): self._resClear() self._initLoadSegment(self._usrStr) # z will be provided self._initCompression() # normal instance, or a manual load else: # process usrStr self._resClear() self._initParse() self._initCompression() def _initCompression(self): # only negative that will show up is binary negative, not unary # some internal intersections may have a complemented residual class self._expType = 'complex' # assume complex if (NEG in self._expTree or LGROUP in self._expTree or RGROUP in self._expTree or XOR in self._expTree): try: self._cmpSegment() # will update self._nonCompressible except IndexError: # case of z not providing a sufficient any segment self._nonCompressible = 1 else: # try intersection try: self._cmpIntersection() self._expType = 'simple' # only if successful except TypeError: # attempted intersection of complemented try: self._cmpSegment() except IndexError: # no segments available self._nonCompressible = 1 method = '' if self._nonCompressible: method = 'no compression possible' elif self._expType == 'complex': method = 'segment' elif self._expType == 'simple': method = 'intersection' return method def _initPeriod(self): ''' Lazy period initialization, called only when needed from public period() method. ''' mListExp = self._resPeriodList('exp') mListCmp = self._resPeriodList('cmp') # get lcm of expanded sieves lcmExp = lcm(*mListExp) if mListExp == mListCmp: self._expPeriod = lcmExp self._cmpPeriod = lcmExp else: # calculate separately self._expPeriod = lcmExp self._cmpPeriod = lcm(*mListCmp) # -------------------------------------------------------------------------- def expand(self): ''' Set this Sieve to its expanded state. ''' self._state = 'exp' def compress(self, z=None): ''' Set this sieve to its compressed state. ''' if z is not None and z != self._z: # only process if z has changed self._z = z self._resClear('cmp') # clear compressed residuals self._initCompression() # may update self._nonCompressible if self._nonCompressible: # do not change state pass # no compression available at this z else: self._state = 'cmp' # -------------------------------------------------------------------------- def _getParameterData(self): ''' Provides a dictionary data representation for exchange ''' data = { 'logStr': self.represent('exp'), } if self._z is None: # get from residual classes, always one at data['z'] = self._resLib[self._resKeyStr(0)].z else: data['z'] = self._z return data # -------------------------------------------------------------------------- # utility functions def setZ(self, z): ''' Set the z as a list. The z is the range of integers to use when generating a sieve segment. ''' self._z = z def setZRange(self, minInt, maxInt): ''' Set the z as a min and max value. The z is the range of integers to use when generating a sieve segment. ''' self._z = list(range(minInt, maxInt + 1)) def setSegmentFormat(self, fmt): # fmt = drawer.strScrub(fmt, 'l') fmt = fmt.strip().lower() if fmt not in self._segmentFormatOptions: raise SieveException(f'cannot set to format: {fmt}') self._segmentFormat = fmt # -------------------------------------------------------------------------- # operator overloading for sieves # problem: redundant parenthesis are not removed def __neg__(self): ''' unary neg operators; return neg object. ''' dataSelf = self._getParameterData() usrStr = ''.join([ NEG, LGROUP, dataSelf['logStr'], RGROUP, ]) z = dataSelf['z'] return Sieve(usrStr, z) def __and__(self, other): ''' &, produces an intersection of two >>> a = sieve.Sieve('3@11') >>> b = sieve.Sieve('2&4&8|5') >>> c = sieve.Sieve('(5|2)&4&8') >>> d = a & b >>> str(d) '{2@0&4@0&8@0|5@0}&{3@2}' ''' dataSelf = self._getParameterData() dataOther = other._getParameterData() usrStr = ''.join([ LGROUP, dataOther['logStr'], RGROUP, AND, LGROUP, dataSelf['logStr'], RGROUP, ]) # take union of z zSet = set(dataSelf['z']) | set(dataOther['z']) z = list(zSet) return Sieve(usrStr, z) def __or__(self, other): ''' |, produces a union >>> a = sieve.Sieve('3@11') >>> b = sieve.Sieve('2&4&8|5') >>> d = a | b >>> str(d) '{2@0&4@0&8@0|5@0}|{3@2}' ''' dataSelf = self._getParameterData() dataOther = other._getParameterData() usrStr = ''.join([ LGROUP, dataOther['logStr'], RGROUP, OR, LGROUP, dataSelf['logStr'], RGROUP, ]) # take union of z zSet = set(dataSelf['z']) | set(dataOther['z']) z = list(zSet) return Sieve(usrStr, z) def __xor__(self, other): ''' ^, produces exclusive disjunction. ''' dataSelf = self._getParameterData() dataOther = other._getParameterData() usrStr = ''.join([ LGROUP, dataOther['logStr'], RGROUP, XOR, LGROUP, dataSelf['logStr'], RGROUP ]) # take union of z zSet = set(dataSelf['z']) | set(dataOther['z']) z = list(zSet) return Sieve(usrStr, z) # -------------------------------------------------------------------------- # string conversions def _parseResidual(self, usrStr): ''' process an arg string for proper Residual creation valid syntax for Mod, shift pairs: all valid: MsubN, M@N, M,N, M if M is given alone, shift is assumed to be 0 this method assumes that all brackets have been replaced with parentheses returns a dictionary of args suitable for creating a Residual class ''' m = 0 # if given a number, not a string if common.isNum(usrStr): return {'m': int(usrStr), 'n': 0, 'neg': 0} usrStr = usrStr.strip() if not usrStr: return None if usrStr.find('sub'): usrStr = usrStr.replace('sub', ',') if usrStr.find('@'): usrStr = usrStr.replace('@', ',') # remove any braces remain, remove # all parenthesis and brackets are converted to braces usrStr = usrStr.replace(LGROUP, '') usrStr = usrStr.replace(RGROUP, '') # check for not if usrStr[0] == '-': # negative/complement neg = 1 # strip to remove any leading white space usrStr = usrStr[1:].strip() else: neg = 0 if not usrStr: return None try: # assume we have either an int (M), or a tuple (M,N) # better to remove the eval, but at least there are no globals or locals this way # waste of two {} dicts -- could be cached, but not worth it for now args = literal_eval(usrStr) except (NameError, SyntaxError, TypeError): return None shift = 0 if common.isNum(args): m = int(args) # int is mod shift = 0 # 0 is given as default shift elif common.isListLike(args): # may only be a list of one element m = args[0] # first is mod if len(args) > 1: shift = args[1] # second is shift else: shift = 0 # return a dictionary of args necessary to create Residual return {'m': m, 'shift': shift, 'neg': neg, } def _parseLogic(self, usrStr): ''' provide synonyms for logical symbols intersection == and, &, * union == or, |, + not == not, - the native format for str representation uses only &, |, - this method converts all other string representations all brackets and braces are replaced with parenthesis parentheses are only used for the internal representation on string representation, braces are restored ''' # if not a string but a number if common.isNum(usrStr): # assume its a single modulus usrStr = int(usrStr) usrStr = f'{usrStr}@0' if usrStr.find('and') >= 0: # replace with '&' usrStr = usrStr.replace('and', AND) if usrStr.find('*') >= 0: # Xenakis notation' usrStr = usrStr.replace('*', AND) if usrStr.find('or') >= 0: usrStr = usrStr.replace('or', OR) if usrStr.find('+') >= 0: usrStr = usrStr.replace('+', OR) if usrStr.find('xor') >= 0: usrStr = usrStr.replace('^', OR) if usrStr.find('not') >= 0: usrStr = usrStr.replace('not', NEG) # all groupings converted to braces if usrStr.find('[') >= 0: # replace brackets w/ parenthesis usrStr = usrStr.replace('[', LGROUP) if usrStr.find(']') >= 0: usrStr = usrStr.replace(']', RGROUP) if usrStr.find('(') >= 0: # replace braces as well usrStr = usrStr.replace('(', LGROUP) if usrStr.find(')') >= 0: usrStr = usrStr.replace(')', RGROUP) # remove space usrStr = usrStr.replace(' ', '') return usrStr # -------------------------------------------------------------------------- def _setInstantiateStr(self, valList): ''' return string necessary to instantiate a set object. ''' valList = list(valList) valList = repr(valList).replace(' ', '') return f'set({valList})' def _resKeyStr(self, resId): return f'' def _resKeys(self, state): ''' get residual keys based on library. ''' if state not in ('cmp', 'exp'): raise SieveException("state must be 'cmp' or 'exp'") if state == 'cmp': libKeys = [] for key in self._resLib: if key in self._cmpTree: libKeys.append(key) return libKeys elif state == 'exp': libKeys = [] for key in self._resLib: if key in self._expTree: libKeys.append(key) return libKeys def _resPeriodList(self, state) -> list[int]: ''' For all residual classes, get the period, or the value of M, and return these in a list. Remove any redundant values and sort. ''' mList: list[int] = [] for key in self._resKeys(state): p = self._resLib[key].period() if p not in mList: mList.append(p) mList.sort() return mList def _resCreate(self, resId, resStr): ''' create a residual object, store in expResidualLib return a string id representation this uses self._z at initialization. ''' resDict = self._parseResidual(''.join(resStr)) if resDict is None: joined = ''.join(resStr) msg = f'cannot parse {joined}' raise SieveException(f'bad residual class notation: ({msg!r})') resObj = Residual(resDict['m'], resDict['shift'], resDict['neg'], self._z) self._resLib[self._resKeyStr(resId)] = resObj return self._resKeyStr(resId) def _resAssign(self, resId, resObj): self._resLib[self._resKeyStr(resId)] = resObj return self._resKeyStr(resId) def _resToSetStr(self, resId, n=0, z=None): ''' this is where residuals are converted to set evaluating strings z should not be stored; should be a temporary value ''' if z is None: # if none given, give internal z = self._z # z is valid, gets default from residual class if not common.isListLike(z) and z is not None: raise SieveException(f'z must be a list of integers, not {z!r}') valList = self._resLib[resId](n, z) # call residual object return self._setInstantiateStr(valList) def _resIdIncrement(self): ''' increment the _resId. ''' self._resId = self._resId + 1 def _resResetId(self): ''' reset self._resId to the next available number may need to re-label some residual classes if gaps develop ids should be contiguous integer sequence ''' iVals = range(len(self._resLib.keys())) for i in iVals: testKey = self._resKeyStr(i) if testKey not in self._cmpTree and testKey not in self._expTree: raise SieveException('gap in residual keys') # set _resId to next available index, the length of the keys self._resId = len(self._resLib.keys()) def _resClear(self, state=None): if state is None: # clear all self._resLib = {} # store id and object self._resId = 0 elif state == 'cmp': cmpKeys = self._resKeys(state) for key in cmpKeys: del self._resLib[key] # reset id to reflect deleted classes self._resResetId() elif state == 'exp': raise SieveException('Expanded residual classes should never be cleared') # -------------------------------------------------------------------------- # expansion methods def _initLoadSegment(self, usrData): ''' load from a segments reload _resId. ''' # clear first self._expTree = [] # string that stores representation # use dynamically generated z segObj = CompressionSegment(usrData, self._z) # a list of values if self._z is None: # non given at init, get from segObj self._z = segObj._z union = segObj() # convert to residual classes for resObj in union: # store resKey in dict, store as string self._expTree.append(self._resAssign(self._resId, resObj)) self._resIdIncrement() self._expTree = OR.join(self._expTree) def _initParse(self, z=None): ''' process usrStr string into proper argument dictionaries for Residual ''' # clear first self._resLib = {} # store id and object self._resId = 0 self._expTree = [] # string that stores representation # will remove all spaces logStr = self._parseLogic(copy.deepcopy(self._usrStr)) # logical string i = 0 while 1: if i == len(logStr): break char = logStr[i] # current char if i == 0: charPrevious = None # first else: charPrevious = logStr[i - 1] if i == len(logStr) - 1: charNext = None # last else: charNext = logStr[i + 1] # if a boundary symbol ({}&|) simply add to string if char in BOUNDS: self._expTree.append(char) i = i + 1 # if NEG is last char this is always an error elif char == NEG and charNext is None: msg = 'negation cannot be used without operands' raise SieveException(f'badly formed logical string (a): ({msg})') # attempting to use negating as a binary operators elif (char == NEG and charPrevious is not None and charPrevious in RESIDUAL): # digit, or @ sign msg = 'negation cannot be used as a binary operator' raise SieveException(f'badly formed logical string (b): ({msg})') # check if NEG is not followed by a digit; # special case of NEG; need to convert into a binary operator elif (char == NEG and charNext is not None and charNext == LGROUP): # if not first char, and the previous char is not an operator or # a delimiter, this is an error (binary negation) if (charPrevious is not None and charPrevious not in (LGROUP, AND, OR, XOR)): msg = 'negation must be of a group and isolated by delimiters' raise SieveException(f'badly formed logical string (c): ({msg})') self._expTree.append(char) i += 1 # processing a normal residual class; only first # char can be negative # NEG, if present, will be followed by digits elif char in string.digits or char == NEG: resStr = [] # string just for this residual class subStart = copy.copy(i) subLen = 0 # first check for leading NEG if logStr[subStart + subLen] == NEG: resStr.append(NEG) subLen = subLen + 1 while 1: # if at the end of the logical string if (subStart + subLen) == len(logStr): break subChar = logStr[subStart + subLen] # neg is boundary, as already gathered above if subChar in BOUNDS or subChar == NEG: break # do not increment else: resStr.append(subChar) subLen = subLen + 1 self._expTree.append(self._resCreate(self._resId, ''.join(resStr))) self._resIdIncrement() i = i + subLen else: # some other char is in here i = i + 1 # do some checks if not self._resLib: raise SieveException('no residual classes defined') self._expTree = ''.join(self._expTree) # -------------------------------------------------------------------------- # compression methods def _cmpIntersection(self): ''' an unbound sieve, intersection Residual ''' self._cmpTree = [] # clear first logStr = copy.copy(self._expTree) # create scratch copy # if not a string but a number orList = logStr.split(OR) intersection = 0 for orGroup in orList: if orGroup == '': continue # need deal with mixed not operations in an and-group andList = orGroup.split(AND) # do intersections, reduce, and add if len(andList) == 1: intersection = self._resLib[andList[0]] else: for i in range(len(andList) - 1): # one less than len if i == 0: # first, get first # problem was here w/ and list value not being in _resLib a = self._resLib[andList[i]] else: a = intersection b = self._resLib[andList[i + 1]] # get second # this may raise an exception if not possible intersection = a & b # operator overloading # store resKey in dict, store as string self._cmpTree.append(self._resAssign(self._resId, intersection)) self._resIdIncrement() self._cmpTree = OR.join(self._cmpTree) def _cmpSegment(self): ''' a bound sieve, uss a newly created segment ''' # clear first self._cmpTree = [] # will use z if set elsewhere seg = self.segment('exp') if not seg: # empty set raise IndexError('empty segment; segment compression not possible') segObj = CompressionSegment(seg, self._z) for resObj in segObj(): self._cmpTree.append(self._resAssign(self._resId, resObj)) self._resIdIncrement() self._cmpTree = OR.join(self._cmpTree) # -------------------------------------------------------------------------- def segment( self, state: t.Literal['cmp']|t.Literal['exp']|None = None, n=0, z=None, segmentFormat=None ) -> list[int]: ''' Return a sieve segment in various formats. >>> a = sieve.Sieve('3@11') >>> a.segment('exp') [2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98] >>> c = sieve.Sieve('(5|2)&4&8') >>> c.segment('cmp', segmentFormat='wid') [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8] ''' if state is None: state = self._state if z is None: z = self._z if segmentFormat is None: segmentFormat = self._segmentFormat if state == 'exp': evalStr = copy.copy(self._expTree) elif state == 'cmp': evalStr = copy.copy(self._cmpTree) else: evalStr = '' keys = self._resKeys(state) # The only "NEG" values that remain are those that are applied to groups. # Replace all remain NEG in the formula w/ '1@1-' # as long as binary negation is evaluated before & and |, this will work # see http://docs.python.org/ref/summary.html # must do this before converting segments (where there will be neg numbers) resObj = Residual(1, 0, 0, z) # create a temporary residual 1@! setStr = self._setInstantiateStr(resObj()) # get segment evalStr = evalStr.replace('-', setStr + '-') # replace residuals (this will add - as -numbers) for key in keys: evalStr = evalStr.replace(key, self._resToSetStr(key, n, z)) # convert all braces to parenthesis evalStr = evalStr.replace(LGROUP, '(') evalStr = evalStr.replace(RGROUP, ')') # this may raise an exception if mal-formed try: # better to remove the eval, but at least there are no globals or locals this way # waste of two {} dicts -- could be cached, but not worth it for now seg = eval(evalStr, {'__builtins__': {'set': set}}, {}) # pylint: disable=eval-used # print('---: ' + evalStr) # print('xxx: ' + repr(seg)) except SyntaxError as se: raise SieveException( f'badly formed logical string ({evalStr})' ) from se seg = list(seg) seg.sort() if segmentFormat in ('bin', 'binary'): return discreteBinaryPad(seg, z) elif segmentFormat == 'unit': return unitNormRange(seg, z) elif segmentFormat in ('wid', 'width'): wid = [] for i in range(len(seg) - 1): wid.append((seg[i + 1] - seg[i])) return wid else: # int, integer return seg def period(self) -> int: ''' Return the period of the sieve. >>> a = sieve.Sieve('3@11') >>> a.period() 3 >>> b = sieve.Sieve('2&4&8|5') >>> b.period() 40 >>> c = sieve.Sieve('(5|2)&4&8') >>> c.period() 40 * Changed in v9: state is taken from the object. ''' # two periods are possible; if residuals are the same # for both exp and cmd, only one is calculated # period only calculated the first time this method is called # check and see if exp has been set yet state = self._state if self._expPeriod == -1: self._initPeriod() if state == 'exp': return self._expPeriod elif state == 'cmp': return self._cmpPeriod else: raise ValueError('State must be exp or cmp') def __call__(self, n=0, z=None, segmentFormat=None): return self.segment(self._state, n, z, segmentFormat) def collect( self, n: int, zMinimum: int, length: int, segmentFormat: str, zStep: int = 100 ) -> list[int]: ''' Collect sieve segment points for the provided length and format. >>> a = sieve.Sieve('3@11') >>> a.collect(10, 100, 10, 'int') [102, 105, 108, 111, 114, 117, 120, 123, 126, 129] ''' # collect a segment to meet a desired length for the segment # z must be extended automatically to continue to search from zMinimum # zStep is the size of each z used to cycle through all z # this seems to only work properly for float and integer sieves found: list[int] = [] p = zMinimum # starting value zExtendCount = 0 while zExtendCount < 10000: # default max to break loops zMin = p zMax = p + zStep # must collect non width formats as integer values; then convert if segmentFormat in ('wid', 'width'): segmentPartial = self.segment(self._state, n, list(range(zMin, zMax)), segmentFormat) else: # if a unit, need to start with integers segmentPartial = self.segment(self._state, n, list(range(zMin, zMax)), 'int') found = found + segmentPartial[:] p = p + zStep # increment start value zExtendCount = zExtendCount + 1 # fail safe if len(found) >= length: break # trim any extra seg = found[:length] if len(seg) != length: raise SieveException('desired length of sieve segment cannot be found') # only width format comes out correct after concatenation # for unit and binary, derive new z based on min and max if segmentFormat == 'unit': # make z to minimum and max value found return unitNormRange(seg, range(seg[0], seg[-1] + 1)) elif segmentFormat in ('bin', 'binary'): # make to minimum and max value found return discreteBinaryPad(seg, range(seg[0], seg[-1] + 1)) else: return seg def represent(self, state=None, style=None): ''' style of None is use for users; adds | to single residuals style abs (absolute) does not add | tos single residual class ''' if state is None: state = self._state if state == 'exp': msg = copy.copy(self._expTree) elif state == 'cmp': msg = copy.copy(self._cmpTree) else: msg = '' # get keys for this library keys = self._resKeys(state) for key in keys: msg = msg.replace(key, self._resLib[key].represent(style)) return msg def __str__(self): return self.represent() # ------------------------------------------------------------------------------ # high level utility obj class PitchSieve: ''' Quick utility generator of :class:`music21.pitch.Pitch` lists from :class:`music21.sieve.Sieve` objects. >>> ps = sieve.PitchSieve('6@0', 'c4', 'c8') >>> [str(p) for p in ps()] ['C4', 'F#4', 'C5', 'F#5', 'C6', 'F#6', 'C7', 'F#7', 'C8'] >>> a = sieve.PitchSieve('4@7') >>> [str(p) for p in a()] ['E-3', 'G3', 'B3', 'E-4', 'G4', 'B4'] ''' def __init__(self, sieveString, pitchLower: str|None = None, pitchUpper: str|None = None, pitchOrigin: str|None = None, eld: int|float = 1): self.sieveString = sieveString # logical sieve string # should be in a try block self.sieveObject: Sieve = Sieve(self.sieveString) if pitchLower is not None: self.pitchLower = pitch.Pitch(pitchLower) else: self.pitchLower = pitch.Pitch('c3') if pitchUpper is not None: self.pitchUpper = pitch.Pitch(pitchUpper) else: self.pitchUpper = pitch.Pitch('c5') if pitchOrigin is not None: self.pitchOrigin = pitch.Pitch(pitchOrigin) else: # use pitchLower value self.pitchOrigin = copy.deepcopy(self.pitchLower) if eld is not None: self.eld = float(eld) else: self.eld = eld # environLocal.printDebug(['PitchSieve', eld]) def __call__(self): # noinspection PyShadowingNames ''' Return a sieve segment as a list of :class:`music21.pitch.Pitch` objects, mapped to the range between pitchLower and pitchUpper. >>> a = sieve.PitchSieve('4@7&5@4') >>> a() [] >>> a = sieve.PitchSieve('13@3|13@6|13@9', 'c1', 'c10') >>> ', '.join([str(p) for p in a()]) 'E-1, F#1, A1, E2, G2, B-2, F3, G#3, B3, F#4, A4, C5, G5, B-5, C#6, G#6, B6, D7, A7, C8, E-8, B-8, C#9, E9, B9' >>> a = sieve.PitchSieve('3@0', 'c4', 'c5', 'c4', 0.5) >>> a.eld 0.5 The following is a microtonal pitch sieve; presently these are not displayed; true values are [0, 1.5, 3.0, 4.5, 6.0, 7.5, 9.0, 10.5, 12.0] >>> pitches = a() >>> ', '.join([str(p) for p in pitches]) 'C4, C#~4, E-4, E~4, F#4, G~4, A4, B`4, C5' True values: [0.5, 2.0, 3.5, 5.0, 6.5, 8.0, 9.5, 11.0] >>> a = sieve.PitchSieve('3@0', 'c4', 'c5', 'c#4', 0.5) >>> pitches = a() >>> ', '.join([str(p) for p in pitches]) 'C~4, D4, E`4, F4, F#~4, G#4, A~4, B4' ''' minPS = self.pitchLower.ps maxPS = self.pitchUpper.ps z = list(range(int(minPS), int(maxPS + 1))) n = self.pitchOrigin.ps # shift origin # get integer range if self.eld == 1: sieveSegIntegers = self.sieveObject(n, z) # make value negative sieveSeg = [] for psNum in sieveSegIntegers: p = pitch.Pitch() p.ps = psNum sieveSeg.append(p) else: # microtonal eld # returns all possible values in this range valList = unitNormStep(self.eld, minPS, maxPS, normalized=False) # this z will not be shifted # need to get list of appropriate size z = list(range(len(valList))) # get a binary segment binSeg = self.sieveObject(n, z, 'bin') sieveSeg = [] # when there is activity on the unitSeg, return the value for i in range(len(binSeg)): if binSeg[i] == 1: p = pitch.Pitch() p.ps = valList[i] sieveSeg.append(p) return sieveSeg def getIntervalSequence(self) -> list[interval.Interval]: ''' Return a list of Interval objects that defines the complete structure of this :class:`music21.sieve.Sieve`. >>> a = sieve.PitchSieve('3@0') >>> a.getIntervalSequence() [] >>> a = sieve.PitchSieve('3@0|7@0') >>> a.sieveObject.segment() [0, 3, 6, 7, 9, 12, 14, 15, 18, 21, 24, 27, 28, 30, 33, 35, 36, 39, 42, 45, 48, 49, 51, 54, 56, 57, 60, 63, 66, 69, 70, 72, 75, 77, 78, 81, 84, 87, 90, 91, 93, 96, 98, 99] >>> a.sieveObject.period() 21 >>> a.getIntervalSequence() [, , , , , , , , ] This is the PitchSieve for a major scale: >>> b = sieve.PitchSieve('(-3@2 & 4) | (-3@1 & 4@1) | (3@2 & 4@2) | (-3 & 4@3)') >>> b.getIntervalSequence() [, , , , , , ] ''' # get a z for the complete period # try: # z = range(self.sieveObject.period() + 1) # except (OverflowError, MemoryError): # environLocal.printDebug('failed to generate a z with period:', # self.sieveObject.period()) p = self.sieveObject.period() z: list[int]|None if p < 999999999: z = list(range(p + 1)) else: # too big to get z as list of values z = None # get widths, then scale by eld # note that the shift here might not always be zero widthSegments = self.sieveObject(0, z, segmentFormat='wid') post: list[interval.Interval] = [] # value = 0 for i, width in enumerate(widthSegments): # environLocal.printDebug(['stepStart', stepStart, 'stepEnd', stepEnd]) intervalObj = interval.Interval(width * self.eld) post.append(intervalObj) if not post: raise PitchSieveException('interval segment has no values') return post # integer steps have no eld # integerSteps = self.sieveObject(0, z, format='int') # # post = [] # for i, step in enumerate(integerSteps): # stepStart = step # if i < len(integerSteps) - 1: # stepEnd = integerSteps[i + 1] # else: # break # # environLocal.printDebug(['stepStart', stepStart, 'stepEnd', stepEnd]) # intervalObj = interval.Interval(stepEnd-stepStart) # post.append(intervalObj) # # if len(post) == 0: # raise PitchSieveException('interval segment has no values') # return post # ------------------------------------------------------------------------------ class Test(unittest.TestCase): def testDummy(self): self.assertEqual(True, True) def pitchOut(self, listIn): out = '[' for p in listIn: out += str(p) + ', ' out = out[0:len(out) - 2] out += ']' return out def testIntersection(self): a = Residual(3) testArgs = [(3, 6, 2, 5), (4, 6, 1, 3), (5, 4, 3, 2), ] for m1, m2, n1, n2 in testArgs: a = Residual(m1, n1) b = Residual(m2, n2) i = a & b # do intersection def testSieveParse(self): testArgs = ['-5 | 4 & 4sub3 & 6 | 4 & 4', '2 or 4 and 4 & 6 or 4 & 4', 3, # '3 and 4 or not 3, 1 and 4, 1 or not 3 and 4, 2 or not 3, 2 and 4, 3', (2, 4, 6, 8), (1, 6, 11, 16, 17), ] for arg in testArgs: # environLocal.printDebug(['testSieveParse', arg]) testObj = Sieve(arg) dummy = testObj(0, list(range(30))) def testSievePitch(self): unused_testObj = PitchSieve('-5 | 4 & 4sub3 & 6', 'b3', 'f#4') testObj = PitchSieve('-5 | 4 & 4sub3 & 6') dummy = testObj.pitchLower, testObj.pitchUpper dummy = testObj() def testTimePoint(self): args = [(3, 6, 12), (0, 6, 12, 15, 18, 24, 30, 36, 42), (4, 6, 13), (2, 3, 4, 5, 8, 9, 10, 11, 14, 17, 19, 20, 23, 24, 26, 29, 31), # (3, 23, 33, 47, 63, 70, 71, 93, 95, 119, 123, 143, 153, 167), (0, 2, 4, 5, 7, 9, 11, 12, 14, 16, 17, 19, 21, 23, 24), (1, 2, 3, 4, 5, 6, 7, 8, 9, 10), (-8, -6, -4, -2, 0, 2, 1), ] for src in args: obj = CompressionSegment(src) sObj = Sieve(str(obj)) dummy = sObj() def testSieve(self): z = list(range(100)) usrStr = '3@2 & 4@1 | 2@0 & 3@1 | 3@3 | -4@2' a = Sieve(usrStr, z) self.assertEqual(str(a), '3@2&4@1|2@0&3@1|3@0|-4@2') usrStr = '-(3@2 & -4@1 & -(12@3 | 12@8) | (-2@0 & 3@1 | (3@3)))' a = Sieve(usrStr, z) self.assertEqual(str(a), '-{3@2&-4@1&-{12@3|12@8}|{-2@0&3@1|{3@0}}}') # 'example from Flint, on Psapha' usrStr = ('[(8@0 | 8@1 | 8@7) & (5@1 | 5@3)] | [(8@0 | 8@1 | 8@2) & 5@0] | ' '[8@3 & (5@0 | 5@1 | 5@2 | 5@3 | 5@4)] | ' '[8@4 & (5@0 | 5@1 | 5@2 | 5@3 | 5@4)] | ' '[(8@5 | 8@6) & (5@2 | 5@3 | 5@4)] | (8@1 & 5@2) | (8@6 & 5@1)') a = Sieve(usrStr, z) self.assertEqual(str(a), '{{8@0|8@1|8@7}&{5@1|5@3}}|{{8@0|8@1|8@2}&5@0}|' '{8@3&{5@0|5@1|5@2|5@3|5@4}}|{8@4&{5@0|5@1|5@2|5@3|5@4}}|' '{{8@5|8@6}&{5@2|5@3|5@4}}|{8@1&5@2}|{8@6&5@1}') # 'major scale from FM, p197' usrStr = '(-3@2 & 4) | (-3@1 & 4@1) | (3@2 & 4@2) | (-3 & 4@3)' a = Sieve(usrStr, z) self.assertEqual(str(a), '{-3@2&4@0}|{-3@1&4@1}|{3@2&4@2}|{-3@0&4@3}') # 'nomos alpha sieve' usrStr = ('(-(13@3 | 13@5 | 13@7 | 13@9) & 11@2) | (-(11@4 | 11@8) & 13@9) | ' '(13@0 | 13@1 | 13@6)') a = Sieve(usrStr, z) self.assertEqual(str(a), '{-{13@3|13@5|13@7|13@9}&11@2}|{-{11@4|11@8}&13@9}|{13@0|13@1|13@6}') def testPitchSieveA(self): from music21 import sieve s1 = sieve.PitchSieve('3@0|7@0', 'c2', 'c6') self.assertEqual(self.pitchOut(s1()), '[C2, E-2, F#2, G2, A2, C3, D3, E-3, F#3, A3, C4, E-4, ' 'E4, F#4, A4, B4, C5, E-5, F#5, A5, C6]') s1 = sieve.PitchSieve('3@0|7@0', 'c2', 'c6', eld=2) self.assertEqual(self.pitchOut(s1()), '[C2, D2, F#2, C3, E3, F#3, C4, F#4, C5, F#5, G#5, C6]') def testPitchSieveB(self): from music21 import sieve # mircotonal elds s1 = sieve.PitchSieve('1@0', 'c2', 'c6', eld=0.5) self.assertEqual(self.pitchOut(s1()), '[C2, C~2, C#2, C#~2, D2, D~2, E-2, E`2, E2, E~2, F2, F~2, F#2, ' 'F#~2, G2, G~2, G#2, G#~2, A2, A~2, B-2, B`2, B2, B~2, C3, C~3, C#3, ' 'C#~3, D3, D~3, E-3, E`3, E3, E~3, F3, F~3, F#3, F#~3, G3, G~3, G#3, ' 'G#~3, A3, A~3, B-3, B`3, B3, B~3, C4, C~4, C#4, C#~4, D4, D~4, E-4, ' 'E`4, E4, E~4, F4, F~4, F#4, F#~4, G4, G~4, G#4, G#~4, A4, A~4, B-4, ' 'B`4, B4, B~4, C5, C~5, C#5, C#~5, D5, D~5, E-5, E`5, E5, E~5, F5, F~5, ' 'F#5, F#~5, G5, G~5, G#5, G#~5, A5, A~5, B-5, B`5, B5, B~5, C6]') s1 = sieve.PitchSieve('3@0', 'c2', 'c6', eld=0.5) self.assertEqual(self.pitchOut(s1()), '[C2, C#~2, E-2, E~2, F#2, G~2, A2, B`2, C3, C#~3, E-3, E~3, F#3, G~3, ' 'A3, B`3, C4, C#~4, E-4, E~4, F#4, G~4, A4, B`4, C5, C#~5, E-5, E~5, F#5, ' 'G~5, A5, B`5, C6]') # sieve that breaks LCM # >>> t = sieve.Sieve((3, 99, 123123, 2433, 2050)) # ------------------------------------------------------------------------------ # define presented order in documentation _DOC_ORDER: list[type] = [] if __name__ == '__main__': import music21 music21.mainTest(Test)