Summary

Class:HeapLibrary.Heap`1
Assembly:HeapLibrary
File(s):D:\Workspaces\MFF\NPRG031-Programovani_2\2016\Workshop-11\HeapLibrary\HeapLibrary\Heap.cs
Covered lines:43
Uncovered lines:60
Coverable lines:103
Total lines:170
Line coverage:41.7%
Branch coverage:32.5%

Metrics

MethodCyclomatic ComplexitySequence CoverageBranch Coverage
Contains(...)1100100
Add(...)27066.67
ChangeCost(...)500
Top()28066.67
Pop()371.4360
MoveUp(...)358.3380
MoveDown(...)1426.1933.33
.ctor()1100100

File(s)

D:\Workspaces\MFF\NPRG031-Programovani_2\2016\Workshop-11\HeapLibrary\HeapLibrary\Heap.cs

#LineLine coverage
 1using System;
 2using System.Collections.Generic;
 3using System.Linq;
 4using System.Text;
 5using System.Threading.Tasks;
 6
 7namespace HeapLibrary
 8{
 9    class HeapItem<T>
 10    {
 11
 12        public int cost;
 13        public T obj;
 14
 15        public HeapItem(int cost, T o)
 16        {
 17            this.cost = cost;
 18            this.obj = o;
 19        }
 20
 21    }
 22
 23    public class Heap<T>
 24    {
 25
 126        List<HeapItem<T>> heap = new List<HeapItem<T>>();
 27
 128        Dictionary<T, HeapItem<T>> items = new Dictionary<T, HeapItem<T>>();
 29
 30        public bool Contains(T o)
 231        {
 232            return items.ContainsKey(o);
 233        }
 34
 35        public void Add(int cost, T o)
 236        {
 237             if (Contains(o))
 038            {
 039                ChangeCost(cost, o);
 040                return;
 41            }
 42
 243            HeapItem<T> item = new HeapItem<T>(cost, o);
 44
 245            heap.Add(item);
 246            items.Add(o, item);
 47
 248            MoveUp(heap.Count() - 1);
 249        }
 50
 51        public void ChangeCost(int cost, T o)
 052        {
 053             for (int i = 0; i < heap.Count(); ++i)
 054            {
 055                HeapItem<T> item = heap[i];
 056                 if (ReferenceEquals(item.obj, o))
 057                {
 058                     if (item.cost == cost) return;
 059                     if (item.cost > cost)
 060                    {
 061                        item.cost = cost;
 062                        MoveDown(i);
 063                    }
 64                    else
 065                    {
 066                        item.cost = cost;
 067                        MoveUp(i);
 068                    }
 069                    return;
 70                }
 071            }
 072        }
 73
 74        public T Top()
 175        {
 176             if (heap.Count() == 0) return default(T);
 177            return heap[0].obj;
 178        }
 79
 80        public T Pop()
 181        {
 182             if (heap.Count() == 0) return default(T);
 83
 184            T first = Top();
 185            items.Remove(first);
 86
 187             if (heap.Count() == 1)
 088            {
 089                heap.RemoveAt(0);
 090                return first;
 91            }
 92
 193            heap[0] = heap[heap.Count() - 1];
 194            heap.RemoveAt(heap.Count() - 1);
 95
 196            MoveDown(0);
 97
 198            return first;
 199        }
 100
 101        private void MoveUp(int index)
 2102        {
 3103             if (index == 0) return;
 1104            HeapItem<T> i1 = heap[index];
 1105            HeapItem<T> i2 = heap[index / 2];
 1106             if (i1.cost < i2.cost)
 0107            {
 0108                heap[index / 2] = i1;
 0109                heap[index] = i2;
 0110                MoveUp(index / 2);
 0111            }
 2112        }
 113
 114        private void MoveDown(int index)
 1115        {
 1116             if (index >= heap.Count()) return;
 1117            HeapItem<T> i1 = heap[index];
 118
 1119             HeapItem<T> i2 = (index * 2 < heap.Count() ? heap[index * 2] : null);
 1120             HeapItem<T> i3 = (index * 2 + 1 < heap.Count() ? heap[index * 2 + 1] : null);
 121
 1122             if (i2 == null)
 0123            {
 0124                 if (i3 == null)
 0125                {
 0126                    return;
 127                }
 0128                 if (i1.cost > i3.cost)
 0129                {
 0130                    heap[index] = i2;
 0131                    heap[index * 2 + 1] = i1;
 0132                    MoveDown(index * 2 + 1);
 0133                }
 0134                return;
 135            }
 136
 1137             if (i3 == null)
 1138            {
 1139                 if (i1.cost > i2.cost)
 0140                {
 0141                    heap[index] = i2;
 0142                    heap[index * 2] = i3;
 0143                    MoveDown(index * 2);
 0144                }
 1145                return;
 146            }
 147
 0148             if (i1.cost <= i2.cost && i1.cost <= i2.cost)
 0149            {
 0150                return;
 151            }
 152
 0153             if (i2.cost > i3.cost)
 0154            {
 0155                heap[index] = i3;
 0156                heap[index * 2 + 1] = i1;
 0157                MoveDown(index * 2 + 1);
 0158            }
 159            else
 0160            {
 0161                heap[index] = i2;
 0162                heap[index * 2 + 1] = i1;
 0163                MoveDown(index * 2);
 0164            }
 165
 1166        }
 167
 168    }
 169
 170}