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}