Free cookie consent management tool by TermsFeed Policy Generator

source: branches/1894_RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/NaivePriorityQueue.cs @ 16110

Last change on this file since 16110 was 8527, checked in by spimming, 12 years ago

#1894:

  • introduced heap interface
  • various heap implementation used as priority queues
  • very simple logger added
  • various versions of Astar algorithm
File size: 2.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using HeuristicLab.Algorithms.GraphRouting.Interfaces;
4
5namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
6  public class NaivePriorityQueue<K, V> : IHeap<K, V>
7    where K : IComparable
8    where V : IComparable {
9    private Node head;
10
11    private int size;
12    public int Size {
13      get { return size; }
14    }
15
16    public NaivePriorityQueue() {
17
18    }
19
20    public void Insert(K key, V value) {
21      Node n = new Node(key, value);
22      if (head == null) {
23        head = n;
24      } else if (head.Key.CompareTo(n.Key) >= 0) {
25        n.Next = head;
26        head = n;
27      } else {
28        Node curr = head;
29        while (curr.Next != null && (curr.Next.Key.CompareTo(n.Key) <= 0)) {
30          curr = curr.Next;
31        }
32        n.Next = curr.Next;
33        curr.Next = n;
34      }
35      size++;
36    }
37
38    public KeyValuePair<K, V> PeekMin() {
39      if (size == 0) {
40        throw new InvalidOperationException("Heap is empty");
41      }
42      KeyValuePair<K, V> pair = new KeyValuePair<K, V>(head.Key, head.Value);
43      return pair;
44    }
45
46    public K PeekMinKey() {
47      if (size == 0) {
48        throw new InvalidOperationException("Heap is empty");
49      }
50      return head.Key;
51    }
52
53    public V PeekMinValue() {
54      if (size == 0) {
55        throw new InvalidOperationException("Heap is empty");
56      }
57      return head.Value;
58    }
59
60    public void DecreaseKey(K key, V value) {
61      Node n = null;
62      Node curr = head;
63      Node prev = null;
64
65      // search for node to be updated
66      while (curr != null) {
67        if (curr.Value.CompareTo(value) == 0) {
68          n = curr;
69          break;
70        }
71        prev = curr;
72        curr = curr.Next;
73      }
74
75      // check if node was found
76      if (n == null) {
77        throw new InvalidOperationException("Value not found");
78      }
79
80      //update key
81      n.Key = key;
82
83      // if node is head of list we're done ...
84
85      if (prev != null) {
86        // ... otherwise remove from list and reinsert it
87        prev.Next = n.Next;
88        Insert(n.Key, n.Value);
89        n = null;
90      }
91    }
92
93    public void RemoveMin() {
94      if (size == 0) {
95        throw new InvalidOperationException("Heap is empty");
96      }
97      head = head.Next;
98      size--;
99    }
100
101    private class Node {
102      public K Key;
103      public V Value;
104      public Node Next;
105
106      public Node(K key, V value) {
107        this.Key = key;
108        this.Value = value;
109      }
110    }
111  }
112}
Note: See TracBrowser for help on using the repository browser.