1 /* Copyright (C) 2011 Jonathan Alvarsson <jonalv@users.sf.net> 2 * 3 * Contact: cdk-devel@lists.sourceforge.net 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public License 7 * as published by the Free Software Foundation; either version 2.1 8 * of the License, or (at your option) any later version. 9 * All we ask is that proper credit is given for our work, which includes 10 * - but is not limited to - adding the above copyright notice to the beginning 11 * of your source code files, and to any copyright notice that you may distribute 12 * with programs based on this work. 13 * 14 * This program is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 * GNU Lesser General Public License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public License 20 * along with this program; if not, write to the Free Software 21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 22 */ 23 package org.openscience.cdk.fingerprint; 24 25 import java.util.ArrayList; 26 import java.util.Arrays; 27 import java.util.BitSet; 28 import java.util.HashSet; 29 import java.util.List; 30 import java.util.Map; 31 import java.util.Set; 32 33 /** 34 * @author jonalv 35 * @cdk.module standard 36 * @cdk.githash 37 */ 38 public class IntArrayFingerprint implements IBitFingerprint { 39 40 /** 41 * 42 */ 43 private static final long serialVersionUID = 5175105019921245323L; 44 private volatile int[] trueBits; 45 IntArrayFingerprint(Map<String, Integer> rawFingerPrint)46 public IntArrayFingerprint(Map<String, Integer> rawFingerPrint) { 47 trueBits = new int[rawFingerPrint.size()]; 48 int i = 0; 49 for (String key : rawFingerPrint.keySet()) { 50 trueBits[i++] = key.hashCode(); 51 } 52 Arrays.sort(trueBits); 53 } 54 IntArrayFingerprint(int[] setBits)55 public IntArrayFingerprint(int[] setBits) { 56 this.trueBits = setBits; 57 } 58 IntArrayFingerprint()59 public IntArrayFingerprint() { 60 trueBits = new int[0]; 61 } 62 IntArrayFingerprint(IBitFingerprint fingerprint)63 public IntArrayFingerprint(IBitFingerprint fingerprint) { 64 // if it is an IntArrayFingerprint we can do faster (System.arraycopy) 65 if (fingerprint instanceof IntArrayFingerprint) { 66 IntArrayFingerprint iaFP = (IntArrayFingerprint) fingerprint; 67 trueBits = new int[iaFP.trueBits.length]; 68 System.arraycopy(iaFP.trueBits, 0, trueBits, 0, trueBits.length); 69 } else { 70 trueBits = new int[fingerprint.cardinality()]; 71 int index = 0; 72 for (int i = 0; i < fingerprint.size(); i++) { 73 if (fingerprint.get(i)) { 74 trueBits[index++] = i; 75 } 76 } 77 } 78 } 79 80 @Override cardinality()81 public int cardinality() { 82 return trueBits.length; 83 } 84 85 @Override size()86 public long size() { 87 return 4294967296L; 88 } 89 90 @Override and(IBitFingerprint fingerprint)91 public void and(IBitFingerprint fingerprint) { 92 if (fingerprint instanceof IntArrayFingerprint) { 93 and((IntArrayFingerprint) fingerprint); 94 } else { 95 //TODO add support for this? 96 throw new UnsupportedOperationException("AND on IntArrayFingerPrint only supported for other " 97 + "IntArrayFingerPrints for the moment"); 98 } 99 } 100 and(IntArrayFingerprint fingerprint)101 public void and(IntArrayFingerprint fingerprint) { 102 List<Integer> tmp = new ArrayList<>(); 103 int i = 0; 104 int j = 0; 105 while (i < trueBits.length && j < fingerprint.trueBits.length) { 106 int local = trueBits[i]; 107 int remote = fingerprint.trueBits[j]; 108 if (local == remote) { 109 tmp.add(local); 110 i++; 111 j++; 112 } else if (local < remote) { 113 i++; 114 } else { 115 j++; 116 } 117 } 118 trueBits = new int[tmp.size()]; 119 i = 0; 120 for (Integer t : tmp) { 121 trueBits[i] = t; 122 } 123 Arrays.sort(trueBits); 124 } 125 126 @Override or(IBitFingerprint fingerprint)127 public void or(IBitFingerprint fingerprint) { 128 if (fingerprint instanceof IntArrayFingerprint) { 129 or((IntArrayFingerprint) fingerprint); 130 } else { 131 //TODO add support for this? 132 throw new UnsupportedOperationException("OR on IntArrayFingerPrint only supported for other " 133 + "IntArrayFingerPrints for the moment"); 134 } 135 } 136 or(IntArrayFingerprint fingerprint)137 public void or(IntArrayFingerprint fingerprint) { 138 Set<Integer> tmp = new HashSet<>(); 139 for (int trueBit : trueBits) { 140 tmp.add(trueBit); 141 } 142 for (int i = 0; i < fingerprint.trueBits.length; i++) { 143 tmp.add(fingerprint.trueBits[i]); 144 } 145 trueBits = new int[tmp.size()]; 146 int i = 0; 147 for (Integer t : tmp) { 148 trueBits[i++] = t; 149 } 150 Arrays.sort(trueBits); 151 } 152 153 @Override get(int index)154 public boolean get(int index) { 155 return (Arrays.binarySearch(trueBits, index) >= 0); 156 } 157 158 /* 159 * This method is VERY INNEFICIENT when called multiple times. It is the 160 * cost of keeping down the memory footprint. Avoid using it for building up 161 * IntArrayFingerprints -- instead use the constructor taking a so called 162 * raw fingerprint. 163 */ 164 @Override set(int index, boolean value)165 public void set(int index, boolean value) { 166 int i = Arrays.binarySearch(trueBits, index); 167 // bit at index is set to true and shall be set to false 168 if (i >= 0 && !value) { 169 int[] tmp = new int[trueBits.length - 1]; 170 System.arraycopy(trueBits, 0, tmp, 0, i); 171 System.arraycopy(trueBits, i + 1, tmp, i, trueBits.length - i - 1); 172 trueBits = tmp; 173 } 174 // bit at index is set to false and shall be set to true 175 else if (i < 0 && value) { 176 int[] tmp = new int[trueBits.length + 1]; 177 System.arraycopy(trueBits, 0, tmp, 0, trueBits.length); 178 tmp[tmp.length - 1] = index; 179 trueBits = tmp; 180 Arrays.sort(trueBits); 181 } 182 } 183 184 @Override asBitSet()185 public BitSet asBitSet() { 186 //TODO support this? 187 throw new UnsupportedOperationException(); 188 } 189 190 @Override set(int i)191 public void set(int i) { 192 set(i, true); 193 } 194 195 @Override hashCode()196 public int hashCode() { 197 return Arrays.hashCode(trueBits); 198 } 199 200 @Override equals(Object obj)201 public boolean equals(Object obj) { 202 if (this == obj) return true; 203 if (obj == null) return false; 204 if (getClass() != obj.getClass()) return false; 205 IntArrayFingerprint other = (IntArrayFingerprint) obj; 206 if (!Arrays.equals(trueBits, other.trueBits)) return false; 207 return true; 208 } 209 210 @Override getSetbits()211 public int[] getSetbits() { 212 int[] copy = new int[trueBits.length]; 213 System.arraycopy(trueBits, 0, copy, 0, trueBits.length); 214 return copy; 215 } 216 217 } 218