<commit_before>/*
 *  @author <NAME>
 *
 *  Copyright 2012 University of Zurich
 *
 *  Licensed 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 com.signalcollect.storage

import com.signalcollect.Vertex
import com.signalcollect.interfaces.VertexStore
import StorageDefaultValues._

// A special adaptation of IntHashMap[Vertex[_, _, _, _]].
// We allow arbitrary types for the vertex id to make
// the usage of the framework simple.
// This unfortunately means that we cannot use the id
// as the key, as these keys might be expensive to
// compare and require more space than an array of Ints.
// As a proxy we use the hashCode of a vertex id as
// the key in this map. In order to handle (rare) collisions,
// we have to do an additional check to verify that the vertex id
// matches indeed (and not just the hash of the vertex id).
class VertexMap[@specialized(Int, Long) Id, Signal](
  initialSize: Int = defaultInitialSize,
  rehashFraction: Float = defaultRehashFraction) extends VertexStore[Id, Signal] {
  assert(initialSize > 0)
  final var maxSize = nextPowerOfTwo(initialSize)
  assert(1.0f >= rehashFraction && rehashFraction > 0.1f, "Unreasonable rehash fraction.")
  assert(maxSize > 0 && maxSize >= initialSize, "Initial size is too large.")
  private[this] final var maxElements: Int = (rehashFraction * maxSize).floor.toInt
  private[this] final var values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
  private[this] final var keys = new Array[Int](maxSize) // 0 means empty
  private[this] final var mask = maxSize - 1
  private[this] final var nextPositionToProcess = 0

  final override def size: Long = numberOfElements
  final def isEmpty: Boolean = numberOfElements == 0
  private[this] final var numberOfElements = 0

  def stream: Stream[Vertex[Id, _, Id, Signal]] = {
    def remainder(i: Int, elementsProcessed: Int): Stream[Vertex[Id, _, Id, Signal]] = {
      if (elementsProcessed == numberOfElements) {
        Stream.empty
      } else {
        var index = i
        var vertex = values(index)
        while (vertex == null) {
          index += 1
          vertex = values(index)
        }
        Stream.cons(vertex, remainder(index + 1, elementsProcessed + 1))
      }
    }

    remainder(0, 0)
  }

  final def clear {
    values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
    keys = new Array[Int](maxSize)
    numberOfElements = 0
    nextPositionToProcess = 0
  }

  final def foreach(f: Vertex[Id, _, Id, Signal] => Unit) {
    var i = 0
    var elementsProcessed = 0
    while (elementsProcessed < numberOfElements) {
      val vertex = values(i)
      if (vertex != null) {
        f(vertex)
        elementsProcessed += 1
      }
      i += 1
    }
  }

  // Removes the vertices after they have been processed.
  final def process(p: Vertex[Id, _, Id, Signal] => Unit, numberOfVertices: Option[Int] = None): Int = {
    val limit = math.min(numberOfElements, numberOfVertices.getOrElse(numberOfElements))
    var elementsProcessed = 0
    while (elementsProcessed < limit) {
      val vertex = values(nextPositionToProcess)
      if (vertex != null) {
        p(vertex)
        elementsProcessed += 1
        keys(nextPositionToProcess) = 0
        values(nextPositionToProcess) = null
      }
      nextPositionToProcess = (nextPositionToProcess + 1) & mask
    }
    if (elementsProcessed > 0) {
      numberOfElements -= elementsProcessed
      optimizeFromPosition(nextPositionToProcess)
    }
    limit
  }

  // Removes the vertices after they have been processed.
  final def processWithCondition(p: Vertex[Id, _, Id, Signal] => Unit, breakCondition: () => Boolean): Int = {
    val limit = numberOfElements
    var elementsProcessed = 0
    while (elementsProcessed < limit && !breakCondition()) {
      val vertex = values(nextPositionToProcess)
      if (vertex != null) {
        p(vertex)
        elementsProcessed += 1
        keys(nextPositionToProcess) = 0
        values(nextPositionToProcess) = null
      }
      nextPositionToProcess = (nextPositionToProcess + 1) & mask
    }
    if (elementsProcessed > 0) {
      numberOfElements -= elementsProcessed
      optimizeFromPosition(nextPositionToProcess)
    }
    elementsProcessed
  }

  private[this] final def tryDouble {
    // 1073741824 is the largest size and cannot be doubled anymore.
    if (maxSize != 1073741824) {
      val oldSize = maxSize
      val oldValues = values
      val oldKeys = keys
      val oldNumberOfElements = numberOfElements
      maxSize *= 2
      maxElements = (rehashFraction * maxSize).floor.toInt
      values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
      keys = new Array[Int](maxSize)
      mask = maxSize - 1
      numberOfElements = 0
      var i = 0
      var elementsMoved = 0
      while (elementsMoved < oldNumberOfElements) {
        if (oldKeys(i) != 0) {<commit_msg>Added conservative dynamic vertex map shrinking.<commit_after>/*
 *  @author <NAME>
 *
 *  Copyright 2012 University of Zurich
 *
 *  Licensed 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 com.signalcollect.storage

import com.signalcollect.Vertex
import com.signalcollect.interfaces.VertexStore
import StorageDefaultValues._

// A special adaptation of IntHashMap[Vertex[_, _, _, _]].
// We allow arbitrary types for the vertex id to make
// the usage of the framework simple.
// This unfortunately means that we cannot use the id
// as the key, as these keys might be expensive to
// compare and require more space than an array of Ints.
// As a proxy we use the hashCode of a vertex id as
// the key in this map. In order to handle (rare) collisions,
// we have to do an additional check to verify that the vertex id
// matches indeed (and not just the hash of the vertex id).
class VertexMap[@specialized(Int, Long) Id, Signal](
  initialSize: Int = defaultInitialSize,
  rehashFraction: Float = defaultRehashFraction,
  shrinkFraction: Float = defaultShrinkFraction) extends VertexStore[Id, Signal] {
  assert(initialSize > 0)
  final var maxSize = nextPowerOfTwo(initialSize)
  assert(1.0f >= rehashFraction && rehashFraction > 0.1f, "Unreasonable rehash fraction.")
  assert(maxSize > 0 && maxSize >= initialSize, "Initial size is too large.")
  private[this] final var maxElements: Int = (rehashFraction * maxSize).floor.toInt
  private[this] final var minElements: Int = (shrinkFraction * maxSize).floor.toInt
  private[this] final var values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
  private[this] final var keys = new Array[Int](maxSize) // 0 means empty
  private[this] final var mask = maxSize - 1
  private[this] final var nextPositionToProcess = 0

  final override def size: Long = numberOfElements
  final def isEmpty: Boolean = numberOfElements == 0
  private[this] final var numberOfElements = 0

  def stream: Stream[Vertex[Id, _, Id, Signal]] = {
    def remainder(i: Int, elementsProcessed: Int): Stream[Vertex[Id, _, Id, Signal]] = {
      if (elementsProcessed == numberOfElements) {
        Stream.empty
      } else {
        var index = i
        var vertex = values(index)
        while (vertex == null) {
          index += 1
          vertex = values(index)
        }
        Stream.cons(vertex, remainder(index + 1, elementsProcessed + 1))
      }
    }

    remainder(0, 0)
  }

  final def clear {
    values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
    keys = new Array[Int](maxSize)
    numberOfElements = 0
    nextPositionToProcess = 0
  }

  final def foreach(f: Vertex[Id, _, Id, Signal] => Unit) {
    var i = 0
    var elementsProcessed = 0
    while (elementsProcessed < numberOfElements) {
      val vertex = values(i)
      if (vertex != null) {
        f(vertex)
        elementsProcessed += 1
      }
      i += 1
    }
  }

  // Removes the vertices after they have been processed.
  final def process(p: Vertex[Id, _, Id, Signal] => Unit, numberOfVertices: Option[Int] = None): Int = {
    val limit = math.min(numberOfElements, numberOfVertices.getOrElse(numberOfElements))
    var elementsProcessed = 0
    while (elementsProcessed < limit) {
      val vertex = values(nextPositionToProcess)
      if (vertex != null) {
        p(vertex)
        elementsProcessed += 1
        keys(nextPositionToProcess) = 0
        values(nextPositionToProcess) = null
      }
      nextPositionToProcess = (nextPositionToProcess + 1) & mask
    }
    if (elementsProcessed > 0) {
      numberOfElements -= elementsProcessed
      // We only want to shrink if the map wasn't emptied entirely.
      if (numberOfElements > 0 && maxSize > minShrinkSize && numberOfElements < minElements) {
        shrink
      } else {
        optimizeFromPosition(nextPositionToProcess)
      }
    }
    limit
  }

  // Removes the vertices after they have been processed.
  final def processWithCondition(p: Vertex[Id, _, Id, Signal] => Unit, breakCondition: () => Boolean): Int = {
    val limit = numberOfElements
    var elementsProcessed = 0
    while (elementsProcessed < limit && !breakCondition()) {
      val vertex = values(nextPositionToProcess)
      if (vertex != null) {
        p(vertex)
        elementsProcessed += 1
        keys(nextPositionToProcess) = 0
        values(nextPositionToProcess) = null
      }
      nextPositionToProcess = (nextPositionToProcess + 1) & mask
    }
    if (elementsProcessed > 0) {
      numberOfElements -= elementsProcessed
      // We only want to shrink if the map wasn't emptied entirely.
      if (numberOfElements > 0 && maxSize > minShrinkSize && numberOfElements < minElements) {
        shrink
      } else {
        optimizeFromPosition(nextPositionToProcess)
      }
    }
    elementsProcessed
  }

  private[this] final def shrink {
    val oldSize = maxSize
    val oldValues = values
    val oldKeys = keys
    val oldNumberOfElements = numberOfElements
    maxSize >>>= 1
    maxElements = (rehashFraction * maxSize).floor.toInt
    values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
    keys = new Array[Int](maxSize)
    mask = maxSize - 1
    numberOfElements = 0
    nextPositionToProcess &= mask
    var i = 0
    var elementsMoved = 0
    while (elementsMoved < oldNumberOfElements) {
      if (oldKeys(i) != 0) {
        put(oldValues(i))
        elementsMoved += 1
      }
      i += 1
    }
  }

  private[this] final def tryDouble {
    // 1073741824 is the largest size and cannot be doubled anymore.
    if (maxSize != 1073741824) {
      val oldSize = maxSize
      val oldValues = values
      val oldKeys = keys
      val oldNumberOfElements = numberOfElements
      maxSize *= 2
      maxElements = (rehashFraction * maxSize).floor.toInt
      minElements = (shrinkFraction * maxSize).floor.toInt
      values = new Array[Vertex[Id, _, Id, Signal]](maxSize)
      keys = new Array[Int](maxSize)
      mask = maxSize - 1
      numberOfElements = 0
      var i = 0
      var elementsMoved = 0
      while (elementsMoved < oldNumberOfElements) {
        if (oldKeys(i) != 0) {
{'fraction_non_alphanumeric': 0.09231282864535514, 'fraction_numerical': 0.01185209915699858, 'mean_word_length': 2.988681757656458, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5104284', 'n_tokens_mistral': 3564, 'n_tokens_neox': 3405, 'n_words': 1161}