]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - src/tmdm/associations.lisp
feat(tmdm): readers for the TMDM 7.2/7.3 relationships; tests for both default name...
[topic-maps.git] / src / tmdm / associations.lisp
1 (in-package #:topic-maps.tmdm)
2
3 (defun same-role-signature-p (a b)
4 (and (eq (%association-role-type a) (%association-role-type b))
5 (eq (%association-role-player a) (%association-role-player b))))
6
7 (defun normalize-roles (association)
8 ;; TMDM 5.8/6.7: shared parent; identifiers are metadata, not equality keys.
9 (loop for parent = (canonical-association association)
10 for pair = (equal-pair (%association-roles parent) #'same-role-signature-p)
11 while pair do
12 (let* ((a (first pair)) (b (second pair))
13 (c (%make-association-role parent (%association-role-type a) (%association-role-player a))))
14 (setf (%association-role-item-identifiers c)
15 (set-union (%association-role-item-identifiers a) (%association-role-item-identifiers b) #'string=)
16 (%association-roles parent) (replace-pair (%association-roles parent) a b c)
17 (%association-role-forward a) c (%association-role-forward b) c)
18 (merge-item-reifiers c a b))))
19
20 (defun equal-associations-p (a b)
21 ;; TMDM 5.7: compare role sets structurally, independent of role ordering.
22 ;; Role parents are the associations being compared (the equality cycle).
23 ;; Scope sets are significant; identifiers do not participate in equality.
24 (and (eq (%association-type a) (%association-type b))
25 (same-scope-p (%association-scope a) (%association-scope b))
26 (= (length (%association-roles a)) (length (%association-roles b)))
27 (every (lambda (role) (find role (%association-roles b) :test #'same-role-signature-p))
28 (%association-roles a))))
29
30 (defun merge-two-associations (map a b)
31 ;; TMDM 6.6/6.7: retarget both equal role sets to C, then merge corresponding
32 ;; Roles. This preserves their identifiers AND every retained role handle.
33 (let ((c (%make-association map (%association-type a))))
34 (setf (%association-scope c) (copy-list (%association-scope a))
35 (%association-item-identifiers c)
36 (set-union (%association-item-identifiers a) (%association-item-identifiers b) #'string=)
37 (%association-roles c) (set-union (%association-roles a) (%association-roles b) #'eq)
38 (%topic-map-associations map) (replace-pair (%topic-map-associations map) a b c)
39 (%association-forward a) c (%association-forward b) c)
40 (dolist (role (%association-roles c)) (setf (%association-role-parent role) c))
41 (normalize-roles c)
42 (merge-item-reifiers c a b)))
43
44 (defun scan-next-association-merge (map)
45 "The pair of Associations to merge next, found by comparing Associations pairwise: the first Association with a
46 later equal one, and the first such later one, in map order; NIL if none. This is the search that defines the
47 choice; NEXT-ASSOCIATION-MERGE returns the same pair."
48 (equal-pair (%topic-map-associations map) #'equal-associations-p))
49
50 (defun next-association-merge (map)
51 "The pair SCAN-NEXT-ASSOCIATION-MERGE returns, found through an index built for this one search and dropped with it.
52 When no Association holds two Roles of one signature and no Scope repeats a theme, EQUAL-ASSOCIATIONS-P holds exactly
53 when the two Associations have the EQ type, the same Scope set and the same set of Role signatures: equal Role counts
54 and inclusion of duplicate-free sets make the sets equal. Those three are the key, built from the stored references
55 as EQUAL-ASSOCIATIONS-P compares them (EQ, never resolved to a representative). The relation is then an equivalence and
56 has no side effect, so the first Association with a later key-sharer, and its first such sharer, are what the pairwise
57 search finds. With a repeated Role signature the relation is not symmetric; then, and with a repeated theme, the
58 pairwise search itself runs. The index is never kept: a merge, a Role merge or a Reifier cascade can change any
59 type, player, theme and the list itself before the next search."
60 (let ((associations (%topic-map-associations map)))
61 (unless (every (lambda (a)
62 (and (null (equal-pair (%association-roles a) #'same-role-signature-p))
63 (let ((scope (%association-scope a)))
64 (= (length scope) (length (remove-duplicates scope :test #'eq))))))
65 associations)
66 (return-from next-association-merge (scan-next-association-merge map)))
67 (let ((ids (make-hash-table :test #'eq)) (next 0) (sharers (make-hash-table :test #'equal)))
68 (flet ((id (object) (or (gethash object ids) (setf (gethash object ids) (incf next))))
69 (signature< (x y) (or (< (car x) (car y)) (and (= (car x) (car y)) (< (cdr x) (cdr y))))))
70 (let ((keys (mapcar (lambda (a)
71 (list (id (%association-type a))
72 (sort (mapcar #'id (%association-scope a)) #'<)
73 (sort (mapcar (lambda (role) (cons (id (%association-role-type role))
74 (id (%association-role-player role))))
75 (%association-roles a))
76 #'signature<)))
77 associations)))
78 ;; Each key lists its Associations in map order.
79 (loop for a in (reverse associations) for key in (reverse keys) do (push a (gethash key sharers)))
80 (loop for a in associations for key in keys
81 for later = (second (member a (gethash key sharers) :test #'eq))
82 when later return (list a later)))))))
83
84 (defun normalize-associations (map)
85 (dolist (association (%topic-map-associations map)) (normalize-roles association))
86 (loop for pair = (next-association-merge map)
87 while pair do (merge-two-associations map (first pair) (second pair)))
88 map)
89
90 (defun make-association (map type roles &key scope)
91 "Create a same-map Association with a Scope Topic set. ROLES is a nonempty list of (TYPE PLAYER).
92 All references are validated before mutation and resolved to live Topics.
93 Return its current representative after duplicate normalization."
94 (check-type map topic-map)
95 (let ((type (live-topic type)) (scope (canonical-scope map scope)))
96 (unless (eq map (%topic-parent type)) (error "Association type belongs to another map."))
97 (unless (and (proper-list-p roles) roles) (error "An Association requires at least one Role."))
98 (let ((references
99 (mapcar (lambda (pair)
100 (unless (and (proper-list-p pair) (= 2 (length pair)))
101 (error "Each Role requires a type and a player."))
102 (let ((type (live-topic (first pair))) (player (live-topic (second pair))))
103 (unless (and (eq map (%topic-parent type)) (eq map (%topic-parent player)))
104 (error "Role type and player must belong to the Association's map."))
105 (list type player))) roles)))
106 (let ((association (%make-association map type)))
107 (setf (%association-scope association) scope
108 (%association-roles association)
109 (mapcar (lambda (pair) (%make-association-role association (first pair) (second pair))) references)
110 (%topic-map-associations map) (append (%topic-map-associations map) (list association)))
111 (normalize-associations map)
112 (canonical-association association)))))