The purpose of this map is identical to that of a {@link ShiftAddXorSignedStringMap}, but * Shift-Add-Xor signatures are 64-bit and stored in a {@link LongBigList}. This approach makes it possible to * store the signatures in a file and read them by memory mapping using a {@link ByteBufferLongBigList}. * If the map has a very large number of keys but the access pattern is strongly skewed towards a relatively * small number of entries, using memory mapping might be advantageous. * *
The intended usage pattern is as follows: * *
To simplify the process, there is a {@linkplain #LongBigListSignedStringMap(Object2LongFunction, String) constructor} that will do the mapping for you.
*
* @author Sebastiano Vigna
* @since 2.0.13
* @deprecated There are much better and faster hash functions.
*/
@Deprecated
public class LongBigListSignedStringMap extends AbstractObject2LongFunction The resulting big array can be saved using {@link BinIO#storeLongs(long[][], CharSequence)}
* or similar {@link BinIO} methods.
*
* @param iterator an iterator over a list of strings.
* @param function the function to be signed.
* @return a big array of 64-bit signatures.
*/
public static long[][] sign(final Iterator iterator, final Object2LongFunction function) {
return sign(iterator, function, null);
}
/** Generates a 64-bit signatures big array using a given function and string sequence.
*
* The resulting big array can be saved using {@link BinIO#storeLongs(long[][], CharSequence)}
* or similar {@link BinIO} methods.
*
* @param iterator an iterator over a list of strings.
* @param function the function to be signed.
* @param pl a progress logger, or {@code null}.
* @return a big array of 64-bit signatures.
*/
public static long[][] sign(final Iterator iterator, final Object2LongFunction function , final ProgressLogger pl) {
final long n = function instanceof Size64 ? ((Size64)function).size64() : function .size();
final long[][] signature = LongBigArrays.newBigArray(n);
if (pl != null) {
pl.expectedUpdates = n;
pl.start("Signing...");
}
CharSequence s;
for(long i = 0; i < n; i++) {
s = iterator.next();
LongBigArrays.set(signature, function .getLong(s), signature(s));
if (pl != null) pl.lightUpdate();
}
if (iterator.hasNext()) throw new IllegalStateException("Iterator provides more than " + n + " elements");
if (pl != null) pl.done();
return signature;
}
/** Creates a signed string map using a given hash map and a big list of 64-bit signatures.
*
* @param function a minimal perfect hash for the strings enumerated by This methods generates on-disk signatures in the same order of the strings returned by
* the provided iterator. Thus, the signature file can be only used with a function that
* maps each string returned by the iterator in its ordinal position. This happens, for instance,
* if you have a sorted set of string and you use a monotone minimal perfect hash function.
*
* @param iterator an iterator over a list of strings.
* @param signatureFile the file name of the resulting signature file.
*/
public static void sign(final Iterator iterator, final String signatureFile) throws IOException {
sign(iterator, signatureFile, null);
}
/** Generates an on-disk list 64-bit signatures big array using a given string sequence.
*
* @param iterator an iterator over a list of strings.
* @param signatureFile the file name of the resulting signature file.
* @param pl a progress logger, or {@code null}.
* @see #sign(Iterator, DataOutput, ProgressLogger)
*/
public static void sign(final Iterator iterator, final String signatureFile, final ProgressLogger pl) throws IOException {
final DataOutputStream dos = new DataOutputStream(new FastBufferedOutputStream(new FileOutputStream(signatureFile)));
sign(iterator, dos, pl);
dos.close();
}
/** Generates an on-disk list 64-bit signatures big array using a given string sequence.
*
* This methods generates on-disk signatures in the same order of the strings returned by
* the provided iterator. Thus, the generated signatures can be only used with a function that
* maps each string returned by the iterator in its ordinal position. This happens, for instance,
* if you have a sorted set of string and you use a
* monotone minimal perfect hash function.
*
* @param iterator an iterator over a list of strings.
* @param signatures a {@link DataOutput} where the signatures will be written.
* @param pl a progress logger, or {@code null}.
*/
public static void sign(final Iterator iterator, final DataOutput signatures, final ProgressLogger pl) throws IOException {
if (pl != null) pl.start("Signing...");
CharSequence s;
while(iterator.hasNext()) {
s = iterator.next();
signatures.writeLong(signature(s));
if (pl != null) pl.lightUpdate();
}
if (pl != null) pl.done();
}
/** Creates a signed string map using a given hash map and a big list of 64-bit signatures.
*
* @param function a minimal perfect hash for the strings enumerated by iterator; it must support {@link Function#size() size()}.
* and have default return value -1.
* @param signatures a big list of 64-bit signatures generated by {@link #sign(Iterator, Object2LongFunction, ProgressLogger)}.
*/
public LongBigListSignedStringMap(final Object2LongFunction function, final LongBigList signatures) {
final long n = function instanceof Size64 ? ((Size64)function).size64() : function.size();
if (n != signatures.size64()) throw new IllegalStateException("The size of the function differs from that of the signature list: " + n + " != " + signatures.size64());
this.function = function;
this.signatures = signatures;
defaultReturnValue(-1);
}
/** Generates an on-disk list 64-bit signatures big array using a given string sequence.
*
* iterator; it must support {@link Function#size() size()}.
* and have default return value -1.
* @param signatures a file containing a list of 64-bit signatures
* generated by {@link #sign(Iterator, Object2LongFunction, ProgressLogger)} and stored in {@link DataOutput} format.
*/
@SuppressWarnings("resource")
public LongBigListSignedStringMap(final Object2LongFunction function, final String signatures) throws FileNotFoundException, IOException {
final long n = function instanceof Size64 ? ((Size64)function).size64() : function.size();
final long signatureSize = new File(signatures).length() / Long.BYTES;
if (n != signatureSize) throw new IllegalStateException("The size of the function differs from that of the signature list: " + n + " != " + signatureSize);
this.function = function;
this.signatures = ByteBufferLongBigList.map(new FileInputStream(signatures).getChannel());
defaultReturnValue(-1);
}
private static long signature(final CharSequence s) {
int i;
final int l = s.length();
long h = 42;
for (i = l; i-- != 0;) h ^= (h << 5) + s.charAt(i) + (h >>> 2);
return h;
}
private boolean checkSignature(final CharSequence s, final long index) {
return index >= 0 && index < function.size() && signatures.getLong(index) == signature(s);
}
@Override
public long getLong(final Object o) {
final CharSequence s = (CharSequence)o;
final long index = function.getLong(s);
return checkSignature(s, index) ? index : defRetValue;
}
@Override
public Long get(final Object o) {
final CharSequence s = (CharSequence)o;
final long index = function.getLong(s);
return checkSignature(s, index) ? Long.valueOf(index) : null;
}
@Override
public boolean containsKey(final Object o) {
final CharSequence s = (CharSequence)o;
return checkSignature(s, function.getLong(s));
}
@Override
@Deprecated
public int size() {
return signatures.size();
}
@Override
public long size64() {
return signatures.size64();
}
@Override
public ObjectBigList