1use std::collections::HashMap;
2
3use kcode_k1_kmap_format::ConnectionTier;
4pub use kcode_k1_kmap_format::{Node, NodeId};
5
6mod selection;
7
8pub const PREVIEW_COST: f64 = 0.3;
9pub const NARRATIVE_COST: f64 = 1.0;
10pub const DEPTH_DECAY: f64 = 0.7;
11
12const PREVIEW_TENTHS: u64 = 3;
13const NARRATIVE_TENTHS: u64 = 10;
14
15#[derive(Clone, Debug, PartialEq)]
16pub struct LoadedNode {
17 pub node_id: NodeId,
18 pub title: String,
19 pub navigation_hint: String,
20 pub narrative: Option<String>,
21}
22
23#[derive(Clone, Debug, PartialEq)]
24pub struct OpenResult {
25 pub nodes: Vec<LoadedNode>,
26 pub automatic_attention_spent: f64,
27}
28
29#[derive(Clone, Copy, Debug, Eq, PartialEq)]
30pub enum OpenMode {
31 Full,
32 NavigationOnly,
33}
34
35pub fn open_node<L, A>(
36 node_id: NodeId,
37 budget: f64,
38 temperature: f64,
39 mode: OpenMode,
40 load_node: L,
41 access_filter: A,
42) -> Result<OpenResult, String>
43where
44 L: FnMut(NodeId) -> Result<Option<Node>, String>,
45 A: FnMut(NodeId) -> bool,
46{
47 open_node_with_random(
48 node_id,
49 budget,
50 temperature,
51 mode,
52 load_node,
53 access_filter,
54 selection::os_random_unit,
55 )
56}
57
58fn open_node_with_random<L, A, R>(
59 node_id: NodeId,
60 budget: f64,
61 temperature: f64,
62 mode: OpenMode,
63 load_node: L,
64 access_filter: A,
65 random: R,
66) -> Result<OpenResult, String>
67where
68 L: FnMut(NodeId) -> Result<Option<Node>, String>,
69 A: FnMut(NodeId) -> bool,
70 R: FnMut() -> Result<f64, String>,
71{
72 if !budget.is_finite() || budget < 0.0 {
73 return Err("budget must be finite and nonnegative".to_owned());
74 }
75 if !temperature.is_finite() || temperature < 0.0 {
76 return Err("temperature must be finite and nonnegative".to_owned());
77 }
78 let mut engine = Engine {
79 budget,
80 temperature,
81 load_node,
82 access_filter,
83 random,
84 decisions: HashMap::new(),
85 };
86 let root = engine.required(node_id)?;
87 match mode {
88 OpenMode::Full => engine.full(node_id, root),
89 OpenMode::NavigationOnly => engine.navigation_only(node_id, root),
90 }
91}
92
93struct Engine<L, A, R> {
94 budget: f64,
95 temperature: f64,
96 load_node: L,
97 access_filter: A,
98 random: R,
99 decisions: HashMap<NodeId, bool>,
100}
101
102impl<L, A, R> Engine<L, A, R>
103where
104 L: FnMut(NodeId) -> Result<Option<Node>, String>,
105 A: FnMut(NodeId) -> bool,
106 R: FnMut() -> Result<f64, String>,
107{
108 fn full(&mut self, node_id: NodeId, root: Node) -> Result<OpenResult, String> {
109 let mut outputs = vec![loaded(node_id, &root, true)];
110 let mut states = HashMap::from([(node_id, NodeState::Opened)]);
111 let mut frontier = Vec::new();
112 let mut spent = 0_u64;
113
114 for connection in &root.connections {
115 let target = connection.target;
116 if matches!(states.get(&target), Some(NodeState::Opened)) || !self.allowed(target) {
117 continue;
118 }
119 if connection.tier == ConnectionTier::Navigation && !states.contains_key(&target) {
120 let node = self.required(target)?;
121 insert_preview(target, node, &mut outputs, &mut states);
122 }
123 frontier.push(Occurrence::new(target, connection.weight.value, 1));
124 }
125
126 loop {
127 let mut candidates = Vec::new();
128 let mut opening_costs = HashMap::new();
129 for (index, occurrence) in frontier.iter().enumerate() {
130 if matches!(states.get(&occurrence.target), Some(NodeState::Opened)) {
131 continue;
132 }
133 let effective = selection::score(occurrence);
134 if !effective.is_finite() || effective <= 0.0 {
135 continue;
136 }
137 let cost = match states.get(&occurrence.target) {
138 None => PREVIEW_TENTHS,
139 Some(NodeState::Previewed(node)) => {
140 if let Some(cost) = opening_costs.get(&occurrence.target) {
141 *cost
142 } else {
143 let previews = self.navigation_targets(node, &states, None).len();
144 let cost = opening_cost(previews)?;
145 let _ = opening_costs.insert(occurrence.target, cost);
146 cost
147 }
148 }
149 Some(NodeState::Opened) => continue,
150 };
151 if affordable(spent, cost, self.budget)? {
152 candidates.push((index, effective, cost));
153 }
154 }
155 if candidates.is_empty() {
156 break;
157 }
158
159 let choice = selection::choose(&candidates, self.temperature, &mut self.random)?;
160 let (selected, _, cost) = candidates[choice];
161 let occurrence = frontier[selected].clone();
162 match states.get(&occurrence.target).cloned() {
163 None => {
164 let node = self.required(occurrence.target)?;
165 insert_preview(occurrence.target, node, &mut outputs, &mut states);
166 }
167 Some(NodeState::Previewed(node)) => {
168 let guarantees = self.navigation_targets(&node, &states, None);
169 let _ = states.insert(occurrence.target, NodeState::Opened);
170 let output = outputs
171 .iter_mut()
172 .find(|node| node.node_id == occurrence.target)
173 .ok_or_else(|| "previewed Kmap node had no output".to_owned())?;
174 output.narrative = Some(node.narrative.clone());
175 frontier.retain(|entry| entry.target != occurrence.target);
176 for target in guarantees {
177 let guaranteed = self.required(target)?;
178 insert_preview(target, guaranteed, &mut outputs, &mut states);
179 }
180 let depth = increment_depth(occurrence.depth)?;
181 frontier.extend(self.outgoing(&node, depth, &states));
182 }
183 Some(NodeState::Opened) => {
184 return Err("opened Kmap node remained selectable".to_owned());
185 }
186 }
187 spent = attention(spent.checked_add(cost))?;
188 }
189 Ok(result(outputs, spent))
190 }
191
192 fn navigation_only(&mut self, node_id: NodeId, root: Node) -> Result<OpenResult, String> {
193 let mut outputs = vec![loaded(node_id, &root, false)];
194 let mut states = HashMap::from([(node_id, NodeState::Opened)]);
195 let root_targets = self.navigation_targets(&root, &states, None);
196 let root_cost = preview_cost(root_targets.len())?;
197 if !affordable(0, root_cost, self.budget)? {
198 return Ok(result(outputs, 0));
199 }
200 let mut root_nodes = Vec::with_capacity(root_targets.len());
201 for target in root_targets {
202 root_nodes.push((target, self.required(target)?));
203 }
204 for (target, node) in &root_nodes {
205 outputs.push(loaded(*target, node, false));
206 let _ = states.insert(*target, NodeState::Opened);
207 }
208
209 let mut spent = root_cost;
210 let mut frontier = self.outgoing(&root, 1, &states);
211 for (_, node) in &root_nodes {
212 frontier.extend(self.outgoing(node, 2, &states));
213 }
214 loop {
215 let mut candidates = Vec::new();
216 for (index, occurrence) in frontier.iter().enumerate() {
217 if states.contains_key(&occurrence.target) {
218 continue;
219 }
220 let effective = selection::score(occurrence);
221 if effective.is_finite() && effective > 0.0 {
222 candidates.push((index, effective, 0));
223 }
224 }
225 if candidates.is_empty() {
226 break;
227 }
228
229 let choice = selection::choose(&candidates, self.temperature, &mut self.random)?;
230 let (selected, _, _) = candidates[choice];
231 let occurrence = frontier[selected].clone();
232 let node = self.required(occurrence.target)?;
233 let children = self.navigation_targets(&node, &states, Some(occurrence.target));
234 let count = attention(children.len().checked_add(1))?;
235 let cost = preview_cost(count)?;
236 if !affordable(spent, cost, self.budget)? {
237 break;
238 }
239 let next_depth = increment_depth(occurrence.depth)?;
240 let new_spent = attention(spent.checked_add(cost))?;
241 let mut child_nodes = Vec::with_capacity(children.len());
242 for target in children {
243 child_nodes.push((target, self.required(target)?));
244 }
245
246 let _ = states.insert(occurrence.target, NodeState::Opened);
247 for (target, _) in &child_nodes {
248 let _ = states.insert(*target, NodeState::Opened);
249 }
250 let mut additions = self.outgoing(&node, next_depth, &states);
251 for (_, child) in &child_nodes {
252 let child_depth = increment_depth(next_depth)?;
253 additions.extend(self.outgoing(child, child_depth, &states));
254 }
255 outputs.push(loaded(occurrence.target, &node, false));
256 for (target, child) in &child_nodes {
257 outputs.push(loaded(*target, child, false));
258 }
259 frontier.retain(|entry| !states.contains_key(&entry.target));
260 frontier.extend(additions);
261 spent = new_spent;
262 }
263 Ok(result(outputs, spent))
264 }
265
266 fn required(&mut self, node_id: NodeId) -> Result<Node, String> {
267 (self.load_node)(node_id)?
268 .ok_or_else(|| format!("authorized Kmap target {node_id:?} is missing"))
269 }
270
271 fn allowed(&mut self, node_id: NodeId) -> bool {
272 let access_filter = &mut self.access_filter;
273 *self
274 .decisions
275 .entry(node_id)
276 .or_insert_with(|| access_filter(node_id))
277 }
278
279 fn navigation_targets(
280 &mut self,
281 node: &Node,
282 states: &HashMap<NodeId, NodeState>,
283 planned: Option<NodeId>,
284 ) -> Vec<NodeId> {
285 let mut targets = Vec::new();
286 for connection in &node.connections {
287 let target = connection.target;
288 if states.contains_key(&target) || planned == Some(target) || !self.allowed(target) {
289 continue;
290 }
291 if connection.tier == ConnectionTier::Navigation && !targets.contains(&target) {
292 targets.push(target);
293 }
294 }
295 targets
296 }
297
298 fn outgoing(
299 &mut self,
300 node: &Node,
301 depth: usize,
302 states: &HashMap<NodeId, NodeState>,
303 ) -> Vec<Occurrence> {
304 let mut entries = Vec::new();
305 for connection in &node.connections {
306 let target = connection.target;
307 if matches!(states.get(&target), Some(NodeState::Opened)) || !self.allowed(target) {
308 continue;
309 }
310 entries.push(Occurrence::new(target, connection.weight.value, depth));
311 }
312 entries
313 }
314}
315
316#[derive(Clone)]
317enum NodeState {
318 Previewed(Node),
319 Opened,
320}
321
322#[derive(Clone)]
323struct Occurrence {
324 target: NodeId,
325 value: f64,
326 depth: usize,
327}
328
329impl Occurrence {
330 fn new(target: NodeId, value: f64, depth: usize) -> Self {
331 Self {
332 target,
333 value,
334 depth,
335 }
336 }
337}
338
339fn loaded(node_id: NodeId, node: &Node, opened: bool) -> LoadedNode {
340 LoadedNode {
341 node_id,
342 title: node.title.clone(),
343 navigation_hint: node.navigation_hint.clone(),
344 narrative: opened.then(|| node.narrative.clone()),
345 }
346}
347
348fn insert_preview(
349 node_id: NodeId,
350 node: Node,
351 outputs: &mut Vec<LoadedNode>,
352 states: &mut HashMap<NodeId, NodeState>,
353) {
354 if states.contains_key(&node_id) {
355 return;
356 }
357 outputs.push(loaded(node_id, &node, false));
358 let _ = states.insert(node_id, NodeState::Previewed(node));
359}
360
361fn result(nodes: Vec<LoadedNode>, spent: u64) -> OpenResult {
362 OpenResult {
363 nodes,
364 automatic_attention_spent: spent as f64 / 10.0,
365 }
366}
367
368fn opening_cost(previews: usize) -> Result<u64, String> {
369 attention(preview_cost(previews)?.checked_add(NARRATIVE_TENTHS))
370}
371
372fn increment_depth(depth: usize) -> Result<usize, String> {
373 depth
374 .checked_add(1)
375 .ok_or_else(|| "Kmap traversal depth overflow".to_owned())
376}
377
378fn attention<T>(value: Option<T>) -> Result<T, String> {
379 value.ok_or_else(|| "Kmap attention cost overflow".to_owned())
380}
381
382fn preview_cost(count: usize) -> Result<u64, String> {
383 let count = attention(u64::try_from(count).ok())?;
384 attention(count.checked_mul(PREVIEW_TENTHS))
385}
386
387fn affordable(spent: u64, cost: u64, budget: f64) -> Result<bool, String> {
388 let total = attention(spent.checked_add(cost))? as f64 / 10.0;
389 let tolerance = 8.0 * f64::EPSILON * total.abs().max(budget.abs()).max(1.0);
390 Ok(total <= budget || total - budget <= tolerance)
391}