X-Git-Url: https://dreyeck.freedombox.rocks/gitweb/topic-maps.git/blobdiff_plain/f24ac27e1e1cc0118411b058d40af3c1c87f3ffb..refs/heads/codex/project-work-slice-22u:/src/tmdm/associations.lisp?ds=inline diff --git a/src/tmdm/associations.lisp b/src/tmdm/associations.lisp index 92ca702..11905a2 100644 --- a/src/tmdm/associations.lisp +++ b/src/tmdm/associations.lisp @@ -6,14 +6,16 @@ (defun normalize-roles (association) ;; TMDM 5.8/6.7: shared parent; identifiers are metadata, not equality keys. - (loop for pair = (equal-pair (%association-roles association) #'same-role-signature-p) + (loop for parent = (canonical-association association) + for pair = (equal-pair (%association-roles parent) #'same-role-signature-p) while pair do (let* ((a (first pair)) (b (second pair)) - (c (%make-association-role association (%association-role-type a) (%association-role-player a)))) + (c (%make-association-role parent (%association-role-type a) (%association-role-player a)))) (setf (%association-role-item-identifiers c) (set-union (%association-role-item-identifiers a) (%association-role-item-identifiers b) #'string=) - (%association-roles association) (replace-pair (%association-roles association) a b c) - (%association-role-forward a) c (%association-role-forward b) c)))) + (%association-roles parent) (replace-pair (%association-roles parent) a b c) + (%association-role-forward a) c (%association-role-forward b) c) + (merge-item-reifiers c a b)))) (defun equal-associations-p (a b) ;; TMDM 5.7: compare role sets structurally, independent of role ordering. @@ -37,11 +39,51 @@ (%association-forward a) c (%association-forward b) c) (dolist (role (%association-roles c)) (setf (%association-role-parent role) c)) (normalize-roles c) - c)) + (merge-item-reifiers c a b))) + +(defun scan-next-association-merge (map) + "The pair of Associations to merge next, found by comparing Associations pairwise: the first Association with a +later equal one, and the first such later one, in map order; NIL if none. This is the search that defines the +choice; NEXT-ASSOCIATION-MERGE returns the same pair." + (equal-pair (%topic-map-associations map) #'equal-associations-p)) + +(defun next-association-merge (map) + "The pair SCAN-NEXT-ASSOCIATION-MERGE returns, found through an index built for this one search and dropped with it. +When no Association holds two Roles of one signature and no Scope repeats a theme, EQUAL-ASSOCIATIONS-P holds exactly +when the two Associations have the EQ type, the same Scope set and the same set of Role signatures: equal Role counts +and inclusion of duplicate-free sets make the sets equal. Those three are the key, built from the stored references +as EQUAL-ASSOCIATIONS-P compares them (EQ, never resolved to a representative). The relation is then an equivalence and +has no side effect, so the first Association with a later key-sharer, and its first such sharer, are what the pairwise +search finds. With a repeated Role signature the relation is not symmetric; then, and with a repeated theme, the +pairwise search itself runs. The index is never kept: a merge, a Role merge or a Reifier cascade can change any +type, player, theme and the list itself before the next search." + (let ((associations (%topic-map-associations map))) + (unless (every (lambda (a) + (and (null (equal-pair (%association-roles a) #'same-role-signature-p)) + (let ((scope (%association-scope a))) + (= (length scope) (length (remove-duplicates scope :test #'eq)))))) + associations) + (return-from next-association-merge (scan-next-association-merge map))) + (let ((ids (make-hash-table :test #'eq)) (next 0) (sharers (make-hash-table :test #'equal))) + (flet ((id (object) (or (gethash object ids) (setf (gethash object ids) (incf next)))) + (signature< (x y) (or (< (car x) (car y)) (and (= (car x) (car y)) (< (cdr x) (cdr y)))))) + (let ((keys (mapcar (lambda (a) + (list (id (%association-type a)) + (sort (mapcar #'id (%association-scope a)) #'<) + (sort (mapcar (lambda (role) (cons (id (%association-role-type role)) + (id (%association-role-player role)))) + (%association-roles a)) + #'signature<))) + associations))) + ;; Each key lists its Associations in map order. + (loop for a in (reverse associations) for key in (reverse keys) do (push a (gethash key sharers))) + (loop for a in associations for key in keys + for later = (second (member a (gethash key sharers) :test #'eq)) + when later return (list a later))))))) (defun normalize-associations (map) (dolist (association (%topic-map-associations map)) (normalize-roles association)) - (loop for pair = (equal-pair (%topic-map-associations map) #'equal-associations-p) + (loop for pair = (next-association-merge map) while pair do (merge-two-associations map (first pair) (second pair))) map)