-
Notifications
You must be signed in to change notification settings - Fork 1
/
blossom.cljc
134 lines (101 loc) · 3.15 KB
/
blossom.cljc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
(ns blossom.blossom
(:require [blossom.constants :as c]
[blossom.context]
[blossom.utils :as u]
[ageneau.utils.core :as utils]))
(defprotocol PBlossom
(set-in-blossom [this v b])
(in-blossom [this v])
(set-parent [this child parent])
(remove-parent [this b])
(parent [this b])
(childs [this b])
(child [this b n]
"Get child for blossom b at index n, wrapping negative indices if necessary.")
(childs-find [this b t])
(childs-count [this b])
(set-childs [this b childs])
(childs-clear [this b])
(set-base [this b v])
(base-clear [this b])
(base [this b])
(set-endps [this b node-list])
(endps-clear [this b])
(endps [this b])
(endpoint [this b n]
"Get endpoint for blossom b at index n, wrapping negative indices if necessary.")
(unused-add [this b])
(unused-peek [this])
(unused-pop [this])
(trivial-blossom? [this b])
(leaves [this b])
(rotate-childs [this b i]
"Rotate the list of sub-blossoms to put the new base at the front.")
(blossom-range [this])
(vertex-range [this]))
(extend-type blossom.context.Context
PBlossom
(set-in-blossom [this v b]
(update this :in-blossom assoc v b))
(in-blossom [this v]
(nth (:in-blossom this) v))
(set-parent [this child parent]
(update this :blossom-parent assoc child parent))
(remove-parent [this b]
(set-parent this b c/NO-NODE))
(parent [this b]
(nth (:blossom-parent this) b))
(childs [this b]
(nth (:blossom-childs this) b))
(child [this b n]
(u/wget (childs this b) n))
(childs-find [this b t]
(first (utils/positions #{t} (childs this b))))
(childs-count [this b]
(count (childs this b)))
(set-childs [this b childs]
(update this :blossom-childs assoc b (vec childs)))
(childs-clear [this b]
(update this :blossom-childs update b empty))
(set-base [this b v]
(update this :blossom-base assoc b v))
(base-clear [this b]
(set-base this b c/NO-NODE))
(base [this b]
(nth (:blossom-base this) b))
(set-endps [this b node-list]
(update this :blossom-endps assoc b (vec node-list)))
(endps-clear [this b]
(update this :blossom-endps update b empty))
(endps [this b]
(nth (:blossom-endps this) b))
(endpoint [this b n]
(u/wget (endps this b) n))
(unused-add [this b]
(update this :unused-blossoms conj b))
(unused-peek [this]
(peek (:unused-blossoms this)))
(unused-pop [this]
(update this :unused-blossoms pop))
(trivial-blossom? [this b]
(< b (:nvertex this)))
(leaves
[this b]
(if-not (trivial-blossom? this b)
(flatten (for [child (childs this b)]
(if-not (trivial-blossom? this child)
(leaves this child)
child)))
[b]))
(rotate-childs
[this b i]
(let [childs (utils/split-and-reverse (childs this b) i)
endps (utils/split-and-reverse (endps this b) i)]
(-> this
(set-childs b childs)
(set-endps b endps)
(set-base b (base this (first childs))))))
(blossom-range [this]
(range (:nvertex this) (* 2 (:nvertex this))))
(vertex-range [this]
(range (:nvertex this))))