#567

Committed 18 Jul 2024 02:44PM UTC coverage: 98.521%. First build

Build # #567

Build Type

push

github

Committed by

web-flow

Commit Message

Merge 78c879340 into 746f09134

Run Details

222 of 232 branches covered (95.69%)

Branch coverage included in aggregate %.

644 of 647 relevant lines covered (99.54%)

735.23 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

100.0

/src/SearchableMap/TreeIterator.ts

import type { RadixTree, Entry, LeafType } from './types'

/** @ignore */
const ENTRIES = 'ENTRIES'

/** @ignore */
const KEYS = 'KEYS'

/** @ignore */
const VALUES = 'VALUES'

/** @ignore */
const LEAF = '' as LeafType

interface Iterators<T> {
  ENTRIES: Entry<T>
  KEYS: string
  VALUES: T
}

type Kind<T> = keyof Iterators<T>
type Result<T, K extends keyof Iterators<T>> = Iterators<T>[K]

type IteratorPath<T> = {
  node: RadixTree<T>,
  keys: string[]
}[]

export type IterableSet<T> = {
  _tree: RadixTree<T>,
  _prefix: string
}

/**
 * @private
 */
class TreeIterator<T, K extends Kind<T>> implements Iterator<Result<T, K>> {
  set: IterableSet<T>
  _type: K
  _path: IteratorPath<T>

  constructor (set: IterableSet<T>, type: K) {
    const node = set._tree
    const keys = Array.from(node.keys())
    this.set = set
    this._type = type
    this._path = keys.length > 0 ? [{ node, keys }] : []
  }

  next (): IteratorResult<Result<T, K>> {
    const value = this.dive()
    this.backtrack()
    return value
  }

  dive (): IteratorResult<Result<T, K>> {
    if (this._path.length === 0) { return { done: true, value: undefined } }
    const { node, keys } = last(this._path)!
    if (last(keys) === LEAF) { return { done: false, value: this.result() } }

    const child = node.get(last(keys)!)!
    this._path.push({ node: child, keys: Array.from(child.keys()) })
    return this.dive()
  }

  backtrack (): void {
    if (this._path.length === 0) { return }
    const keys = last(this._path)!.keys
    keys.pop()
    if (keys.length > 0) { return }
    this._path.pop()
    this.backtrack()
  }

  key (): string {
    return this.set._prefix + this._path
      .map(({ keys }) => last(keys))
      .filter(key => key !== LEAF)
      .join('')
  }

  value (): T {
    return last(this._path)!.node.get(LEAF)!
  }

  result (): Result<T, K> {
    switch (this._type) {
      case VALUES: return this.value() as Result<T, K>
      case KEYS: return this.key() as Result<T, K>
      default: return [this.key(), this.value()] as Result<T, K>
    }
  }

  [Symbol.iterator] () {
    return this
  }
}

const last = <T>(array: T[]): T | undefined => {
  return array[array.length - 1]
}

export { TreeIterator, ENTRIES, KEYS, VALUES, LEAF }

1	import type { RadixTree, Entry, LeafType } from './types'
2
3	/** @ignore */
4	const ENTRIES = 'ENTRIES'	2✔
5
6	/** @ignore */
7	const KEYS = 'KEYS'	2✔
8
9	/** @ignore */
10	const VALUES = 'VALUES'	2✔
11
12	/** @ignore */
13	const LEAF = '' as LeafType	2✔
14
15	interface Iterators<T> {
16	ENTRIES: Entry<T>
17	KEYS: string
18	VALUES: T
19	}
20
21	type Kind<T> = keyof Iterators<T>
22	type Result<T, K extends keyof Iterators<T>> = Iterators<T>[K]
23
24	type IteratorPath<T> = {
25	node: RadixTree<T>,
26	keys: string[]
27	}[]
28
29	export type IterableSet<T> = {
30	_tree: RadixTree<T>,
31	_prefix: string
32	}
33
34	/**
35	* @private
36	*/
37	class TreeIterator<T, K extends Kind<T>> implements Iterator<Result<T, K>> {
38	set: IterableSet<T>
39	_type: K
40	_path: IteratorPath<T>
41
42	constructor (set: IterableSet<T>, type: K) {
43	const node = set._tree	521✔
44	const keys = Array.from(node.keys())	521✔
45	this.set = set	521✔
46	this._type = type	521✔
47	this._path = keys.length > 0 ? [{ node, keys }] : []	521✔
48	}
49
50	next (): IteratorResult<Result<T, K>> {
51	const value = this.dive()	2,141✔
52	this.backtrack()	2,141✔
53	return value	2,141✔
54	}
55
56	dive (): IteratorResult<Result<T, K>> {
57	if (this._path.length === 0) { return { done: true, value: undefined } }	3,853✔
58	const { node, keys } = last(this._path)!	3,332✔
59	if (last(keys) === LEAF) { return { done: false, value: this.result() } }	3,332✔
60
61	const child = node.get(last(keys)!)!	1,712✔
62	this._path.push({ node: child, keys: Array.from(child.keys()) })	1,712✔
63	return this.dive()	1,712✔
64	}
65
66	backtrack (): void {
67	if (this._path.length === 0) { return }	4,128✔
68	const keys = last(this._path)!.keys	3,332✔
69	keys.pop()	3,332✔
70	if (keys.length > 0) { return }	3,332✔
71	this._path.pop()	1,987✔
72	this.backtrack()	1,987✔
73	}
74
75	key (): string {
76	return this.set._prefix + this._path	1,588✔
77	.map(({ keys }) => last(keys))	3,653✔
78	.filter(key => key !== LEAF)	3,653✔
79	.join('')
80	}
81
82	value (): T {
83	return last(this._path)!.node.get(LEAF)!	1,498✔
84	}
85
86	result (): Result<T, K> {
87	switch (this._type) {	1,620✔
88	case VALUES: return this.value() as Result<T, K>	32✔
89	case KEYS: return this.key() as Result<T, K>	122✔
90	default: return [this.key(), this.value()] as Result<T, K>	1,466✔
91	}
92	}
93
94	[Symbol.iterator] () {
95	return this	211✔
96	}
97	}
98
99	const last = <T>(array: T[]): T \| undefined => {	2✔
100	return array[array.length - 1]	16,859✔
101	}
102
103	export { TreeIterator, ENTRIES, KEYS, VALUES, LEAF }	2✔

lucaong / minisearch / #567

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous