| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| */ |
| |
| package org.apache.datasketches.tuple; |
| |
| import java.nio.ByteBuffer; |
| |
| import org.apache.datasketches.hash.MurmurHash3; |
| import org.apache.datasketches.memory.Memory; |
| import org.apache.datasketches.thetacommon.ThetaUtil; |
| |
| /** |
| * An extension of QuickSelectSketch<S>, which can be updated with many types of keys. |
| * Summary objects are created using a user-defined SummaryFactory class, |
| * which should allow very flexible parameterization if needed. |
| * Keys are presented to a sketch along with values of a user-defined |
| * update type U. When an entry is inserted into a sketch or a duplicate key is |
| * presented to a sketch then summary.update(U value) method will be called. So |
| * any kind of user-defined accumulation is possible. Summaries also must know |
| * how to copy themselves. Also union and intersection of summaries can be |
| * implemented in a sub-class of SummarySetOperations, which will be used in |
| * case Union or Intersection of two instances of Tuple Sketch is needed |
| * @param <U> Type of the value, which is passed to update method of a Summary |
| * @param <S> Type of the UpdatableSummary<U> |
| */ |
| public class UpdatableSketch<U, S extends UpdatableSummary<U>> extends QuickSelectSketch<S> { |
| |
| /** |
| * This is to create a new instance of an UpdatableQuickSelectSketch. |
| * @param nomEntries Nominal number of entries. Forced to the nearest power of 2 greater than |
| * or equal to the given value. |
| * @param lgResizeFactor log2(resizeFactor) - value from 0 to 3: |
| * <pre> |
| * 0 - no resizing (max size allocated), |
| * 1 - double internal hash table each time it reaches a threshold |
| * 2 - grow four times |
| * 3 - grow eight times (default) |
| * </pre> |
| * @param samplingProbability |
| * <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability</a> |
| * @param summaryFactory An instance of a SummaryFactory. |
| */ |
| public UpdatableSketch(final int nomEntries, final int lgResizeFactor, |
| final float samplingProbability, final SummaryFactory<S> summaryFactory) { |
| super(nomEntries, lgResizeFactor, samplingProbability, summaryFactory); |
| } |
| |
| /** |
| * This is to create an instance of a sketch given a serialized form |
| * @param srcMem Memory object with data of a serialized UpdatableSketch |
| * @param deserializer instance of SummaryDeserializer |
| * @param summaryFactory instance of SummaryFactory |
| * @deprecated As of 3.0.0, heapifying an UpdatableSketch is deprecated. |
| * This capability will be removed in a future release. |
| * Heapifying a CompactSketch is not deprecated. |
| */ |
| @Deprecated |
| public UpdatableSketch( |
| final Memory srcMem, |
| final SummaryDeserializer<S> deserializer, |
| final SummaryFactory<S> summaryFactory) { |
| super(srcMem, deserializer, summaryFactory); |
| } |
| |
| /** |
| * Copy Constructor |
| * @param sketch the sketch to copy |
| */ |
| public UpdatableSketch(final UpdatableSketch<U, S> sketch) { |
| super(sketch); |
| } |
| |
| /** |
| * @return a deep copy of this sketch |
| */ |
| @Override |
| public UpdatableSketch<U,S> copy() { |
| return new UpdatableSketch<>(this); |
| } |
| |
| /** |
| * Updates this sketch with a long key and U value. |
| * The value is passed to update() method of the Summary object associated with the key |
| * |
| * @param key The given long key |
| * @param value The given U value |
| */ |
| public void update(final long key, final U value) { |
| update(new long[] {key}, value); |
| } |
| |
| /** |
| * Updates this sketch with a double key and U value. |
| * The value is passed to update() method of the Summary object associated with the key |
| * |
| * @param key The given double key |
| * @param value The given U value |
| */ |
| public void update(final double key, final U value) { |
| update(Util.doubleToLongArray(key), value); |
| } |
| |
| /** |
| * Updates this sketch with a String key and U value. |
| * The value is passed to update() method of the Summary object associated with the key |
| * |
| * @param key The given String key |
| * @param value The given U value |
| */ |
| public void update(final String key, final U value) { |
| update(Util.stringToByteArray(key), value); |
| } |
| |
| /** |
| * Updates this sketch with a byte[] key and U value. |
| * The value is passed to update() method of the Summary object associated with the key |
| * |
| * @param key The given byte[] key |
| * @param value The given U value |
| */ |
| public void update(final byte[] key, final U value) { |
| if ((key == null) || (key.length == 0)) { return; } |
| insertOrIgnore(MurmurHash3.hash(key, ThetaUtil.DEFAULT_UPDATE_SEED)[0] >>> 1, value); |
| } |
| |
| /** |
| * Updates this sketch with a ByteBuffer and U value |
| * The value is passed to the update() method of the Summary object associated with the key |
| * |
| * @param buffer The given ByteBuffer key |
| * @param value The given U value |
| */ |
| public void update(final ByteBuffer buffer, final U value) { |
| if (buffer == null || buffer.hasRemaining() == false) { return; } |
| insertOrIgnore(MurmurHash3.hash(buffer, ThetaUtil.DEFAULT_UPDATE_SEED)[0] >>> 1, value); |
| } |
| |
| /** |
| * Updates this sketch with a int[] key and U value. |
| * The value is passed to update() method of the Summary object associated with the key |
| * |
| * @param key The given int[] key |
| * @param value The given U value |
| */ |
| public void update(final int[] key, final U value) { |
| if ((key == null) || (key.length == 0)) { return; } |
| insertOrIgnore(MurmurHash3.hash(key, ThetaUtil.DEFAULT_UPDATE_SEED)[0] >>> 1, value); |
| } |
| |
| /** |
| * Updates this sketch with a long[] key and U value. |
| * The value is passed to update() method of the Summary object associated with the key |
| * |
| * @param key The given long[] key |
| * @param value The given U value |
| */ |
| public void update(final long[] key, final U value) { |
| if ((key == null) || (key.length == 0)) { return; } |
| insertOrIgnore(MurmurHash3.hash(key, ThetaUtil.DEFAULT_UPDATE_SEED)[0] >>> 1, value); |
| } |
| |
| void insertOrIgnore(final long hash, final U value) { |
| setEmpty(false); |
| if (hash >= getThetaLong()) { return; } |
| int index = findOrInsert(hash); |
| if (index < 0) { |
| index = ~index; |
| insertSummary(index, getSummaryFactory().newSummary()); |
| } |
| summaryTable_[index].update(value); |
| rebuildIfNeeded(); |
| } |
| |
| } |