Подтвердить что ты не робот

Односторонняя синхронизация двух иерархий

Я надеюсь написать алгоритм для синхронизации двух иерархических структур. Эти структуры могут быть объектными графами, данными, хранящимися в реляционных таблицах баз данных и т.д. (Даже две разные структуры, если у них есть сопоставимые ключи). Синхронизация будет односторонней, т.е. Одна структура будет прототипом, а другая будет изменена для соответствия.

Скажем, мы имеем функцию sync. Он должен принять следующее:

  • objA - прототип
  • objB - объект, подлежащий изменению
  • keyA - функция генерации ключей для objA
  • keyB - функция генерации ключей для objB
  • addB - функция для создания objB (возвращает идентификатор нового objB)
  • setB - функция обновления objB
  • remB - функция для удаления objB
  • parB - id из objB parent - это передается addB для контекста

Итак, мы имеем это:

let sync (objA:'a) (objB:'b) (keyA:'a -> 'k) (keyB:'b -> 'k)
         (addB:'p * 'a -> 'p) (setB:'a * 'b -> unit) (remB:'b -> unit) 
         (parB:'p) = ...

Теперь, когда у меня возникают проблемы. 'a и 'b являются иерархическими, поэтому функции должны знать, какие свойства 'a и 'b должны пересекаться (как только они сравнивают свои ключи и решают, что они соответствуют до сих пор и должны быть пройдены дальше). Для этих "дочерних" свойств ему нужны все те же аргументы, которые передаются для синхронизации, но для их соответствующих типов.

Вот когда стало очевидно, что это проблема структуры данных. Как я могу объединить эту информацию так, чтобы корневой объект мог быть передан в sync, и он может пересекать графики вниз? Моя первоначальная мысль заключалась в том, чтобы включить все аргументы в класс, который имел бы дочернее свойство (a ResizeArray того же типа). Но с различными свойствами, имеющими разные типы, я не мог найти способ заставить его работать, не выбрасывая типы из окна и делая большинство или все аргументы типа obj.

Итак, вот мои вопросы:

  • Есть ли устоявшийся метод для этого уже (я ничего не смог найти)
  • Какую структуру данных я могу использовать для инкапсуляции данных, необходимых для выполнения этой работы?

Я старался изо всех сил объяснить это, но если что-то остается неясным, спросите, и я постараюсь предоставить лучшую информацию.

4b9b3361

Ответ 1

Я уверен, что это упрощает его, но здесь моя идея.

Если это DAG, вы можете выполнить обход objA в ширину. Когда вы вставляете node из objA, включаете objB и любую другую необходимую вам информацию (кортеж). Затем, когда вы удаляете ключ, вы устанавливаете objB.

Вы можете использовать дискриминированный союз для обработки разных типов дочерних элементов в очереди.

Ответ 2

Создайте diffgrams из двух структур данных и преобразуйте преобразования в преобразованную проблему.