Microscopic Traffic Simulator

- Main Page
- Packages
- Classes
- Files

- File List

Heap.cs
Go to the documentation of this file.
1 using System;
2 using System.Collections.Generic;
3
4 namespace Microscopic_Traffic_Simulator___Model.Utilities
5 {
11 class Heap<TKey, TValue> where TKey : IComparable
12 {
16 List<KeyValuePair<TKey, TValue>> list = new List<KeyValuePair<TKey, TValue>>();
17
18
22 internal KeyValuePair<TKey, TValue> Top { get { return list[0]; } }
23
27 internal int Count { get { return list.Count; } }
28
34 internal void Push(TKey key, TValue value)
35 {
36 list.Add(new KeyValuePair<TKey, TValue>(key, value));
37 int index = list.Count - 1;
38 while (index > 0 && list[index].Key.CompareTo(list[(index - 1) >> 1].Key) < 0)
39 {
40 Swap(index, (index - 1) >> 1);
41 index = (index - 1) >> 1;
42 }
43 }
44
49 internal KeyValuePair<TKey, TValue> Pop()
50 {
51 KeyValuePair<TKey, TValue> toReturn =
52 new KeyValuePair<TKey, TValue>(list[0].Key, list[0].Value);
53 list[0] = list[list.Count - 1];
54 list.RemoveAt(list.Count - 1);
55 int index = 0;
56 bool end;
57 do
58 {
59 end = true;
60 int son1 = (index << 1) + 1;
61 int son2 = (index << 1) + 2;
62 if (son2 < list.Count)
63 {
64 int lessSon = list[son1].Key.CompareTo(list[son2].Key) > 0 ? son2 : son1;
65 if (list[index].Key.CompareTo(list[lessSon].Key) >= 0)
66 {
67 Swap(index, lessSon);
68 index = lessSon;
69 end = false;
70 }
71 }
72 else if (son1 < list.Count)
73 {
74 if (list[index].Key.CompareTo(list[son1].Key) >= 0)
75 {
76 Swap(index, son1);
77 index = son1;
78 end = false;
79 }
80 }
81 } while (!end);
82 return toReturn;
83 }
84
88 internal void Clear()
89 {
90 list.Clear();
91 }
92
98 private void Swap(int index1, int index2)
99 {
100 KeyValuePair<TKey, TValue> pom = list[index1];
101 list[index1] = list[index2];
102 list[index2] = pom;
103 }
104 }
105 }
System
Microscopic_Traffic_Simulator___Model.Utilities.Heap
Heap data structure where values of items are ordered by their keys.
Definition: Heap.cs:11
Microscopic_Traffic_Simulator___Model