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