def merge(items, key=(lambda x: x)):
    """
    Given sorted lists of iterables, return new iterable that returns
    elements of all iterables sorted with respect to key.
    """
    state = {}
    for item in map(iter, items):
        try:
            first = next(item)
        except StopIteration:
            continue
        else:
            state[item] = (first, key(first))

    while state:
        for item, (value, tk) in six.iteritems(state):
            # Value is biggest.
            if all(tk >= k for it, (v, k) in six.iteritems(state)
                   if it is not item):
                yield value
                break
        try:
            n = next(item)
            state[item] = (n, key(n))
        except StopIteration:
            del state[item]

    def super(self, *args, **kwargs):
        """ Like __call__, only that when you give it super(cls, obj) items,
        it will skip the multimethod for cls and use the one for its parent
        class. The normal __call__ does not consider this for performance
        reasons. """
        objs = self.get(*args, **kwargs)
        types = tuple(
            [
                x.__thisclass__.__mro__[1] if isinstance(x, super) else type(x)
                for x in objs
            ]
        )
        nargs = [
            x.__self__ if isinstance(x, super) else x
            for x in args
        ]

        for k, elem in six.iteritems(kwargs):
            if isinstance(elem, super):
                kwargs[k] = elem.__self__

        # This code is duplicate for performance reasons.
        cached = self.cache.get(types, None)
        if cached is not None:
            return cached(*nargs, **kwargs)

        for signature, fun in reversed(self.methods):
            if all(issubclass(ty, sig) for ty, sig in zip(types, signature)):
                self.cache[types] = fun
                return fun(*nargs, **kwargs)
        raise TypeError

def _freeze(obj):
    """ Create hashable representation of result dict. """
    if isinstance(obj, dict):
        return tuple((k, _freeze(v)) for k, v in iteritems(obj))
    if isinstance(obj, list):
        return tuple(_freeze(elem) for elem in obj)
    return obj

 def _URL_followsPattern(self, url):
     """Check whether the url provided follows the pattern"""
     pattern = self.pattern
     for k, v in six.iteritems(TIME_CONVERSIONS):
         pattern = pattern.replace(k, v)
     matches = re.match(pattern, url)
     if matches:
         return matches.end() == matches.endpos == len(self.now)
     return False

def _create(wlk, root, session):
    query = session.query(DatabaseEntry)
    for key, value in six.iteritems(root.attrs):
        typ = key[0]
        if typ == 'tag':
            criterion = TableTag.name.in_([value])
            # `key[1]` is here the `inverted` attribute of the tag. That means
            # that if it is True, the given tag must not be included in the
            # resulting entries.
            if key[1]:
                query = query.filter(~DatabaseEntry.tags.any(criterion))
            else:
                query = query.filter(DatabaseEntry.tags.any(criterion))
        elif typ == 'fitsheaderentry':
            key, val, inverted = value
            key_criterion = TableFitsHeaderEntry.key == key
            value_criterion = TableFitsHeaderEntry.value == val
            if inverted:
                query = query.filter(not_(and_(
                    DatabaseEntry.fits_header_entries.any(key_criterion),
                    DatabaseEntry.fits_header_entries.any(value_criterion))))
            else:
                query = query.filter(and_(
                    DatabaseEntry.fits_header_entries.any(key_criterion),
                    DatabaseEntry.fits_header_entries.any(value_criterion)))
        elif typ == 'download time':
            start, end, inverted = value
            if inverted:
                query = query.filter(
                    ~DatabaseEntry.download_time.between(start, end))
            else:
                query = query.filter(
                    DatabaseEntry.download_time.between(start, end))
        elif typ == 'path':
            path, inverted = value
            if inverted:
                # pylint: disable=E711
                query = query.filter(or_(
                    DatabaseEntry.path != path, DatabaseEntry.path == None))
            else:
                query = query.filter(DatabaseEntry.path == path)
        elif typ == 'wave':
            wavemin, wavemax, waveunit = value
            query = query.filter(and_(
                DatabaseEntry.wavemin >= wavemin,
                DatabaseEntry.wavemax <= wavemax))
        elif typ == 'time':
            start, end, near = value
            query = query.filter(and_(
                DatabaseEntry.observation_time_start < end,
                DatabaseEntry.observation_time_end > start))
        else:
            if typ.lower() not in SUPPORTED_SIMPLE_VSO_ATTRS.union(SUPPORTED_NONVSO_ATTRS):
                raise NotImplementedError("The attribute {0!r} is not yet supported to query a database.".format(typ))
            query = query.filter_by(**{typ: value})
    return query.all()

    def _extractDateURL(self, url):
        """Extracts the date from a particular url following the pattern"""

        # remove the user and passwd from files if there:
        url = url.replace("anonymous:[email protected]@", "")

        # url_to_list substitutes '.' and '_' for '/' to then create
        # a list of all the blocks in times - assuming they are all
        # separated with either '.', '_' or '/'
        url_to_list = lambda txt: re.sub(r'\.|_', '/', txt).split('/')
        pattern_list = url_to_list(self.pattern)
        url_list = url_to_list(url)
        time_order = ['%Y', '%y', '%b', '%B', '%m', '%d', '%j',
                      '%H', '%I', '%M', '%S', '%e', '%f']
        final_date = []
        final_pattern = []
        # Find in directory and filename
        for pattern_elem, url_elem in zip(pattern_list, url_list):
            time_formats = [x for x in time_order if x in pattern_elem]
            if len(time_formats) > 0:
                # Find whether there's text that should not be here
                toremove = re.split('%.', pattern_elem)
                if len(toremove) > 0:
                    for bit in toremove:
                        if bit != '':
                            url_elem = url_elem.replace(bit, '', 1)
                            pattern_elem = pattern_elem.replace(bit, '', 1)
                final_date.append(url_elem)
                final_pattern.append(pattern_elem)
                for time_bit in time_formats:
                    time_order.remove(time_bit)
        # Find and remove repeated elements eg: %Y in ['%Y', '%Y%m%d']
        #   Make all as single strings
        date_together = ''.join(final_date)
        pattern_together = ''.join(final_pattern)
        re_together = pattern_together
        for k, v in six.iteritems(TIME_CONVERSIONS):
            re_together = re_together.replace(k, v)

        #   Lists to contain the unique elements of the date and the pattern
        final_date = list()
        final_pattern = list()
        re_together = re_together.replace('[A-Z]', '\\[A-Z]')
        for p, r in zip(pattern_together.split('%')[1:], re_together.split('\\')[1:]):
            if p == 'e':
                continue
            regexp = r'\{}'.format(r) if not r.startswith('[') else r
            pattern = '%{}'.format(p)
            date_part = re.search(regexp, date_together)
            date_together = date_together[:date_part.start()] + \
                            date_together[date_part.end():]
            if pattern not in final_pattern:
                final_pattern.append('%{}'.format(p))
                final_date.append(date_part.group())
        return datetime.datetime.strptime(' '.join(final_date),
                                          ' '.join(final_pattern))

def _apply(wlk, root, api, queryblock):
    """ Implementation detail. """
    for k, v in iteritems(root.attrs):
        lst = k[-1]
        rest = k[:-1]

        block = queryblock
        for elem in rest:
            block = block[elem]
        block[lst] = v

    def make_getdatarequest(self, response, methods=None, info=None):
        """ Make datarequest with methods from response. """
        if methods is None:
            methods = self.method_order + ['URL']

        return self.create_getdatarequest(
            dict((k, [x.fileid for x in v])
                 for k, v in iteritems(self.by_provider(response))),
            methods, info
        )

    def to_be_removed(self):
        """Returns the key with the lowest times of access and its
        corresponding value as a tuple.

        """
        min_ = float('inf')
        lfu_key = None
        for k, v in six.iteritems(self.usage_counter):
            if v < min_:
                min_ = v
                lfu_key = k
        return lfu_key, self.get(lfu_key)

    def make(self, atype, **kwargs):
        """ Create new SOAP object with attributes specified in kwargs.
        To assign subattributes, use foo__bar=1 to assign
        ['foo']['bar'] = 1. """
        obj = self.api.factory.create(atype)
        for k, v in iteritems(kwargs):
            split = k.split('__')
            tip = split[-1]
            rest = split[:-1]

            item = obj
            for elem in rest:
                item = item[elem]

            if isinstance(v, dict):
                # Do not throw away type information for dicts.
                for k, v in iteritems(v):
                    item[tip][k] = v
            else:
                item[tip] = v
        return obj

    def create_getdatarequest(self, maps, methods, info=None):
        """ Create datarequest from maps mapping data provider to
        fileids and methods, """
        if info is None:
            info = {}

        return self.make(
            'VSOGetDataRequest',
            request__method__methodtype=methods,
            request__info=info,
            request__datacontainer__datarequestitem=[
                self.make('DataRequestItem', provider=k, fileiditem__fileid=[v])
                for k, v in iteritems(maps)
            ]
        )

def find_time(string, format):
    """ Return iterator of occurrences of date formatted with format
    in string. Currently supported format codes: """
    re_format = format
    for key, value in six.iteritems(REGEX):
        re_format = re_format.replace(key, value)
    matches = re.finditer(re_format, string)
    for match in matches:
        try:
            matchstr = string[slice(*match.span())]
            dt = datetime.strptime(matchstr, format)
        except ValueError:
            continue
        else:
            yield dt

    def _extractDateURL(self, url):
        """Extracts the date from a particular url following the pattern"""
        # url_to_list substitutes '.' and '_' for '/' to then create
        # a list of all the blocks in times - assuming they are all
        # separated with either '.', '_' or '/'
        url_to_list = lambda txt: re.sub(r'\.|_', '/', txt).split('/')
        pattern_list = url_to_list(self.pattern)
        url_list = url_to_list(url)

        time_order = ['%Y', '%y', '%b', '%B', '%m', '%d', '%j',
                      '%H', '%I', '%M', '%S']
        final_date = []
        final_pattern = []
        # Find in directory and filename
        for pattern_elem, url_elem in zip(pattern_list, url_list):
            time_formats = [x for x in time_order if x in pattern_elem]
            if len(time_formats) > 0:
                final_date.append(url_elem)
                final_pattern.append(pattern_elem)
                for time_bit in time_formats:
                    time_order.remove(time_bit)
        # Find and remove repeated elements eg: %Y in ['%Y', '%Y%m%d']
        #   Make all as single strings
        date_together = ''.join(final_date)
        pattern_together = ''.join(final_pattern)
        re_together = pattern_together
        for k, v in six.iteritems(TIME_CONVERSIONS):
            re_together = re_together.replace(k, v)

        #   Create new empty lists
        final_date = list()
        final_pattern = list()
        for p,r in zip(pattern_together.split('%')[1:], re_together.split('\\')[1:]):
            regexp = '\\{}'.format(r)
            pattern = '%{}'.format(p)
            date_part = re.match(regexp, date_together)
            date_together = date_together[:date_part.start()] + \
                            date_together[date_part.end():]
            if pattern not in final_pattern:
                final_pattern.append('%{}'.format(p))
                final_date.append(date_part.group())
        return datetime.datetime.strptime(' '.join(final_date),
                                          ' '.join(final_pattern))

    def _close(self, callback, args, server):
        """ Called after download is done. Activated queued downloads, call callback.
        """
        callback(*args)

        self.connections[server] -= 1
        self.conns -= 1

        if self.q[server]:
            self._attempt_download(*self.q[server].pop())
        else:
            for k, v in iteritems(self.q):  # pylint: disable=W0612
                while v:
                    if self._attempt_download(*v[0]):
                        v.popleft()
                        if self.conns == self.max_total:
                            return
                    else:
                        break

def print_all(key=None):
    """
    Provides a table of the complete list of constants.

    Parameters
    ----------
    key : Python string or unicode
        Key in dictionary `constants`

    Returns
    -------
    table : `astropy.table.Table`
    """
    data_rows = []
    for key, this_constant in iteritems(constants):
        data_rows.append([key, this_constant.name, this_constant.value, this_constant.uncertainty,
                          str(this_constant.unit), this_constant.reference])

    t = Table(rows=data_rows, names=('key', 'name', 'value', 'uncertainty', 'unit', 'Reference'))
    return t

def _regex_parse_time(inp, format):
    # Parser for finding out the minute value so we can adjust the string
    # from 24:00:00 to 00:00:00 the next day because strptime does not
    # understand the former.
    for key, value in six.iteritems(REGEX):
        format = format.replace(key, value)
    match = re.match(format, inp)
    if match is None:
        return None, None
    try:
        hour = match.group("hour")
    except IndexError:
        return inp, timedelta(days=0)
    if match.group("hour") == "24":
        if not all(_n_or_eq(_group_or_none(match, g, int), 00)
            for g in ["minute", "second", "microsecond"]
        ):
            raise ValueError
        from_, to = match.span("hour")
        return inp[:from_] + "00" + inp[to:], timedelta(days=1)
    return inp, timedelta(days=0)

from __future__ import absolute_import
from sunpy.sun import constants as con
from astropy.constants import Constant
import pytest
from sunpy.extern.six import iteritems


@pytest.mark.parametrize('this_constant', [value for key, value in iteritems(con.constants)])
def test_all_constants_are_constants(this_constant):
    """Test that each member of the constants dict is an astropy Constant"""
    assert type(this_constant) is Constant


@pytest.mark.parametrize('this_key', [key for key, value in iteritems(con.constants)])
def test_get_function(this_key):
    """Test that the get function works for all the keys"""
    assert type(con.get(this_key)) is Constant


@pytest.mark.parametrize('this_key', [key for key, value in iteritems(con.constants)])
def test_find_function(this_key):
    """Test that the find function works for all the keys"""
    assert len(con.find(this_key)) >= 1


@pytest.mark.parametrize('this_key', [key for key, value in iteritems(con.constants)])
def test_find_function(this_key):
    """Test that the find function works for all the keys"""
    assert len(con.find(this_key)) >= 1

 def undo(self):
     for k, v in six.iteritems(self.prev_values):
         setattr(self.database_entry, k, v)

 def __hash__(self):
     return hash(frozenset(iteritems(self.attrs.iteritems)))

def entries_from_file(file, default_waveunit=None):
    """Use the headers of a FITS file to generate an iterator of
    :class:`sunpy.database.tables.DatabaseEntry` instances. Gathered
    information will be saved in the attribute `fits_header_entries`. If the
    key INSTRUME, WAVELNTH or DATE-OBS / DATE_OBS is available, the attribute
    `instrument`, `wavemin` and `wavemax` or `observation_time_start` is set,
    respectively. If the wavelength unit can be read, the values of `wavemin`
    and `wavemax` are converted to nm (nanometres). The value of the `file`
    parameter is used to set the attribute `path` of each generated database
    entry.

    Parameters
    ----------
    file : str or file-like object
        Either a path pointing to a FITS file or a an opened file-like object.
        If an opened file object, its mode must be one of the following rb,
        rb+, or ab+.

    default_waveunit : str, optional
        The wavelength unit that is used for a header if it cannot be
        found.

    Raises
    ------
    sunpy.database.WaveunitNotFoundError
        If `default_waveunit` is not given and the wavelength unit cannot
        be found in one of the FITS headers

    sunpy.WaveunitNotConvertibleError
        If a wavelength unit could be found but cannot be used to create an
        instance of the type ``astropy.units.Unit``. This can be the case
        for example if a FITS header has the key `WAVEUNIT` with the value
        `nonsense`.

    Examples
    --------
    >>> from sunpy.database.tables import entries_from_file
    >>> import sunpy.data
    >>> sunpy.data.download_sample_data(overwrite=False)   # doctest: +SKIP
    >>> import sunpy.data.sample
    >>> entries = list(entries_from_file(sunpy.data.sample.SWAP_LEVEL1_IMAGE))
    >>> len(entries)
    1
    >>> entry = entries.pop()
    >>> entry.instrument
    'SWAP'
    >>> entry.observation_time_start, entry.observation_time_end
    (datetime.datetime(2012, 1, 1, 0, 16, 7, 836000), None)
    >>> entry.wavemin, entry.wavemax
    (17.400000000000002, 17.400000000000002)
    >>> len(entry.fits_header_entries)
    111

    """
    headers = fits.get_header(file)
    if isinstance(file, (str, six.text_type)):
        filename = file
    else:
        filename = getattr(file, 'name', None)
    for header in headers:
        entry = DatabaseEntry(path=filename)
        for key, value in six.iteritems(header):
            # Yes, it is possible to have an empty key in a FITS file.
            # Example: sunpy.data.sample.EIT_195_IMAGE
            # Don't ask me why this could be a good idea.
            if key == '':
                value = str(value)
            elif key == 'KEYCOMMENTS':
                for k, v in six.iteritems(value):
                    entry.fits_key_comments.append(FitsKeyComment(k, v))
                continue
            entry.fits_header_entries.append(FitsHeaderEntry(key, value))
        waveunit = fits.extract_waveunit(header)
        if waveunit is None:
            waveunit = default_waveunit
        unit = None
        if waveunit is not None:
            try:
                unit = Unit(waveunit)
            except ValueError:
                raise WaveunitNotConvertibleError(waveunit)
        for header_entry in entry.fits_header_entries:
            key, value = header_entry.key, header_entry.value
            if key == 'INSTRUME':
                entry.instrument = value
            elif key == 'WAVELNTH':
                if unit is None:
                    raise WaveunitNotFoundError(file)
                # use the value of `unit` to convert the wavelength to nm
                entry.wavemin = entry.wavemax = unit.to(
                    nm, value, equivalencies.spectral())
            # NOTE: the key DATE-END or DATE_END is not part of the official
            # FITS standard, but many FITS files use it in their header
            elif key in ('DATE-END', 'DATE_END'):
                entry.observation_time_end = parse_time(value)
            elif key in ('DATE-OBS', 'DATE_OBS'):
                entry.observation_time_start = parse_time(value)
        yield entry