@Test public void testMergingConcurrency() throws TimeoutException { rootQuad = new ConcurrentRegionQuadTree<CollisionBox>(CONCURRENCY_TEST_ELEMENT_LIMIT, CONCURRENCY_TEST_WATERMARK, 0, 0, CONCURRENCY_TREE_WIDTH, CONCURRENCY_TREE_HEIGHT); List<CollisionBox> initialCollisions = new ArrayList<CollisionBox>(); for (int i = 0; i < MathUtils.round(CONCURRENCY_TREE_WIDTH / CONCURRENCY_TEST_ELEMENT_LIMIT); i++) { createNextConcurrencyCollision(initialCollisions); createRandomConcurrencyCollision(initialCollisions); } Collections.shuffle(initialCollisions); threadCollisions.addAll(initialCollisions); int totalThreads = Runtime.getRuntime().availableProcessors(); while (totalThreads % 3 != 0) { totalThreads++; } for (int i = 0; i < totalThreads; i++) { new Thread(this).start(); } concurrentTestStartLatch.countDown(); waiter.await(CONCURRENCY_TEST_TIMEOUT); System.out.println(rootQuad.getTotalMergeOperations() + " total merge operations."); System.out.println(collisionsFound.get() + " collisions found concurrently."); System.out.println(collisionsMoved.get() + " collisions moved concurrently."); Assert.assertEquals(true, rootQuad.getTotalMergeOperations() > 0); Assert.assertEquals(true, collisionsFound.get() > 0); Assert.assertEquals(true, collisionsMoved.get() > 0); Assert.assertEquals(false, concurrencyExceptionOccurred.get()); }
@Override public void addAll(Array<T> elements) { if (elements == null || elements.size == 0) return; Array<T> elementsWithinQuad = new Array<T>(); for(T element : elements) { if (this.contains(element) || this.intersects(element)) { elementsWithinQuad.add(element); } } clearTotalElementsCache(); lock.lockWrite(); if(topLeft != null) { lock.lockRead(); lock.unlockWrite(); for(int i = elementsWithinQuad.size - 1; i >= 0; i--) { T element = elementsWithinQuad.get(i); if (topLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (topRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } } lock.unlockRead(); if(elementsWithinQuad.size == 0) { return; } lock.lockWrite(); } this.elements.addAll(elementsWithinQuad); for(T element : elementsWithinQuad) { element.addPostionChangeListener(this); } int totalElements = this.elements.size; lock.unlockWrite(); if (totalElements > elementLimitPerQuad && getWidth() >= 2f && getHeight() >= 2f) { subdivide(); } }
ConcurrentRegionQuadTree extends ConcurrentPointQuadTree<T> { @Override public void addAll(Array<T> elements) { if (elements == null || elements.size == 0) return; Array<T> elementsWithinQuad = new Array<T>(); for(T element : elements) { if (this.contains(element) || this.intersects(element)) { elementsWithinQuad.add(element); } } clearTotalElementsCache(); lock.lockWrite(); if(topLeft != null) { lock.lockRead(); lock.unlockWrite(); for(int i = elementsWithinQuad.size - 1; i >= 0; i--) { T element = elementsWithinQuad.get(i); if (topLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (topRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } } lock.unlockRead(); if(elementsWithinQuad.size == 0) { return; } lock.lockWrite(); } this.elements.addAll(elementsWithinQuad); for(T element : elementsWithinQuad) { element.addPostionChangeListener(this); } int totalElements = this.elements.size; lock.unlockWrite(); if (totalElements > elementLimitPerQuad && getWidth() >= 2f && getHeight() >= 2f) { subdivide(); } } }
ConcurrentRegionQuadTree extends ConcurrentPointQuadTree<T> { @Override public void addAll(Array<T> elements) { if (elements == null || elements.size == 0) return; Array<T> elementsWithinQuad = new Array<T>(); for(T element : elements) { if (this.contains(element) || this.intersects(element)) { elementsWithinQuad.add(element); } } clearTotalElementsCache(); lock.lockWrite(); if(topLeft != null) { lock.lockRead(); lock.unlockWrite(); for(int i = elementsWithinQuad.size - 1; i >= 0; i--) { T element = elementsWithinQuad.get(i); if (topLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (topRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } } lock.unlockRead(); if(elementsWithinQuad.size == 0) { return; } lock.lockWrite(); } this.elements.addAll(elementsWithinQuad); for(T element : elementsWithinQuad) { element.addPostionChangeListener(this); } int totalElements = this.elements.size; lock.unlockWrite(); if (totalElements > elementLimitPerQuad && getWidth() >= 2f && getHeight() >= 2f) { subdivide(); } } ConcurrentRegionQuadTree(int elementLimit, int mergeWatermark, float x, float y, float width, float height);  ConcurrentRegionQuadTree(int elementLimit, float x, float y, float width, float height);  ConcurrentRegionQuadTree(ConcurrentRegionQuadTree<T> parent, float x, float y, float width, float height);  ConcurrentRegionQuadTree(float minimumQuadWidth, float minimumQuadHeight, int elementLimitPerQuad,
			int mergeWatermark, float x, float y, float width, float height); }
ConcurrentRegionQuadTree extends ConcurrentPointQuadTree<T> { @Override public void addAll(Array<T> elements) { if (elements == null || elements.size == 0) return; Array<T> elementsWithinQuad = new Array<T>(); for(T element : elements) { if (this.contains(element) || this.intersects(element)) { elementsWithinQuad.add(element); } } clearTotalElementsCache(); lock.lockWrite(); if(topLeft != null) { lock.lockRead(); lock.unlockWrite(); for(int i = elementsWithinQuad.size - 1; i >= 0; i--) { T element = elementsWithinQuad.get(i); if (topLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (topRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } } lock.unlockRead(); if(elementsWithinQuad.size == 0) { return; } lock.lockWrite(); } this.elements.addAll(elementsWithinQuad); for(T element : elementsWithinQuad) { element.addPostionChangeListener(this); } int totalElements = this.elements.size; lock.unlockWrite(); if (totalElements > elementLimitPerQuad && getWidth() >= 2f && getHeight() >= 2f) { subdivide(); } } ConcurrentRegionQuadTree(int elementLimit, int mergeWatermark, float x, float y, float width, float height);  ConcurrentRegionQuadTree(int elementLimit, float x, float y, float width, float height);  ConcurrentRegionQuadTree(ConcurrentRegionQuadTree<T> parent, float x, float y, float width, float height);  ConcurrentRegionQuadTree(float minimumQuadWidth, float minimumQuadHeight, int elementLimitPerQuad,
			int mergeWatermark, float x, float y, float width, float height); @Override void debugRender(Graphics g); @Override void addAll(Array<T> elements); @Override boolean add(T element); @Override void removeAll(Array<T> elementsToRemove); @Override boolean remove(T element); @Override void getElementsWithinArea(Array<T> result, Shape area); @Override void getElementsWithinArea(Array<T> result, Shape area, QuadTreeSearchDirection searchDirection); @Override Array<T> getElementsContainingArea(Shape area, boolean entirelyContained); @Override Array<T> getElementsContainingArea(Shape area, QuadTreeSearchDirection searchDirection, boolean entirelyContained); @Override void getElementsContainingArea(Array<T> result, Shape area, boolean entirelyContained); @Override void getElementsContainingArea(Array<T> result, Shape area, QuadTreeSearchDirection searchDirection, boolean entirelyContained); @Override void getElementsContainingPoint(Array<T> result, Point point); @Override void getElementsContainingPoint(Array<T> result, Point point, QuadTreeSearchDirection searchDirection); @Override void getElementsIntersectingLineSegment(Array<T> result, LineSegment lineSegment); @Override void getElementsIntersectingLineSegment(Array<T> result, LineSegment lineSegment, QuadTreeSearchDirection searchDirection); @Override Array<T> getElements(); @Override void getElements(Array<T> result); @Override int getTotalElements(); @Override void positionChanged(T moved); }
ConcurrentRegionQuadTree extends ConcurrentPointQuadTree<T> { @Override public void addAll(Array<T> elements) { if (elements == null || elements.size == 0) return; Array<T> elementsWithinQuad = new Array<T>(); for(T element : elements) { if (this.contains(element) || this.intersects(element)) { elementsWithinQuad.add(element); } } clearTotalElementsCache(); lock.lockWrite(); if(topLeft != null) { lock.lockRead(); lock.unlockWrite(); for(int i = elementsWithinQuad.size - 1; i >= 0; i--) { T element = elementsWithinQuad.get(i); if (topLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (topRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomLeft.add(element)) { elementsWithinQuad.removeIndex(i); continue; } if (bottomRight.add(element)) { elementsWithinQuad.removeIndex(i); continue; } } lock.unlockRead(); if(elementsWithinQuad.size == 0) { return; } lock.lockWrite(); } this.elements.addAll(elementsWithinQuad); for(T element : elementsWithinQuad) { element.addPostionChangeListener(this); } int totalElements = this.elements.size; lock.unlockWrite(); if (totalElements > elementLimitPerQuad && getWidth() >= 2f && getHeight() >= 2f) { subdivide(); } } ConcurrentRegionQuadTree(int elementLimit, int mergeWatermark, float x, float y, float width, float height);  ConcurrentRegionQuadTree(int elementLimit, float x, float y, float width, float height);  ConcurrentRegionQuadTree(ConcurrentRegionQuadTree<T> parent, float x, float y, float width, float height);  ConcurrentRegionQuadTree(float minimumQuadWidth, float minimumQuadHeight, int elementLimitPerQuad,
			int mergeWatermark, float x, float y, float width, float height); @Override void debugRender(Graphics g); @Override void addAll(Array<T> elements); @Override boolean add(T element); @Override void removeAll(Array<T> elementsToRemove); @Override boolean remove(T element); @Override void getElementsWithinArea(Array<T> result, Shape area); @Override void getElementsWithinArea(Array<T> result, Shape area, QuadTreeSearchDirection searchDirection); @Override Array<T> getElementsContainingArea(Shape area, boolean entirelyContained); @Override Array<T> getElementsContainingArea(Shape area, QuadTreeSearchDirection searchDirection, boolean entirelyContained); @Override void getElementsContainingArea(Array<T> result, Shape area, boolean entirelyContained); @Override void getElementsContainingArea(Array<T> result, Shape area, QuadTreeSearchDirection searchDirection, boolean entirelyContained); @Override void getElementsContainingPoint(Array<T> result, Point point); @Override void getElementsContainingPoint(Array<T> result, Point point, QuadTreeSearchDirection searchDirection); @Override void getElementsIntersectingLineSegment(Array<T> result, LineSegment lineSegment); @Override void getElementsIntersectingLineSegment(Array<T> result, LineSegment lineSegment, QuadTreeSearchDirection searchDirection); @Override Array<T> getElements(); @Override void getElements(Array<T> result); @Override int getTotalElements(); @Override void positionChanged(T moved);  }