001/* 002 * BioJava development code 003 * 004 * This code may be freely distributed and modified under the 005 * terms of the GNU Lesser General Public Licence. This should 006 * be distributed with the code. If you do not have a copy, 007 * see: 008 * 009 * http://www.gnu.org/copyleft/lesser.html 010 * 011 * Copyright for this code is held jointly by the individual 012 * authors. These should be listed in @author doc comments. 013 * 014 * For more information on the BioJava project and its aims, 015 * or to join the biojava-l mailing list, visit the home page 016 * at: 017 * 018 * http://www.biojava.org/ 019 * 020 */ 021package org.biojava.nbio.structure.symmetry.geometry; 022 023import javax.vecmath.Point3d; 024import java.util.*; 025 026/** 027 * 028 * @author Peter 029 */ 030public class DistanceBox<T> { 031 private Map<Long, List<T>> map; 032 private Map<Long, List<T>> layerMap; 033 private boolean modified; 034 private double inverseBinWidth; 035 // relative locations of 26 boxes surrounding a box at (0, 0, 0) 036 private static final long[] offset = new long[] { 037 0 + ( 0 * 10000) + ( 0 * 1000000000L), 038 -1 + (-1 * 10000) + (-1 * 1000000000L), 039 -1 + (-1 * 10000) + ( 0 * 1000000000L), 040 -1 + (-1 * 10000) + ( 1 * 1000000000L), 041 -1 + ( 0 * 10000) + (-1 * 1000000000L), 042 -1 + ( 0 * 10000) + ( 0 * 1000000000L), 043 -1 + ( 0 * 10000) + ( 1 * 1000000000L), 044 -1 + ( 1 * 10000) + (-1 * 1000000000L), 045 -1 + ( 1 * 10000) + ( 0 * 1000000000L), 046 -1 + ( 1 * 10000) + ( 1 * 1000000000L), 047 0 + (-1 * 10000) + (-1 * 1000000000L), 048 0 + (-1 * 10000) + ( 0 * 1000000000L), 049 0 + (-1 * 10000) + ( 1 * 1000000000L), 050 0 + ( 0 * 10000) + (-1 * 1000000000L), 051 0 + ( 0 * 10000) + ( 1 * 1000000000L), 052 0 + ( 1 * 10000) + (-1 * 1000000000L), 053 0 + ( 1 * 10000) + ( 0 * 1000000000L), 054 0 + ( 1 * 10000) + ( 1 * 1000000000L), 055 1 + (-1 * 10000) + (-1 * 1000000000L), 056 1 + (-1 * 10000) + ( 0 * 1000000000L), 057 1 + (-1 * 10000) + ( 1 * 1000000000L), 058 1 + ( 0 * 10000) + (-1 * 1000000000L), 059 1 + ( 0 * 10000) + ( 0 * 1000000000L), 060 1 + ( 0 * 10000) + ( 1 * 1000000000L), 061 1 + ( 1 * 10000) + (-1 * 1000000000L), 062 1 + ( 1 * 10000) + ( 0 * 1000000000L), 063 1 + ( 1 * 10000) + ( 1 * 1000000000L) 064 }; 065 066 private List<T> tempBox = new ArrayList<T>(offset.length); 067 068 /** Creates a new instance of DistanceBox */ 069 public DistanceBox(double binWidth) { 070 map = new HashMap<Long, List<T>>(); 071 layerMap = new HashMap<Long, List<T>>(); 072 this.inverseBinWidth = 1.0f/binWidth; 073 this.modified = true; 074 } 075 076 public void addPoint(Point3d point, T object) { 077 long i = (long) StrictMath.rint(point.x * inverseBinWidth); 078 long j = (long) StrictMath.rint(point.y * inverseBinWidth); 079 long k = (long) StrictMath.rint(point.z * inverseBinWidth); 080 long location = i + (j * 10000L) + (k * 1000000000L); 081 082 List<T> box = map.get(location); 083 084 if (box == null) { 085 box = new ArrayList<T>(); 086 map.put(location, box); 087 } 088 089 box.add(object); 090 modified = true; 091 } 092 093 public List<T> getNeighborsWithCache(Point3d point) { 094 if (modified) { 095 layerMap.clear(); 096 modified = false; 097 } 098 099 long i = (long) StrictMath.rint(point.x * inverseBinWidth); 100 long j = (long) StrictMath.rint(point.y * inverseBinWidth); 101 long k = (long) StrictMath.rint(point.z * inverseBinWidth); 102 long location = i + (j * 10000L) + (k * 1000000000L); 103 104 List<T> box = layerMap.get(location); 105 106 if (box == null) { 107 box = getBoxTwo(location); 108 layerMap.put(location, box); 109 } 110 111 return box; 112 } 113 114 public List<T> getNeighbors(Point3d point) { 115 if (modified) { 116 layerMap.clear(); 117 modified = false; 118 } 119 120 long i = (long) StrictMath.rint(point.x * inverseBinWidth); 121 long j = (long) StrictMath.rint(point.y * inverseBinWidth); 122 long k = (long) StrictMath.rint(point.z * inverseBinWidth); 123 long location = i + (j * 10000L) + (k * 1000000000L); 124 125 List<T> box = getBoxTwo(location); 126 return box; 127 } 128 129 public List<T> getIntersection(DistanceBox<T> distanceBox) { 130 List<T> intersection = new ArrayList<T>(); 131 HashSet<Long> checkedLocations = new HashSet<Long>(); 132 133 for (Iterator<Long> iter = map.keySet().iterator(); iter.hasNext();) { 134 long location = iter.next(); 135 boolean overlap = false; 136 for (int i = 0, n = offset.length; i < n; i++) { 137 long loc = location + offset[i]; 138 if (distanceBox.contains(loc)) { 139 overlap = true; 140 break; 141 } 142 } 143 if (overlap) { 144 for (int i = 0, n = offset.length; i < n; i++) { 145 long loc = location + offset[i]; 146 if (checkedLocations.contains(loc)) 147 continue; 148 149 checkedLocations.add(loc); 150 if (contains(loc)) { 151 intersection.addAll(map.get(loc)); 152 } 153 } 154 } 155 } 156 return intersection; 157 } 158 159 private List<T> getBoxTwo(long location) { 160 tempBox.clear(); 161 for (int i = 0, n = offset.length; i < n; i++) { 162 List<T> box = map.get(location + offset[i]); 163 if (box != null) { 164 tempBox.addAll(box); 165 } 166 } 167 // ensure that boxTwo has no empty element by copying from tempBox of defined size 168 List<T> boxTwo = null; 169 if (tempBox.size() == 0) { 170 boxTwo = Collections.emptyList(); 171 } else if (tempBox.size() == 1) { 172 boxTwo = Collections.singletonList(tempBox.get(0)); 173 } else { 174 boxTwo = new ArrayList<T>(tempBox); 175 } 176 return boxTwo; 177 } 178 179 private boolean contains(long location) { 180 return map.containsKey(location); 181 } 182}