FilesExpand file tree

 master

/

Trie.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

121 lines (108 loc) · 3.28 KB

 master

/

Trie.js

Copy path

Top

File metadata and controls

• Code
• Blame

121 lines (108 loc) · 3.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

const TrieNode = function TrieNode (key, parent) {

this.key = key

this.count = 0

this.children = Object.create(null)

if (parent === undefined) {

this.parent = null

} else {

this.parent = parent

}

}

function Trie () {

// create only root with null key and parent

this.root = new TrieNode(null, null)

}

// Recursively finds the occurrence of all words in a given node

Trie.findAllWords = function (root, word, output) {

if (root === null) return

if (root.count > 0) {

if (typeof output === 'object') { output.push({ word, count: root.count }) }

}

let key

for (key in root.children) {

word += key

this.findAllWords(root.children[key], word, output)

word = word.slice(0, -1)

}

}

Trie.prototype.insert = function (word) {

if (typeof word !== 'string') return

if (word === '') {

this.root.count += 1

return

}

let node = this.root

const len = word.length

let i

for (i = 0; i < len; i++) {

if (node.children[word.charAt(i)] === undefined) { node.children[word.charAt(i)] = new TrieNode(word.charAt(i), node) }

node = node.children[word.charAt(i)]

}

node.count += 1

}

Trie.prototype.findPrefix = function (word) {

if (typeof word !== 'string') return null

let node = this.root

const len = word.length

let i

// After end of this loop node will be at desired prefix

for (i = 0; i < len; i++) {

if (node.children[word.charAt(i)] === undefined) return null // No such prefix exists

node = node.children[word.charAt(i)]

}

return node

}

Trie.prototype.remove = function (word, count) {

if (typeof word !== 'string') return

if (typeof count !== 'number') count = 1

else if (count <= 0) return

// for empty string just delete count of root

if (word === '') {

if (this.root.count >= count) this.root.count -= count

else this.root.count = 0

return

}

let child = this.root

const len = word.length

let i, key

// child: node which is to be deleted

for (i = 0; i < len; i++) {

key = word.charAt(i)

if (child.children[key] === undefined) return

child = child.children[key]

}

// Delete no of occurrences specified

if (child.count >= count) child.count -= count

else child.count = 0

// If some occurrences are left we don't delete it or else

// if the object forms some other objects prefix we don't delete it

// For checking an empty object

// https://stackoverflow.com/questions/679915/how-do-i-test-for-an-empty-javascript-object

if (child.count <= 0 && (Object.keys(child.children).length && child.children.constructor === Object)) {

child.parent.children[child.key] = undefined

}

}

Trie.prototype.findAllWords = function (prefix) {

const output = []

// find the node with provided prefix

const node = this.findPrefix(prefix)

// No such prefix exists

if (node === null) return output

Trie.findAllWords(node, prefix, output)

return output

}

Trie.prototype.contains = function (word) {

// find the node with given prefix

const node = this.findPrefix(word)

// No such word exists

if (node === null || node.count === 0) return false

return true

}

Trie.prototype.findOccurrences = function (word) {

// find the node with given prefix

const node = this.findPrefix(word)

// No such word exists

if (node === null) return 0

return node.count

}

export { Trie }