1 2
import { findIndex } from 'lodash'
2

3
/**
4
 * A key-value map where the members' keys represent prefixes.
5
 *
6
 * Example:
7
 *   const map = new PrefixMap()
8
 *   map.insert("foo", 1)
9
 *   map.insert("bar", 2)
10
 *   map.get("foo")     // ⇒ 1
11
 *   map.get("foo.bar") // ⇒ 1 ("foo" is the longest known prefix of "foo.bar")
12
 *   map.get("bar")     // ⇒ 2
13
 *   map.get("bar.foo") // ⇒ 2 ("bar" is the longest known prefix of "bar.foo")
14
 *   map.get("random")  // ⇒ null
15
 */
16 2
export default class PrefixMap<T> {
17
  protected prefixes: string[]
18
  protected items: { [key: string]: T }
19

20
  constructor () {
21 2
    this.prefixes = []
22 2
    this.items = {}
23
  }
24

25 2
  keys () { return this.prefixes }
26

27 2
  size () { return this.prefixes.length }
28

29
  /**
30
   * Find the value of the longest matching prefix key.
31
   */
32
  resolve (key: string) {
33 2
    const prefix = this.resolvePrefix(key)
34

35 2
    return typeof prefix !== 'undefined' ? this.items[prefix] : undefined
36
  }
37

38
  /**
39
   * Find the longest matching prefix key.
40
   */
41
  resolvePrefix (key: string) {
42
    // Exact match
43 2
    if (this.items[key]) return key // redundant; optimization?
44
    // prefix match (the list is in descending length order, and secondarily, reverse-alphabetically)
45 2
    const index = findIndex(this.prefixes, (e: string) => key.startsWith(e + '.'))
46 2
    if (index === -1) return undefined
47 2
    const prefix = this.prefixes[index]
48 2
    return prefix
49
  }
50

51 2
  get (prefix: string): T | undefined { return this.items[prefix] }
52

53
  /**
54
   * Look up all keys that start with a certain prefix.
55
   */
56
  * getKeysStartingWith (prefix: string): IterableIterator<string> {
57
    // TODO: This could be done *much* more efficiently
58 2
    const predicate = (key: string) => key.startsWith(prefix)
59 2
    let index = -1
60
    // tslint:disable-next-line:no-conditional-assignment
61 2
    while ((index = findIndex(this.prefixes, predicate, index + 1)) !== -1) {
62 2
      yield this.prefixes[index]
63
    }
64
  }
65

66
  * getKeysPrefixesOf (search: string): IterableIterator<string> {
67 2
    const predicate = (key: string) => search.startsWith(key + '.')
68 2
    let index = -1
69
    // tslint:disable-next-line:no-conditional-assignment
70 2
    while ((index = findIndex(this.prefixes, predicate, index + 1)) !== -1) {
71 0
      yield this.prefixes[index]
72
    }
73
  }
74

75
  /**
76
   * @param {function(item, key)} fn
77
   */
78
  each (fn: (item: T, key: string) => void) {
79 2
    for (const prefix of this.prefixes) {
80 2
      fn(this.items[prefix], prefix)
81
    }
82
  }
83

84
  /**
85
   * Insert the prefix while keeping the prefixes sorted first in length order
86
   * and if two prefixes are the same length, sort them in reverse alphabetical order
87
   */
88
  insert (prefix: string, item: T) {
89 2
    if (!this.items[prefix]) {
90 2
      const index = findIndex(this.prefixes, (e) => {
91 2
        if (prefix.length === e.length) {
92 2
          return prefix > e
93
        }
94 2
        return prefix.length > e.length
95
      })
96

97 2
      if (index === -1) {
98 2
        this.prefixes.push(prefix)
99
      } else {
100 2
        this.prefixes.splice(index, 0, prefix)
101
      }
102
    }
103 2
    this.items[prefix] = item
104 2
    return item
105
  }
106

107
  delete (prefix: string) {
108 2
    const index = this.prefixes.indexOf(prefix)
109 2
    if (this.prefixes[index] === prefix) this.prefixes.splice(index, 1)
110 2
    delete this.items[prefix]
111
  }
112

113
  toJSON () {
114 2
    return this.items
115
  }
116

117
  /**
118
   * Find the shortest unambiguous prefix of an ILP address in a prefix map.
119
   *
120
   * This let's us figure out what addresses the selected route applies to. For
121
   * example, the most specific route for destination "a.b.c" might be "a", but
122
   * that doesn't mean that that route applies to any destination starting with
123
   * "a" because there may be a more specific route like "a.c".
124
   *
125
   * So we would call this utility function to find out that the least specific
126
   * prefix for which there are no other more specific routes is "a.b".
127
   *
128
   * In order to force a minimum prefix, it can be passed as the third parameter.
129
   * This function may make it even more specific if necessary to make it
130
   * unambiguous, but it will never return a less specific prefix.
131
   */
132 2
  getShortestUnambiguousPrefix (address: string, prefix = '') {
133 2
    if (!address.startsWith(prefix)) {
134 0
      throw new Error(`address must start with prefix. address=${address} prefix=${prefix}`)
135
    }
136

137 0
    this.keys().forEach((secondPrefix: string) => {
138 2
      if (secondPrefix === prefix) {
139 0
        return
140
      }
141

142 0
      while (secondPrefix.startsWith(prefix)) {
143 2
        if (secondPrefix === prefix) {
144 0
          return
145
        }
146

147 0
        const nextSegmentEnd = address.indexOf('.', prefix.length + 1)
148

149 2
        if (nextSegmentEnd === -1) {
150 0
          prefix = address
151 0
          return
152
        } else {
153 0
          prefix = address.slice(0, nextSegmentEnd)
154
        }
155
      }
156
    })
157

158 0
    return prefix
159
  }
160
}

Read our documentation on viewing source code .

Loading