LCOV - code coverage report
Current view: top level - src/renderer/core/spatial - SpatialIndex.ts Coverage Total Hit
Test: ComfyUI E2E Coverage Lines: 62.8 % 43 27
Test Date: 2026-11-17 04:17:53

            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              : }
        

Generated by: LCOV version 2.0-1