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