#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Copyright (c) 2014-2018 Gonzalo Ciruelos <gonzalo.ciruelos@gmail.com>
Copyright (c) 2018-2023 Federico Ferri <federico.ferri.it@gmail.com>
"""

import re
from collections import namedtuple


def UnsupportedOperands(op, type1, type2):
    def as_type(x):
        return x if isinstance(x, type) else type(x)
    fmt = 'unsupported operand type(s) for {}: {} and {}'
    type1 = as_type(type1)
    type2 = as_type(type2)
    return TypeError(fmt.format(op, type1.__name__, type2.__name__))


class PitchClassRenderingOptions:
    use_unicode = True
    use_solfege = False


class PitchClass:
    """
    The pitch class.

    The pitch class refers to all pitches that are a whole number of octaves apart.

    The pitch class is composed by:
    * a pitch name,
    * (optional) accidentals, up to 6.

    Commonly used pitch names are the 7 letters: C, D, E, F, G, A, and B.

    Alternatively, solfège names (Do, Re, Mi, ...) are recognized.
    """

    max_accidentals = 6

    Info = namedtuple('Info', ('name', 'index', 'number', 'normal_accidentals', 'solfege_names'))

    info = {
        'C': Info('C', 0, 0,      {0, 1}, ('Do',)),
        'D': Info('D', 1, 2,  {-1, 0, 1}, ('Re',)),
        'E': Info('E', 2, 4,  {-1, 0},    ('Mi',)),
        'F': Info('F', 3, 5,      {0, 1}, ('Fa',)),
        'G': Info('G', 4, 7,  {-1, 0, 1}, ('Sol',)),
        'A': Info('A', 5, 9,  {-1, 0, 1}, ('La',)),
        'B': Info('B', 6, 11, {-1, 0},    ('Si', 'Ti')),
    }

    names = tuple(info.keys())
    solfege_names_inv = {sn: info.name for info in info.values() for sn in info.solfege_names}
    all_names = names + tuple(solfege_names_inv.keys())

    pattern_str = '(' + '|'.join(all_names) + ')(' + \
        '|'.join(('b{0,$MAX}', '#{0,$MAX}', '♭{0,$MAX}', '♯{0,$MAX}', '𝄫', '𝄪')) \
        .replace('$MAX', str(max_accidentals)) + ')'
    pattern = re.compile('^' + pattern_str + '$')

    rendering_options = PitchClassRenderingOptions()

    @staticmethod
    def all(max_accidentals=-1):
        """
        Generate all pitch classes.

        Depending on the `max_accidentals` parameter, it will include:
        * only "basic" accidentals, as found on the black keys of a piano, if `max_accidentals` is -1;
        * no accidentals, if `max_accidentals` is 0;
        * at most 1 accidental, if `max_accidentals` is 1;
        * and so on...
        """
        if not isinstance(max_accidentals, int):
            raise TypeError('Invalid max_accidentals type')
        if max_accidentals < -1:
            raise ValueError('Invalid max_accidentals value')

        if max_accidentals == -1:
            for n, info in PitchClass.info.items():
                for acc in info.normal_accidentals:
                    yield PitchClass(n, acc)
        else:
            for n in PitchClass.names:
                for acc in [0] + [sign * (a + 1) for a in range(max_accidentals) for sign in (-1, 1)]:
                    yield PitchClass(n, acc)

    @staticmethod
    def parse(s):
        if isinstance(s, PitchClass):
            return s
        if not isinstance(s, str):
            raise TypeError('Invalid input type')

        m = PitchClass.pattern.match(s)
        if m is None:
            raise ValueError('Could not parse PitchClass: {!r}'.format(s))

        name = m.group(1)

        acc = m.group(2)
        if acc == '':
            acc = 0
        elif acc == '𝄫':
            acc = -2
        elif acc == '𝄪':
            acc = 2
        else:
            acc = len(acc) * {'b': -1, '#': 1, '♭': -1, '♯': 1}[acc[0:1]]

        return PitchClass(name, acc)

    def __init__(self, name, accidentals=None):
        """
        Construct a pitch class from either:
        * pitch name (A, B, C, D, E, F, or G) and number of accidentals (negative for flat, positive for sharp);
        * its string representation, e.g. 'C#'.
        """

        if isinstance(name, str) and accidentals is None and name not in self.all_names:
            pc = PitchClass.parse(name)
            for f in ('name', 'accidentals'):
                setattr(self, f, getattr(pc, f))
            return

        if not isinstance(name, str):
            raise TypeError('Invalid name type')
        if accidentals is None:
            accidentals = 0
        if not isinstance(accidentals, int):
            raise TypeError('Invalid accidentals type')
        if abs(accidentals) > PitchClass.max_accidentals:
            raise ValueError('Too many accidentals: {}'.format(accidentals))

        if name in PitchClass.names:
            self.name = name
        elif name in PitchClass.solfege_names_inv:
            self.name = PitchClass.solfege_names_inv[name]
        else:
            raise ValueError('Invalid pitch name: {!r}'.format(name))

        self.accidentals = accidentals

    def __lt__(self, other):
        return (PitchClass.info[self.name].number, self.accidentals) < \
               (PitchClass.info[other.name].number, other.accidentals)

    def __le__(self, other):
        return self == other or self < other

    def __str__(self):
        return self.name_str + self.accidentals_str

    def __repr__(self):
        return 'PitchClass({!r})'.format(str(self))

    def __hash__(self):
        return hash(str(self))

    def __eq__(self, other):
        return str(self) == str(other)

    @property
    def index(self):
        return PitchClass.info[self.name].index

    @property
    def number(self):
        return PitchClass.info[self.name].number + self.accidentals

    @property
    def name_str(self):
        if PitchClass.rendering_options.use_solfege:
            return PitchClass.info[self.name].solfege_names[0]
        else:
            return self.name

    @property
    def accidentals_str(self):
        if self.accidentals == 0:
            return ''

        num = abs(self.accidentals)
        sign = self.accidentals // num
        if PitchClass.rendering_options.use_unicode:
            if num == 2:
                return {-1: '𝄫', 1: '𝄪'}[sign]
            else:
                return {-1: '♭', 1: '♯'}[sign] * num
        else:
            return {-1: 'b', 1: '#'}[sign] * num

    def flat(self):
        return PitchClass(self.name, self.accidentals - 1)

    def sharp(self):
        return PitchClass(self.name, self.accidentals + 1)

    def natural(self):
        return PitchClass(self.name, 0)

    def to_octave(self, octave):
        return Note(self, octave)

    @property
    def lilypond_notation(self):
        s = self.name.lower()
        for i in range(-self.accidentals):
            s += 'es'
        for i in range(self.accidentals):
            s += 'is'
        return s


class Note:
    """
    The note class.

    A note refers to a specific pitch, and it is composed by:
    * the pitch class,
    * the octave.
    """

    pattern_str = '(' + PitchClass.pattern_str + r')(\d{1})'
    pattern = re.compile('^' + pattern_str + '$')

    @staticmethod
    def all(min_octave=4, max_octave=4, max_accidentals=-1):
        for octave in range(min_octave, max_octave + 1):
            for pc in PitchClass.all(max_accidentals):
                yield Note(pc, octave)

    @staticmethod
    def parse(s):
        if isinstance(s, Note):
            return s
        if not isinstance(s, str):
            raise TypeError('Invalid input type')

        m = Note.pattern.match(s)
        if m is None:
            raise ValueError('Could not parse Note: {!r}'.format(s))

        pc_name, *_, octave = m.groups()
        return Note(PitchClass.parse(pc_name), int(octave))

    number_inv_mapping = {}

    @staticmethod
    def from_number(number, allowed_accidentals=range(-2, 3)):
        if not Note.number_inv_mapping:
            # generate the inverse mapping once:
            for n in Note.all(0, 9, PitchClass.max_accidentals):
                if n.number not in Note.number_inv_mapping:
                    Note.number_inv_mapping[n.number] = set()
                Note.number_inv_mapping[n.number].add(n)

        return set(n for n in Note.number_inv_mapping.get(number, [])
                   if (allowed_accidentals == -1 and
                       n.pitch_class.accidentals in PitchClass.info[n.pitch_class.name].normal_accidentals)
                   or (allowed_accidentals != -1 and
                       n.pitch_class.accidentals in allowed_accidentals))

    @staticmethod
    def from_midi_note(midi_note, allowed_accidentals=range(-2, 3)):
        return Note.from_number(midi_note - 12, allowed_accidentals)

    @staticmethod
    def from_numbers(numbers, allowed_accidentals=range(-2, 3)):
        if 1 in allowed_accidentals and -1 in allowed_accidentals:
            # need to split into two subproblems
            raise NotImplementedError
        # XXX: we assume it is either [-n,0] or [0,n] range
        #      (not 100% correct and/or safe)
        m = {n: Note.from_number(n, allowed_accidentals) for n in numbers}
        import constraint
        p = constraint.Problem()

        for n, notes in m.items():
            p.addVariable(n, list(notes))

        def un(n):
            # str of unaltered note
            return n.pitch_class.name + str(n.octave)
        for n1 in m:
            for n2 in m:
                if n1 != n2:
                    p.addConstraint(lambda a, b: un(a) != un(b), [n1, n2])

        solutions = p.getSolutions()

        return tuple(tuple(solution[n] for n in numbers) for solution in solutions)

    @staticmethod
    def from_midi_notes(midi_notes, allowed_accidentals=range(-2, 3)):
        return Note.from_numbers([n - 12 for n in midi_notes], allowed_accidentals)

    def __init__(self, pitch_class, octave=None):
        """
        Construct a note from either:
        * pitch class and octave;
        * its string representation, e.g. 'C#4'
        """

        if octave is None:
            n = Note.parse(pitch_class)
            for f in ('pitch_class', 'octave', 'number'):
                setattr(self, f, getattr(n, f))
            return

        if not isinstance(pitch_class, PitchClass):
            raise TypeError('Invalid pitch_class type')
        if not isinstance(octave, int):
            raise TypeError('Invalid octave type')
        if octave not in range(10):
            raise ValueError('Invalid octave number')

        self.pitch_class = pitch_class
        self.octave = octave
        self.number = self.pitch_class.number + self.octave * 12

    def __add__(self, other):
        if isinstance(other, Interval):
            if other.is_compound():
                from functools import reduce
                return reduce(lambda a, b: a + b, other.split(), self)

            assert other.size != 0
            new_index = (self.pitch_class.index + other.size -
                         (1 if other.size > 0 else -1)) % len(PitchClass.names)
            new_pitch_name = PitchClass.names[new_index]

            new_number = self.number + other.semitones

            new_note_octave = self.octave + int(self.pitch_class.name in PitchClass.names[8 - other.size:])

            difference = new_number % 12 - PitchClass.info[new_pitch_name].number
            if difference < -PitchClass.max_accidentals:
                difference += 12
            if difference > PitchClass.max_accidentals:
                difference -= 12

            return Note(PitchClass(new_pitch_name, difference), new_note_octave)
        else:
            raise UnsupportedOperands('+', self, other)

    def __sub__(self, other):
        if isinstance(other, Interval):
            if other.is_compound():
                from functools import reduce
                return reduce(lambda a, b: a - b, other.split(), self)

            return self.to_octave(self.octave - 1) + other.complement()
        elif isinstance(other, Note):
            semitones = self.number - other.number
            if semitones < -1:
                raise ArithmeticError('Interval smaller than d1')
            octaves = 0
            while semitones >= 12:
                semitones -= 12
                octaves += 1

            size = self.pitch_class.index - other.pitch_class.index
            size += 1 if size >= 0 else -1
            size = (size + (1 if size < 0 else -1)) % 7 + 1

            for i in Interval.all(True):
                if i.size == size and i.semitones == semitones:
                    return Interval(i.quality + str(octaves * 7 + size))

            raise ValueError('Interval N={} S={}'.format(size, semitones))
        else:
            raise UnsupportedOperands('-', self, other)

    @property
    def midi_note(self):
        return self.number + 12

    @property
    def frequency(self):
        from math import pow
        return 440.0 * pow(2, (self.number - Note('A4').number) / 12.)

    def to_octave(self, octave):
        return Note(self.pitch_class, octave)

    @property
    def lilypond_notation(self):
        oct_str = ''
        if self.octave < 3:
            oct_str = ',' * (3 - self.octave)
        elif self.octave > 3:
            oct_str = '\'' * (self.octave - 3)
        return self.pitch_class.lilypond_notation.replace('b', 'es').replace('#', 'is').lower() + oct_str

    def __lt__(self, other):
        return (self.octave, self.pitch_class) < (other.octave, other.pitch_class)

    def __le__(self, other):
        return self == other or self < other

    def __repr__(self):
        return 'Note({!r})'.format(str(self))

    def __str__(self):
        return str(self.pitch_class) + str(self.octave)

    def __hash__(self):
        return hash(str(self))

    def __eq__(self, other):
        return str(self) == str(other)


class Interval:
    """
    The interval class.

    The intervals are to be parsed in th following way:
    * the quality, (m, M, p, A, d)
    * the size.

    For example, 'd8', 'P1', 'A5' are valid intervals. 'P3', '5' are not.
    """

    pattern_str = r'(d+|m|P|M|A+)(\d+)'
    pattern = re.compile('^' + pattern_str + '$')

    intervals = {
        'd1': -1,           'P1': 0,            'A1': 1,
        'd2': 0,  'm2': 1,            'M2': 2,  'A2': 3,
        'd3': 2,  'm3': 3,            'M3': 4,  'A3': 5,
        'd4': 4,            'P4': 5,            'A4': 6,
        'd5': 6,            'P5': 7,            'A5': 8,
        'd6': 7,  'm6': 8,            'M6': 9,  'A6': 10,
        'd7': 9,  'm7': 10,           'M7': 11, 'A7': 12,
        'd8': 11,           'P8': 12,           'A8': 13,
    }

    quality_inverse = {
        'P': 'P',
        'd': 'A',
        'A': 'd',
        'm': 'M',
        'M': 'm',
    }

    # generate double, tryply, etc... augmented/diminished intervals:
    intervals = (lambda intervals:
                 dict(tuple(intervals.items()) +
                      tuple((dA * k + str(sz), intervals[dA + str(sz)] + mp * (k - 1))
                            for k in (2, 3)
                            for sz in range(1, 9)
                            for (dA, mp) in (('d', -1), ('A', 1)))))(intervals)
    quality_inverse = (lambda quality_inverse:
                       dict(tuple(quality_inverse.items()) +
                            tuple((dA * k, Ad * k)
                                  for k in (2, 3)
                                  for (dA, Ad) in (('d', 'A'), ('A', 'd')))))(quality_inverse)

    @staticmethod
    def all(include_atypical=False):
        for name in Interval.intervals:
            interval = Interval(name)
            if include_atypical or interval.semitones in range(13):
                yield Interval(name)

    @staticmethod
    def parse(s):
        if isinstance(s, Interval):
            return s
        if not isinstance(s, str):
            raise TypeError('Invalid input type')

        m = Interval.pattern.match(s)
        if m is None:
            raise ValueError('Could not parse Interval: {!r}'.format(s))

        quality, size = m.groups()
        return Interval(quality, int(size))

    def __init__(self, quality, size=None):
        """
        Construct an interval from either:
        * quality (str) and size (int);
        * its string representation, e.g. 'd5'
        """

        if size is None:
            n = Interval.parse(quality)
            for f in ('quality', 'size', 'semitones'):
                setattr(self, f, getattr(n, f))
            return

        if not isinstance(quality, str):
            raise TypeError('Invalid quality type')
        if quality not in Interval.quality_inverse:
            raise ValueError('Invalid interval quality')
        if not isinstance(size, int):
            raise TypeError('Invalid size type')
        if size <= 0:
            raise ValueError('Invalid interval size')

        self.quality = quality
        self.size = size
        self.semitones = 0

        # compound intervals:
        size = self.size
        while size > 8:
            size -= 7
            self.semitones += 12

        try:
            self.semitones += self.intervals[quality + str(size)]
        except KeyError:
            raise ValueError('Invalid interval {!r}.'.format(quality + str(size)))

    def __add__(self, other):
        if isinstance(other, Interval):
            n = Note('C0')
            return n + self + other - n
        else:
            raise TypeError('Cannot add {} to Interval'.format(type(other).__name__))

    def __sub__(self, other):
        if isinstance(other, Interval):
            if other.size > self.size:
                raise ArithmeticError('Cannot subtract a greater interval')
            n = Note('C0')
            return (n + self) - (n + other)
        else:
            raise TypeError('Cannot subtract {} from Interval'.format(type(other).__name__))

    def __lt__(self, other):
        return (self.size, self.semitones) < (other.size, other.semitones)

    def __le__(self, other):
        return self == other or self < other

    def __str__(self):
        return self.quality + str(self.size)

    def __repr__(self):
        return 'Interval({!r})'.format(str(self))

    def __hash__(self):
        return hash(str(self))

    def __eq__(self, other):
        return str(self) == str(other)

    def is_compound(self):
        return self.size > 8

    def split(self):
        """
        Split a compound interval into simple intervals.
        The sum of splitted intervals is equal to the compound interval.
        """
        ret = []
        i = Interval(str(self))
        while i.is_compound():
            i.size -= 7
            i.semitones -= 12
            ret.append(Interval('P8'))
        ret.append(i)
        return ret

    def complement(self):
        """
        Return the complement of this interval also known as inverted interval.
        The sum of this interval plus its complement is equal to 1 octave (P8),
        except for the case of A8, for which there is no d1 interval.
        """
        if self.is_compound():
            raise ValueError('Cannot invert a compound interval')
        else:
            n = 9 - self.size
            q = self.quality_inverse[self.quality]
            return Interval(q + str(n))

    def reduce(self):
        if self.size < 8:
            return self
        i = Interval(str(self))
        i.size -= 7 * ((i.size - 1) // 7)
        return i


class Chord:
    """
    The chord class.

    Contains recipes for common chords.
    """

    recipes = {
        'maj':       ('P1', 'M3', 'P5'),
        'min':       ('P1', 'm3', 'P5'),
        'aug':       ('P1', 'M3', 'A5'),
        'dim':       ('P1', 'm3', 'd5'),
        'dom7':      ('P1', 'M3', 'P5', 'm7'),
        'min7':      ('P1', 'm3', 'P5', 'm7'),
        'maj7':      ('P1', 'M3', 'P5', 'M7'),
        'aug7':      ('P1', 'M3', 'A5', 'm7'),
        'dim7':      ('P1', 'm3', 'd5', 'd7'),
        'min7dim5':  ('P1', 'm3', 'd5', 'm7'),
        'sus2':      ('P1', 'M2', 'P5'),
        'sus4':      ('P1', 'P4', 'P5'),
        'dom7sus4':  ('P1', 'P4', 'P5', 'm7'),
        'maj7sus4':  ('P1', 'P4', 'P5', 'M7'),
        'open5':     ('P1', 'P5', 'P8'),
        'dom9':      ('P1', 'M3', 'P5', 'm7', 'M9'),
        'min9':      ('P1', 'm3', 'P5', 'm7', 'M9'),
        'maj9':      ('P1', 'M3', 'P5', 'M7', 'M9'),
        'aug9':      ('P1', 'M3', 'A5', 'm7', 'M9'),
        'dim9':      ('P1', 'm3', 'd5', 'd7', 'M9'),
        'maj6':      ('P1', 'M3', 'P5', 'M6'),
        'min6':      ('P1', 'm3', 'P5', 'm6'),
        'dom6':      ('P1', 'M3', 'P5', 'm6'),
        'min/maj6':  ('P1', 'm3', 'P5', 'M6'),
    }

    aliases = {
        'M':       'maj',
        'm':       'min',
        '+':       'aug',
        '°':       'dim',
        'sus':     'sus4',
        '7':       'dom7',
        'm7':      'min7',
        'M7':      'maj7',
        '+7':      'aug7',
        '7aug5':   'aug7',
        '7#5':     'aug7',
        'm7dim5':  'min7dim5',
        '°7':      'min7dim5',
        'ø7':      'min7dim5',
        'm7b5':    'min7dim5',
        '7sus':    'dom7sus4',
        '7sus4':   'dom7sus4',
        'maj7sus': 'maj7sus4',
        '9':       'dom9',
        'm9':      'min9',
        'M9':      'maj9',
        '+9':      'aug9',
        '°9':      'dim9',
        'M6':      'maj6',
        'm6':      'min6',
        '6':       'dom6',
        'm/M6':    'min/maj6',
    }

    recipes_inv = {v: k for k, v in recipes.items()}

    RecipeInfo = namedtuple('RecipeInfo', ('known', 'name', 'inversion', 'full_name'),
                            defaults=(False, '', 0, ''))

    @staticmethod
    def all(root=None):
        if root is None:
            roots = PitchClass.all()
        elif isinstance(root, (list, set, tuple)):
            roots = root
        elif isinstance(root, PitchClass):
            roots = [root]
        else:
            raise TypeError('Invalid root type: {}'.format(type(root)))
        for root in roots:
            for name in Chord.recipes:
                yield Chord(root, name)

    @staticmethod
    def parse(s):
        if isinstance(s, Chord):
            return s
        if '/' in s:
            chord, root = s.split('/')
            chord = Chord.parse(chord)
            root = PitchClass.parse(root)
            inversion = chord.pitches.index(root)
            return chord.invert(inversion)

        for suffix in sorted(set(Chord.recipes.keys()) | set(Chord.aliases.keys()), key=lambda x: -len(x)):
            if s.endswith(suffix):
                chord_type = suffix
                return Chord(PitchClass(s[:-len(suffix)]), chord_type)

        raise ValueError('Invalid chord: {!r}'.format(root))

    def __init__(self, root, chord_type=None):
        """
        Construct a chord from either:
        * root (pitch class), chord type;
        * its string representation, e.g. 'C#maj7'.

        `chord_type` can be a string (standard recipes, e.g.: min, dim, maj7, aug9, etc...) or a list of intervals.

        When using exotic chord recipes, string rendering of chords will not work, and intervals will be displayed.
        """

        if isinstance(root, str) and chord_type is None:
            c = Chord.parse(root)
            for f in ('root', 'intervals'):
                setattr(self, f, getattr(c, f))
            return

        if isinstance(root, str):
            root = PitchClass.parse(root)
        if not isinstance(root, PitchClass):
            raise TypeError('Invalid root type')
        if chord_type is None:
            chord_type = 'maj'
        if isinstance(chord_type, str):
            if chord_type in self.aliases:
                chord_type = self.aliases[chord_type]
            if chord_type not in self.recipes.keys():
                raise ValueError('Invalid chord_type value: {}.'.format(chord_type))
            chord_type = self.recipes[chord_type]
        if not isinstance(chord_type, tuple):
            raise TypeError('Invalid chord_type type: {}.'.format(type(chord_type).__name__))
        if all(isinstance(x, str) for x in chord_type):
            chord_type = tuple(Interval(x) for x in chord_type)
        if not all(isinstance(x, Interval) for x in chord_type):
            raise TypeError('Invalid chord_type element type: {}.'.format(type(chord_type).__name__))

        self.root = root
        self.intervals = tuple(sorted(chord_type))

    def __lt__(self, other):
        return (self.root, self.intervals) < (other.root, other.intervals)

    def __le__(self, other):
        return self == other or self < other

    def __repr__(self):
        return 'Chord({!r})'.format(str(self))

    def __str__(self):
        return self.recipe.full_name

    def __hash__(self):
        return hash((self.root,) + tuple(self.intervals))

    def __eq__(self, other):
        return self.root == other.root and self.intervals == other.intervals

    def __len__(self):
        return len(self.intervals)

    @property
    def recipe(self):
        recipe = getattr(self, '__recipe', None)
        if recipe is None:
            try:
                n, i = next(self.identify_from_intervals(self.intervals))
                s = '{}{}'.format(self.root, n)
                if i != 0:
                    s += '/{}'.format((self.root.to_octave(4) + self.intervals[0]).pitch_class)
                recipe = Chord.RecipeInfo(True, n, i, s)
            except StopIteration:
                recipe = Chord.RecipeInfo(False, '', 0, '-'.join(str(i) for i in self.intervals))
            setattr(self, '__recipe', recipe)
        return recipe

    @property
    def pitches(self):
        return tuple(n.pitch_class for n in self.notes())

    def notes(self, base_octave=4):
        r = self.root.to_octave(base_octave)
        return [r + i for i in self.intervals]

    def invert(self, num_times=1):
        if num_times == 0:
            return self
        return Chord(self.root, self.intervals[1:] + (self.intervals[0] + Interval('P8'),)).invert(num_times - 1)

    @staticmethod
    def identify_from_intervals(intervals):
        intervals = tuple(sorted(intervals))

        def flip(interval):
            if interval.is_compound() or interval == Interval('P8'):
                r = interval.reduce()
            else:
                r = interval + Interval('P8')
            return r
        n = len(intervals)
        for mask in range(2**n):
            new_intervals = tuple(sorted(flip(interval) if mask & 2**i else interval
                                         for i, interval in enumerate(intervals)))
            k = tuple(str(i) for i in new_intervals)
            if k in Chord.recipes_inv:
                c = Chord(PitchClass('C'), new_intervals)
                for inversion in range(n):
                    if c.invert(inversion).intervals == intervals:
                        yield Chord.recipes_inv[k], inversion

    @staticmethod
    def identify_from_notes(notes):
        notes = tuple(sorted(notes))

        n = len(notes)
        for mask in range(2**n):
            new_notes = tuple(sorted(n + Interval('P8' if mask & 2**i else 'P1')
                                     for i, n in enumerate(notes)))
            intervals_inv = tuple(n - new_notes[0] for n in new_notes)
            for recipe, inv in Chord.identify_from_intervals(intervals_inv):
                for inversion in range(n):
                    for root in notes:
                        c = Chord(root.pitch_class, recipe).invert(inversion)
                        cnotes = tuple(sorted(c.notes()))
                        if [n.pitch_class for n in cnotes] == [n.pitch_class for n in notes]:
                            yield c


class Scale:
    """
    The scale class.

    Contains recipes for common scales, and operators for accessing the
    notes of the scale, and for checking if a scale contains specific
    notes or chords.
    """

    scales = {
        'major':            ('P1', 'M2', 'M3', 'P4', 'P5', 'M6', 'M7'),
        'natural_minor':    ('P1', 'M2', 'm3', 'P4', 'P5', 'm6', 'm7'),
        'harmonic_minor':   ('P1', 'M2', 'm3', 'P4', 'P5', 'm6', 'M7'),
        'melodic_minor':    ('P1', 'M2', 'm3', 'P4', 'P5', 'M6', 'M7'),
        'major_pentatonic': ('P1', 'M2', 'M3',       'P5', 'M6'),
        'minor_pentatonic': ('P1',       'm3', 'P4', 'P5',       'm7'),
        # greek modes:
        'ionian':           ('P1', 'M2', 'M3', 'P4', 'P5', 'M6', 'M7'),
        'dorian':           ('P1', 'M2', 'm3', 'P4', 'P5', 'M6', 'm7'),
        'phrygian':         ('P1', 'm2', 'm3', 'P4', 'P5', 'm6', 'm7'),
        'lydian':           ('P1', 'M2', 'M3', 'A4', 'P5', 'M6', 'M7'),
        'mixolydian':       ('P1', 'M2', 'M3', 'P4', 'P5', 'M6', 'm7'),
        'aeolian':          ('P1', 'M2', 'm3', 'P4', 'P5', 'm6', 'm7'),
        'locrian':          ('P1', 'm2', 'm3', 'P4', 'd5', 'm6', 'm7'),
    }
    greek_modes = {
        1: 'ionian',
        2: 'dorian',
        3: 'phrygian',
        4: 'lydian',
        5: 'mixolydian',
        6: 'aeolian',
        7: 'locrian',
    }
    greek_modes_set = set(greek_modes.values())

    @staticmethod
    def all(include_greek_modes=False):
        for root in PitchClass.all():
            for name in Scale.scales:
                if not include_greek_modes and name in Scale.greek_modes_set:
                    continue
                yield Scale(root, name)

    def __init__(self, root, scale_type):
        self.recipe = None

        if isinstance(root, str):
            root = PitchClass(root)
        if not isinstance(root, PitchClass):
            raise TypeError('Invalid root type: {}'.format(type(root).__name__))

        if isinstance(scale_type, str):
            if scale_type not in self.scales:
                raise NameError('No such scale: {}'.format(scale_type))
            self.recipe = scale_type
            scale_type = self.scales[scale_type][:]
        if isinstance(scale_type, (list, tuple)):
            if all(isinstance(x, str) for x in scale_type):
                scale_type = tuple(map(Interval, scale_type))
            if not all(isinstance(x, Interval) for x in scale_type):
                raise TypeError('Scale intervals must be all of type str or all of type Interval.')

        self.root = root
        self.intervals = scale_type

    def __getitem__(self, k):
        if isinstance(k, int):
            try:
                octaves = k // len(self)
                offset = k - octaves * len(self)
                return self.root.to_octave(4 + octaves) + self.intervals[offset]
            except ValueError:
                raise IndexError('Index out of range')
        elif isinstance(k, slice):
            start = k.start or 0
            stop = k.stop or self.max_index
            step = k.step or 1
            return [self[i] for i in range(start, stop, step)]
        else:
            raise TypeError('Scale cannot be indexed by {}.'.format(type(k)))

    def __len__(self):
        return len(self.intervals)

    def __contains__(self, k):
        if isinstance(k, Note):
            return k.pitch_class in self
        elif isinstance(k, PitchClass):
            return k in self.pitches
        elif isinstance(k, Chord):
            return all(n in self for n in k.pitches)
        elif isinstance(k, (list, set, tuple)):
            return all(x in self for x in k)
        else:
            return False

    def __str__(self):
        if self.recipe:
            return '{} {}'.format(self.root, self.recipe)
        else:
            return '{} <{}>'.format(self.root, '-'.join(map(str, self.intervals)))

    def __repr__(self):
        if self.recipe:
            return 'Scale({!r}, {!r})'.format(str(self.root), self.recipe)
        else:
            return 'Scale({!r}, {!r})'.format(str(self.root), tuple(map(str, self.intervals)))

    def __lt__(self, other):
        return (self.root, self.intervals) < (other.root, other.intervals)

    def __le__(self, other):
        return self == other or self < other

    def __hash__(self):
        return hash((self.root,) + tuple(self.intervals))

    def __eq__(self, other):
        return self.root == other.root and self.intervals == other.intervals

    @property
    def pitches(self):
        return tuple(n.pitch_class for n in self[0:len(self)])

    def find_similar(self, max_levenshtein_dist=1, include_greek_modes=None):
        if include_greek_modes is None:
            include_greek_modes = self.recipe in Scale.greek_modes_set

        for scale in Scale.all(include_greek_modes):
            if scale == self:
                continue
            if len(self) - len(set(scale.pitches) & set(self.pitches)) <= max_levenshtein_dist:
                yield scale

    @staticmethod
    def identify_from_notes(notes):
        for scale in Scale.all(True):
            if notes in scale:
                yield scale
