chain-lightning - npm Package Compare versions

Comparing version 0.4.2 to 0.4.3

lib/QuadTree.js

@@ -45,15 +45,16 @@ /*
 	Options:
-		minSquareSize `number` the min size of a node, should be a power of 2 like 1, 2, 4, or 0.5, 0.25, 0.125, ...
-			No subdivision will occur below that size
+		minNodeAreaSize `number` the min size of the area of a node, i.e. the square side, should be a power of 2 like 1, 2, 4, or 0.5, 0.25, 0.125, ...
+			No subdivision will occur below that area size
 		maxLeafPoints `number` above this number of points, the leaf will become a node with 4 child leaves (except if its size
-			is already the min square size)
+			is already the min area size)
 		minLeafPoints `number` below this number of points, the leaf will trigger the join-leaves mecanism
 		minChildrenPoints `number` a node may merge all its children leaves and become the leaf itself if the sum of the points
 			of all its direct children leaves is below this number
-		x,y `number` the initial lower limit of the bounding box, should be a multiple of minSquareSize
-		size `number` the initial side size of the bounding box, should be a power of 2 and greater than or equals to minSquareSize
+		x,y `number` the initial lower limit of the bounding box, should be a multiple of minNodeAreaSize
+		areaSize `number` the initial side size of the bounding box, should be a power of 2 and greater than or equals to minNodeAreaSize
+		autoResize `boolean` if set, the original BBox can be modified, e.g.: expand when adding out of bounds elements, or adapt to the first elements inserted
 */
 
 function QuadTree( options = {} ) {
-	this.minSquareSize = options.minSquareSize || 1 / 1024 ;
+	this.minNodeAreaSize = options.minNodeAreaSize || 1 / 1024 ;
 	this.maxLeafPoints = options.maxLeafPoints || 16 ;
@@ -65,6 +66,10 @@ this.minLeafPoints = options.minLeafPoints || Math.floor( options.maxLeafPoints / 8 ) || 1 ;
 	this.y = options.y || 0 ;
-	this.size = options.size || 1 ;
+	this.areaSize = options.areaSize || 1 ;
+	this.autoResize = !! options.autoResize ;
 
-	this.trunc = new Node() ;
-	this.trunc.points = new Set() ;
+	this.trunk = new Node() ;
+	this.trunk.points = new Set() ;
+
+	// Number of elements stored
+	this.size = 0 ;
 }
@@ -545,3 +550,3 @@
 QuadTree.prototype.nodeCount = function() {
-	return this.trunc.recursiveNodeCount() ;
+	return this.trunk.recursiveNodeCount() ;
 } ;
@@ -552,3 +557,3 @@
 QuadTree.prototype.leafCount = function() {
-	return this.trunc.recursiveLeafCount() ;
+	return this.trunk.recursiveLeafCount() ;
 } ;
@@ -561,3 +566,3 @@
 QuadTree.prototype.getLeaf = function( x , y , search = GET_LEAF_SEARCH ) {
-	search.set( x , y , 0 , 0 , this.x , this.y , this.size , this.trunc ).toLeaf() ;
+	search.set( x , y , 0 , 0 , this.x , this.y , this.areaSize , this.trunk ).toLeaf() ;
 	return search ;
@@ -571,3 +576,3 @@ } ;
 QuadTree.prototype.getPoint = function( x , y , search = GET_POINT_SEARCH ) {
-	search.set( x , y , 0 , 0 , this.x , this.y , this.size , this.trunc ).toLeaf() ;
+	search.set( x , y , 0 , 0 , this.x , this.y , this.areaSize , this.trunk ).toLeaf() ;
 	if ( ! search.node || ! search.node.points ) { return ; }
@@ -578,3 +583,3 @@ return findXYInSet( search.node.points , x , y ) ;
 QuadTree.prototype.getPointSaveSteps = function( x , y , search , searchSteps ) {
-	search.set( x , y , 0 , 0 , this.x , this.y , this.size , this.trunc ).toLeafSaveSteps( searchSteps ) ;
+	search.set( x , y , 0 , 0 , this.x , this.y , this.areaSize , this.trunk ).toLeafSaveSteps( searchSteps ) ;
 	if ( ! search.node || ! search.node.points ) { return ; }
@@ -610,3 +615,3 @@ return findXYInSet( search.node.points , x , y ) ;
 	var leaves = [] ;
-	search.set( x , y , w , h , this.x , this.y , this.size , this.trunc ) ;
+	search.set( x , y , w , h , this.x , this.y , this.areaSize , this.trunk ) ;
 	search.recursiveAreaLeaves( leaves ) ;
@@ -622,3 +627,3 @@ return leaves ;
 	var points = [] ;
-	search.set( x , y , w , h , this.x , this.y , this.size , this.trunc ) ;
+	search.set( x , y , w , h , this.x , this.y , this.areaSize , this.trunk ) ;
 	search.recursiveAreaPoints( points ) ;
@@ -634,3 +639,3 @@ return points ;
 	var elements = [] ;
-	search.set( x , y , w , h , this.x , this.y , this.size , this.trunc ) ;
+	search.set( x , y , w , h , this.x , this.y , this.areaSize , this.trunk ) ;
 	search.recursiveAreaElements( elements ) ;
@@ -652,3 +657,3 @@ return elements ;
 
-	search.set( x , y , 0 , 0 , this.x , this.y , this.size , this.trunc ).toLeafSaveSteps( searchSteps ) ;
+	search.set( x , y , 0 , 0 , this.x , this.y , this.areaSize , this.trunk ).toLeafSaveSteps( searchSteps ) ;
 
@@ -751,11 +756,15 @@ // First check if there is anything in the node and if a point exists and its distance
 
-	// There should be some mecanisms for when there is nothing stored, or when everything is stored in the trunc node
-	//if ( ! this.trunc.children && ( this.trunc.points || ! this.trunc.points.size ) ) {}
+	// We don't add undefined values, because undefined = no value
+	if ( element === undefined ) { return ; }
 
-	// While out of the trunc BBox, zomm-out the whole tree...
-	while ( x < this.x || x >= this.x + this.size || y < this.y || y >= this.y + this.size ) {
-		this.zoomOutFor( x , y ) ;
+	// There should be some mecanisms for when there is nothing stored, or when everything is stored in the trunk node
+	//if ( ! this.trunk.children && ( this.trunk.points || ! this.trunk.points.size ) ) {}
+
+	// While out of the trunk BBox, zoom-out the whole tree...
+	if ( x < this.x || x >= this.x + this.areaSize || y < this.y || y >= this.y + this.areaSize ) {
+		if ( ! this.autoResize ) { return ; }
+		this.resizeBBoxFor( x , y ) ;
 	}
 
-	search.set( x , y , 0 , 0 , this.x , this.y , this.size , this.trunc ) ;
+	search.set( x , y , 0 , 0 , this.x , this.y , this.areaSize , this.trunk ) ;
 	search.toLeaf() ;
@@ -783,2 +792,4 @@
 
+		this.size ++ ;
+
 		return point ;
@@ -789,4 +800,5 @@ }
 	search.node.points.add( point ) ;
+	this.size ++ ;
 
-	if ( search.node.points.size > this.maxLeafPoints && search.bbs > this.minSquareSize ) {
+	if ( search.node.points.size > this.maxLeafPoints && search.bbs > this.minNodeAreaSize ) {
 		this.subdivideNode( search ) ;
@@ -809,2 +821,8 @@ }
 
+	// Adjust the size
+	this.size -=
+		point.s ? point.s.length :
+		point.e !== undefined ? 1 :
+		0 ;
+
 	search.node.points.delete( point ) ;
@@ -827,18 +845,23 @@
 QuadTree.prototype.removeElement = function( x , y , element , search = REMOVE_ELEMENT_SEARCH ) {
-	var length , searchSteps = [] ,
-		point = this.getPointSaveSteps( x , y , search , searchSteps ) ;
+	var deletedCount = 0 , point , searchSteps = [] ;
 
-	if ( ! point ) { return false ; }
+	if ( element === undefined ) { return 0 ; }
 
+	point = this.getPointSaveSteps( x , y , search , searchSteps ) ;
+
+	if ( ! point ) { return 0 ; }
+
 	if ( point.s ) {
-		length = point.s.length ;
-		arrayKit.deleteValue( point.s , element ) ;
-		if ( point.s.length ) { return length !== point.s.length ; }
+		deletedCount = arrayKit.deleteValue( point.s , element ) ;
+		this.size -= deletedCount ;
+		if ( point.s.length ) { return deletedCount ; }
 		search.node.points.delete( point ) ;
 	}
 	else if ( point.e === element ) {
+		deletedCount = 1 ;
+		this.size -- ;
 		search.node.points.delete( point ) ;
 	}
 	else {
-		return false ;
+		return 0 ;
 	}
@@ -850,3 +873,3 @@
 
-	return true ;
+	return deletedCount ;
 } ;
@@ -856,16 +879,41 @@
 
-// Create a new trunc having current trunc as one quad-child, do it for a specific direction
-QuadTree.prototype.zoomOutFor = function( x , y ) {
+// We assume that x,y is already out of bounds
+QuadTree.prototype.resizeBBoxFor = function( x , y ) {
+	if ( this.trunk.children || ( this.trunk.points && this.trunk.points.size ) ) {
+		// There are already elements, so we will just create a super node replacing the trunk
+		do {
+			this.superNodeToward( x , y ) ;
+		} while ( x < this.x || x >= this.x + this.areaSize || y < this.y || y >= this.y + this.areaSize ) ;
+
+		return ;
+	}
+
+	// No content already, just adjust the trunk for the element to be inserted
+	this.translateBBoxTo( x , y ) ;
+} ;
+
+
+
+// We assume that x,y is already out of bounds
+QuadTree.prototype.translateBBoxTo = function( x , y ) {
+	this.x += Math.floor( ( x - this.x ) / this.areaSize ) * this.areaSize ;
+	this.y += Math.floor( ( y - this.y ) / this.areaSize ) * this.areaSize ;
+} ;
+
+
+
+// Create a new trunk having current trunk as one quad-child, do it for a specific direction
+QuadTree.prototype.superNodeToward = function( x , y ) {
 	var qIndex ,
 		newTrunc = new Node() ,
-		xSplit = this.x + this.size / 2 ,
-		ySplit = this.y + this.size / 2 ;
+		xSplit = this.x + this.areaSize / 2 ,
+		ySplit = this.y + this.areaSize / 2 ;
 
 	// Note that we are doing the REVERSE of .subQuadIndex()
 	if ( y < ySplit ) {
-		this.y -= this.size ;
+		this.y -= this.areaSize ;
 
 		if ( x < xSplit ) {
 			qIndex = TOP_RIGHT ;
-			this.x -= this.size ;
+			this.x -= this.areaSize ;
 		}
@@ -878,3 +926,3 @@ else {
 		qIndex = BOTTOM_RIGHT ;
-		this.x -= this.size ;
+		this.x -= this.areaSize ;
 	}
@@ -886,5 +934,5 @@ else {
 	newTrunc.children = [ null , null , null , null ] ;
-	newTrunc.children[ qIndex ] = this.trunc ;
-	this.trunc = newTrunc ;
-	this.size *= 2 ;
+	newTrunc.children[ qIndex ] = this.trunk ;
+	this.trunk = newTrunc ;
+	this.areaSize *= 2 ;
 } ;
@@ -896,3 +944,3 @@
 QuadTree.prototype.subdivideNode = function( search ) {
-	if ( search.node.points.size <= this.maxLeafPoints && search.bbs > this.minSquareSize ) { return ; }
+	if ( search.node.points.size <= this.maxLeafPoints && search.bbs > this.minNodeAreaSize ) { return ; }
 
@@ -922,3 +970,3 @@ var i , point , qIndex , children , child , searchChild ,
 	// Check if we can subdivide those new children
-	if ( search.bbs / 2 <= this.minSquareSize ) { return ; }
+	if ( search.bbs / 2 <= this.minNodeAreaSize ) { return ; }
 
@@ -994,3 +1042,3 @@ for ( i = 0 ; i < 4 ; i ++ ) {
 
-QuadTree.prototype.values = function *( node = this.trunc ) {
+QuadTree.prototype.values = function *( node = this.trunk ) {
 	if ( node.children ) {
@@ -1016,3 +1064,3 @@ for ( let i = 0 ; i < 4 ; i ++ ) {
 
-QuadTree.prototype.entries = function *( node = this.trunc ) {
+QuadTree.prototype.entries = function *( node = this.trunk ) {
 	if ( node.children ) {
@@ -1043,3 +1091,3 @@ for ( let i = 0 ; i < 4 ; i ++ ) {
 // Return keys, do not return the same key twice, even if there is multiple values on the same key
-QuadTree.prototype.keys = function *( node = this.trunc ) {
+QuadTree.prototype.keys = function *( node = this.trunk ) {
 	if ( node.children ) {
@@ -1122,3 +1170,3 @@ for ( let i = 0 ; i < 4 ; i ++ ) {
 
-QuadTree.prototype.debug = function( node = this.trunc , spaces = 0 , prefix = '━' , showValue = false ) {
+QuadTree.prototype.debug = function( node = this.trunk , spaces = 0 , prefix = '━' , showValue = false ) {
 	var i , iMax , str , point ,
@@ -1176,3 +1224,3 @@ nextSpaces = spaces + 5 ;
 
-QuadTree.prototype.debugValues = function() { return this.debug( this.trunc , 0 , '━' , true ) ; } ;
+QuadTree.prototype.debugValues = function() { return this.debug( this.trunk , 0 , '━' , true ) ; } ;
 

package.json

 {
   "name": "chain-lightning",
-  "version": "0.4.2",
+  "version": "0.4.3",
   "description": "Linked list",
@@ -14,3 +14,3 @@ "main": "lib/chainlightning.js",
   "dependencies": {
-    "array-kit": "^0.2.3"
+    "array-kit": "^0.2.4"
   },
@@ -17,0 +17,0 @@ "scripts": {

test/quadtree-test.js

@@ -97,2 +97,3 @@ /*
 			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 } ) ;
+			expect( tree.size ).to.be( 0 ) ;
 			
@@ -104,2 +105,3 @@ tree.add( 0.1 , 0.1 , "one" ) ;
 			expect( [ ... tree.values() ] ).to.equal( [ "one" , "two" , "three" , "four" ] ) ;
+			expect( tree.size ).to.be( 4 ) ;
 
@@ -112,2 +114,3 @@ tree.add( 0.11 , 0.11 , "five" ) ;
 			expect( [ ... tree.values() ] ).to.equal( [ "one" , "two" , "five" , "six" , "three" , "seven" , "eight" , "nine" , "four" ] ) ;
+			expect( tree.size ).to.be( 9 ) ;
 		} ) ;
@@ -121,2 +124,3 @@
 			tree.add( 0.1 , 0.1 , "one" ) ;
+			expect( tree.size ).to.be( 1 ) ;
 			expect( tree.getOne( 0.1 , 0.1 ) ).to.be( "one" ) ;
@@ -127,2 +131,3 @@ expect( tree.getMany( 0.1 , 0.1 ) ).to.equal( [ "one" ] ) ;
 			tree.add( 0.1 , 0.1 , "two" ) ;
+			expect( tree.size ).to.be( 2 ) ;
 			expect( tree.getOne( 0.1 , 0.1 ) ).to.be( "one" ) ;
@@ -134,3 +139,3 @@ expect( tree.getMany( 0.1 , 0.1 ) ).to.equal( [ "one" , "two" ] ) ;
 		it( ".deleteElement()" , () => {
-			var tree ;
+			var tree , deletedCount ;
 			
@@ -142,2 +147,3 @@ tree = new QuadTree() ;
 			tree.add( 0.2 , 0.2 , "three" ) ;
+			expect( tree.size ).to.be( 3 ) ;
 			expect( [ ... tree ] ).to.equal( [
@@ -149,3 +155,5 @@ [ { x: 0.1 , y: 0.1 } , "one" ] ,
 
-			tree.deleteElement( 0.2 , 0.2 , "one" ) 
+			deletedCount = tree.deleteElement( 0.2 , 0.2 , "one" ) 
+			expect( deletedCount ).to.be( 0 ) ;
+			expect( tree.size ).to.be( 3 ) ;
 			expect( [ ... tree ] ).to.equal( [
@@ -157,3 +165,5 @@ [ { x: 0.1 , y: 0.1 } , "one" ] ,
 
-			tree.deleteElement( 0.1 , 0.1 , "one" ) 
+			deletedCount = tree.deleteElement( 0.1 , 0.1 , "one" ) 
+			expect( deletedCount ).to.be( 1 ) ;
+			expect( tree.size ).to.be( 2 ) ;
 			expect( [ ... tree ] ).to.equal( [
@@ -164,3 +174,5 @@ [ { x: 0.1 , y: 0.1 } , "two" ] ,
 
-			tree.deleteElement( 0.1 , 0.1 , "two" ) 
+			deletedCount = tree.deleteElement( 0.1 , 0.1 , "two" ) 
+			expect( deletedCount ).to.be( 1 ) ;
+			expect( tree.size ).to.be( 1 ) ;
 			expect( [ ... tree ] ).to.equal( [
@@ -170,4 +182,37 @@ [ { x: 0.2 , y: 0.2 } , "three" ]
 
-			tree.deleteElement( 0.2 , 0.2 , "three" ) 
+			deletedCount = tree.deleteElement( 0.2 , 0.2 , "three" ) 
+			expect( deletedCount ).to.be( 1 ) ;
+			expect( tree.size ).to.be( 0 ) ;
 			expect( [ ... tree ] ).to.equal( [] ) ;
+
+			// Now delete identical values at the same point
+			tree = new QuadTree() ;
+			
+			tree.add( 0.1 , 0.1 , "other1" ) ;
+			tree.add( 0.1 , 0.1 , "same" ) ;
+			tree.add( 0.1 , 0.1 , "same" ) ;
+			tree.add( 0.1 , 0.1 , "same" ) ;
+			tree.add( 0.1 , 0.1 , "other2" ) ;
+			tree.add( 0.2 , 0.2 , "other3" ) ;
+			tree.add( 0.2 , 0.2 , "same" ) ;
+			expect( tree.size ).to.be( 7 ) ;
+			expect( [ ... tree ] ).to.equal( [
+				[ { x: 0.1 , y: 0.1 } , "other1" ] ,
+				[ { x: 0.1 , y: 0.1 } , "same" ] ,
+				[ { x: 0.1 , y: 0.1 } , "same" ] ,
+				[ { x: 0.1 , y: 0.1 } , "same" ] ,
+				[ { x: 0.1 , y: 0.1 } , "other2" ] ,
+				[ { x: 0.2 , y: 0.2 } , "other3" ] ,
+				[ { x: 0.2 , y: 0.2 } , "same" ]
+			] ) ;
+
+			deletedCount = tree.deleteElement( 0.1 , 0.1 , "same" ) 
+			expect( deletedCount ).to.be( 3 ) ;
+			expect( tree.size ).to.be( 4 ) ;
+			expect( [ ... tree ] ).to.equal( [
+				[ { x: 0.1 , y: 0.1 } , "other1" ] ,
+				[ { x: 0.1 , y: 0.1 } , "other2" ] ,
+				[ { x: 0.2 , y: 0.2 } , "other3" ] ,
+				[ { x: 0.2 , y: 0.2 } , "same" ]
+			] ) ;
 		} ) ;
@@ -226,3 +271,3 @@
 				randomX , randomY , randomW , randomH ,
-				testCount = 100 , sizeLimit = 0.5 ,
+				testCount = 100 , areaSizeLimit = 0.5 ,
 				rawData = generateRawData( 1000 ) ;
@@ -237,6 +282,6 @@
 				//QuadTree.overlap = QuadTree.encompass = QuadTree.seen = 0 ;
-				randomW = Math.random() * sizeLimit ;
+				randomW = Math.random() * areaSizeLimit ;
 				randomX = Math.random() * ( 1 - randomW ) ;
 				
-				randomH = Math.random() * sizeLimit ;
+				randomH = Math.random() * areaSizeLimit ;
 				randomY = Math.random() * ( 1 - randomH ) ;
@@ -290,4 +335,4 @@
 			tree.add( 0.14 , 0.14 , "four" ) ;
-			expect( tree.trunc.children ).to.be( null ) ;
-			expect( [ ... tree.trunc.points ] ).to.be.like( [
+			expect( tree.trunk.children ).to.be( null ) ;
+			expect( [ ... tree.trunk.points ] ).to.be.like( [
 				{ x: 0.11, y: 0.11, e: "one", s: null } ,
@@ -301,7 +346,7 @@ { x: 0.12, y: 0.12, e: "two", s: null } ,
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].points ] ).to.be.like( [
 				{ x: 0.11, y: 0.11, e: "one", s: null } ,
 				{ x: 0.12, y: 0.12, e: "two", s: null }
 			] ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[3].points ] ).to.be.like( [
 				{ x: 0.13, y: 0.13, e: "three", s: null } ,
@@ -314,6 +359,6 @@ { x: 0.14, y: 0.14, e: "four", s: null } ,
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].points ] ).to.be.like( [
 				{ x: 0.12, y: 0.12, e: "two", s: null }
 			] ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[3].points ] ).to.be.like( [
 				{ x: 0.13, y: 0.13, e: "three", s: null } ,
@@ -326,4 +371,4 @@ { x: 0.14, y: 0.14, e: "four", s: null } ,
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].points ] ).to.be.like( [] ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].points ] ).to.be.like( [] ) ;
+			expect( [ ... tree.trunk.children[0].children[0].children[3].points ] ).to.be.like( [
 				{ x: 0.13, y: 0.13, e: "three", s: null } ,
@@ -336,4 +381,4 @@ { x: 0.14, y: 0.14, e: "four", s: null } ,
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( tree.trunc.children ).to.be( null ) ;
-			expect( [ ... tree.trunc.points ] ).to.be.like( [
+			expect( tree.trunk.children ).to.be( null ) ;
+			expect( [ ... tree.trunk.points ] ).to.be.like( [
 				{ x: 0.14, y: 0.14, e: "four", s: null } ,
@@ -344,6 +389,6 @@ { x: 0.15, y: 0.15, e: "five", s: null }
 
-		it( "Out of trunc-node BBox should create a new zoomed-out trunc-node" , () => {
+		it( "Out of trunk-node BBox should create a new zoomed-out trunk-node" , () => {
 			var tree , i , point , leaf ;
 			
-			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 } ) ;
+			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 , autoResize: true } ) ;
 			
@@ -356,7 +401,7 @@ tree.add( 0.11 , 0.11 , "one" ) ;
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].points ] ).to.be.like( [
 				{ x: 0.11, y: 0.11, e: "one", s: null } ,
 				{ x: 0.12, y: 0.12, e: "two", s: null }
 			] ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[3].points ] ).to.be.like( [
 				{ x: 0.13, y: 0.13, e: "three", s: null } ,
@@ -370,7 +415,7 @@ { x: 0.14, y: 0.14, e: "four", s: null } ,
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].children[0].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].children[0].points ] ).to.be.like( [
 				{ x: 0.11, y: 0.11, e: "one", s: null } ,
 				{ x: 0.12, y: 0.12, e: "two", s: null }
 			] ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].children[3].points ] ).to.be.like( [
 				{ x: 0.13, y: 0.13, e: "three", s: null } ,
@@ -380,3 +425,3 @@ { x: 0.14, y: 0.14, e: "four", s: null } ,
 			] ) ;
-			expect( [ ... tree.trunc.children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[3].points ] ).to.be.like( [
 				{ x: 1.2, y: 1.2, e: "out-one", s: null }
@@ -387,3 +432,3 @@ ] ) ;
 			// Force a double zoom-out
-			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 } ) ;
+			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 , autoResize: true } ) ;
 			
@@ -397,7 +442,7 @@ tree.add( 0.11 , 0.11 , "one" ) ;
 			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].children[0].children[0].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].children[0].children[0].points ] ).to.be.like( [
 				{ x: 0.11, y: 0.11, e: "one", s: null } ,
 				{ x: 0.12, y: 0.12, e: "two", s: null }
 			] ) ;
-			expect( [ ... tree.trunc.children[0].children[0].children[0].children[0].children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[0].children[0].children[0].children[0].children[3].points ] ).to.be.like( [
 				{ x: 0.13, y: 0.13, e: "three", s: null } ,
@@ -407,5 +452,50 @@ { x: 0.14, y: 0.14, e: "four", s: null } ,
 			] ) ;
-			expect( [ ... tree.trunc.children[3].points ] ).to.be.like( [
+			expect( [ ... tree.trunk.children[3].points ] ).to.be.like( [
 				{ x: 2.2, y: 2.2, e: "out-one", s: null }
 			] ) ;
+
+
+			// Translate trunk BBox when the first item to be inserted is out of bounds
+			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 , autoResize: true } ) ;
+			
+			tree.add( 2.2 , 2.2 , "out-one" ) ;
+			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
+			expect( tree.x ).to.be( 2 ) ;
+			expect( tree.y ).to.be( 2 ) ;
+			expect( tree.areaSize ).to.be( 1 ) ;
+			expect( [ ... tree.trunk.points ] ).to.be.like( [
+				{ x: 2.2, y: 2.2, e: "out-one", s: null }
+			] ) ;
+
+			tree.add( 2.2 , 2.3 , "out-two" ) ;
+			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
+			expect( tree.x ).to.be( 2 ) ;
+			expect( tree.y ).to.be( 2 ) ;
+			expect( tree.areaSize ).to.be( 1 ) ;
+			expect( [ ... tree.trunk.points ] ).to.be.like( [
+				{ x: 2.2, y: 2.2, e: "out-one", s: null } ,
+				{ x: 2.2, y: 2.3, e: "out-two", s: null }
+			] ) ;
+
+			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 , autoResize: true } ) ;
+			
+			tree.add( -0.3 , 0.4 , "out-one" ) ;
+			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
+			expect( tree.x ).to.be( -1 ) ;
+			expect( tree.y ).to.be( 0 ) ;
+			expect( tree.areaSize ).to.be( 1 ) ;
+			expect( [ ... tree.trunk.points ] ).to.be.like( [
+				{ x: -0.3, y: 0.4, e: "out-one", s: null }
+			] ) ;
+
+			tree = new QuadTree( { maxLeafPoints: 4 , minLeafPoints: 2 , minChildrenPoints: 3 , autoResize: true } ) ;
+			
+			tree.add( 12.3 , 0.4 , "out-one" ) ;
+			//tree.debugValues() ; console.log( "\n\n------------\n\n" ) ;
+			expect( tree.x ).to.be( 12 ) ;
+			expect( tree.y ).to.be( 0 ) ;
+			expect( tree.areaSize ).to.be( 1 ) ;
+			expect( [ ... tree.trunk.points ] ).to.be.like( [
+				{ x: 12.3, y: 0.4, e: "out-one", s: null }
+			] ) ;
 		} ) ;
@@ -412,0 +502,0 @@ } ) ;

New alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Fixed alerts

Long strings

Supply chain risk

Contains long string literals, which may be a sign of obfuscated or packed code.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

191209

2.7%

Lines of code

4781

2.42%

Worsened metrics

Number of low supply chain risk alerts

6

20%

Dependency changes

• Updated

  array-kit@^0.2.4