Class Counter

  • Direct Known Subclasses:
    FastNonCollidingCounter, NonZeroCachingCounter

    public class Counter
    extends Object
    Maps integer keys to integer counts using a fixed-size table.

    Hash collisions are completely ignored; therefore, the counts are unreliable.

    Throughout the internal documentation, the term "key" is used to refer to the keys that are hashed, while "index" is used to the result of key-hashing, i.e. the location in the internal array storage.

    Author:
    Rohan Padhye
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int[] counts
      The counter map as an array of integers.
      protected int size
      The size of the counter map.
    • Constructor Summary

      Constructors 
      Constructor Description
      Counter​(int size)
      Creates a new counter with given size.
      Counter​(Counter counter)  
    • Field Detail

      • size

        protected final int size
        The size of the counter map.
      • counts

        protected final int[] counts
        The counter map as an array of integers.
    • Constructor Detail

      • Counter

        public Counter​(int size)
        Creates a new counter with given size.
        Parameters:
        size - the fixed-number of elements in the hashtable.
      • Counter

        public Counter​(Counter counter)
    • Method Detail

      • size

        public int size()
        Returns the size of this counter.
        Returns:
        the size of this counter
      • clear

        public void clear()
        Clears the counter by setting all values to zero.
      • incrementAtIndex

        protected int incrementAtIndex​(int index,
                                       int delta)
      • increment

        public int increment​(int key)
        Increments the count at the given key.

        Note that the key is hashed and therefore the count to increment may be shared with another key that hashes to the same value.

        Parameters:
        key - the key whose count to increment
        Returns:
        the new value after incrementing the count
      • increment1

        public int increment1​(int k1,
                              int k2)
        Increments the count at the given key pair.

        Note that the key pair is hashed and therefore the count to increment may be shared with another key pair that hashes to the same value.

        Parameters:
        k1 - the key (part 1) whose count to increment
        k2 - the key (part 2) whose count to increment
        Returns:
        the new value after incrementing the count
      • increment

        public int increment​(int key,
                             int delta)
        Increments the count at the given key by a given delta.

        Note that the key is hashed and therefore the count to increment may be shared with another key that hashes to the same value.

        Parameters:
        key - the key whose count to increment
        delta - the amount to increment by
        Returns:
        the new value after incrementing the count
      • getNonZeroSize

        public int getNonZeroSize()
        Returns the number of indices with non-zero counts.
        Returns:
        the number of indices with non-zero counts
      • hasNonZeros

        public boolean hasNonZeros()
        Checks if all indices have zero counts and returns a boolean as result.
        Returns:
        true if some indices have non-zero counts, otherwise false.
      • getNonZeroIndices

        public org.eclipse.collections.api.list.primitive.IntList getNonZeroIndices()
        Returns a set of indices at which the count is non-zero.

        Note that indices are different from keys, in that multiple keys can map to the same index due to hash collisions.

        Returns:
        a set of indices at which the count is non-zero
      • getNonZeroValues

        public org.eclipse.collections.api.list.primitive.IntList getNonZeroValues()
        Returns a set of non-zero count values in this counter.
        Returns:
        a set of non-zero count values in this counter.
      • get

        public int get​(int key)
        Retreives a value for a given key.

        The key is first hashed to retreive a value from the counter, and hence the result is modulo collisions.

        Parameters:
        key - the key to query
        Returns:
        the count for the index corresponding to this key
      • getAtIndex

        public int getAtIndex​(int idx)
      • setAtIndex

        public void setAtIndex​(int idx,
                               int value)