from collections import namedtuple
from typing import Any
import numpy
ItemAddition = namedtuple('ItemAddition', ['insert_index', 'new_list_index'])
ItemDeletion = namedtuple('ItemDeletion', ['deletion_index'])
[docs]
def compute_list_changes(new_list: list, original_list: list) -> tuple[list[ItemDeletion], list[ItemAddition]]:
"""
Computes a list of changes that has to be performed on ``original_list`` to transform it to ``new_list``.
Equivalence of items is determined using the ``==`` operator.
This method can be used on table headers to compute which columns needs to be removed and which needs to be
added.
The operations must be performed in the following order:
1. Perform all deletions in the given order.
2. Add all columns in the given order.
:param new_list: Desired state of the list.
:param original_list: Original state of the list.
:return: Tuple containing ``(list_of_deletions, list_of_additions)``
"""
new_list = normalize_column_list(new_list)
original_list = normalize_column_list(original_list)
deletions: list[ItemDeletion] = []
additions: list[ItemAddition] = []
i_max = len(original_list)
j_max = len(new_list)
matrix = numpy.zeros((i_max + 1, j_max + 1), dtype=numpy.uint32)
for i in range(1, len(original_list) + 1):
for j in range(1, len(new_list) + 1):
if original_list[i - 1] == new_list[j - 1]:
matrix[i, j] = matrix[i - 1, j - 1] + 1
else:
matrix[i, j] = max(matrix[i, j - 1], matrix[i - 1, j])
i = i_max
j = j_max
while i > 0 or j > 0:
if i == 0:
# We have reached top row - move only left (additions)
j -= 1
additions.append(ItemAddition(j, j))
elif j == 0:
# We have reached left column - move only up (deletions)
i -= 1
deletions.append(ItemDeletion(i))
elif original_list[i - 1] == new_list[j - 1]:
# Values in list are equal - move left-up.
i -= 1
j -= 1
elif matrix[i, j - 1] == matrix[i, j]:
# Value equals to left cell - move left (addition).
j -= 1
additions.append(ItemAddition(j, j))
else:
# Value equals to top cell - move up (deletion).
i -= 1
deletions.append(ItemDeletion(i))
additions.reverse()
return deletions, additions
[docs]
def normalize_column_list(column_list: list[Any]):
"""
Normalizes the given list of columns. Performs the following operations:
1. Converts columns specified by a list to tuples.
:param column_list: Input column list, may be previously stored.
:return: Normalized column list.
"""
return [tuple(col) if isinstance(col, list) else col for col in column_list]