Line data Source code
1 : /**
2 : * Spatial Index Manager
3 : *
4 : * Manages spatial indexing for efficient node queries based on bounds.
5 : * Uses QuadTree for fast spatial lookups with caching for performance.
6 : */
7 : import {
8 : PERFORMANCE_CONFIG,
9 : QUADTREE_CONFIG
10 : } from '@/renderer/core/layout/constants'
11 : import type { Bounds } from '@comfyorg/shared-frontend-utils/geometry'
12 : import type { NodeId } from '@/renderer/core/layout/types'
13 :
14 : import { QuadTree } from './QuadTree'
15 :
16 : /**
17 : * Cache entry for spatial queries
18 : */
19 : interface CacheEntry<TId> {
20 : result: TId[]
21 : timestamp: number
22 : }
23 :
24 : /**
25 : * Spatial index manager using QuadTree
26 : */
27 2356 : export class SpatialIndexManager<TId extends string | number = NodeId> {
28 : private quadTree: QuadTree<TId>
29 : private queryCache: Map<string, CacheEntry<TId>>
30 : private cacheSize = 0
31 :
32 : constructor(bounds?: Bounds) {
33 4712 : this.quadTree = new QuadTree<TId>(
34 : bounds ?? QUADTREE_CONFIG.DEFAULT_BOUNDS,
35 : {
36 : maxDepth: QUADTREE_CONFIG.MAX_DEPTH,
37 : maxItemsPerNode: QUADTREE_CONFIG.MAX_ITEMS_PER_NODE
38 : }
39 : )
40 4712 : this.queryCache = new Map()
41 : }
42 :
43 : /**
44 : * Insert a node into the spatial index
45 : */
46 : insert(nodeId: TId, bounds: Bounds): void {
47 41 : this.quadTree.insert(String(nodeId), bounds, nodeId)
48 41 : this.invalidateCache()
49 : }
50 :
51 : /**
52 : * Update a node's bounds in the spatial index
53 : */
54 : update(nodeId: TId, bounds: Bounds): void {
55 5 : this.quadTree.update(String(nodeId), bounds)
56 5 : this.invalidateCache()
57 : }
58 :
59 : /**
60 : * Batch update multiple nodes' bounds in the spatial index
61 : * More efficient than calling update() multiple times as it only invalidates cache once
62 : */
63 : batchUpdate(updates: Array<{ nodeId: TId; bounds: Bounds }>): void {
64 0 : for (const { nodeId, bounds } of updates) {
65 0 : this.quadTree.update(String(nodeId), bounds)
66 : }
67 0 : this.invalidateCache()
68 : }
69 :
70 : /**
71 : * Remove a node from the spatial index
72 : */
73 : remove(nodeId: TId): void {
74 16 : this.quadTree.remove(String(nodeId))
75 16 : this.invalidateCache()
76 : }
77 :
78 : /**
79 : * Query nodes within the given bounds
80 : */
81 : query(bounds: Bounds): TId[] {
82 851 : const cacheKey = this.getCacheKey(bounds)
83 851 : const cached = this.queryCache.get(cacheKey)
84 :
85 : // Check cache validity
86 851 : if (cached) {
87 : const age = Date.now() - cached.timestamp
88 307 : if (age < PERFORMANCE_CONFIG.SPATIAL_CACHE_TTL) {
89 302 : return cached.result
90 : }
91 : // Remove stale entry
92 5 : this.queryCache.delete(cacheKey)
93 5 : this.cacheSize--
94 : }
95 :
96 : // Perform query
97 549 : const result = this.quadTree.query(bounds)
98 :
99 : // Cache result
100 549 : this.addToCache(cacheKey, result)
101 :
102 549 : return result
103 : }
104 :
105 : /**
106 : * Clear all nodes from the spatial index
107 : */
108 : clear(): void {
109 1757 : this.quadTree.clear()
110 1757 : this.invalidateCache()
111 : }
112 :
113 : /**
114 : * Get the current size of the index
115 : */
116 : get size(): number {
117 0 : return this.quadTree.size
118 : }
119 :
120 : /**
121 : * Get debug information about the spatial index
122 : */
123 : getDebugInfo() {
124 0 : return {
125 : quadTreeInfo: this.quadTree.getDebugInfo(),
126 : cacheSize: this.cacheSize,
127 : cacheEntries: this.queryCache.size
128 : }
129 : }
130 :
131 : /**
132 : * Generate cache key for bounds
133 : */
134 : private getCacheKey(bounds: Bounds): string {
135 851 : return `${bounds.x},${bounds.y},${bounds.width},${bounds.height}`
136 : }
137 :
138 : /**
139 : * Add result to cache with LRU eviction
140 : */
141 : private addToCache(key: string, result: TId[]): void {
142 : // Evict oldest entries if cache is full
143 549 : if (this.cacheSize >= PERFORMANCE_CONFIG.SPATIAL_CACHE_MAX_SIZE) {
144 0 : const oldestKey = this.findOldestCacheEntry()
145 0 : if (oldestKey) {
146 0 : this.queryCache.delete(oldestKey)
147 0 : this.cacheSize--
148 : }
149 : }
150 :
151 549 : this.queryCache.set(key, {
152 : result,
153 : timestamp: Date.now()
154 : })
155 549 : this.cacheSize++
156 : }
157 :
158 : /**
159 : * Find oldest cache entry for LRU eviction
160 : */
161 : private findOldestCacheEntry(): string | null {
162 0 : let oldestKey: string | null = null
163 0 : let oldestTime = Infinity
164 :
165 0 : for (const [key, entry] of this.queryCache) {
166 0 : if (entry.timestamp < oldestTime) {
167 0 : oldestTime = entry.timestamp
168 0 : oldestKey = key
169 : }
170 : }
171 :
172 0 : return oldestKey
173 : }
174 :
175 : /**
176 : * Invalidate all cached queries
177 : */
178 : private invalidateCache(): void {
179 1819 : this.queryCache.clear()
180 1819 : this.cacheSize = 0
181 : }
182 : }
|