source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/NaivePriorityQueue.cs @ 8539

using System;
using System.Collections.Generic;
using HeuristicLab.Algorithms.GraphRouting.Interfaces;

namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
  public class NaivePriorityQueue<K, V> : IHeap<K, V>
    where K : IComparable
    where V : IComparable {
    private Node head;

    private int size;
    public int Size {
      get { return size; }
    }

    public NaivePriorityQueue() {

    }

    public void Insert(K key, V value) {
      Node n = new Node(key, value);
      if (head == null) {
        head = n;
      } else if (head.Key.CompareTo(n.Key) >= 0) {
        n.Next = head;
        head = n;
      } else {
        Node curr = head;
        while (curr.Next != null && (curr.Next.Key.CompareTo(n.Key) <= 0)) {
          curr = curr.Next;
        }
        n.Next = curr.Next;
        curr.Next = n;
      }
      size++;
    }

    public KeyValuePair<K, V> PeekMin() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      KeyValuePair<K, V> pair = new KeyValuePair<K, V>(head.Key, head.Value);
      return pair;
    }

    public K PeekMinKey() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      return head.Key;
    }

    public V PeekMinValue() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      return head.Value;
    }

    public void DecreaseKey(K key, V value) {
      Node n = null;
      Node curr = head;
      Node prev = null;

      // search for node to be updated
      while (curr != null) {
        if (curr.Value.CompareTo(value) == 0) {
          n = curr;
          break;
        }
        prev = curr;
        curr = curr.Next;
      }

      // check if node was found
      if (n == null) {
        throw new InvalidOperationException("Value not found");
      }

      //update key
      n.Key = key;

      // if node is head of list we're done ...

      if (prev != null) {
        // ... otherwise remove from list and reinsert it
        prev.Next = n.Next;
        Insert(n.Key, n.Value);
        n = null;
      }
    }

    public void RemoveMin() {
      if (size == 0) {
        throw new InvalidOperationException("Heap is empty");
      }
      head = head.Next;
      size--;
    }

    private class Node {
      public K Key;
      public V Value;
      public Node Next;

      public Node(K key, V value) {
        this.Key = key;
        this.Value = value;
      }
    }
  }
}