sortednodelist.cs

来自「A .NET Path Finder Library Path Finder 」· CS 代码 · 共 68 行

//This will later be replaced with something fast such as a binary heap.

using System.Collections.Generic;

namespace HenizeSoftware
{
  namespace PathFinding
  {
    class NodeComparer : IComparer<Node>
    {
      public int Compare(Node a, Node b)
      {
        return a.TotalCost - b.TotalCost;
      }
    }

    class SortedNodeList
    {
      List<Node> list = new List<Node>();
      NodeComparer nodeComparer = new NodeComparer();

      public int Count
      {
        get { return list.Count; }
      }

      public Node NodeAt(int i)
      {
        return list[i];
      }

      public void RemoveAt(int i)
      {
        list.RemoveAt(i);
      }

      public int IndexOf(Node n)
      {
        return list.IndexOf(n);
      }

      public int Add(Node n)
      {
        int k = list.BinarySearch(n, nodeComparer);
          
        if (k == -1) // no element
          list.Insert(0, n);
        else if (k < 0) // find location by complement
        {
          k = ~k;
          list.Insert(k, n);
        }
        else if (k >= 0)
          list.Insert(k, n);

        return k;
      }

      public Node RemoveFirst()
      {
        Node n = list[0];
        list.RemoveAt(0);
        return n;
      }

    }
  }
}