text: """
  colorLib.builder: Build COLR/CPAL tables from scratch
  
  """
  import collections
  import copy
  import enum
  from functools import partial
  from math import ceil, log
  from typing import (
      Any,
      Dict,
      Generator,
      Iterable,
      List,
      Mapping,
      Optional,
      Sequence,
      Tuple,
      Type,
      TypeVar,
      Union,
  )
  from fontTools.misc.arrayTools import intRect
  from fontTools.misc.fixedTools import fixedToFloat
  from fontTools.ttLib.tables import C_O_L_R_
  from fontTools.ttLib.tables import C_P_A_L_
  from fontTools.ttLib.tables import _n_a_m_e
  from fontTools.ttLib.tables import otTables as ot
  from fontTools.ttLib.tables.otTables import ExtendMode, CompositeMode
  from .errors import ColorLibError
  from .geometry import round_start_circle_stable_containment
  from .table_builder import BuildCallback, TableBuilder
  
  
  # TODO move type aliases to colorLib.types?
  T = TypeVar("T")
  _Kwargs = Mapping[str, Any]
  _PaintInput = Union[int, _Kwargs, ot.Paint, Tuple[str, "_PaintInput"]]
  _PaintInputList = Sequence[_PaintInput]
  _ColorGlyphsDict = Dict[str, Union[_PaintInputList, _PaintInput]]
  _ColorGlyphsV0Dict = Dict[str, Sequence[Tuple[str, int]]]
  _ClipBoxInput = Union[
      Tuple[int, int, int, int, int],  # format 1, variable
      Tuple[int, int, int, int],  # format 0, non-variable
      ot.ClipBox,
  ]
  
  
  MAX_PAINT_COLR_LAYER_COUNT = 255
  _DEFAULT_ALPHA = 1.0
  _MAX_REUSE_LEN = 32
  
  
  def _beforeBuildPaintRadialGradient(paint, source):
      x0 = source["x0"]
      y0 = source["y0"]
      r0 = source["r0"]
      x1 = source["x1"]
      y1 = source["y1"]
      r1 = source["r1"]
  
      # TODO apparently no builder_test confirms this works (?)
  
      # avoid abrupt change after rounding when c0 is near c1's perimeter
      c = round_start_circle_stable_containment((x0, y0), r0, (x1, y1), r1)
      x0, y0 = c.centre
      r0 = c.radius
  
      # update source to ensure paint is built with corrected values
      source["x0"] = x0
      source["y0"] = y0
      source["r0"] = r0
      source["x1"] = x1
      source["y1"] = y1
      source["r1"] = r1
  
      return paint, source
  
  
  def _defaultColorStop():
      colorStop = ot.ColorStop()
      colorStop.Alpha = _DEFAULT_ALPHA
      return colorStop
  
  
  def _defaultVarColorStop():
      colorStop = ot.VarColorStop()
      colorStop.Alpha = _DEFAULT_ALPHA
      return colorStop
  
  
  def _defaultColorLine():
      colorLine = ot.ColorLine()
      colorLine.Extend = ExtendMode.PAD
      return colorLine
  
  
  def _defaultVarColorLine():
      colorLine = ot.VarColorLine()
      colorLine.Extend = ExtendMode.PAD
      return colorLine
  
  
  def _defaultPaintSolid():
      paint = ot.Paint()
      paint.Alpha = _DEFAULT_ALPHA
      return paint
  
  
  def _buildPaintCallbacks():
      return {
          (
              BuildCallback.BEFORE_BUILD,
              ot.Paint,
              ot.PaintFormat.PaintRadialGradient,
          ): _beforeBuildPaintRadialGradient,
          (
              BuildCallback.BEFORE_BUILD,
              ot.Paint,
              ot.PaintFormat.PaintVarRadialGradient,
          ): _beforeBuildPaintRadialGradient,
          (BuildCallback.CREATE_DEFAULT, ot.ColorStop): _defaultColorStop,
          (BuildCallback.CREATE_DEFAULT, ot.VarColorStop): _defaultVarColorStop,
          (BuildCallback.CREATE_DEFAULT, ot.ColorLine): _defaultColorLine,
          (BuildCallback.CREATE_DEFAULT, ot.VarColorLine): _defaultVarColorLine,
          (
              BuildCallback.CREATE_DEFAULT,
              ot.Paint,
              ot.PaintFormat.PaintSolid,
          ): _defaultPaintSolid,
          (
              BuildCallback.CREATE_DEFAULT,
              ot.Paint,
              ot.PaintFormat.PaintVarSolid,
          ): _defaultPaintSolid,
      }
  
  
  def populateCOLRv0(
      table: ot.COLR,
      colorGlyphsV0: _ColorGlyphsV0Dict,
      glyphMap: Optional[Mapping[str, int]] = None,
  ):
      """Build v0 color layers and add to existing COLR table.
  
      Args:
          table: a raw otTables.COLR() object (not ttLib's table_C_O_L_R_).
          colorGlyphsV0: map of base glyph names to lists of (layer glyph names,
              color palette index) tuples. Can be empty.
          glyphMap: a map from glyph names to glyph indices, as returned from
              TTFont.getReverseGlyphMap(), to optionally sort base records by GID.
      """
      if glyphMap is not None:
          colorGlyphItems = sorted(
              colorGlyphsV0.items(), key=lambda item: glyphMap[item[0]]
          )
      else:
          colorGlyphItems = colorGlyphsV0.items()
      baseGlyphRecords = []
      layerRecords = []
      for baseGlyph, layers in colorGlyphItems:
          baseRec = ot.BaseGlyphRecord()
          baseRec.BaseGlyph = baseGlyph
          baseRec.FirstLayerIndex = len(layerRecords)
          baseRec.NumLayers = len(layers)
          baseGlyphRecords.append(baseRec)
  
          for layerGlyph, paletteIndex in layers:
              layerRec = ot.LayerRecord()
              layerRec.LayerGlyph = layerGlyph
              layerRec.PaletteIndex = paletteIndex
              layerRecords.append(layerRec)
  
      table.BaseGlyphRecordArray = table.LayerRecordArray = None
      if baseGlyphRecords:
          table.BaseGlyphRecordArray = ot.BaseGlyphRecordArray()
          table.BaseGlyphRecordArray.BaseGlyphRecord = baseGlyphRecords
      if layerRecords:
          table.LayerRecordArray = ot.LayerRecordArray()
          table.LayerRecordArray.LayerRecord = layerRecords
      table.BaseGlyphRecordCount = len(baseGlyphRecords)
      table.LayerRecordCount = len(layerRecords)
  
  
  def buildCOLR(
      colorGlyphs: _ColorGlyphsDict,
      version: Optional[int] = None,
      glyphMap: Optional[Mapping[str, int]] = None,
      varStore: Optional[ot.VarStore] = None,
      varIndexMap: Optional[ot.DeltaSetIndexMap] = None,
      clipBoxes: Optional[Dict[str, _ClipBoxInput]] = None,
  ) -> C_O_L_R_.table_C_O_L_R_:
      """Build COLR table from color layers mapping.
      Args:
          colorGlyphs: map of base glyph name to, either list of (layer glyph name,
              color palette index) tuples for COLRv0; or a single Paint (dict) or
              list of Paint for COLRv1.
          version: the version of COLR table. If None, the version is determined
              by the presence of COLRv1 paints or variation data (varStore), which
              require version 1; otherwise, if all base glyphs use only simple color
              layers, version 0 is used.
          glyphMap: a map from glyph names to glyph indices, as returned from
              TTFont.getReverseGlyphMap(), to optionally sort base records by GID.
          varStore: Optional ItemVarationStore for deltas associated with v1 layer.
          varIndexMap: Optional DeltaSetIndexMap for deltas associated with v1 layer.
          clipBoxes: Optional map of base glyph name to clip box 4- or 5-tuples:
              (xMin, yMin, xMax, yMax) or (xMin, yMin, xMax, yMax, varIndexBase).
      Return:
          A new COLR table.
      """
      self = C_O_L_R_.table_C_O_L_R_()
  
      if varStore is not None and version == 0:
          raise ValueError("Can't add VarStore to COLRv0")
  
      if version in (None, 0) and not varStore:
          # split color glyphs into v0 and v1 and encode separately
          colorGlyphsV0, colorGlyphsV1 = _split_color_glyphs_by_version(colorGlyphs)
          if version == 0 and colorGlyphsV1:
              raise ValueError("Can't encode COLRv1 glyphs in COLRv0")
      else:
          # unless explicitly requested for v1 or have variations, in which case
          # we encode all color glyph as v1
          colorGlyphsV0, colorGlyphsV1 = {}, colorGlyphs
  
      colr = ot.COLR()
  
      populateCOLRv0(colr, colorGlyphsV0, glyphMap)
  
      colr.LayerList, colr.BaseGlyphList = buildColrV1(colorGlyphsV1, glyphMap)
  
      if version is None:
          version = 1 if (varStore or colorGlyphsV1) else 0
      elif version not in (0, 1):
          raise NotImplementedError(version)
      self.version = colr.Version = version
  
      if version == 0:
          self.ColorLayers = self._decompileColorLayersV0(colr)
      else:
          clipBoxes = {
              name: clipBoxes[name] for name in clipBoxes or {} if name in colorGlyphsV1
          }
          colr.ClipList = buildClipList(clipBoxes) if clipBoxes else None
          colr.VarIndexMap = varIndexMap
          colr.VarStore = varStore
          self.table = colr
  
      return self
  
  
  def buildClipList(clipBoxes: Dict[str, _ClipBoxInput]) -> ot.ClipList:
      clipList = ot.ClipList()
      clipList.Format = 1
      clipList.clips = {name: buildClipBox(box) for name, box in clipBoxes.items()}
      return clipList
  
  
  def buildClipBox(clipBox: _ClipBoxInput) -> ot.ClipBox:
      if isinstance(clipBox, ot.ClipBox):
          return clipBox
      n = len(clipBox)
      clip = ot.ClipBox()
      if n not in (4, 5):
          raise ValueError(f"Invalid ClipBox: expected 4 or 5 values, found {n}")
      clip.xMin, clip.yMin, clip.xMax, clip.yMax = intRect(clipBox[:4])
      clip.Format = int(n == 5) + 1
      if n == 5:
          clip.VarIndexBase = int(clipBox[4])
      return clip
  
  
  class ColorPaletteType(enum.IntFlag):
      USABLE_WITH_LIGHT_BACKGROUND = 0x0001
      USABLE_WITH_DARK_BACKGROUND = 0x0002
  
      @classmethod
      def _missing_(cls, value):
          # enforce reserved bits
          if isinstance(value, int) and (value < 0 or value & 0xFFFC != 0):
              raise ValueError(f"{value} is not a valid {cls.__name__}")
          return super()._missing_(value)
  
  
  # None, 'abc' or {'en': 'abc', 'de': 'xyz'}
  _OptionalLocalizedString = Union[None, str, Dict[str, str]]
  
  
  def buildPaletteLabels(
      labels: Iterable[_OptionalLocalizedString], nameTable: _n_a_m_e.table__n_a_m_e
  ) -> List[Optional[int]]:
      return [
          nameTable.addMultilingualName(l, mac=False)
          if isinstance(l, dict)
          else C_P_A_L_.table_C_P_A_L_.NO_NAME_ID
          if l is None
          else nameTable.addMultilingualName({"en": l}, mac=False)
          for l in labels
      ]
  
  
  def buildCPAL(
      palettes: Sequence[Sequence[Tuple[float, float, float, float]]],
      paletteTypes: Optional[Sequence[ColorPaletteType]] = None,
      paletteLabels: Optional[Sequence[_OptionalLocalizedString]] = None,
      paletteEntryLabels: Optional[Sequence[_OptionalLocalizedString]] = None,
      nameTable: Optional[_n_a_m_e.table__n_a_m_e] = None,
  ) -> C_P_A_L_.table_C_P_A_L_:
      """Build CPAL table from list of color palettes.
  
      Args:
          palettes: list of lists of colors encoded as tuples of (R, G, B, A) floats
              in the range [0..1].
          paletteTypes: optional list of ColorPaletteType, one for each palette.
          paletteLabels: optional list of palette labels. Each lable can be either:
              None (no label), a string (for for default English labels), or a
              localized string (as a dict keyed with BCP47 language codes).
          paletteEntryLabels: optional list of palette entry labels, one for each
              palette entry (see paletteLabels).
          nameTable: optional name table where to store palette and palette entry
              labels. Required if either paletteLabels or paletteEntryLabels is set.
  
      Return:
          A new CPAL v0 or v1 table, if custom palette types or labels are specified.
      """
      if len({len(p) for p in palettes}) != 1:
          raise ColorLibError("color palettes have different lengths")
  
      if (paletteLabels or paletteEntryLabels) and not nameTable:
          raise TypeError(
              "nameTable is required if palette or palette entries have labels"
          )
  
      cpal = C_P_A_L_.table_C_P_A_L_()
      cpal.numPaletteEntries = len(palettes[0])
  
      cpal.palettes = []
      for i, palette in enumerate(palettes):
          colors = []
          for j, color in enumerate(palette):
              if not isinstance(color, tuple) or len(color) != 4:
                  raise ColorLibError(
                      f"In palette[{i}][{j}]: expected (R, G, B, A) tuple, got {color!r}"
                  )
              if any(v > 1 or v < 0 for v in color):
                  raise ColorLibError(
                      f"palette[{i}][{j}] has invalid out-of-range [0..1] color: {color!r}"
                  )
              # input colors are RGBA, CPAL encodes them as BGRA
              red, green, blue, alpha = color
              colors.append(
                  C_P_A_L_.Color(*(round(v * 255) for v in (blue, green, red, alpha)))
              )
          cpal.palettes.append(colors)
  
      if any(v is not None for v in (paletteTypes, paletteLabels, paletteEntryLabels)):
          cpal.version = 1
  
          if paletteTypes is not None:
              if len(paletteTypes) != len(palettes):
                  raise ColorLibError(
                      f"Expected {len(palettes)} paletteTypes, got {len(paletteTypes)}"
                  )
              cpal.paletteTypes = [ColorPaletteType(t).value for t in paletteTypes]
          else:
              cpal.paletteTypes = [C_P_A_L_.table_C_P_A_L_.DEFAULT_PALETTE_TYPE] * len(
                  palettes
              )
  
          if paletteLabels is not None:
              if len(paletteLabels) != len(palettes):
                  raise ColorLibError(
                      f"Expected {len(palettes)} paletteLabels, got {len(paletteLabels)}"
                  )
              cpal.paletteLabels = buildPaletteLabels(paletteLabels, nameTable)
          else:
              cpal.paletteLabels = [C_P_A_L_.table_C_P_A_L_.NO_NAME_ID] * len(palettes)
  
          if paletteEntryLabels is not None:
              if len(paletteEntryLabels) != cpal.numPaletteEntries:
                  raise ColorLibError(
                      f"Expected {cpal.numPaletteEntries} paletteEntryLabels, "
                      f"got {len(paletteEntryLabels)}"
                  )
              cpal.paletteEntryLabels = buildPaletteLabels(paletteEntryLabels, nameTable)
          else:
              cpal.paletteEntryLabels = [
                  C_P_A_L_.table_C_P_A_L_.NO_NAME_ID
              ] * cpal.numPaletteEntries
      else:
          cpal.version = 0
  
      return cpal
  
  
  # COLR v1 tables
  # See draft proposal at: https://github.com/googlefonts/colr-gradients-spec
  
  
  def _is_colrv0_layer(layer: Any) -> bool:
      # Consider as COLRv0 layer any sequence of length 2 (be it tuple or list) in which
      # the first element is a str (the layerGlyph) and the second element is an int
      # (CPAL paletteIndex).
      # https://github.com/googlefonts/ufo2ft/issues/426
      try:
          layerGlyph, paletteIndex = layer
      except (TypeError, ValueError):
          return False
      else:
          return isinstance(layerGlyph, str) and isinstance(paletteIndex, int)
  
  
  def _split_color_glyphs_by_version(
      colorGlyphs: _ColorGlyphsDict,
  ) -> Tuple[_ColorGlyphsV0Dict, _ColorGlyphsDict]:
      colorGlyphsV0 = {}
      colorGlyphsV1 = {}
      for baseGlyph, layers in colorGlyphs.items():
          if all(_is_colrv0_layer(l) for l in layers):
              colorGlyphsV0[baseGlyph] = layers
          else:
              colorGlyphsV1[baseGlyph] = layers
  
      # sanity check
      assert set(colorGlyphs) == (set(colorGlyphsV0) | set(colorGlyphsV1))
  
      return colorGlyphsV0, colorGlyphsV1
  
  
  def _reuse_ranges(num_layers: int) -> Generator[Tuple[int, int], None, None]:
      # TODO feels like something itertools might have already
      for lbound in range(num_layers):
          # Reuse of very large #s of layers is relatively unlikely
          # +2: we want sequences of at least 2
          # otData handles single-record duplication
          for ubound in range(
              lbound + 2, min(num_layers + 1, lbound + 2 + _MAX_REUSE_LEN)
          ):
              yield (lbound, ubound)
  
  
  class LayerListBuilder:
      slices: List[ot.Paint]
      layers: List[ot.Paint]
      reusePool: Mapping[Tuple[Any, ...], int]
      tuples: Mapping[int, Tuple[Any, ...]]
      keepAlive: List[ot.Paint]  # we need id to remain valid
  
      def __init__(self):
          self.slices = []
          self.layers = []
          self.reusePool = {}
          self.tuples = {}
          self.keepAlive = []
  
          # We need to intercept construction of PaintColrLayers
          callbacks = _buildPaintCallbacks()
          callbacks[
              (
                  BuildCallback.BEFORE_BUILD,
                  ot.Paint,
                  ot.PaintFormat.PaintColrLayers,
              )
          ] = self._beforeBuildPaintColrLayers
          self.tableBuilder = TableBuilder(callbacks)
  
      def _paint_tuple(self, paint: ot.Paint):
          # start simple, who even cares about cyclic graphs or interesting field types
          def _tuple_safe(value):
              if isinstance(value, enum.Enum):
                  return value
              elif hasattr(value, "__dict__"):
                  return tuple(
                      (k, _tuple_safe(v)) for k, v in sorted(value.__dict__.items())
                  )
              elif isinstance(value, collections.abc.MutableSequence):
                  return tuple(_tuple_safe(e) for e in value)
              return value
  
          # Cache the tuples for individual Paint instead of the whole sequence
          # because the seq could be a transient slice
          result = self.tuples.get(id(paint), None)
          if result is None:
              result = _tuple_safe(paint)
              self.tuples[id(paint)] = result
              self.keepAlive.append(paint)
          return result
  
      def _as_tuple(self, paints: Sequence[ot.Paint]) -> Tuple[Any, ...]:
          return tuple(self._paint_tuple(p) for p in paints)
  
      # COLR layers is unusual in that it modifies shared state
      # so we need a callback into an object
      def _beforeBuildPaintColrLayers(self, dest, source):
          paint = ot.Paint()
          paint.Format = int(ot.PaintFormat.PaintColrLayers)
          self.slices.append(paint)
  
          # Sketchy gymnastics: a sequence input will have dropped it's layers
          # into NumLayers; get it back
          if isinstance(source.get("NumLayers", None), collections.abc.Sequence):
              layers = source["NumLayers"]
          else:
              layers = source["Layers"]
  
          # Convert maps seqs or whatever into typed objects
          layers = [self.buildPaint(l) for l in layers]
  
          # No reason to have a colr layers with just one entry
          if len(layers) == 1:
              return layers[0], {}
  
          # Look for reuse, with preference to longer sequences
          # This may make the layer list smaller
          found_reuse = True
          while found_reuse:
              found_reuse = False
  
              ranges = sorted(
                  _reuse_ranges(len(layers)),
                  key=lambda t: (t[1] - t[0], t[1], t[0]),
                  reverse=True,
              )
              for lbound, ubound in ranges:
                  reuse_lbound = self.reusePool.get(
                      self._as_tuple(layers[lbound:ubound]), -1
                  )
                  if reuse_lbound == -1:
                      continue
                  new_slice = ot.Paint()
                  new_slice.Format = int(ot.PaintFormat.PaintColrLayers)
                  new_slice.NumLayers = ubound - lbound
                  new_slice.FirstLayerIndex = reuse_lbound
                  layers = layers[:lbound] + [new_slice] + layers[ubound:]
                  found_reuse = True
                  break
  
          # The layer list is now final; if it's too big we need to tree it
          is_tree = len(layers) > MAX_PAINT_COLR_LAYER_COUNT
          layers = _build_n_ary_tree(layers, n=MAX_PAINT_COLR_LAYER_COUNT)
  
          # We now have a tree of sequences with Paint leaves.
          # Convert the sequences into PaintColrLayers.
          def listToColrLayers(layer):
              if isinstance(layer, collections.abc.Sequence):
                  return self.buildPaint(
                      {
                          "Format": ot.PaintFormat.PaintColrLayers,
                          "Layers": [listToColrLayers(l) for l in layer],
                      }
                  )
              return layer
  
          layers = [listToColrLayers(l) for l in layers]
  
          paint.NumLayers = len(layers)
          paint.FirstLayerIndex = len(self.layers)
          self.layers.extend(layers)
  
          # Register our parts for reuse provided we aren't a tree
          # If we are a tree the leaves registered for reuse and that will suffice
          if not is_tree:
              for lbound, ubound in _reuse_ranges(len(layers)):
                  self.reusePool[self._as_tuple(layers[lbound:ubound])] = (
                      lbound + paint.FirstLayerIndex
                  )
  
          # we've fully built dest; empty source prevents generalized build from kicking in
          return paint, {}
  
      def buildPaint(self, paint: _PaintInput) -> ot.Paint:
          return self.tableBuilder.build(ot.Paint, paint)
  
      def build(self) -> Optional[ot.LayerList]:
          if not self.layers:
              return None
          layers = ot.LayerList()
          layers.LayerCount = len(self.layers)
          layers.Paint = self.layers
          return layers
  
  
  def buildBaseGlyphPaintRecord(
      baseGlyph: str, layerBuilder: LayerListBuilder, paint: _PaintInput
  ) -> ot.BaseGlyphList:
      self = ot.BaseGlyphPaintRecord()
      self.BaseGlyph = baseGlyph
      self.Paint = layerBuilder.buildPaint(paint)
      return self
  
  
  def _format_glyph_errors(errors: Mapping[str, Exception]) -> str:
      lines = []
      for baseGlyph, error in sorted(errors.items()):
          lines.append(f"    {baseGlyph} => {type(error).__name__}: {error}")
      return "\n".join(lines)
  
  
  def buildColrV1(
      colorGlyphs: _ColorGlyphsDict,
      glyphMap: Optional[Mapping[str, int]] = None,
  ) -> Tuple[Optional[ot.LayerList], ot.BaseGlyphList]:
      if glyphMap is not None:
          colorGlyphItems = sorted(
              colorGlyphs.items(), key=lambda item: glyphMap[item[0]]
          )
      else:
          colorGlyphItems = colorGlyphs.items()
  
      errors = {}
      baseGlyphs = []
      layerBuilder = LayerListBuilder()
      for baseGlyph, paint in colorGlyphItems:
          try:
              baseGlyphs.append(buildBaseGlyphPaintRecord(baseGlyph, layerBuilder, paint))
  
          except (ColorLibError, OverflowError, ValueError, TypeError) as e:
              errors[baseGlyph] = e
  
      if errors:
          failed_glyphs = _format_glyph_errors(errors)
          exc = ColorLibError(f"Failed to build BaseGlyphList:\n{failed_glyphs}")
          exc.errors = errors
          raise exc from next(iter(errors.values()))
  
      layers = layerBuilder.build()
      glyphs = ot.BaseGlyphList()
      glyphs.BaseGlyphCount = len(baseGlyphs)
      glyphs.BaseGlyphPaintRecord = baseGlyphs
      return (layers, glyphs)
  
  
  def _build_n_ary_tree(leaves, n):
      """Build N-ary tree from sequence of leaf nodes.
  
      Return a list of lists where each non-leaf node is a list containing
      max n nodes.
      """
      if not leaves:
          return []
  
      assert n > 1
  
      depth = ceil(log(len(leaves), n))
  
      if depth <= 1:
          return list(leaves)
  
      # Fully populate complete subtrees of root until we have enough leaves left
      root = []
      unassigned = None
      full_step = n ** (depth - 1)
      for i in range(0, len(leaves), full_step):
          subtree = leaves[i : i + full_step]
          if len(subtree) < full_step:
              unassigned = subtree
              break
          while len(subtree) > n:
              subtree = [subtree[k : k + n] for k in range(0, len(subtree), n)]
          root.append(subtree)
  
      if unassigned:
          # Recurse to fill the last subtree, which is the only partially populated one
          subtree = _build_n_ary_tree(unassigned, n)
          if len(subtree) <= n - len(root):
              # replace last subtree with its children if they can still fit
              root.extend(subtree)
          else:
              root.append(subtree)
          assert len(root) <= n
  
      return root
  