<commit_before>package scalax.collection

import annotation.tailrec
import collection.mutable.{ArrayBuffer, ListBuffer, Queue, PriorityQueue, Stack,
                           Set => MutableSet, Map => MutableMap}
import GraphPredef.{EdgeLikeIn, GraphParam, GraphParamIn, GraphParamOut,
                    NodeIn, NodeOut, EdgeIn, EdgeOut}
import GraphEdge.{EdgeLike}
import mutable.{ArraySet, ExtBitSet}
import scalax.collection.mutable.ExtBitSet
import scalax.collection.mutable.ExtBitSet

trait GraphTraversalImpl[N, E[X] <: EdgeLikeIn[X]]
  extends GraphTraversal[N,E]
  with State[N,E]
{
  import GraphTraversalImpl._
  import GraphTraversal.VisitorReturn._
  import GraphTraversal._
  import State._
  override def findCycle(nodeFilter : (NodeT) => Boolean       = anyNode,
                         edgeFilter : (EdgeT) => Boolean       = anyEdge,
                         maxDepth   :  Int                     = 0,
                         nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                         edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                         ordering   : ElemOrdering             = noOrdering): Option[Cycle] =
    if (order == 0) None
    else {
      val path = CycleBuffer(nodeFilter, edgeFilter)
      val traversal = new Traversal(Successors, nodeFilter, edgeFilter,
                                                nodeVisitor, edgeVisitor, ordering)
      withHandles(2) { handles => 
        implicit val visitedHandle = handles(0) 
        for (node <- nodes if ! node.visited) {
          val res = traversal.depthFirstSearchWGB(
                      node,
                      onPopFound = (n: NodeT) => {
                        if (path.isEmpty) path. +=: (n)
                        else              path. +=: (n, path.firstEdge _)},
                      globalState = handles) 
          if (res.isDefined)
            return Some(path)
        }
      }
      None
    }
  type NodeT <: InnerNodeTraversalImpl
  trait InnerNodeTraversalImpl extends super.InnerNodeLike with InnerNodeState
  { this: NodeT =>
    override def findSuccessor(pred: (NodeT) => Boolean,
                               nodeFilter : (NodeT) => Boolean       = anyNode,
                               edgeFilter : (EdgeT) => Boolean       = anyEdge,
                               nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                               edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                               ordering   : ElemOrdering             = noOrdering) =
    {
      new Traversal(Successors, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this, pred, 0)
    }
    override def findPredecessor(pred: (NodeT) => Boolean,
                                 nodeFilter : (NodeT) => Boolean       = anyNode,
                                 edgeFilter : (EdgeT) => Boolean       = anyEdge,
                                 nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                                 edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                                 ordering   : ElemOrdering             = noOrdering) =
    {
      new Traversal(Predecessors, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this, pred = pred)
    }
    override def findConnected(pred: (NodeT) => Boolean,
                               nodeFilter : (NodeT) => Boolean       = anyNode,
                               edgeFilter : (EdgeT) => Boolean       = anyEdge,
                               nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                               edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                               ordering   : ElemOrdering             = noOrdering) =
    {
      new Traversal(AnyConnected, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this, pred)
    }
    override def pathUntil(pred: (NodeT) => Boolean,
                           nodeFilter : (NodeT) => Boolean       = anyNode,
                           edgeFilter : (EdgeT) => Boolean       = anyEdge,
                           nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                           edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                           ordering   : ElemOrdering             = noOrdering): Option[Path] = {
      val path = PathBuffer(nodeFilter, edgeFilter)
      if (new Traversal(Successors, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this,
                           pred,
                           onPopFound = (n: NodeT) => {
                             if (path.isEmpty) path. +=: (n)
                             else              path. +=: (n, path.firstEdge _) 
                           }).isDefined)
        Some(path.+=:(this, path.firstEdge _))
      else
        None
    }
    override def shortestPathTo(to: NodeT,
                                nodeFilter : (NodeT) => Boolean       = anyNode,
                                edgeFilter : (EdgeT) => Boolean       = anyEdge,
                                nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                                edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                                ordering   : ElemOrdering             = noOrdering): Option[Path] =
    {
      withHandle() { implicit visitedHandle => 
        @inline def visited(n: NodeT) = n visited
  
        type NodeWeight    = (NodeT,Long)
        val dest      = MutableMap[NodeT,Long](this -> 0L)
        val mapToPred = MutableMap[NodeT,NodeT]()
        val traversal = new Traversal(Successors, nodeFilter, edgeFilter,
                                           nodeVisitor, edgeVisitor, ordering) 
        val doNodeVisitor = isCustomNodeVisitor(nodeVisitor)
        val extendedVisitor =
          if (doNodeVisitor)
            nodeVisitor match {
              case e: ExtendedNodeVisitor => Some(e)
              case _ => None
            }
          else None
        // not implicit due to issues #4405 and #4407
        object ordNodeWeight extends Ordering[NodeWeight] {
          def compare(x: NodeWeight,
                      y: NodeWeight) = y._2.compare(x._2)
        }
        val qNodes = new PriorityQueue[NodeWeight]()(ordNodeWeight) += ((this->0L))
  
        def sortedAdjacentsNodes(node: NodeT): Option[PriorityQueue[NodeWeight]] = 
          traversal.filteredDiSuccessors(node, visited, false) match {
            case adj if adj.nonEmpty =>
              Some(adj.
                   foldLeft(new PriorityQueue[NodeWeight]()(ordNodeWeight))(
                     (q,n) => q += ((n, node.outgoingTo(n).filter(edgeFilter(_)).
                                        min(Edge.WeightOrdering).weight))))
            case _ => None
          }
        def relax(pred: NodeT, succ: NodeT) {
          val cost = dest(pred) + pred.outgoingTo(succ).filter(edgeFilter(_)).
                                  min(Edge.WeightOrdering).weight
          if(! dest.isDefinedAt(succ) || cost < dest(succ)) {
            dest      += (succ -> cost)
            mapToPred += (succ -> pred)
          }
        }<commit_msg>Visit nodes in order of their tentative distance value.<commit_after>package scalax.collection

import annotation.tailrec
import collection.mutable.{ArrayBuffer, ListBuffer, Queue, PriorityQueue, Stack,
                           Set => MutableSet, Map => MutableMap}
import GraphPredef.{EdgeLikeIn, GraphParam, GraphParamIn, GraphParamOut,
                    NodeIn, NodeOut, EdgeIn, EdgeOut}
import GraphEdge.{EdgeLike}
import mutable.{ArraySet, ExtBitSet}
import scalax.collection.mutable.ExtBitSet
import scalax.collection.mutable.ExtBitSet

trait GraphTraversalImpl[N, E[X] <: EdgeLikeIn[X]]
  extends GraphTraversal[N,E]
  with State[N,E]
{
  import GraphTraversalImpl._
  import GraphTraversal.VisitorReturn._
  import GraphTraversal._
  import State._
  override def findCycle(nodeFilter : (NodeT) => Boolean       = anyNode,
                         edgeFilter : (EdgeT) => Boolean       = anyEdge,
                         maxDepth   :  Int                     = 0,
                         nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                         edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                         ordering   : ElemOrdering             = noOrdering): Option[Cycle] =
    if (order == 0) None
    else {
      val path = CycleBuffer(nodeFilter, edgeFilter)
      val traversal = new Traversal(Successors, nodeFilter, edgeFilter,
                                                nodeVisitor, edgeVisitor, ordering)
      withHandles(2) { handles => 
        implicit val visitedHandle = handles(0) 
        for (node <- nodes if ! node.visited) {
          val res = traversal.depthFirstSearchWGB(
                      node,
                      onPopFound = (n: NodeT) => {
                        if (path.isEmpty) path. +=: (n)
                        else              path. +=: (n, path.firstEdge _)},
                      globalState = handles) 
          if (res.isDefined)
            return Some(path)
        }
      }
      None
    }
  type NodeT <: InnerNodeTraversalImpl
  trait InnerNodeTraversalImpl extends super.InnerNodeLike with InnerNodeState
  { this: NodeT =>
    override def findSuccessor(pred: (NodeT) => Boolean,
                               nodeFilter : (NodeT) => Boolean       = anyNode,
                               edgeFilter : (EdgeT) => Boolean       = anyEdge,
                               nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                               edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                               ordering   : ElemOrdering             = noOrdering) =
    {
      new Traversal(Successors, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this, pred, 0)
    }
    override def findPredecessor(pred: (NodeT) => Boolean,
                                 nodeFilter : (NodeT) => Boolean       = anyNode,
                                 edgeFilter : (EdgeT) => Boolean       = anyEdge,
                                 nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                                 edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                                 ordering   : ElemOrdering             = noOrdering) =
    {
      new Traversal(Predecessors, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this, pred = pred)
    }
    override def findConnected(pred: (NodeT) => Boolean,
                               nodeFilter : (NodeT) => Boolean       = anyNode,
                               edgeFilter : (EdgeT) => Boolean       = anyEdge,
                               nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                               edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                               ordering   : ElemOrdering             = noOrdering) =
    {
      new Traversal(AnyConnected, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this, pred)
    }
    override def pathUntil(pred: (NodeT) => Boolean,
                           nodeFilter : (NodeT) => Boolean       = anyNode,
                           edgeFilter : (EdgeT) => Boolean       = anyEdge,
                           nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                           edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                           ordering   : ElemOrdering             = noOrdering): Option[Path] = {
      val path = PathBuffer(nodeFilter, edgeFilter)
      if (new Traversal(Successors, nodeFilter, edgeFilter, nodeVisitor, edgeVisitor, ordering).
          depthFirstSearch(this,
                           pred,
                           onPopFound = (n: NodeT) => {
                             if (path.isEmpty) path. +=: (n)
                             else              path. +=: (n, path.firstEdge _) 
                           }).isDefined)
        Some(path.+=:(this, path.firstEdge _))
      else
        None
    }
    override def shortestPathTo(to: NodeT,
                                nodeFilter : (NodeT) => Boolean       = anyNode,
                                edgeFilter : (EdgeT) => Boolean       = anyEdge,
                                nodeVisitor: (NodeT) => VisitorReturn = noNodeAction,
                                edgeVisitor: (EdgeT) => Unit          = noEdgeAction,
                                ordering   : ElemOrdering             = noOrdering): Option[Path] =
    {
      withHandle() { implicit visitedHandle => 
        @inline def visited(n: NodeT) = n visited
  
        type NodeWeight    = (NodeT,Long)
        val dest      = MutableMap[NodeT,Long](this -> 0L)
        val mapToPred = MutableMap[NodeT,NodeT]()
        val traversal = new Traversal(Successors, nodeFilter, edgeFilter,
                                           nodeVisitor, edgeVisitor, ordering) 
        val doNodeVisitor = isCustomNodeVisitor(nodeVisitor)
        val extendedVisitor =
          if (doNodeVisitor)
            nodeVisitor match {
              case e: ExtendedNodeVisitor => Some(e)
              case _ => None
            }
          else None
        // not implicit due to issues #4405 and #4407
        object ordNodeWeight extends Ordering[NodeWeight] {
          def compare(x: NodeWeight,
                      y: NodeWeight) = y._2.compare(x._2)
        }
        val qNodes = new PriorityQueue[NodeWeight]()(ordNodeWeight) += ((this->0L))
  
        def sortedAdjacentsNodes(node: NodeT): Option[PriorityQueue[NodeWeight]] = 
          traversal.filteredDiSuccessors(node, visited, false) match {
            case adj if adj.nonEmpty =>
              Some(adj.
                   foldLeft(new PriorityQueue[NodeWeight]()(ordNodeWeight))(
                     (q,n) => q += ((n, dest(node) +
                                        node.outgoingTo(n).filter(edgeFilter(_)).
                                        min(Edge.WeightOrdering).weight))))
            case _ => None
          }
        def relax(pred: NodeT, succ: NodeT) {
          val cost = dest(pred) + pred.outgoingTo(succ).filter(edgeFilter(_)).
                                  min(Edge.WeightOrdering).weight
          if(! dest.isDefinedAt(succ) || cost < dest(succ)) {
            dest      += (succ -> cost)
            mapToPred += (succ -> pred)
          }
        }
{'fraction_non_alphanumeric': 0.09156034659207204, 'fraction_numerical': 0.002319710718428055, 'mean_word_length': 1.4718381112984822, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 91, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3870996', 'n_tokens_mistral': 3785, 'n_tokens_neox': 3655, 'n_words': 859}