/**
* Random Tree Model traversal and recall mechanisms
* Implements working memory constraints and hierarchical summarization
* @module core/rtm-traversal
*/
import {
RandomTree,
RTMNode,
TraversalResult,
Clause
} from '../types/rtm.js';
/**
* Traverses a Random Tree to simulate recall at different abstraction levels
*/
export class RTMTraversal {
constructor(
private tree: RandomTree,
private clauseMap: Map<string, Clause>
) {}
/**
* Traverse the tree to a specific depth, respecting working memory constraints
* @param maxDepth - Maximum depth to traverse (D parameter)
* @returns Traversal result with nodes at the target depth
*/
traverseToDepth(maxDepth: number): TraversalResult {
const rootNode = this.tree.nodes.get(this.tree.rootNodeId);
if (!rootNode) {
throw new Error('Invalid tree: root node not found');
}
const nodesAtDepth: RTMNode[] = [];
const visited = new Set<string>();
// Breadth-first traversal to target depth
this.collectNodesAtDepth(rootNode, 0, maxDepth, nodesAtDepth, visited);
// Calculate aggregate statistics
const totalClauses = nodesAtDepth.reduce(
(sum, node) => sum + node.clauses.length,
0
);
const avgCompressionRatio = nodesAtDepth.length > 0
? nodesAtDepth.reduce((sum, node) => sum + node.compressionRatio, 0) / nodesAtDepth.length
: 0;
// Generate summaries for each node
const summaries = nodesAtDepth.map(node => this.generateNodeSummary(node));
return {
depth: maxDepth,
nodes: nodesAtDepth,
totalClauses,
compressionRatio: avgCompressionRatio,
summary: summaries
};
}
/**
* Collect all nodes at a specific depth
* @param node - Current node
* @param currentDepth - Current depth in traversal
* @param targetDepth - Target depth to collect
* @param collector - Array to collect nodes
* @param visited - Set of visited node IDs
*/
private collectNodesAtDepth(
node: RTMNode,
currentDepth: number,
targetDepth: number,
collector: RTMNode[],
visited: Set<string>
): void {
if (visited.has(node.id)) return;
visited.add(node.id);
if (currentDepth === targetDepth || node.children.length === 0) {
// We've reached target depth or a leaf node
collector.push(node);
return;
}
// Continue traversal to children
for (const childId of node.children) {
const childNode = this.tree.nodes.get(childId);
if (childNode) {
this.collectNodesAtDepth(
childNode,
currentDepth + 1,
targetDepth,
collector,
visited
);
}
}
}
/**
* Generate a summary for a node
* @param node - Node to summarize
* @returns Summary text
*/
private generateNodeSummary(node: RTMNode): string {
if (node.summary) return node.summary;
// Generate summary from clauses
const clauseTexts = node.clauses
.slice(0, Math.min(3, node.clauses.length))
.map(id => this.clauseMap.get(id)?.text || '')
.filter(text => text.length > 0);
if (clauseTexts.length === 0) return '[Empty node]';
const summary = clauseTexts.join(' ');
return summary.length > 100
? summary.substring(0, 97) + '...'
: summary;
}
/**
* Simulate recall with working memory constraints
* Returns the sequence of recalled items in order
* @param maxDepth - Maximum recall depth (D parameter)
* @returns Array of recalled summaries in sequential order
*/
simulateRecall(maxDepth: number): string[] {
const rootNode = this.tree.nodes.get(this.tree.rootNodeId);
if (!rootNode) return [];
const recallSequence: string[] = [];
this.recursiveRecall(rootNode, 0, maxDepth, recallSequence);
return recallSequence;
}
/**
* Recursively generate recall sequence
* @param node - Current node
* @param currentDepth - Current depth
* @param maxDepth - Maximum depth
* @param sequence - Recall sequence collector
*/
private recursiveRecall(
node: RTMNode,
currentDepth: number,
maxDepth: number,
sequence: string[]
): void {
// Add current node's summary to recall
sequence.push(this.generateNodeSummary(node));
// Stop if we've reached max depth or leaf node
if (currentDepth >= maxDepth || node.children.length === 0) {
return;
}
// Recall children in order
for (const childId of node.children) {
const childNode = this.tree.nodes.get(childId);
if (childNode) {
this.recursiveRecall(childNode, currentDepth + 1, maxDepth, sequence);
}
}
}
/**
* Find the optimal traversal depth for a target recall length
* Binary search for the depth that yields closest to target length
* @param targetLength - Desired recall length
* @returns Optimal depth
*/
findOptimalDepth(targetLength: number): number {
let low = 1;
let high = this.tree.parameters.maxRecallDepth;
let bestDepth = 1;
let bestDiff = Infinity;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const result = this.traverseToDepth(mid);
const diff = Math.abs(result.totalClauses - targetLength);
if (diff < bestDiff) {
bestDiff = diff;
bestDepth = mid;
}
if (result.totalClauses < targetLength) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return bestDepth;
}
/**
* Get statistics about the tree structure
* @returns Tree statistics
*/
getTreeStatistics(): {
totalNodes: number;
maxDepth: number;
avgBranchingFactor: number;
leafNodes: number;
compressionProfile: Map<number, number>;
} {
const nodes = Array.from(this.tree.nodes.values());
const leafNodes = nodes.filter(n => n.children.length === 0);
// Calculate max depth
let maxDepth = 0;
nodes.forEach(node => {
maxDepth = Math.max(maxDepth, node.level);
});
// Calculate average branching factor
const nodesWithChildren = nodes.filter(n => n.children.length > 0);
const avgBranchingFactor = nodesWithChildren.length > 0
? nodesWithChildren.reduce((sum, n) => sum + n.children.length, 0) / nodesWithChildren.length
: 0;
// Compression profile by level
const compressionProfile = new Map<number, number>();
nodes.forEach(node => {
const currentAvg = compressionProfile.get(node.level) || 0;
const currentCount = nodes.filter(n => n.level === node.level).length;
compressionProfile.set(
node.level,
(currentAvg * (currentCount - 1) + node.compressionRatio) / currentCount
);
});
return {
totalNodes: nodes.length,
maxDepth,
avgBranchingFactor,
leafNodes: leafNodes.length,
compressionProfile
};
}
}
/**
* Create a traversal instance for a tree
* @param tree - Random tree to traverse
* @param clauses - Map of clause IDs to clause objects
* @returns Traversal instance
*/
export function createTraversal(
tree: RandomTree,
clauses: Map<string, Clause>
): RTMTraversal {
return new RTMTraversal(tree, clauses);
}