var reflect = require( "can-reflect" );
var reflect = require( "can-reflect" );
Returns if obj
is the prototype of a built-in JS type like Map
.
Built in types’ toString
returns [object TYPENAME]
.
function isBuiltInPrototype ( obj ) {
if ( obj === Object.prototype ) {
return true;
}
var protoString = Object.prototype.toString.call( obj );
var isNotObjObj = protoString !== '[object Object]';
var isObjSomething = protoString.indexOf( '[object ' ) !== -1;
return isNotObjObj && isObjSomething;
}
function getDeepSize ( root, level ) {
if ( level === 0 ) {
return reflect.size( root );
} else if ( reflect.size( root ) === 0 ) {
return 0;
} else {
var count = 0;
reflect.each( root, function ( value ) {
count += getDeepSize( value, level - 1 );
});
return count;
}
}
Adds all leaf values under node
to items
.
depth
is how deep node
is in the tree.
maxDepth
is the total depth of the tree structure.
function getDeep ( node, items, depth, maxDepth ) {
if ( !node ) {
return;
}
if ( maxDepth === depth ) {
if ( reflect.isMoreListLikeThanMapLike( node ) ) {
reflect.addValues( items, reflect.toArray( node ) );
} else {
throw new Error( "can-key-tree: Map-type leaf containers are not supported yet." );
}
} else {
reflect.each( node, function ( value ) {
getDeep( value, items, depth + 1, maxDepth );
});
}
}
function clearDeep ( node, depth, maxDepth ) {
if ( maxDepth === depth ) {
if ( reflect.isMoreListLikeThanMapLike( node ) ) {
reflect.removeValues( node, reflect.toArray( node ) );
} else {
throw new Error( "can-key-tree: Map-type leaf containers are not supported yet." );
}
} else {
reflect.each( node, function ( value, key ) {
clearDeep( value, depth+1, maxDepth );
reflect.deleteKeyValue( node, key );
});
}
}
var KeyTree = function ( treeStructure, callbacks ) {
this.callbacks = callbacks || {};
this.treeStructure = treeStructure;
var FirstConstructor = treeStructure[0];
if ( reflect.isConstructorLike( FirstConstructor ) ) {
this.root = new FirstConstructor();
} else {
this.root = FirstConstructor;
}
};
reflect.assign(KeyTree.prototype,{
add: function ( keys ) {
if ( keys.length > this.treeStructure.length ) {
throw new Error( "can-key-tree: Can not add path deeper than tree." );
}
The place we will add the final leaf value.
var place = this.root;
Record if the root was empty so we know to call onFirst
.
var rootWasEmpty = reflect.size( this.root ) === 0;
For each key, try to get the corresponding childNode.
for ( var i = 0; i < keys.length - 1; i++ ) {
var key = keys[i];
var childNode = reflect.getKeyValue( place, key );
if ( !childNode ) {
If there is no childNode, create it and add it to the parent node.
var Constructor = this.treeStructure[i + 1];
if ( isBuiltInPrototype( Constructor.prototype ) ) {
childNode = new Constructor();
} else {
childNode = new Constructor( key );
}
reflect.setKeyValue( place, key, childNode );
}
place = childNode;
}
Add the final leaf value in the tree.
if ( reflect.isMoreListLikeThanMapLike( place ) ) {
reflect.addValues( place, [keys[keys.length - 1]] );
} else {
throw new Error( "can-key-tree: Map types are not supported yet." );
}
Callback onFirst
if appropriate.
if ( rootWasEmpty && this.callbacks.onFirst ) {
this.callbacks.onFirst.call( this );
}
return this;
},
getNode: function ( keys ) {
var node = this.root;
For each key, try to read the child node.
If a child is not found, return undefined
.
for ( var i = 0; i < keys.length; i++ ) {
var key = keys[i];
node = reflect.getKeyValue( node, key );
if ( !node ) {
return;
}
}
return node;
},
get: function ( keys ) {
Get the node specified by keys.
var node = this.getNode( keys );
If it’s a leaf, return it.
if ( this.treeStructure.length === keys.length ) {
return node;
} else {
Otherwise, create a container for leaf values and recursively walk the node’s children.
var Type = this.treeStructure[this.treeStructure.length - 1];
var items = new Type();
getDeep( node, items, keys.length, this.treeStructure.length - 1 );
return items;
}
},
delete: function ( keys ) {
parentNode
will eventually be the parent nodde of the
node specified by keys.
var parentNode = this.root,
The nodes traversed to the node specified by keys
.
path = [this.root],
lastKey = keys[keys.length - 1];
Set parentNode to the node specified by keys
and record the nodes in path
.
for ( var i = 0; i < keys.length - 1; i++ ) {
var key = keys[i];
var childNode = reflect.getKeyValue( parentNode, key );
if ( childNode === undefined ) {
return false;
} else {
path.push( childNode );
}
parentNode = childNode;
}
Depending on which keys were specified and the content of the key, do various cleanups …
if ( !keys.length ) {
If there are no keys, recursively clear the entire tree.
clearDeep( parentNode, 0, this.treeStructure.length - 1 );
}
else if ( keys.length === this.treeStructure.length ) {
If removing a leaf, remove that value.
if ( reflect.isMoreListLikeThanMapLike( parentNode ) ) {
reflect.removeValues( parentNode, [lastKey] );
} else {
throw new Error( "can-key-tree: Map types are not supported yet." );
}
}
else {
If removing a node ‘within’ the tree, recursively clear that node and then delete the key from parent to node.
var nodeToRemove = reflect.getKeyValue( parentNode, lastKey );
if ( nodeToRemove !== undefined ) {
clearDeep( nodeToRemove, keys.length, this.treeStructure.length - 1 );
reflect.deleteKeyValue( parentNode, lastKey );
} else {
return false;
}
}
After deleting the node, check if its parent is empty and recursively prune parent nodes that are now empty.
for ( i = path.length - 2; i >= 0; i-- ) {
if ( reflect.size( parentNode ) === 0 ) {
parentNode = path[i];
reflect.deleteKeyValue( parentNode, keys[i] );
} else {
break;
}
}
Call onEmpty
if the tree is now empty.
if ( this.callbacks.onEmpty && reflect.size( this.root ) === 0 ) {
this.callbacks.onEmpty.call( this );
}
return true;
},
size: function () {
return getDeepSize( this.root, this.treeStructure.length - 1 );
}
});
module.exports = KeyTree;