Scala example source code file (LongMap.scala)

This example Scala source code file (LongMap.scala) is included in my "Source Code Warehouse" project. The intent of this project is to help you more easily find Scala source code examples by using tags.

All credit for the original source code belongs to scala-lang.org; I'm just trying to make examples easier to find. (For my Scala work, see my Scala examples and tutorials.)

Scala tags/keywords

anyref, array, indexmask, int, long, longmap, longmapbuilder, none, v, vacantbit

The LongMap.scala Scala example source code

package scala
package collection
package mutable

import generic.CanBuildFrom

/** This class implements mutable maps with `Long` keys based on a hash table with open addressing.
 * 
 *  Basic map operations on single entries, including `contains` and `get`, 
 *  are typically substantially faster with `LongMap` than [[HashMap]].  Methods
 *  that act on the whole map,  including `foreach` and `map` are not in
 *  general expected to be faster than with a generic map, save for those
 *  that take particular advantage of the internal structure of the map:
 *  `foreachKey`, `foreachValue`, `mapValuesNow`, and `transformValues`.
 * 
 *  Maps with open addressing may become less efficient at lookup after
 *  repeated addition/removal of elements.  Although `LongMap` makes a
 *  decent attempt to remain efficient regardless,  calling `repack`
 *  on a map that will no longer have elements removed but will be
 *  used heavily may save both time and storage space.
 * 
 *  This map is not indended to contain more than 2^29 entries (approximately
 *  500 million).  The maximum capacity is 2^30, but performance will degrade
 *  rapidly as 2^30 is approached.
 *
 */
final class LongMap[V] private[collection] (defaultEntry: Long => V, initialBufferSize: Int, initBlank: Boolean)
extends AbstractMap[Long, V]
   with Map[Long, V]
   with MapLike[Long, V, LongMap[V]]
   with Serializable
{
  import LongMap._

  def this() = this(LongMap.exceptionDefault, 16, true)
  
  /** Creates a new `LongMap` that returns default values according to a supplied key-value mapping. */
  def this(defaultEntry: Long => V) = this(defaultEntry, 16, true)
  
  /** Creates a new `LongMap` with an initial buffer of specified size.
   * 
   *  A LongMap can typically contain half as many elements as its buffer size
   *  before it requires resizing.
   */
  def this(initialBufferSize: Int) = this(LongMap.exceptionDefault, initialBufferSize, true)
  
  /** Creates a new `LongMap` with specified default values and initial buffer size. */
  def this(defaultEntry: Long => V,  initialBufferSize: Int) = this(defaultEntry,  initialBufferSize,  true)
  
  private[this] var mask = 0
  private[this] var extraKeys: Int = 0
  private[this] var zeroValue: AnyRef = null
  private[this] var minValue: AnyRef = null
  private[this] var _size = 0
  private[this] var _vacant = 0
  private[this] var _keys: Array[Long] = null
  private[this] var _values: Array[AnyRef] = null
    
  if (initBlank) defaultInitialize(initialBufferSize)
  
  private[this] def defaultInitialize(n: Int) = {
    mask = 
      if (n<0) 0x7
      else (((1 << (32 - java.lang.Integer.numberOfLeadingZeros(n-1))) - 1) & 0x3FFFFFFF) | 0x7
    _keys = new Array[Long](mask+1)
    _values = new Array[AnyRef](mask+1)
  }
  
  private[collection] def initializeTo(
    m: Int, ek: Int, zv: AnyRef, mv: AnyRef, sz: Int, vc: Int, kz: Array[Long], vz: Array[AnyRef]
  ) {
    mask = m; extraKeys = ek; zeroValue = zv; minValue = mv; _size = sz; _vacant = vc; _keys = kz; _values = vz
  }
  
  override def size: Int = _size + (extraKeys+1)/2
  override def empty: LongMap[V] = new LongMap()
  
  private def imbalanced: Boolean = 
    (_size + _vacant) > 0.5*mask || _vacant > _size
  
  private def toIndex(k: Long): Int = {
    // Part of the MurmurHash3 32 bit finalizer
    val h = ((k ^ (k >>> 32)) & 0xFFFFFFFFL).toInt
    var x = (h ^ (h >>> 16)) * 0x85EBCA6B
    (x ^ (x >>> 13)) & mask
  }
  
  private def seekEmpty(k: Long): Int = {
    var e = toIndex(k)
    var x = 0
    while (_keys(e) != 0) { x += 1; e = (e + 2*(x+1)*x - 3) & mask }
    e
  }
  
  private def seekEntry(k: Long): Int = {
    var e = toIndex(k)
    var x = 0
    var q = 0L
    while ({ q = _keys(e); if (q==k) return e; q != 0}) { x += 1; e = (e + 2*(x+1)*x - 3) & mask }
    e | MissingBit
  }
  
  private def seekEntryOrOpen(k: Long): Int = {
    var e = toIndex(k)
    var x = 0
    var q = 0L
    while ({ q = _keys(e); if (q==k) return e; q+q != 0}) {
      x += 1
      e = (e + 2*(x+1)*x - 3) & mask
    }
    if (q == 0) return e | MissingBit
    val o = e | MissVacant
    while ({ q = _keys(e); if (q==k) return e; q != 0}) {
      x += 1
      e = (e + 2*(x+1)*x - 3) & mask
    }
    o
  }
  
  override def contains(key: Long): Boolean = {
    if (key == -key) (((key>>>63).toInt+1) & extraKeys) != 0
    else seekEntry(key) >= 0
  }
  
  override def get(key: Long): Option[V] = {
    if (key == -key) {
      if ((((key>>>63).toInt+1) & extraKeys) == 0) None
      else if (key == 0) Some(zeroValue.asInstanceOf[V])
      else Some(minValue.asInstanceOf[V])
    }
    else {
      val i = seekEntry(key)
      if (i < 0) None else Some(_values(i).asInstanceOf[V])
    }
  }
  
  override def getOrElse[V1 >: V](key: Long, default: => V1): V1 = {
    if (key == -key) {
      if ((((key>>>63).toInt+1) & extraKeys) == 0) default
      else if (key == 0) zeroValue.asInstanceOf[V1]
      else minValue.asInstanceOf[V1]
    }
    else {
      val i = seekEntry(key)
      if (i < 0) default else _values(i).asInstanceOf[V1]
    }
  }
  
  override def getOrElseUpdate(key: Long, defaultValue: => V): V = {
    if (key == -key) {
      val kbits = (key>>>63).toInt + 1
      if ((kbits & extraKeys) == 0) {
        val value = defaultValue
        extraKeys |= kbits
        if (key == 0) zeroValue = value.asInstanceOf[AnyRef]
        else minValue = value.asInstanceOf[AnyRef]
        value
      }
      else if (key == 0) zeroValue.asInstanceOf[V]
      else minValue.asInstanceOf[V]
    }
    else {
      var i = seekEntryOrOpen(key)
      if (i < 0) {
        // It is possible that the default value computation was side-effecting
        // Our hash table may have resized or even contain what we want now
        // (but if it does, we'll replace it)
        val value = {
          val ok = _keys
          val ans = defaultValue
          if (ok ne _keys) {
            i = seekEntryOrOpen(key)
            if (i >= 0) _size -= 1
          }
          ans
        }
        _size += 1
        val j = i & IndexMask
        _keys(j) = key
        _values(j) = value.asInstanceOf[AnyRef]
        if ((i & VacantBit) != 0) _vacant -= 1
        else if (imbalanced) repack()
        value
      }
      else _values(i).asInstanceOf[V]
    }
  }
  
  /** Retrieves the value associated with a key, or the default for that type if none exists
   *  (null for AnyRef, 0 for floats and integers).
   * 
   *  Note: this is the fastest way to retrieve a value that may or
   *  may not exist, if the default null/zero is acceptable.  For key/value
   *  pairs that do exist,  `apply` (i.e. `map(key)`) is equally fast.
   */
  def getOrNull(key: Long): V = {
    if (key == -key) {
      if ((((key>>>63).toInt+1) & extraKeys) == 0) null.asInstanceOf[V]
      else if (key == 0) zeroValue.asInstanceOf[V]
      else minValue.asInstanceOf[V]
    }
    else {
      val i = seekEntry(key)
      if (i < 0) null.asInstanceOf[V] else _values(i).asInstanceOf[V]
    }
  }
  
  /** Retrieves the value associated with a key. 
   *  If the key does not exist in the map, the `defaultEntry` for that key
   *  will be returned instead.
   */
  override def apply(key: Long): V = {
    if (key == -key) {
      if ((((key>>>63).toInt+1) & extraKeys) == 0) defaultEntry(key)
      else if (key == 0) zeroValue.asInstanceOf[V]
      else minValue.asInstanceOf[V]
    }
    else {
      val i = seekEntry(key)
      if (i < 0) defaultEntry(key) else _values(i).asInstanceOf[V]
    }
  }
  
  /** The user-supplied default value for the key.  Throws an exception
   *  if no other default behavior was specified.
   */
  override def default(key: Long) = defaultEntry(key)
  
  private def repack(newMask: Int) {
    val ok = _keys
    val ov = _values
    mask = newMask
    _keys = new Array[Long](mask+1)
    _values = new Array[AnyRef](mask+1)
    _vacant = 0
    var i = 0
    while (i < ok.length) {
      val k = ok(i)
      if (k != -k) {
        val j = seekEmpty(k)
        _keys(j) = k
        _values(j) = ov(i)
      }
      i += 1
    }
  }
  
  /** Repacks the contents of this `LongMap` for maximum efficiency of lookup.
   * 
   *  For maps that undergo a complex creation process with both addition and
   *  removal of keys, and then are used heavily with no further removal of
   *  elements, calling `repack` after the end of the creation can result in
   *  improved performance.  Repacking takes time proportional to the number
   *  of entries in the map.
   */
  def repack() {
    var m = mask
    if (_size + _vacant >= 0.5*mask && !(_vacant > 0.2*mask)) m = ((m << 1) + 1) & IndexMask
    while (m > 8 && 8*_size < m) m = m >>> 1
    repack(m)
  }
  
  override def put(key: Long, value: V): Option[V] = {
    if (key == -key) {
      if (key == 0) {
        val ans = if ((extraKeys&1) == 1) Some(zeroValue.asInstanceOf[V]) else None
        zeroValue = value.asInstanceOf[AnyRef]
        extraKeys |= 1
        ans
      }
      else {
        val ans = if ((extraKeys&2) == 1) Some(minValue.asInstanceOf[V]) else None
        minValue = value.asInstanceOf[AnyRef]
        extraKeys |= 2
        ans
      }
    }
    else {
      val i = seekEntryOrOpen(key)
      if (i < 0) {
        val j = i & IndexMask
        _keys(j) = key
        _values(j) = value.asInstanceOf[AnyRef]
        _size += 1
        if ((i & VacantBit) != 0) _vacant -= 1
        else if (imbalanced) repack()
        None
      }
      else {
        val ans = Some(_values(i).asInstanceOf[V])
        _keys(i) = key
        _values(i) = value.asInstanceOf[AnyRef]
        ans
      }
    }
  }
  
  /** Updates the map to include a new key-value pair.
   * 
   *  This is the fastest way to add an entry to a `LongMap`.
   */
  override def update(key: Long, value: V): Unit = {
    if (key == -key) {
      if (key == 0) {
        zeroValue = value.asInstanceOf[AnyRef]
        extraKeys |= 1
      }
      else {
        minValue = value.asInstanceOf[AnyRef]
        extraKeys |= 2
      }
    }
    else {
      var i = seekEntryOrOpen(key)
      if (i < 0) {
        val j = i & IndexMask
        _keys(j) = key
        _values(j) = value.asInstanceOf[AnyRef]
        _size += 1
        if ((i & VacantBit) != 0) _vacant -= 1
        else if (imbalanced) repack()
      }
      else {
        _keys(i) = key
        _values(i) = value.asInstanceOf[AnyRef]
      }
    }
  }
  
  /** Adds a new key/value pair to this map and returns the map. */
  def +=(key: Long, value: V): this.type = { update(key, value); this }
  
  def +=(kv: (Long, V)): this.type = { update(kv._1, kv._2); this }
  
  def -=(key: Long): this.type = {
    if (key == -key) {
      if (key == 0L) {
        extraKeys &= 0x2
        zeroValue = null
      }
      else {
        extraKeys &= 0x1
        minValue = null
      }
    }
    else {
      val i = seekEntry(key)
      if (i >= 0) {
        _size -= 1
        _vacant += 1
        _keys(i) = Long.MinValue
        _values(i) = null
      }
    }
    this
  }
  
  def iterator: Iterator[(Long, V)] = new Iterator[(Long, V)] {
    private[this] val kz = _keys
    private[this] val vz = _values
    
    private[this] var nextPair: (Long, V) = 
      if (extraKeys==0) null
      else if ((extraKeys&1)==1) (0L, zeroValue.asInstanceOf[V])
      else (Long.MinValue, minValue.asInstanceOf[V])

    private[this] var anotherPair: (Long, V) = 
      if (extraKeys==3) (Long.MinValue, minValue.asInstanceOf[V])
      else null
        
    private[this] var index = 0
    
    def hasNext: Boolean = nextPair != null || (index < kz.length && {
      var q = kz(index)
      while (q == -q) {
        index += 1
        if (index >= kz.length) return false
        q = kz(index)
      }
      nextPair = (kz(index), vz(index).asInstanceOf[V])
      index += 1
      true
    })
    def next = {
      if (nextPair == null && !hasNext) throw new NoSuchElementException("next")
      val ans = nextPair
      if (anotherPair != null) {
        nextPair = anotherPair
        anotherPair = null
      }
      nextPair = null
      ans
    }
  }
  
  override def foreach[A](f: ((Long,V)) => A) {
    var i,j = 0
    while (i < _keys.length & j < _size) {
      val k = _keys(i)
      if (k != -k) {
        j += 1
        f((k, _values(i).asInstanceOf[V]))
      }
      i += 1
    }
    if ((extraKeys & 1) == 1) f((0L, zeroValue.asInstanceOf[V]))
    if ((extraKeys & 2) == 2) f((Long.MinValue, minValue.asInstanceOf[V]))
  }
  
  override def clone(): LongMap[V] = {
    val kz = java.util.Arrays.copyOf(_keys, _keys.length)
    val vz = java.util.Arrays.copyOf(_values,  _values.length)
    val lm = new LongMap[V](defaultEntry, 1, false)
    lm.initializeTo(mask, extraKeys, zeroValue, minValue, _size, _vacant, kz,  vz)
    lm
  }
  
  /** Applies a function to all keys of this map. */
  def foreachKey[A](f: Long => A) {
    var i,j = 0
    while (i < _keys.length & j < _size) {
      val k = _keys(i)
      if (k != -k) {
        j += 1
        f(k)
      }
      i += 1
    }
    if ((extraKeys & 1) == 1) f(0L)
    if ((extraKeys & 2) == 2) f(Long.MinValue)
  }

  /** Applies a function to all values of this map. */
  def foreachValue[A](f: V => A) {
    var i,j = 0
    while (i < _keys.length & j < _size) {
      val k = _keys(i)
      if (k != -k) {
        j += 1
        f(_values(i).asInstanceOf[V])
      }
      i += 1
    }
    if ((extraKeys & 1) == 1) f(zeroValue.asInstanceOf[V])
    if ((extraKeys & 2) == 2) f(minValue.asInstanceOf[V])
  }
  
  /** Creates a new `LongMap` with different values.
   *  Unlike `mapValues`, this method generates a new
   *  collection immediately.
   */
  def mapValuesNow[V1](f: V => V1): LongMap[V1] = {
    val lm = new LongMap[V1](LongMap.exceptionDefault,  1,  false)
    val kz = java.util.Arrays.copyOf(_keys, _keys.length)
    val vz = new Array[AnyRef](_values.length)
    var i,j = 0
    while (i < _keys.length & j < _size) {
      val k = _keys(i)
      if (k != -k) {
        j += 1
        vz(i) = f(_values(i).asInstanceOf[V]).asInstanceOf[AnyRef]
      }
      i += 1
    }
    val zv = if ((extraKeys & 1) == 1) f(zeroValue.asInstanceOf[V]).asInstanceOf[AnyRef] else null
    val mv = if ((extraKeys & 2) == 2) f(minValue.asInstanceOf[V]).asInstanceOf[AnyRef] else null
    lm.initializeTo(mask, extraKeys, zv, mv, _size, _vacant, kz, vz)
    lm
  }
  
  /** Applies a transformation function to all values stored in this map. 
   *  Note: the default, if any,  is not transformed.
   */
  def transformValues(f: V => V): this.type = {
    var i,j = 0
    while (i < _keys.length & j < _size) {
      val k = _keys(i)
      if (k != -k) {
        j += 1
        _values(i) = f(_values(i).asInstanceOf[V]).asInstanceOf[AnyRef]
      }
      i += 1
    }
    if ((extraKeys & 1) == 1) zeroValue = f(zeroValue.asInstanceOf[V]).asInstanceOf[AnyRef]
    if ((extraKeys & 2) == 2) minValue = f(minValue.asInstanceOf[V]).asInstanceOf[AnyRef]
    this
  }
  
  /*
  override def toString = {
    val sb = new StringBuilder("LongMap(")
    var n = 0
    foreach{ case (k,v) => 
      if (n > 0) sb ++= ", "
      sb ++= k.toString
      sb ++= " -> "
      sb ++= v.toString
      n += 1
    }
    sb += ')'
    sb.result
  }
  */
}

object LongMap {
  private final val IndexMask  = 0x3FFFFFFF
  private final val MissingBit = 0x80000000
  private final val VacantBit  = 0x40000000
  private final val MissVacant = 0xC0000000
  
  private val exceptionDefault: Long => Nothing = (k: Long) => throw new NoSuchElementException(k.toString)
  
  implicit def canBuildFrom[V, U]: CanBuildFrom[LongMap[V], (Long, U), LongMap[U]] = 
    new CanBuildFrom[LongMap[V], (Long, U), LongMap[U]] {
      def apply(from: LongMap[V]): LongMapBuilder[U] = apply()
      def apply(): LongMapBuilder[U] = new LongMapBuilder[U]
    }
  
  final class LongMapBuilder[V] extends Builder[(Long, V), LongMap[V]] {
    private[collection] var elems: LongMap[V] = new LongMap[V]
    def +=(entry: (Long, V)): this.type = {
      elems += entry
      this
    }
    def clear() { elems = new LongMap[V] }
    def result(): LongMap[V] = elems
  }

  /** Creates a new `LongMap` with zero or more key/value pairs. */
  def apply[V](elems: (Long, V)*): LongMap[V] = {
    val sz = if (elems.hasDefiniteSize) elems.size else 4
    val lm = new LongMap[V](sz * 2)
    elems.foreach{ case (k,v) => lm(k) = v }
    if (lm.size < (sz>>3)) lm.repack()
    lm
  }
  
  /** Creates a new empty `LongMap`. */
  def empty[V]: LongMap[V] = new LongMap[V]
  
  /** Creates a new empty `LongMap` with the supplied default */
  def withDefault[V](default: Long => V): LongMap[V] = new LongMap[V](default)
  
  /** Creates a new `LongMap` from arrays of keys and values. 
   *  Equivalent to but more efficient than `LongMap((keys zip values): _*)`.
   */
  def fromZip[V](keys: Array[Long], values: Array[V]): LongMap[V] = {
    val sz = math.min(keys.length, values.length)
    val lm = new LongMap[V](sz * 2)
    var i = 0
    while (i < sz) { lm(keys(i)) = values(i); i += 1 }
    if (lm.size < (sz>>3)) lm.repack()
    lm
  }
  
  /** Creates a new `LongMap` from keys and values. 
   *  Equivalent to but more efficient than `LongMap((keys zip values): _*)`.
   */
  def fromZip[V](keys: Iterable[Long], values: Iterable[V]): LongMap[V] = {
    val sz = math.min(keys.size, values.size)
    val lm = new LongMap[V](sz * 2)
    val ki = keys.iterator
    val vi = values.iterator
    while (ki.hasNext && vi.hasNext) lm(ki.next) = vi.next
    if (lm.size < (sz >> 3)) lm.repack()
    lm
  }
}