Debian Codegraph @

lib/util/temporal-relation.scm

raw
1 ;;;
2 ;;; Temporal relations
3 ;;;
4 ;;; Copyright (c) 2022-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; This module detemines relations between two temporal intervals,
35 ;; one temporal interval and one time point, or two time points.
36 ;; This module doesn't assume a particular representation of temporal
37 ;; intervals or timepoints.
38
39 ;; This is inspired by Haskell Rampart library.
40 ;; https://hackage.haskell.org/package/rampart-2.0.0.0/docs/Rampart.html
41
42 (define-module util.temporal-relation
43 (use srfi.114 :only (if3))
44 (export make-interval-protocol
45 pair-interval-protocol
46 relation?
47 inverse
48 relate
49 relate-point
50 ))
51 (select-module util.temporal-relation)
52
53 ;; Anything that conforms given interval protocol can be used as
54 ;; an interval.
55 ;; greater I - returns greater point of I
56 ;; lesser I - returns lesser point of I
57 ;; compare P1, P2 - compare two points P1 and P2, returns negative/0/positive
58 ;; real numbers.
59
60 (define-class <interval-protocol> ()
61 ((%lesser :init-keyword :lesser)
62 (%greater :init-keyword :greater)
63 (%compare :init-keyword :compare)))
64
65 (define (make-interval-protocol lesser greater :optional (cmp compare))
66 (make <interval-protocol>
67 :lesser lesser
68 :greater greater
69 :compare cmp))
70
71 (define-inline pair-interval-protocol
72 (make-interval-protocol car cdr))
73
74
75 ;; Interval relations
76 (define (relation? sym)
77 (boolean (memq sym '(before
78 meets
79 overlaps
80 finished-by
81 contains
82 starts
83 equal
84 started-by
85 during
86 finishes
87 overlapped-by
88 met-by
89 after))))
90
91 (define (inverse sym)
92 (ecase sym
93 [(before) 'after]
94 [(meets) 'met-by]
95 [(overlaps) 'overlapped-by]
96 [(finished-by) 'finishes]
97 [(contains) 'during]
98 [(starts) 'started-by]
99 [(equal) 'equal]
100 [(started-by) 'starts]
101 [(during) 'contains]
102 [(finishes) 'finished-by]
103 [(overlapped-by)'overlaps]
104 [(met-by) 'meets]
105 [(after) 'before]))
106
107 (define (relate protocol int-x int-y)
108 (let ([xl ((~ protocol'%lesser) int-x)]
109 [xg ((~ protocol'%greater) int-x)]
110 [yl ((~ protocol'%lesser) int-y)]
111 [yg ((~ protocol'%greater) int-y)]
112 [cmp (~ protocol'%compare)])
113 (if3 (cmp xl yl)
114 (if3 (cmp xg yl)
115 'before
116 'meets
117 (if3 (cmp xg yg)
118 'overlaps
119 'finished-by
120 'contains))
121 (if3 (cmp xg yg)
122 'starts
123 'equal
124 'started-by)
125 (if3 (cmp xl yg)
126 (if3 (cmp xg yg)
127 'during
128 'finishes
129 'overlapped-by)
130 'met-by
131 'after))))
132
133 (define (relate-point protocol int point)
134 (let ([l ((~ protocol'%lesser) int)]
135 [g ((~ protocol'%greater) int)]
136 [cmp (~ protocol'%compare)])
137 (if3 (cmp g point)
138 'before
139 'finished-by
140 (if3 (cmp l point)
141 'contains
142 'started-by
143 'after))))