1 /* 2 * Copyright (c) 2013 John May <jwmay@users.sf.net> 3 * 4 * Contact: cdk-devel@lists.sourceforge.net 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU Lesser General Public License 8 * as published by the Free Software Foundation; either version 2.1 9 * of the License, or (at your option) any later version. 10 * All we ask is that proper credit is given for our work, which includes 11 * - but is not limited to - adding the above copyright notice to the beginning 12 * of your source code files, and to any copyright notice that you may distribute 13 * with programs based on this work. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License for more details. 19 * 20 * You should have received a copy of the GNU Lesser General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 U 23 */ 24 25 package org.openscience.cdk.hash; 26 27 import org.openscience.cdk.interfaces.IAtomContainer; 28 import org.openscience.cdk.interfaces.IBond; 29 30 import java.util.Arrays; 31 32 /** 33 * An abstract hash function providing several utility methods to be used by 34 * other hashing functions. 35 * 36 * @author John May 37 * @cdk.module hash 38 * @cdk.githash 39 */ 40 class AbstractHashGenerator { 41 42 /* pseudorandom number generator */ 43 private final Pseudorandom pseudorandom; 44 45 /** 46 * Construct an abstract hash function providing the pseudorandom number 47 * generator. 48 * 49 * @param pseudorandom a pseudorandom number generator 50 * @throws NullPointerException the pseudorandom number generator was null 51 */ AbstractHashGenerator(Pseudorandom pseudorandom)52 public AbstractHashGenerator(Pseudorandom pseudorandom) { 53 if (pseudorandom == null) throw new NullPointerException("null pseduorandom number generator provided"); 54 this.pseudorandom = pseudorandom; 55 } 56 57 /** 58 * Create a copy of the array of long values. 59 * 60 * @param src original values 61 * @return copy of the original values 62 * @see Arrays#copyOf(long[], int) 63 */ copy(long[] src)64 static long[] copy(long[] src) { 65 return Arrays.copyOf(src, src.length); 66 } 67 68 /** 69 * Copy the values from the source (src) array to the destination (dest). 70 * 71 * @param src source values 72 * @param dest destination of the source copy 73 * @see System#arraycopy(Object, int, Object, int, int); 74 */ copy(long[] src, long[] dest)75 static void copy(long[] src, long[] dest) { 76 System.arraycopy(src, 0, dest, 0, dest.length); 77 } 78 79 /** 80 * Generate the next random number. 81 * 82 * @param seed a {@literal long} value to seed a pseudorandom number 83 * generator 84 * @return next pseudorandom number 85 */ rotate(long seed)86 long rotate(long seed) { 87 return pseudorandom.next(seed); 88 } 89 90 /** 91 * Rotate a <i>value</i>, <i>n</i> times. The rotation uses a pseudorandom 92 * number generator to sequentially generate values seed on the previous 93 * value. 94 * 95 * @param value the {@literal long} value to rotate 96 * @param n the number of times to rotate the value 97 * @return the {@literal long} value rotated the specified number of times 98 */ rotate(long value, int n)99 long rotate(long value, int n) { 100 while (n-- > 0) 101 value = pseudorandom.next(value); 102 return value; 103 } 104 105 /** 106 * Returns the value of the lowest three bits. This value is between 0 and 7 107 * inclusive. 108 * 109 * @param value a {@literal long} value 110 * @return the {@literal int} value of the lowest three bits. 111 */ lowestThreeBits(long value)112 static int lowestThreeBits(long value) { 113 return (int) (value & 0x7); 114 } 115 116 /** 117 * Distribute the provided value across the set of {@literal long} values. 118 * 119 * @param value a {@literal long} value to distribute 120 * @return the {@literal long} value distributed a set amount 121 */ distribute(long value)122 long distribute(long value) { 123 // rotate 1-8 times 124 return rotate(value, 1 + lowestThreeBits(value)); 125 } 126 127 /** 128 * Convert an IAtomContainer to an adjacency list. 129 * 130 * @param container the container to convert 131 * @return adjacency list representation 132 */ toAdjList(IAtomContainer container)133 static int[][] toAdjList(IAtomContainer container) { 134 135 if (container == null) throw new IllegalArgumentException("atom container was null"); 136 137 int n = container.getAtomCount(); 138 139 int[][] graph = new int[n][16]; 140 int[] degree = new int[n]; 141 142 for (IBond bond : container.bonds()) { 143 144 int v = container.indexOf(bond.getBegin()); 145 int w = container.indexOf(bond.getEnd()); 146 147 if (v < 0 || w < 0) 148 throw new IllegalArgumentException("bond at index " + container.indexOf(bond) 149 + " contained an atom not pressent in molecule"); 150 151 graph[v][degree[v]++] = w; 152 graph[w][degree[w]++] = v; 153 154 // if the vertex degree of v or w reaches capacity, double the size 155 if (degree[v] == graph[v].length) graph[v] = Arrays.copyOf(graph[v], degree[v] * 2); 156 if (degree[w] == graph[w].length) graph[w] = Arrays.copyOf(graph[w], degree[w] * 2); 157 } 158 159 for (int v = 0; v < n; v++) { 160 graph[v] = Arrays.copyOf(graph[v], degree[v]); 161 } 162 163 return graph; 164 165 } 166 } 167