FuzzyTree
A tree inplementation in which nodes' paths can be non-deterministic. In other words, nodes can be placed in a path which can match more than one search query.
Using this kind of tree structure, one can, very efficiently, match specific queries to generic pre-defined patterns.
Example:
var node = new FuzzyTree();
// insert a new node under a fuzzy path:
node.insert("usa.#.main-street.99");
// query the tree two times:
node.match("usa.new-york.main-street.99") // has a match!
node.match("usa.texas.houston.main-street.99") // has a match!
API
Constructor
var node = new FuzzyTree()
Construct a new tree node. Every node in the tree is an instance of FuzzyTree
.
Reset
node.reset()
Resets the node by removing its data and children.
Set data
node.setData(data)
data {*}
: The data to be stored in the node.
Returns the node itself.
Get data
node.getData()
Returns the data stored in the node, or null if no data.
Match / query nodes in the tree
node.match(query)
query {String|Array}
: The path to match nodes' path patterns.
Returns an array of matching nodes.
Example:
var child1 = node.insert("hello.#.world");
var child2 = node.insert("hello.*.world");
var child3 = node.insert("hello.foo.bar.world");
node.match("hello.foo.bar.world");
// returned array will contain child1 and child3, but not child3.
Find a specific node
node.find(path)
query {String|Array}
: The path of the requested node.
Returns the found node, or null if not found.
Example:
// the following expression is true:
node.insert("hello.#.world") === node.find("hello.#.world");
Insert a new node under a path
node.insert(path)
Insert a node under the specified path. If a node already exists under this path it will be resetted.
path {String|Array}
: The path of the new node.
Returns the newly created node.
Paths structure
A path is simply a string with one or more sections. Sections are separated
by a '.'
. Sections in a path form the nodes hirarchy in the tree.
For example, the path 'country.city.street'
has three sections 'country'
,
'city'
and 'street'
. The node under 'country.city.street'
is a child of
the node under 'country.city'
, etc.
country
/ \
/ \
/ \
city ...
/ \
/ \
/ \
street ...
Fuzzy paths & wildcards
Any section of a path can be a wildcard; in which case the path is termed a "fuzzy path". When querying the tree for matches of a specific path, any node under a fuzzy path with a matching structure will be returned as well.
There are two types of wildcards:
'*'
: Matches exactly one section.'#'
: Matches one or more sections.
For example, let's say we have two nodes in the tree under the following fuzzy paths:
'country.*.street'
'country.#.street'
country
/ \
/ \
/ \
* #
/ \
/ \
/ \
street street
When we query for matches against 'country.city.street'
both nodes will be
returend. But when querying against 'country.state.city.street'
, only the
second node will be returned.