text: # ----------------------------------------------------------------------------
  # Copyright (c) 2013--, scikit-bio development team.
  #
  # Distributed under the terms of the Modified BSD License.
  #
  # The full license is in the file COPYING.txt, distributed with this software.
  # ----------------------------------------------------------------------------
  
  import operator
  import copy
  import functools
  
  from ._intersection import IntervalTree
  from skbio.util._decorator import experimental, classonlymethod
  
  
  class Interval:
      """Stores the bounds and metadata of an interval feature.
  
      This class stores an interval feature. An interval feature
      is defined as a sub-region of a biological sequence or sequence
      alignment that is a functional entity, e.g., a gene, a riboswitch,
      an exon, etc. It can span a single contiguous region or multiple
      non-contiguous regions (e.g. multiple exons in a transcript, or
      multiple genes in an operon).
  
      Parameters
      ----------
      interval_metadata : object
          A reference to the ``IntervalMetadata`` object that this
          ``Interval`` object is associated to.
      bounds : iterable of tuple of int
          Tuples representing start and end coordinates. It is *zero-based*
          numbering. It is always inclusive on start bound and exclusive on
          end bound.
      fuzzy : iterable of tuple of bool, optional
          Tuples representing the fuzziness of each bound coordinates.
          If this isn't specified, then the fuzziness of all bound
          coordinates are ``False``. If any of the coordinate fuzziness
          is ``True``, it indicates that the exact bound point of a
          interval feature is unknown. The bound may begin or end at
          some points outside the specified coordinates. This
          accommodates the location format [1]_ of INSDC.
      metadata : dict, optional
          Dictionary of attributes storing information of the feature
          such as "strand", "gene_name", or "product".
  
      See Also
      --------
      skbio.metadata.IntervalMetadata
  
      Notes
      -----
      While the construction of an ``Interval`` object automatically add
      itself to its associated ``IntervalMetadata`` object,
      ``IntervalMetadata.add`` is the typical/easier way to
      create and add it to ``IntervalMetadata``.
  
      References
      ----------
      .. [1] ftp://ftp.ebi.ac.uk/pub/databases/embl/doc/FT_current.html#3.4.3
  
      Examples
      --------
      Hypothetically, let's say we have a gene called "genA" with 10 nt
      as shown in the following diagram.  The second row represents the
      two exons (indicated by "=") on this gene:
  
      ::
  
          TGGATTCTGC
          -====--==-
          0123456789
  
      We can create an ``Interval`` object to represent the exons of the gene:
  
      >>> from skbio.metadata import Interval, IntervalMetadata
      >>> interval_metadata = IntervalMetadata(10)
  
      Remember the coordinates are inclusive in lower bound and exclusive on
      upper bound:
  
      >>> gene = Interval(interval_metadata,
      ...                 bounds=[(1, 5), (7, 9)],
      ...                 metadata={'name': 'genA'})
      >>> gene    # doctest: +ELLIPSIS
      Interval(interval_metadata=..., bounds=[(1, 5), (7, 9)], \
  fuzzy=[(False, False), (False, False)], metadata={'name': 'genA'})
  
      """
      def __init__(self, interval_metadata, bounds,
                   fuzzy=None, metadata=None):
          if not isinstance(interval_metadata, IntervalMetadata):
              raise TypeError('You need to provide an IntervalMetadata'
                              'object, not %r' % interval_metadata)
          # Intervals
          self._interval_metadata = interval_metadata
  
          self._bounds_fuzzy_setter(bounds, fuzzy)
  
          # Metadata
          if metadata is None:
              metadata = {}
          self.metadata = metadata
  
          # add this interval feature to the associated IntervalMetadata
          self._add()
  
      def _add(self):
          """Add the current ``Interval`` to the IntervalMetadata object."""
          for bound in self.bounds:
              start, end = bound
              self._interval_metadata._interval_tree.add(start, end, self)
          self._interval_metadata._intervals.append(self)
  
      @experimental(as_of='0.5.1')
      def __eq__(self, other):
          '''Test if this ``Interval`` object is equal to another.
  
          The equality is performed by checking if the ``metadata``,
          ``bounds`` and ``fuzzy`` are equal. Since the ``bounds``
          and the ``fuzzy`` are sorted, the permutations of them during
          the ``Interval`` construction or assignment won't matter.
  
          Parameters
          ----------
          other : Interval
              Interval to test for equality against.
  
          Returns
          -------
          bool
              Indicates if the two objects are equal.
          '''
          return ((self.metadata == other.metadata) and
                  (self.bounds == other.bounds) and
                  (self.fuzzy == other.fuzzy))
  
      @experimental(as_of='0.5.1')
      def __ne__(self, other):
          '''Test if this ``Interval`` object is not equal to another.
  
          Parameters
          ----------
          other : Interval
              Interval to test for inequality against.
  
          Returns
          -------
          bool
              Indicates if the two objects are not equal.
          '''
          return not (self == other)
  
      @experimental(as_of='0.5.1')
      def __repr__(self):
          '''Return a string representation of this ``Interval`` object.
  
          Returns
          -------
          str
              String representation of this ``Interval`` object.
          '''
          if self.dropped:
              s = ('{}(dropped=True, bounds={!r}, '
                   'fuzzy={!r}, metadata={!r})')
              return s.format(self.__class__.__name__,
                              self.bounds, self.fuzzy, self.metadata)
          else:
              s = ('{}(interval_metadata=<{!r}>, bounds={!r}, '
                   'fuzzy={!r}, metadata={!r})')
              return s.format(self.__class__.__name__,
                              id(self._interval_metadata),
                              self.bounds, self.fuzzy, self.metadata)
  
      @experimental(as_of='0.5.1')
      def drop(self):
          '''Drop this ``Interval`` object from the interval metadata it links to.
  
          If the ``Interval`` object is dropped, you can still get values of
          ``bounds``, ``fuzzy``, and ``metadata`` attributes, but you
          can not change their values with the setters.
  
          See Also
          --------
          skbio.metadata.IntervalMetadata.drop
          '''
          if not self.dropped:
              self._interval_metadata.drop([self])
  
      def _bounds_fuzzy_setter(self, bounds=None, fuzzy=None):
          if self.dropped:
              raise RuntimeError('Cannot change `bounds` or `fuzzy` '
                                 'on a dropped Interval object.')
          # Casts to `list`, validation, sorting, and setting of `bounds`
          # and `fuzzy` happen here.
          if bounds is not None:
              # check iterability
              try:
                  # check iterability
                  bounds = list(bounds)
              except TypeError:
                  raise TypeError('Cannot give an non-iterable (%r) '
                                  'to `bounds`.' % bounds)
  
              # check it is not empty
              if not bounds:
                  raise ValueError('Cannot give empty `bounds`.')
              # check each contiguous span is in right format
              for bound in bounds:
                  _assert_valid_bound(bound)
  
              spans = len(bounds)
          else:
              spans = len(self.bounds)
  
          if fuzzy is not None:
              try:
                  fuzzy = list(fuzzy)
              except TypeError:
                  raise TypeError(
                      'Cannot give a non-iterable (%r) '
                      'to `fuzzy`.' % fuzzy)
  
              if len(fuzzy) != spans:
                  raise ValueError(
                      'The length of fuzzy must '
                      'be equal to the length of bounds.')
  
              for fuzzy_i in fuzzy:
                  _assert_valid_fuzzy(fuzzy_i)
  
          if bounds is None:
              # `bounds` and `fuzzy` cannot both be omitted.
              if fuzzy is None:
                  raise ValueError('Cannot give `None` to both `bounds` '
                                   'and `fuzzy`.')
              # If only `fuzzy` is provided, set `self.fuzzy` and don't
              # change `self.bounds`.
              else:
                  self._fuzzy = fuzzy
          else:
              # If only `bounds` is provided, reset `self.fuzzy` to
              # all `False`.
              if fuzzy is None:
                  bounds.sort()
                  self._check_bounds(bounds)
                  self._bounds = bounds
                  # reset all the fuzzy to False!!
                  del self.fuzzy
  
              # If both `bounds` and `fuzzy` are provided, set
              # `self.bounds` and `self.fuzzy`.
              else:
                  bounds, fuzzy = [
                      list(e) for e in zip(*sorted(zip(bounds, fuzzy)))]
                  self._check_bounds(bounds)
                  self._bounds = bounds
                  self._fuzzy = fuzzy
  
              self._interval_metadata._is_stale_tree = True
  
      def _check_bounds(self, bounds):
          '''input `bounds` must be sorted.'''
          upper_bound = self._interval_metadata.upper_bound
          lower_bound = self._interval_metadata.lower_bound
          if upper_bound is not None and bounds[-1][-1] > upper_bound:
              raise ValueError('Cannot set `bounds` (%r) with coordinate '
                               'larger than upper bound (%r)' %
                               (bounds, upper_bound))
  
          if bounds[0][0] < lower_bound:
              raise ValueError('Cannot set `bounds` (%r) with coordinate '
                               'smaller than lower bound (%r).' %
                               (bounds, lower_bound))
  
      @property
      @experimental(as_of='0.5.1')
      def fuzzy(self):
          '''The openness of each coordinate.
  
          This indicates that the exact bound of a interval feature
          is unknown. The bound may begin or end at some points outside
          the specified coordinates. This accommodates the bound format [1]_
          of INSDC.
  
          References
          ----------
          .. [1] ftp://ftp.ebi.ac.uk/pub/databases/embl/doc/FT_current.html#3.4.3
          '''
          return self._fuzzy
  
      @fuzzy.setter
      @experimental(as_of='0.5.1')
      def fuzzy(self, value):
          '''Set ``fuzzy``.
  
          The ``value`` should an iterable matching ``self.bounds``.
          '''
          self._bounds_fuzzy_setter(fuzzy=value)
  
      @fuzzy.deleter
      @experimental(as_of='0.5.1')
      def fuzzy(self):
          '''Delete ``fuzzy``.
  
          This set all fuzzy to be ``False``.
          '''
          if self.dropped:
              raise RuntimeError('Cannot change fuzzy on dropped '
                                 'Interval object.')
          self._fuzzy = [(False, False)] * len(self.bounds)
  
      @property
      @experimental(as_of='0.5.1')
      def bounds(self):
          '''The coordinates of the interval feature.
  
          It should be a list of tuples of int pair. Each tuple stores
          the start and end coordinates of a span of the interval
          feature. The coordinates are *zero-based*. They are inclusive on
          the start and exclusive on the end.
          '''
          return self._bounds
  
      @bounds.setter
      @experimental(as_of='0.5.1')
      def bounds(self, value):
          '''Set ``bounds``.
  
          WARNING: setting ``bounds`` will reset ``fuzzy`` value to ``False``.
          This is not totally surprising because it is justifiable your old
          ``fuzzy`` don't fit the new bounds.
          '''
          self._bounds_fuzzy_setter(bounds=value)
  
      @property
      @experimental(as_of='0.5.1')
      def metadata(self):
          '''The metadata of the interval feature.
  
          It stores the metadata (eg. gene name, function, ID, etc.) of
          the interval feature as a ``dict``.
          '''
          return self._metadata
  
      @metadata.setter
      @experimental(as_of='0.5.1')
      def metadata(self, value):
          if self.dropped:
              raise RuntimeError('Cannot change metadata on dropped '
                                 'Interval object.')
          if not isinstance(value, dict):
              raise TypeError("metadata must be a dict, not %r" % value)
          self._metadata = value
  
      @metadata.deleter
      @experimental(as_of='0.5.1')
      def metadata(self):
          '''Delete metadata.
  
          This sets metadata to be empty dict.
          '''
          if self.dropped:
              raise RuntimeError('Cannot change metadata to dropped '
                                 'Interval object.')
          self._metadata = {}
  
      @property
      @experimental(as_of='0.5.1')
      def dropped(self):
          '''Boolean value indicating if the ``Interval`` object is dropped.
  
          If it is dropped, it means it is not associated with IntervalMetadata
          object any more.
  
          Notes
          -----
          This property is not writable.
  
          See Also
          --------
          skbio.metadata.Interval.drop
          skbio.metadata.IntervalMetadata.drop
          '''
          return self._interval_metadata is None
  
  
  class IntervalMetadata():
      """Stores the interval features.
  
      ``IntervalMetadata`` object allows storage, modification, and
      querying of interval features covering a region of a single coordinate
      system. For instance, this can be used to store functional annotations
      about genes across a genome. This object is also applied to the sequence
      alignment.
  
      This object is typically coupled with another object, such as a
      ``Sequence`` object (or its child class), or a ``TabularMSA`` object.
  
      Parameters
      ----------
      upper_bound : int or None
          Defines the exclusive upper bound of the interval features. No
          coordinate can be greater than it. ``None``
          means that the coordinate space is unbounded.
      copy_from : IntervalMetadata or None, optional
          Create a new object from the input ``IntervalMetadata`` object by
          shallow copying if it is not ``None``. The upper bound of the new
          object will be updated with the ``upper_bound`` parameter specified.
  
      Notes
      -----
      This class stores coordinates of all feature bounds into a interval
      tree. It allows the speed up of query-by-bound. The building of
      interval tree is deferred until necessary to save computation. It is
      updated from all coordinates only when you need to fetch info from
      the interval tree.
  
      When you add a method into this class and if you method need to fetch
      info from ``IntervalMetadata._interval_tree``, you should decorate it with
      ``_rebuild_tree``. This decorator will check if the current interval tree
      is stale and will update it if so. Additionally, if your method add,
      delete, or changes the coordinates of any interval features, you should
      set ``self._is_stale_tree`` to ``True`` at the end of your method to
      indicate the interval tree becomes stale.
  
      See Also
      --------
      skbio.metadata.Interval
  
      Examples
      --------
      Let's say we have a sequence of length 10 and want to add annotation
      to it. Create an ``IntervalMetadata`` object:
  
      >>> from skbio.metadata import Interval, IntervalMetadata
      >>> im = IntervalMetadata(10)
  
      Let's add annotations of 3 genes:
  
      >>> im.add(bounds=[(3, 9)],
      ...        metadata={'gene': 'sagB'})  # doctest: +ELLIPSIS
      Interval(interval_metadata=..., bounds=[(3, 9)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagB'})
      >>> im.add(bounds=[(3, 7)],
      ...        metadata={'gene': 'sagC'})  # doctest: +ELLIPSIS
      Interval(interval_metadata=..., bounds=[(3, 7)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagC'})
      >>> im.add(bounds=[(1, 2), (4, 7)],
      ...        metadata={'gene': 'sagA'})  # doctest: +ELLIPSIS
      Interval(interval_metadata=..., bounds=[(1, 2), (4, 7)], \
  fuzzy=[(False, False), (False, False)], metadata={'gene': 'sagA'})
  
      Show the object representation:
  
      >>> im    # doctest: +ELLIPSIS
      3 interval features
      -------------------
      Interval(interval_metadata=..., bounds=[(3, 9)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagB'})
      Interval(interval_metadata=..., bounds=[(3, 7)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagC'})
      Interval(interval_metadata=..., bounds=[(1, 2), (4, 7)], \
  fuzzy=[(False, False), (False, False)], metadata={'gene': 'sagA'})
  
      We can sort the genes by their bounds:
  
      >>> im.sort()
      >>> im    # doctest: +ELLIPSIS
      3 interval features
      -------------------
      Interval(interval_metadata=..., bounds=[(1, 2), (4, 7)], \
  fuzzy=[(False, False), (False, False)], metadata={'gene': 'sagA'})
      Interval(interval_metadata=..., bounds=[(3, 7)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagC'})
      Interval(interval_metadata=..., bounds=[(3, 9)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagB'})
  
      Query the genes by bound and/or metadata:
  
      >>> intvls = im.query([(1, 2)], metadata={'gene': 'foo'})
      >>> list(intvls)
      []
      >>> intvls = im.query([(7, 9)])
      >>> list(intvls)  # doctest: +ELLIPSIS
      [Interval(interval_metadata=..., bounds=[(3, 9)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagB'})]
      >>> intvls = im.query(metadata={'gene': 'sagA'})
      >>> intvls = list(intvls)
      >>> intvls  # doctest: +ELLIPSIS
      [Interval(interval_metadata=..., bounds=[(1, 2), (4, 7)], \
  fuzzy=[(False, False), (False, False)], metadata={'gene': 'sagA'})]
  
      Drop the gene(s) we get from query:
  
      >>> im.drop(intvls)
      >>> im.sort()
      >>> im   # doctest: +ELLIPSIS
      2 interval features
      -------------------
      Interval(interval_metadata=..., bounds=[(3, 7)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagC'})
      Interval(interval_metadata=..., bounds=[(3, 9)], \
  fuzzy=[(False, False)], metadata={'gene': 'sagB'})
  
      """
      default_write_format = 'gff3'
  
      def __init__(self, upper_bound, copy_from=None):
          self._upper_bound = upper_bound
          if self.upper_bound is not None:
              if self.upper_bound < self.lower_bound:
                  raise ValueError('Cannot set `upper_bound` (%r) '
                                   'smaller than `lower_bound` (%r)'
                                   % (self.upper_bound, self.lower_bound))
          # List of Interval objects.
          self._intervals = []
  
          # IntervalTree object to allow faster querying of interval objects.
          self._interval_tree = IntervalTree()
  
          # Indicates if the IntervalTree needs to be rebuilt.
          self._is_stale_tree = False
  
          if copy_from is not None:
              for interval in copy_from._intervals:
                  bounds_cp = interval.bounds[:]
                  fuzzy_cp = interval.fuzzy[:]
                  metadata_cp = copy.copy(interval.metadata)
  
                  self.add(bounds_cp, fuzzy=fuzzy_cp, metadata=metadata_cp)
  
      @property
      @experimental(as_of='0.5.1')
      def upper_bound(self):
          '''The exclusive upper bound of interval features.'''
          return self._upper_bound
  
      @property
      @experimental(as_of='0.5.1')
      def lower_bound(self):
          '''The inclusive lower bound of interval features.'''
          return 0
  
      @property
      @experimental(as_of='0.5.1')
      def num_interval_features(self):
          '''The total number of interval features.'''
          return len(self._intervals)
  
      def _rebuild_tree(method):
          """Rebuild the IntervalTree."""
          @functools.wraps(method)
          def inner(self, *args, **kwargs):
              if self._is_stale_tree is False:
                  return method(self, *args, **kwargs)
              self._interval_tree = IntervalTree()
              for f in self._intervals:
                  for start, end in f.bounds:
                      self._interval_tree.add(start, end, f)
              self._is_stale_tree = False
              return method(self, *args, **kwargs)
          return inner
  
      def _reverse(self):
          """Reverse ``IntervalMetadata`` object.
  
          This operation reverses all of the interval coordinates.
          For instance, this can be used to compare coordinates
          in the forward strand to coordinates in the reversal strand.
          """
  
          for f in self._intervals:
              try:
                  intvls = [(self.upper_bound - x[1], self.upper_bound - x[0])
                            for x in reversed(f.bounds)]
              except TypeError:
                  raise TypeError('You cannot reverse the coordinates '
                                  'when the upper bound is `None`')
              f.bounds = intvls
  
          # DON'T forget this!!!
          self._is_stale_tree = True
  
      @classonlymethod
      @experimental(as_of="0.5.1")
      def concat(cls, interval_metadata):
          '''Concatenate an iterable of ``IntervalMetadata`` objects.
  
          It concatenates the multiple ``IntervalMetadata`` objects into
          one coordinate space. The order of the objects in the input
          iterable matters. The coordinate of the second
          ``InterableMetadata`` will be shifted up with the length of
          the first ``IntervalMetadata`` object.
  
          This function is useful when you concatenate multiple sequences.
  
          Parameters
          ----------
          interval_metadata : Iterable (IntervalMetadata)
              The interval metadata to concatenate.
  
          Returns
          -------
          IntervalMetadata
              Concatenated interval metadata.
  
          Examples
          --------
          >>> from skbio.metadata import IntervalMetadata
  
          Create two ``IntervalMetadata`` objects:
  
          >>> im1 = IntervalMetadata(3)
          >>> _ = im1.add([(0, 2)], [(True, False)], {'gene': 'sagA'})
          >>> im2 = IntervalMetadata(4)
          >>> _ = im2.add([(1, 4)], [(True, True)], {'gene': 'sagB'})
  
          Concatenate them into a single coordinate space. The second
          ``IntervalMetadata``'s interval features are all shifted
          up. The resulting ``IntervalMetadata``'s upper bound is the
          sum of upper bounds of concatenated objects:
  
          >>> im = IntervalMetadata.concat([im1, im2])
          >>> im   # doctest: +ELLIPSIS
          2 interval features
          -------------------
          Interval(interval_metadata=<...>, bounds=[(0, 2)], \
  fuzzy=[(True, False)], metadata={'gene': 'sagA'})
          Interval(interval_metadata=<...>, bounds=[(4, 7)], \
  fuzzy=[(True, True)], metadata={'gene': 'sagB'})
          >>> im.upper_bound
          7
  
          '''
          interval_metadata = list(interval_metadata)
  
          if len(interval_metadata) == 0:
              return cls(0)
  
          upper_bound = 0
          for im in interval_metadata:
              try:
                  upper_bound += im.upper_bound
              except TypeError:
                  raise TypeError('You cannot concat the interval metadata '
                                  'because its upper bound is `None`:\n%r' % im)
          new = cls(upper_bound)
  
          length = 0
          for i, im in enumerate(interval_metadata):
              for intvl in im._intervals:
                  bounds = intvl.bounds
                  fuzzy = intvl.fuzzy
                  if i != 0:
                      bounds = [(start + length, end + length)
                                for start, end in bounds]
                  new.add(bounds, fuzzy, intvl.metadata)
              length += im.upper_bound
  
          return new
  
      @experimental(as_of='0.5.1')
      def merge(self, other):
          '''Merge the interval features of another ``IntervalMetadata`` object.
  
          It adds all the interval features of the other object into
          ``self``. Note this will not check if there are any duplicates
          of interval features after merge.
  
          Notes
          -----
          It will raise error if you merge an unbounded
          ``IntervalMetadata`` object to the current object if it is
          bounded. This avoids partially updating the current object if
          the merge fails in the middle of the process due to the
          possibility that some interval features to be merged may live
          outside the current defined upper bound.
  
          Parameters
          ----------
          other : ``IntervalMetadata``
              The other ``IntervalMetadata`` to be merged.
  
          '''
          if self.upper_bound is not None:
              if other.upper_bound is None:
                  raise ValueError(
                      'Cannot merge an unbound IntervalMetadata object '
                      'to a bounded one')
              elif self.upper_bound != other.upper_bound:
                  raise ValueError(
                      'The upper bounds of the two IntervalMetadata objects '
                      'are not equal (%r != %r)' % (
                          self.upper_bound, other.upper_bound))
          if self.lower_bound != other.lower_bound:
              raise ValueError(
                  'The lower bounds of the two IntervalMetadata objects '
                  'are not equal (%d != %d)' % (
                      self.lower_bound, other.lower_bound))
          for intvl in other._intervals:
              self.add(intvl.bounds, intvl.fuzzy, intvl.metadata)
  
      @experimental(as_of='0.5.1')
      def sort(self, ascending=True):
          '''Sort interval features by their coordinates.
  
          It sorts by the start coordinate first. If they are the same between
          two interval features, they will be sorted by comparing their end
          coordinates. For example, an interval feature with [(1, 2), (4, 7)]
          will be sorted in front of another one with [(1, 2), (3, 8)].
  
          Parameters
          ----------
          ascending : bool, optional
              sort in ascending or descending coordinates.
          '''
          self._intervals.sort(
              key=lambda i: [i.bounds[0][0], i.bounds[-1][1]],
              reverse=not ascending)
  
      @experimental(as_of='0.5.1')
      def add(self, bounds, fuzzy=None, metadata=None):
          """Create and add an ``Interval`` to this ``IntervalMetadata``.
  
          This method creates an ``Interval`` object and inserts it into
          the ``IntervalMetadata`` object.
  
          Parameters
          ----------
          bounds : iterable of tuple of ints
              Tuples representing start and end coordinates. It is *zero-based*
              numbering. It is always inclusive on start bound and exclusive on
              end bound.
          fuzzy : iterable of tuple of bool, optional
              Tuples representing the fuzziness of each bound coordinates.
          metadata : dict, optional
              A dictionary of key-value pairs associated with the
              ``Interval`` object.
  
          Returns
          -------
          Interval
              The ``Interval`` object added.
  
          See Also
          --------
          skbio.metadata.Interval
          """
          # Add an interval to the tree. Note that the add functionality is
          # built within the Interval constructor.
          return Interval(interval_metadata=self,
                          bounds=bounds,
                          fuzzy=fuzzy,
                          metadata=metadata)
  
      @_rebuild_tree
      def _query_interval(self, bound):
          """Yield ``Interval`` objects that overlap with the bound."""
          _assert_valid_bound(bound)
  
          start, end = bound
          intvls = self._interval_tree.find(start, end)
          # if a ``Interval`` has many non-contiguous spans and
          # multiple of them overlap with the bound, then
          # this ``Interval`` object will be returned
          # multiple times. So we need to remove duplicates.
          seen = set()
          for intvl in intvls:
              if id(intvl) not in seen:
                  seen.add(id(intvl))
                  yield intvl
  
      def _query_attribute(self, metadata, intervals=None):
          """Yield ``Interval`` objects based on query attributes.
  
          Parameters
          ----------
          metadata : dict or ``None``
              If it is ``None``, return empty iterator; if it is
              ``{}``, return an interator of all the ``Interval``
              objects.
          intervals : an iterable of ``Interval`` objects
          """
          if metadata is None:
              return
  
          if intervals is None:
              intervals = self._intervals
  
          for intvl in intervals:
              for (key, value) in metadata.items():
                  if (key not in intvl.metadata or
                          intvl.metadata[key] != value):
                      break
              else:
                  yield intvl
  
      @experimental(as_of='0.5.1')
      @_rebuild_tree
      def query(self, bounds=None, metadata=None):
          """Yield ``Interval`` object with the bounds and attributes.
  
          The ``Interval`` objects must meet both requirements: 1) overlap
          with any of the spans specified by ``bounds``; 2) satisfy
          ``metadata`` specification. For instance, you can identify
          all the recA genes that overlap with (10, 100) or (900, 1000)
          with this code ``interval_metadata.query([(10, 100),
          (900, 1000)], {'gene': 'recA'})``.
  
          Parameters
          ----------
          bounds : iterable of tuples of int pair, optional
              Specifies bounds to look for the ``Interval``
              objects. An satisfying interval feature only need to overlap with
              one bound. Default (``None``) means all ``Intervals`` meet
              this requirement.
  
          metadata : dict, optional
              A dictionary of key word attributes associated with the
              ``Interval`` object. It specifies what metadata keywords and
              values to look for. Default (``None``) means all ``Intervals``
              meet this requirement.
  
          Yields
          ------
          Interval
              ``Interval`` object satisfying the search criteria.
          """
          if bounds is None:
              for intvl in self._query_attribute(metadata):
                  yield intvl
          else:
              for loc in bounds:
                  intvls = self._query_interval(loc)
                  if metadata is None:
                      metadata = {}
                  for intvl in self._query_attribute(metadata, intvls):
                      yield intvl
  
      @experimental(as_of='0.5.1')
      def drop(self, intervals, negate=False):
          """Drops Interval objects.
  
          The given ``Interval`` objects will be removed and their
          associated ``IntervalMetadata`` will be set to ``None``.
  
          Parameters
          ----------
          intervals : iterable of ``Interval``
              ``Interval`` objects to drop from this object.
          negate : bool
              Negate the drop operation, i.e. keeping the specified intervals
              instead of dropping them.
          """
          to_delete = {id(f) for f in intervals}
  
          new_intvls = []
          # iterate through queries and drop them
          for intvl in self._intervals:
              drop = id(intvl) in to_delete
              if negate is True:
                  drop = not drop
              if drop:
                  intvl._interval_metadata = None
              else:
                  new_intvls.append(intvl)
  
          self._intervals = new_intvls
          self._is_stale_tree = True
  
      @experimental(as_of='0.5.1')
      def __eq__(self, other):
          '''Test if this object is equal to another.
  
          It checks if the coordinate spaces are the same between the
          two objects. If so, then check if all the interval features
          are equal between the two objects after sorting them by
          bounds.
  
          Parameters
          ----------
          other : IntervalMetadata
              Interval metadata to test for equality against.
  
          Returns
          -------
          bool
              Indicates if the two objects are equal.
          '''
          if self.upper_bound != other.upper_bound or \
             self.lower_bound != other.lower_bound:
              return False
          else:
              self_intervals = sorted(self._intervals,
                                      key=operator.attrgetter('bounds'))
              other_intervals = sorted(other._intervals,
                                       key=operator.attrgetter('bounds'))
              return self_intervals == other_intervals
  
      @experimental(as_of='0.5.1')
      def __ne__(self, other):
          '''Test if this object is not equal to another.
  
          Parameters
          ----------
          other : IntervalMetadata
              Interval metadata to test for inequality against.
  
          Returns
          -------
          bool
              Indicates if the two objects are not equal.
  
          See Also
          --------
          skbio.metadata.IntervalMetadata.__eq__
          '''
          return not (self == other)
  
      @experimental(as_of='0.5.1')
      def __repr__(self):
          '''Return a string representation of this object.
  
          Returns
          -------
          str
              String representation of this ``IntervalMetadata`` object.
          '''
          n = self.num_interval_features
          l1 = '{} interval feature'.format(n)
          if n != 1:
              l1 += 's'
          l2 = '-' * len(l1)
  
          if n <= 5:
              items = [repr(i) for i in self._intervals]
          else:
              # intentionally overwrite items[2] to make code cleaner
              items = [repr(self._intervals[i]) for i in [0, 1, 2, n-2, n-1]]
              items[2] = '...'
  
          return '\n'.join([l1, l2] + items)
  
      @experimental(as_of='0.5.1')
      def __copy__(self):
          '''Return a shallow copy.
  
          Notes
          -----
          The ``IntervalMetadata`` copy will have copies of the
          ``Interval`` objects present in this object.  The ``metadata``
          dictionary of each ``Interval`` object will be a shallow copy.
  
          See Also
          --------
          __deepcopy__
          '''
          return self._copy(False, {})
  
      @experimental(as_of='0.5.1')
      def __deepcopy__(self, memo):
          '''Return a deep copy.
  
          Notes
          -----
          The ``IntervalMetadata`` copy will have copies of the
          ``Interval`` objects present in this object.  The ``metadata``
          dictionary of each ``Interval`` object will be a deep copy.
  
          See Also
          --------
          __copy__
          '''
          return self._copy(True, memo)
  
      def _copy(self, deep, memo):
          cp = IntervalMetadata(self.upper_bound)
  
          for interval in self._intervals:
              # Only need to shallow-copy `bounds` and `fuzzy`
              # because their elements are immutable.
              bounds_cp = interval.bounds[:]
              fuzzy_cp = interval.fuzzy[:]
              if deep:
                  metadata_cp = copy.deepcopy(interval.metadata, memo)
              else:
                  metadata_cp = copy.copy(interval.metadata)
  
              cp.add(bounds_cp,
                     fuzzy=fuzzy_cp,
                     metadata=metadata_cp)
  
          return cp
  
  
  def _assert_valid_bound(bound):
      if isinstance(bound, tuple):
          try:
              start, end = bound
          except ValueError:
              raise ValueError("A `bound` must be a tuple of exactly "
                               "two coordinates, not {!r}".format(bound))
          if not (isinstance(start, int) and
                  isinstance(end, int)) or start > end:
              raise ValueError('`start` (%r) cannot be a larger int '
                               'than `end` (%r).' % (start, end))
      else:
          raise TypeError("Each `bound` must be a tuple, not {!r}".format(
              bound))
  
  
  def _assert_valid_fuzzy(fuzzy):
      if isinstance(fuzzy, tuple):
          try:
              start, end = fuzzy
          except ValueError:
              raise ValueError("A `fuzzy` must be a tuple of exactly "
                               "two, not {!r}".format(fuzzy))
          if not (isinstance(start, bool) and isinstance(end, bool)):
              raise TypeError('A `fuzzy` must be a tuple of two booleans')
      else:
          raise TypeError("Each `fuzzy` must be a tuple, not {!r}".format(
              fuzzy))
  