| """ |
| 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.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, |
| VariableValue, |
| VariableFloat, |
| VariableInt, |
| ) |
| from .errors import ColorLibError |
| from .geometry import round_start_circle_stable_containment |
| from .table_builder import ( |
| convertTupleClass, |
| 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]]] |
| |
| |
| MAX_PAINT_COLR_LAYER_COUNT = 255 |
| _DEFAULT_ALPHA = VariableFloat(1.0) |
| _MAX_REUSE_LEN = 32 |
| |
| |
| def _beforeBuildPaintVarRadialGradient(paint, source, srcMapFn=lambda v: v): |
| # normalize input types (which may or may not specify a varIdx) |
| x0 = convertTupleClass(VariableFloat, source["x0"]) |
| y0 = convertTupleClass(VariableFloat, source["y0"]) |
| r0 = convertTupleClass(VariableFloat, source["r0"]) |
| x1 = convertTupleClass(VariableFloat, source["x1"]) |
| y1 = convertTupleClass(VariableFloat, source["y1"]) |
| r1 = convertTupleClass(VariableFloat, 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.value, y0.value), r0.value, (x1.value, y1.value), r1.value |
| ) |
| x0, y0 = x0._replace(value=c.centre[0]), y0._replace(value=c.centre[1]) |
| r0 = r0._replace(value=c.radius) |
| |
| # update source to ensure paint is built with corrected values |
| source["x0"] = srcMapFn(x0) |
| source["y0"] = srcMapFn(y0) |
| source["r0"] = srcMapFn(r0) |
| source["x1"] = srcMapFn(x1) |
| source["y1"] = srcMapFn(y1) |
| source["r1"] = srcMapFn(r1) |
| |
| return paint, source |
| |
| |
| def _beforeBuildPaintRadialGradient(paint, source): |
| return _beforeBuildPaintVarRadialGradient(paint, source, lambda v: v.value) |
| |
| |
| def _defaultColorIndex(): |
| colorIndex = ot.ColorIndex() |
| colorIndex.Alpha = _DEFAULT_ALPHA.value |
| return colorIndex |
| |
| |
| def _defaultVarColorIndex(): |
| colorIndex = ot.VarColorIndex() |
| colorIndex.Alpha = _DEFAULT_ALPHA |
| return colorIndex |
| |
| |
| def _defaultColorLine(): |
| colorLine = ot.ColorLine() |
| colorLine.Extend = ExtendMode.PAD |
| return colorLine |
| |
| |
| def _defaultVarColorLine(): |
| colorLine = ot.VarColorLine() |
| colorLine.Extend = ExtendMode.PAD |
| return colorLine |
| |
| |
| def _buildPaintCallbacks(): |
| return { |
| ( |
| BuildCallback.BEFORE_BUILD, |
| ot.Paint, |
| ot.PaintFormat.PaintRadialGradient, |
| ): _beforeBuildPaintRadialGradient, |
| ( |
| BuildCallback.BEFORE_BUILD, |
| ot.Paint, |
| ot.PaintFormat.PaintVarRadialGradient, |
| ): _beforeBuildPaintVarRadialGradient, |
| (BuildCallback.CREATE_DEFAULT, ot.ColorIndex): _defaultColorIndex, |
| (BuildCallback.CREATE_DEFAULT, ot.VarColorIndex): _defaultVarColorIndex, |
| (BuildCallback.CREATE_DEFAULT, ot.ColorLine): _defaultColorLine, |
| (BuildCallback.CREATE_DEFAULT, ot.VarColorLine): _defaultVarColorLine, |
| } |
| |
| |
| 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, |
| ) -> 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. |
| 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.LayerV1List, colr.BaseGlyphV1List = 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: |
| colr.VarStore = varStore |
| self.table = colr |
| |
| return self |
| |
| |
| 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 LayerV1ListBuilder: |
| 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.LayerV1List]: |
| if not self.layers: |
| return None |
| layers = ot.LayerV1List() |
| layers.LayerCount = len(self.layers) |
| layers.Paint = self.layers |
| return layers |
| |
| |
| def buildBaseGlyphV1Record( |
| baseGlyph: str, layerBuilder: LayerV1ListBuilder, paint: _PaintInput |
| ) -> ot.BaseGlyphV1List: |
| self = ot.BaseGlyphV1Record() |
| 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.LayerV1List], ot.BaseGlyphV1List]: |
| if glyphMap is not None: |
| colorGlyphItems = sorted( |
| colorGlyphs.items(), key=lambda item: glyphMap[item[0]] |
| ) |
| else: |
| colorGlyphItems = colorGlyphs.items() |
| |
| errors = {} |
| baseGlyphs = [] |
| layerBuilder = LayerV1ListBuilder() |
| for baseGlyph, paint in colorGlyphItems: |
| try: |
| baseGlyphs.append(buildBaseGlyphV1Record(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 BaseGlyphV1List:\n{failed_glyphs}") |
| exc.errors = errors |
| raise exc from next(iter(errors.values())) |
| |
| layers = layerBuilder.build() |
| glyphs = ot.BaseGlyphV1List() |
| glyphs.BaseGlyphCount = len(baseGlyphs) |
| glyphs.BaseGlyphV1Record = 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 |