import java.lang.Math; import java.util.*; class PointTree { public PointTree( double left, double top, double right, double bottom, PointTree parent ) { this.point = null; this.subTrees = null; this.parent = parent; this.left = left; this.top = top; this.right = right; this.bottom = bottom; this.horizontalMid = (this.left + this.right) / 2; this.verticalMid = (this.bottom + this.top) / 2; } public void subAdd( Positioned added ) { Point addedPos = added.getPos(); if ( addedPos.getX() < horizontalMid && addedPos.getY() < verticalMid ) subTrees[0].add( added ); else if ( addedPos.getX() > horizontalMid && addedPos.getY() < verticalMid ) subTrees[1].add( added ); else if ( addedPos.getX() < horizontalMid && addedPos.getY() > verticalMid ) subTrees[2].add( added ); else if ( addedPos.getX() > horizontalMid && addedPos.getY() > verticalMid ) subTrees[3].add( added ); } public void add( Positioned added ) { Point addedPos = added.getPos(); if ( subTrees != null ) { subAdd( added ); } else if ( point == null ) { this.point = added; } else { Point currPos = this.point.getPos(); if ( Math.abs( addedPos.getX() - currPos.getX() ) < 0.001 && Math.abs( addedPos.getY() - currPos.getY() ) < 0.001 ) { return; } else { PointTree lt = new PointTree( left, top, horizontalMid, verticalMid, this ); PointTree rt = new PointTree( horizontalMid, top, right, verticalMid, this ); PointTree lb = new PointTree( left, verticalMid, horizontalMid, bottom, this ); PointTree rb = new PointTree( horizontalMid, verticalMid, right, bottom, this ); subTrees = new PointTree[4]; subTrees[0] = lt; subTrees[1] = rt; subTrees[2] = lb; subTrees[3] = rb; subAdd( point ); subAdd( added ); point = null; } } } public boolean isEmpty() { return subTrees == null && point == null; } public boolean isNode() { return subTrees == null; } public void contract() { int empties = 0; PointTree notEmpty = null; if ( subTrees[0].isEmpty() ) empties++; else notEmpty = subTrees[0]; if ( subTrees[1].isEmpty() ) empties++; else notEmpty = subTrees[1]; if ( subTrees[2].isEmpty() ) empties++; else notEmpty = subTrees[2]; if ( subTrees[3].isEmpty() ) empties++; else notEmpty = subTrees[3]; if ( empties == 4 ) { subTrees = null; if (parent != null) parent.contract(); } else if ( empties == 3 ) { if ( notEmpty.isNode() ) { point = notEmpty.point; subTrees = null; } } } public void subRem( Positioned remed ) { Point remedPos = remed.getPos(); if ( remedPos.getX() < horizontalMid && remedPos.getY() < verticalMid ) subTrees[0].rem( remed ); else if ( remedPos.getX() > horizontalMid && remedPos.getY() < verticalMid ) subTrees[1].rem( remed ); else if ( remedPos.getX() < horizontalMid && remedPos.getY() > verticalMid ) subTrees[2].rem( remed ); else if ( remedPos.getX() > horizontalMid && remedPos.getY() > verticalMid ) subTrees[3].rem( remed ); } public void rem( Positioned remed ) { Point remedPos = remed.getPos(); if ( subTrees != null ) { subRem( remed ); } else if ( point == null ) { // can't find (LOL) point to remove lolz } else if ( point == remed ) { point = null; parent.contract(); } else { // nothing founds xxxxxxxD } } public int inWhich( Positioned point ) { Point pointPos = point.getPos(); if ( pointPos.getX() < horizontalMid && pointPos.getY() < verticalMid ) return 0; if ( pointPos.getX() >= horizontalMid && pointPos.getY() < verticalMid ) return 1; if ( pointPos.getX() < horizontalMid && pointPos.getY() >= verticalMid ) return 2; if ( pointPos.getX() >= horizontalMid && pointPos.getY() >= verticalMid ) return 3; return -1; } public ArrayList getAll() { ArrayList ret = new ArrayList(); if ( subTrees == null ) { if ( point != null ) ret.add( point ); } else { for ( PointTree subTree : subTrees ) { ret.addAll( subTree.getAll() ); } } return ret; } public PointTree getSubTree( int subTreeIdx ) { if ( subTrees == null ) { return this; } else return subTrees[subTreeIdx]; } public PointTree getParent() { if ( parent == null ) return this; else return parent; } public PointTree[] getSubTrees() { return subTrees; } public int oppositeOf( int dir ) { return 3 - dir; } // find the submost PointTrees public ArrayList closestOnes( Positioned searched, PointTree[] pieces, int containedIdx ) { Point searchedPos = searched.getPos(); System.out.println( toString() ); System.out.println( "" ); System.out.println( "" ); System.out.println( "" ); while ( pieces[ containedIdx ].subTrees != null ) { System.out.println( pieces[ containedIdx ].toString() ); System.out.println( pieces[ containedIdx ].left ); System.out.println( pieces[ containedIdx ].top ); System.out.println( pieces[ containedIdx ].right ); System.out.println( pieces[ containedIdx ].bottom ); int nextSubIdx = pieces[ containedIdx ].inWhich( searched ); System.out.println( containedIdx ); System.out.println( nextSubIdx ); System.out.println( "" ); System.out.println( "" ); System.out.println( "" ); // going the opposite direction as last if ( nextSubIdx == oppositeOf( containedIdx ) ) { for ( int i = 0; i < 4; i++ ) { pieces[i] = pieces[i].getSubTree(i); } //containedIdx = oppositeOf( containedIdx ); // going deeper in the previous direction } else if ( nextSubIdx == containedIdx ) { System.out.println("ooookokokoko"); pieces = getParent().getSubTrees(); pieces[0] = pieces[0].getSubTree( 3 ); pieces[1] = pieces[1].getSubTree( 2 ); pieces[2] = pieces[2].getSubTree( 1 ); pieces[3] = pieces[3].getSubTree( 0 ); containedIdx = oppositeOf( containedIdx ); } else { System.out.println( ";;)"); // separately handle the other 8 cases :DD if ( nextSubIdx == 1 && containedIdx == 0 ) { // p[0].ur, p[0].par.ur.lr, p[1].par.ul.ll, p[1].ul PointTree a = pieces[0].getSubTree( 1 ); PointTree b = pieces[0].getParent().getSubTree(1).getSubTree(3); PointTree c = pieces[1].getParent().getSubTree(0).getSubTree(2); PointTree d = pieces[1].getSubTree(0); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 2 && containedIdx == 0 ) { // p[0].ll, p[0].par.ll.lr, p[2].par.ul.ur, p[2].ul PointTree a = pieces[0].getSubTree( 2 ); PointTree b = pieces[0].getParent().getSubTree(2).getSubTree(3); PointTree c = pieces[2].getParent().getSubTree(0).getSubTree(1); PointTree d = pieces[2].getSubTree(0); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 0 && containedIdx == 1 ) { // p[1].ul, p[1].par.ul.ll, p[0].par.ur.lr, p[0].ur PointTree a = pieces[1].getSubTree( 0 ); PointTree b = pieces[1].getParent().getSubTree(0).getSubTree(2); PointTree c = pieces[0].getParent().getSubTree(1).getSubTree(3); PointTree d = pieces[0].getSubTree(1); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 3 && containedIdx == 1 ) { // p[1].lr, p[1].par.lr.ll, p[3].par.ur.ul, p[3].ur PointTree a = pieces[1].getSubTree( 3 ); PointTree b = pieces[1].getParent().getSubTree(3).getSubTree(2); PointTree c = pieces[3].getParent().getSubTree(1).getSubTree(0); PointTree d = pieces[3].getSubTree(1); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 0 && containedIdx == 2 ) { // p[2].ul, p[2].par.ul.ur, p[0].par.ll.lr, p[0].ll PointTree a = pieces[2].getSubTree( 0 ); PointTree b = pieces[2].getParent().getSubTree(0).getSubTree(1); PointTree c = pieces[0].getParent().getSubTree(2).getSubTree(3); PointTree d = pieces[0].getSubTree(2); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 3 && containedIdx == 2 ) { // p[2].lr, p[2].par.lr.ur, p[3].par.ll.ul, p[3].ll PointTree a = pieces[2].getSubTree( 3 ); PointTree b = pieces[2].getParent().getSubTree(3).getSubTree(1); PointTree c = pieces[3].getParent().getSubTree(2).getSubTree(0); PointTree d = pieces[3].getSubTree(2); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 1 && containedIdx == 3 ) { // p[3].ur, p[3].par.ur.ul, p[1].par.lr.ll, p[1].lr PointTree a = pieces[3].getSubTree( 1 ); PointTree b = pieces[3].getParent().getSubTree(1).getSubTree(0); PointTree c = pieces[1].getParent().getSubTree(3).getSubTree(2); PointTree d = pieces[1].getSubTree(3); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } else if ( nextSubIdx == 2 && containedIdx == 3 ) { // p[3].ll, p[3].par.ll.ul, p[2].par.lr.ur, p[2].lr PointTree a = pieces[3].getSubTree( 2 ); PointTree b = pieces[3].getParent().getSubTree(2).getSubTree(0); PointTree c = pieces[2].getParent().getSubTree(3).getSubTree(1); PointTree d = pieces[2].getSubTree(3); pieces[0] = a; pieces[1] = b; pieces[2] = c; pieces[3] = d; } } } ArrayList ret = new ArrayList(); for ( PointTree p : pieces ) { ret.addAll( p.getParent().getAll() ); } return ret; } // return closest from given set of points public Positioned closestOf( Positioned searched, ArrayList points ) { Point searchedPos = searched.getPos(); Point closest = null; double minDistance = -1; for( Positioned point : points ) { Point pointPos = point.getPos(); double distance = pointPos.distanceTo( searchedPos ); if( minDistance<0 || distance closests = closestOnes( searched, subTrees, containedIdx ); System.out.println( closests.toString() ); return closestOf( searched, closests); } } public String toString() { if ( subTrees != null ) { return "{" + subTrees[0].toString() + ", " + subTrees[1].toString() + ", " + subTrees[2].toString() + ", " + subTrees[3].toString() + "}"; } else if ( point != null ) { return point.getPos().toString(); } else { return "*"; } } private Positioned point; private PointTree[] subTrees; private PointTree parent; private double left; private double top; private double right; private double bottom; private double horizontalMid; private double verticalMid; } class Pair implements Comparable { public Pair() { this.car = null; this.cdr = null; } public Pair( CarType car, CdrType cdr ) { this.car = car; this.cdr = cdr; } public int compareTo( Object p ) { return car.compareTo( ((Pair) p).getCar() ); } public void setCar( CarType newValue ) { car = newValue; } public void setCdr( CdrType newValue ) { cdr = newValue; } public CarType getCar() { return car; } public CdrType getCdr() { return cdr; } private CarType car; private CdrType cdr; } // elements are intersperced every class DynamicSortedArray { public DynamicSortedArray(int spaces, int capacity) { this.spaces = spaces; int realCapacity = capacity * ( spaces + 1 ); list = new ArrayList< Pair< K, V > >( realCapacity ); } // find the next non null value to the right public int fixIdx( int idx ) { while ( idx < list.size() && list.get( idx ) == null ) idx++; return idx; } public int fixIdxBackw( int idx ) { while ( idx >= 0 && list.get( idx ) == null ) idx--; return idx; } // fix gaps, they are either too big or too small public void fix() { ArrayList< Pair > newList = new ArrayList< Pair > ( list.size() ); for( int il = 0; il < list.size(); il++) { il = fixIdx( il ); if ( il >= list.size() ) break; for (int is = 0; is < spaces; is++ ) { newList.add( null ); } newList.add( list.get( il ) ); } list = newList; } public void remGaps() { int reali = 0; int puti = 0; while ( reali < list.size() ) { if ( list.get(reali) != null ) { list.set( puti, list.get(reali) ); puti++; } reali++; } } public void sortAndFix() { remGaps(); Object[] sortee = list.toArray(); Arrays.sort( sortee ); list.clear(); for ( Object x : sortee ) { list.add( (Pair)x ); } fix(); } // find rightmost neighbor, the actual position if obj in list, or size of list public int find( K key, int a, int b ) { /* DEBUG: System.out.println( "as" ); System.out.println( a ); System.out.println( b ); System.out.println( this.toString() ); */ if ( a == b) { return a; } else { int midIdx = fixIdx( (a+b)/2 ); if ( midIdx == list.size() ) { fix(); return list.size(); } else if ( midIdx == b ) { Pair valAtA = list.get( a ); if ( valAtA != null && valAtA.getCar().equals( key ) ) return a; return b; } K pivot = list.get( midIdx ).getCar(); int cmp = key.compareTo( pivot ); if ( cmp == 0 ) { return midIdx; } else if ( cmp < 0 ) { return find( key, a, midIdx ); } else if ( cmp > 0 ) { return find( key, midIdx + 1, b ); } return 0; // this is never reached } } public int find( K key ) { if ( list.isEmpty() ) { return 0; } else { return find( key, 0, list.size() ); } } public void rawAdd( K key, V val ) { list.add( new Pair(key, val)); } public void add( K key, V val ) { int idx = find( key ); Pair kvPair = new Pair( key, val ); // DEBUG: System.out.println( idx ); if ( idx >= list.size() ) { for ( int i = 0; i < spaces; i++ ) { list.add( null ); } list.add( kvPair ); } else { if ( list.get( idx - 1 ) == null ) { list.set( idx - 1, kvPair ); } else { // obviously corrupt, so fix all gaps! // DEBUG System.out.println( "kuli..." ); fix(); // retry adding (guaranteed to work this time) add( key, val ); } } } public int size() { return list.size(); } public boolean isEmpty() { return list.isEmpty(); } public V rawGet( int idx ) { return list.get( idx ).getCdr(); } public int exactIdx( K key, V val ) { int idxNext = find( key ); int idxPrev = idxNext; while ( idxNext < list.size() && list.get( idxNext ).getCar().equals( key ) ) { if ( list.get( idxNext ).getCdr().equals( val ) ) { return idxNext; } idxNext = fixIdx( idxNext + 1 ); } while ( idxPrev >= 0 && list.get( idxPrev ).getCar().equals( key ) ) { if ( list.get( idxPrev ).getCdr().equals( val ) ) { return idxPrev; } idxPrev = fixIdxBackw( idxPrev - 1 ); } return -1; } public void rem( K key, V val ) { int idx = exactIdx( key, val ); if ( idx != -1 ) { list.set( idx, null ); maybeFixAt( idx ); } } public void maybeFixAt( int idx ) { boolean leftOkay = false; boolean rightOkay = false; for ( int i = 1; i <= 2*spaces; i++ ) { if ( idx - i < 0 ) leftOkay = true; else if ( list.get( idx - i ) != null ) leftOkay = true; if ( idx + i >= list.size() ) rightOkay = true; else if ( list.get( idx + i ) != null ) rightOkay = true; } if ( !leftOkay || !rightOkay ) fix(); } public String toString() { String ret = ""; for ( Pair i : list ) { if ( i == null ) { ret += "* "; } else { ret += i.getCar().toString() + ":" + i.getCdr().toString() + " "; } } return ret; } private int spaces; private ArrayList< Pair< K, V > > list; } class OrderedStorer { public OrderedStorer ( int spaces, int capacity ) { xAxisLookup = new DynamicSortedArray( spaces, capacity ); yAxisLookup = new DynamicSortedArray( spaces, capacity ); } public void add(Positioned added) { Point addedPos = added.getPos(); xAxisLookup.add( addedPos.getX(), added ); yAxisLookup.add( addedPos.getY(), added ); } public void rawAdd(Positioned added) { Point addedPos = added.getPos(); xAxisLookup.rawAdd( addedPos.getX(), added ); yAxisLookup.rawAdd( addedPos.getY(), added ); } public void sortAndFix() { xAxisLookup.sortAndFix(); yAxisLookup.sortAndFix(); } public void rem(Positioned remed) { Point remedPos = remed.getPos(); xAxisLookup.rem( remedPos.getX(), remed ); yAxisLookup.rem( remedPos.getY(), remed ); } public Positioned closestTo(Positioned searched) { if ( xAxisLookup.isEmpty() ) return null; Point searchedPos = searched.getPos(); int xNext = xAxisLookup.find( searchedPos.getX() ); int xPrev = xAxisLookup.fixIdxBackw( xNext - 1 ); int yNext = yAxisLookup.find( searchedPos.getY() ); int yPrev = yAxisLookup.fixIdxBackw( yNext - 1 ); Positioned closestPoint = xAxisLookup.rawGet( xAxisLookup.fixIdx(0) ); double bestDist = closestPoint.getPos().distanceTo( searchedPos ); Positioned curr = null; double currDist = 0; while ( xPrev >= 0 || xNext < xAxisLookup.size() || yPrev >= 0 || yNext < yAxisLookup.size()) { //System.out.println( currDist ); //System.out.println( bestDist ); //System.out.println( xPrev ); //System.out.println( xNext ); //System.out.println( yPrev ); //System.out.println( yNext ); if ( xPrev >= 0 ) { curr = xAxisLookup.rawGet( xPrev ); currDist = curr.getPos().distanceTo( searchedPos ); if ( currDist < bestDist ) { closestPoint = curr; bestDist = currDist; } else { // the "clever" part, shortcut if too far x-wise if ( Math.abs( searchedPos.getX() - curr.getPos().getX() ) > bestDist) { xPrev = -1; } else { //System.out.println("xprevlol"); //System.out.println( Math.abs( searchedPos.getX() - curr.getPos().getX() ) ); } } xPrev = xAxisLookup.fixIdxBackw( xPrev - 1); } if ( xNext < xAxisLookup.size() ) { curr = xAxisLookup.rawGet( xNext ); currDist = curr.getPos().distanceTo( searchedPos ); if ( currDist < bestDist ) { closestPoint = curr; bestDist = currDist; } else { // the "clever" part, shortcut if too far x-wise if ( Math.abs( searchedPos.getX() - curr.getPos().getX() ) > bestDist) { xNext = xAxisLookup.size(); } else { //System.out.println("xnextlol"); //System.out.println( Math.abs( searchedPos.getX() - curr.getPos().getX() ) ); } } xNext = xAxisLookup.fixIdx( xNext + 1); } if ( yPrev >= 0 ) { curr = yAxisLookup.rawGet( yPrev ); currDist = curr.getPos().distanceTo( searchedPos ); if ( currDist < bestDist ) { closestPoint = curr; bestDist = currDist; } else { // the "clever" part, shortcut if too far y-wise if ( Math.abs( searchedPos.getY() - curr.getPos().getY() ) > bestDist) { yPrev = -1; } else { //System.out.println("yprevlol"); //System.out.println( Math.abs( searchedPos.getY() - curr.getPos().getY() ) ); } } yPrev = yAxisLookup.fixIdxBackw( yPrev - 1); } if ( yNext < yAxisLookup.size() ) { curr = yAxisLookup.rawGet( xNext ); currDist = curr.getPos().distanceTo( searchedPos ); if ( currDist < bestDist ) { closestPoint = curr; bestDist = currDist; } else { // the "clever" part, shortcut if too far y-wise if ( Math.abs( searchedPos.getY() - curr.getPos().getY() ) > bestDist) { yNext = yAxisLookup.size(); } else { //System.out.println("ynextlol"); //System.out.println( Math.abs( searchedPos.getY() - curr.getPos().getY() ) ); } } yNext = yAxisLookup.fixIdx( yNext + 1); } //System.out.println( "" ); } return closestPoint; } public String toString() { return yAxisLookup.toString() + "\n\n" + xAxisLookup.toString(); } DynamicSortedArray xAxisLookup; DynamicSortedArray yAxisLookup; } class Storor { public Storor( double left, double top, double right, double bottom ) { pointTree = new PointTree(left, top, right, bottom, null); orderedStorer = new OrderedStorer( 2, 256 ); } public void add( Positioned p ) { points.add( p ); orderedStorer.add( p ); //pointTree.add( p ); } public void rawAdd( Positioned p ) { points.add( p ); orderedStorer.rawAdd( p ); //pointTree.add( p ); } public void sortAndFix() { orderedStorer.sortAndFix(); } public void rem( Positioned p ) { points.remove( p ); orderedStorer.rem( p ); //pointTree.rem( p ); } public ArrayList getAll() { return points; } public Positioned closestTo( Positioned searched ) { return orderedStorer.closestTo( searched ); // pointTree.closestTo( searched ); } public Positioned slowClosestTo( Positioned searched ) { Point searchedPos = searched.getPos(); Point closest = null; double minDistance = -1; for( Positioned point : points ) { Point pointPos = point.getPos(); double distance = pointPos.distanceTo( searchedPos ); if( minDistance<0 || distance points = new ArrayList(); private PointTree pointTree; private OrderedStorer orderedStorer; // testmain for storer löl :D public static void _main( String[] args ) { DynamicSortedArray d = new DynamicSortedArray( 2, 50 ); // Pair p = new Pair (); d.add( 4.0, "neli" ); d.add( 4.0, "kuli" ); d.add( 4.0, "vili" ); d.add( 4.0, "voli" ); d.add( 4.0, "hili" ); d.add( 4.0, "hali" ); System.out.println( d.toString() ); d.rem( 4.0, "neli" ); System.out.println( d.toString() ); d.rem( 4.0, "kuli" ); System.out.println( d.toString() ); d.rem( 4.0, "voli" ); System.out.println( d.toString() ); } /* 50 x 50 fast takes... 1785 slow takes... 16416 100 x 100 fast takes... 3640 slow takes... 60816 150 x 150 fast takes... 5304 slow takes... 131856 */ public static void main( String[] args ) { Storor s = new Storor( 0, 0, 5, 5 ); for ( int ix = 0; ix < 150; ix++ ) { for ( int iy = 0; iy < 150; iy++ ) { s.rawAdd( new Point( ix, iy ) ); } } System.out.println( "ok" ); s.sortAndFix(); System.out.println( "fof.." ); Random rander = new Random( 1 ); //while ( s.getAll().size() > 100 ) { // int ridx = Math.abs( rander.nextInt() % s.getAll().size() ); // s.rawRem( s.getAll().get( ridx ) ); // System.out.println( s.toString() ); //} System.out.println( "okol" ); //GregorianCalendar timer = ; long time = (new GregorianCalendar()).getTimeInMillis(); System.out.println( "fast takes..." ); for(int i=0;i<1000;i++)s.closestTo( new Point( 32.2, 32.1 )); //System.out.println( (Point)( s.closestTo( new Point( 32.2, 32.1 ) ) ) ); System.out.println( (new GregorianCalendar()).getTimeInMillis() - time ); time = (new GregorianCalendar()).getTimeInMillis(); System.out.println( "slow takes..." ); for(int i=0;i<1000;i++) s.slowClosestTo( new Point( 32.2, 32.1 ) ); System.out.println( (new GregorianCalendar()).getTimeInMillis() - time ); } } interface Positioned { Point getPos(); } class Point implements Positioned { public Point (double x, double y) { this.x=x; this.y=y; } public double getX() { return x; } public double getY() { return y; } public Point getPos() { return this; } public double distanceTo( Point p ) { double xDiff = p.getX() - x; double yDiff = p.getY() - y; return Math.sqrt( xDiff*xDiff + yDiff*yDiff ); } public String toString() { return "("+x+", "+y+")"; } private double x; private double y; }