code: def get_parent_paths(
      paths: list[str],
      parents: list[str],
      only_with_parents: bool = False,
      *,
      sep: str = "/",
  ) -> list[str]:
      """Given a list of children paths, return their parent paths among parents
      or their own path if there is no known parent. A path is also considered its
      own parent (haven't you watched Predestination?) ;)
  
      All paths should be relative, not pointing outside (not starting
      with ../), and normalized (no // or dir/../dir and alike). Only minimal
      sanity checking of values is done.  By default paths are considered to be
      POSIX. Use 'sep' kwarg to set to `os.sep` to provide OS specific handling.
  
      Accent is made on performance to avoid O(len(paths) * len(parents))
      runtime.  ATM should be typically less than O(len(paths) * len(log(parents)))
  
      Initial intended use - for a list of paths in the repository
      to provide their paths as files/submodules known to that repository, to
      overcome difference in ls-tree and ls-files, where ls-files outputs nothing
      for paths within submodules.
      It is coded, so it could later be applied even whenever there are nested
      parents, e.g. parents = ['sub', 'sub/sub'] and then the "deepest" parent
      is selected
  
      Parameters
      ----------
      parents: list of str
      paths: list of str
      only_with_parents: bool, optional
        If set to True, return a list of only parent paths where that path had
        a parent
      sep: str, optional
        Path separator.  By default - '/' and thus treating paths as POSIX.
        If you are processing OS-specific paths (for both `parents` and `paths`),
        specify `sep=os.sep`.
  
      Returns
      -------
      A list of paths (without duplicates), where some entries replaced with
      their "parents" without duplicates.  So for 'a/b' and 'a/c' with a being
      among parents, there will be a single 'a'
      """
      # Let's do an early check even though then we would skip the checks on paths
      # being relative etc
      if not parents:
          return [] if only_with_parents else paths
  
      # We will create a lookup for known parent lengths
      parent_set = set(parents)  # O(log(len(parents))) lookup
  
      # Will be used in sanity checking that we got consistently used separators, i.e.
      # not mixing non-POSIX paths and POSIX parents
      asep = {"/": "\\", "\\": "/"}[sep]
  
      # rely on path[:n] be quick, and len(parent_lengths) << len(parent_set)
      # when len(parent_set) is large.  We will also bail checking any parent of
      # the length if at that length path has no directory boundary ('/').
      #
      # Create mapping for each length of
      # parent path to list of parents with that length
      parent_lengths_map: dict[int, set[str]] = _defaultdict(set)
      for parent in parent_set:
          _get_parent_paths_check(parent, sep, asep)
          parent_lengths_map[len(parent)].add(parent)
  
      # Make it ordered in the descending order so we select the deepest/longest parent
      # and store them as sets for faster lookup.
      # Could be an ordered dict but no need
      parent_lengths = [
          (l, parent_lengths_map[l])
          for l in sorted(parent_lengths_map, reverse=True)
      ]
  
      res = []
      seen = set()
  
      for (
          path
      ) in (
          paths
      ):  # O(len(paths)) - unavoidable but could be parallelized!
          # Sanity check -- should not be too expensive
          _get_parent_paths_check(path, sep, asep)
          for (
              parent_length,
              parents_,
          ) in parent_lengths:  # O(len(parent_lengths))
              if (len(path) < parent_length) or (
                  len(path) > parent_length
                  and path[parent_length] != sep
              ):
                  continue  # no directory deep enough
              candidate_parent = path[:parent_length]
              if (
                  candidate_parent in parents_
              ):  # O(log(len(parent_set))) but expected one less due to per length handling
                  if candidate_parent not in seen:
                      res.append(candidate_parent)
                      seen.add(candidate_parent)
                  break  # it is!
          else:  # no hits
              if not only_with_parents:
                  if path not in seen:
                      res.append(path)
                      seen.add(path)
  
      return res
  
file_path: datalad/datalad/support/path.py
imports: from __future__ import annotations
  import os
  import os.path
  from collections import defaultdict
  from collections.abc import Iterable, Iterator
  from functools import wraps
  from itertools import dropwhile
  from pathlib import Path, PurePosixPath
  from ..utils import ensure_bytes, getpwd
label_desc: Use image node_id 4 for calling a global function with example usage: get_parent_paths(paths, parents, only_with_parents) and returns: res, unknown