Algorithms

thebiggestbangtheory wrote:

Also, what could be a good measure of the "assumed" run time, I'm thinking median.

I are Troll

using System;
 
namespace Pfz.Threading
{
  /// <summary>
  /// Class that returns the value of DateTime.Now.Ticks when GetValue is called 
  /// but also guarantees that two calls will generate different values, even if
  /// they are done one just after the other.
  /// </summary>
  public static class TicksOrIncrement
  {
    private static readonly object fLock = new object();
    private static long fLastValue = DateTime.Now.Ticks;
    private static readonly Random fRandom = new Random();
		
    /// <summary>
    /// Gets a new DateTime.Now.Ticks value or a random incremented value if
    /// this is a call done at the same microsecond of the last one.
    /// </summary>
    public static long GetNext()
    {
      long ticks = DateTime.Now.Ticks;
			
      lock(fLock)
      {
        if (ticks <= fLastValue)
          ticks = fLastValue + 1 + fRandom.Next(1000);
				
        fLastValue = ticks;
      }
			
      return ticks;
    }
  }
}

  class NodeHeap
  {
    private Node[] m_nodeHeap = new Node[1000000];
    private uint m_lastNodeIndex;
 
    public long Count
    {
      get { return m_nodeHeap.LongLength - 1; }
    }
 
    public Node NodeAt(uint index)
    {
      return m_nodeHeap[index];
    }
 
    public void RemoveAt(uint index)
    {
      if (index > m_lastNodeIndex)
      {
        throw new ArgumentOutOfRangeException("uint index");
      }
 
      SwapNode(ref m_nodeHeap[index], ref  m_nodeHeap[m_lastNodeIndex]);
 
      m_nodeHeap[m_lastNodeIndex--] = null;
 
      SiftUp(index);
    }
 
    public uint IndexOf(Node n) //this needs optimized
    {
      for (uint i = 1; i <= m_lastNodeIndex; i++)
      {
        if (m_nodeHeap[i] == n) return i;
      }
 
      return 0;
    }
 
    public void Add(Node n)
    {
      m_nodeHeap[++m_lastNodeIndex] = n;
 
      SiftDown(m_lastNodeIndex);
    }
 
    public void SiftUp(uint index)
    {
      if (index >= m_lastNodeIndex) return;
 
      uint next = index;
 
      next *= 2;
 
      if (next > m_lastNodeIndex) return;
 
      if (m_nodeHeap[next].Cost < m_nodeHeap[index].Cost)
      {
        if (next != m_lastNodeIndex && m_nodeHeap[next + 1].Cost < m_nodeHeap[next].Cost)
        {
          SwapNode(ref m_nodeHeap[++next], ref m_nodeHeap[index]);
        }
        else
        {
          SwapNode(ref m_nodeHeap[next], ref m_nodeHeap[index]);
        }
 
        SiftUp(next);
      }
    }
 
    public void SiftDown(uint index)
    {
      if (index == 1) return;
 
      uint next = index;
 
      next /= 2;
 
      if (m_nodeHeap[next].Cost > m_nodeHeap[index].Cost)
      {
        SwapNode(ref m_nodeHeap[next], ref m_nodeHeap[index]);
        SiftDown(next);
      }
    }
 
    public Node RemoveFirst()
    {
      Node n = m_nodeHeap[1];
      RemoveAt(1);
      return n;
    }
 
    private void SwapNode(ref Node a, ref Node b)
    {
      Node temp = a;
      a = b;
      b = temp;
    }
  }

harold aptroot wrote:

Btw, your swap work "oddly", I would expect to swap by index and avoid ref hacks, but w/e.

harold aptroot wrote:

see if your value is smaller than the current root, and if so, return and go the other way instead (recursively)

harold aptroot wrote:

(btw, are you going to do A* with it? Heap is a good choice for A* IME)

CaptainSeeSharp wrote:

I'm not quite sure what you mean. Are you saying bounds back and forth between the first and last, then second to first, then second to last, ect...?

harold aptroot wrote:

I didn't need that feature (searching by value) in my A* implementation. Why do you need it?

if((dist(a,b)^2-RadiusSqrd)<0)
{
//inside circle might be a collision canidate
}

public static int blah(point P, point Q)//IComparer
{
     if(P.X>Q.x){ return 1;}
     else if(P.X==Q.x){return 0}
     else{return-1}
}