Summary

Class:HeapLibrary.HeapItem`1
Assembly:HeapLibrary
File(s):D:\Workspaces\MFF\NPRG031-Programovani_2\2016\Workshop-11\HeapLibrary\HeapLibrary\Heap.cs
Covered lines:5
Uncovered lines:0
Coverable lines:5
Total lines:170
Line coverage:100%

Metrics

MethodCyclomatic ComplexitySequence CoverageBranch Coverage
.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
 215        public HeapItem(int cost, T o)
 216        {
 217            this.cost = cost;
 218            this.obj = o;
 219        }
 20
 21    }
 22
 23    public class Heap<T>
 24    {
 25
 26        List<HeapItem<T>> heap = new List<HeapItem<T>>();
 27
 28        Dictionary<T, HeapItem<T>> items = new Dictionary<T, HeapItem<T>>();
 29
 30        public bool Contains(T o)
 31        {
 32            return items.ContainsKey(o);
 33        }
 34
 35        public void Add(int cost, T o)
 36        {
 37            if (Contains(o))
 38            {
 39                ChangeCost(cost, o);
 40                return;
 41            }
 42
 43            HeapItem<T> item = new HeapItem<T>(cost, o);
 44
 45            heap.Add(item);
 46            items.Add(o, item);
 47
 48            MoveUp(heap.Count() - 1);
 49        }
 50
 51        public void ChangeCost(int cost, T o)
 52        {
 53            for (int i = 0; i < heap.Count(); ++i)
 54            {
 55                HeapItem<T> item = heap[i];
 56                if (ReferenceEquals(item.obj, o))
 57                {
 58                    if (item.cost == cost) return;
 59                    if (item.cost > cost)
 60                    {
 61                        item.cost = cost;
 62                        MoveDown(i);
 63                    }
 64                    else
 65                    {
 66                        item.cost = cost;
 67                        MoveUp(i);
 68                    }
 69                    return;
 70                }
 71            }
 72        }
 73
 74        public T Top()
 75        {
 76            if (heap.Count() == 0) return default(T);
 77            return heap[0].obj;
 78        }
 79
 80        public T Pop()
 81        {
 82            if (heap.Count() == 0) return default(T);
 83
 84            T first = Top();
 85            items.Remove(first);
 86
 87            if (heap.Count() == 1)
 88            {
 89                heap.RemoveAt(0);
 90                return first;
 91            }
 92
 93            heap[0] = heap[heap.Count() - 1];
 94            heap.RemoveAt(heap.Count() - 1);
 95
 96            MoveDown(0);
 97
 98            return first;
 99        }
 100
 101        private void MoveUp(int index)
 102        {
 103            if (index == 0) return;
 104            HeapItem<T> i1 = heap[index];
 105            HeapItem<T> i2 = heap[index / 2];
 106            if (i1.cost < i2.cost)
 107            {
 108                heap[index / 2] = i1;
 109                heap[index] = i2;
 110                MoveUp(index / 2);
 111            }
 112        }
 113
 114        private void MoveDown(int index)
 115        {
 116            if (index >= heap.Count()) return;
 117            HeapItem<T> i1 = heap[index];
 118
 119            HeapItem<T> i2 = (index * 2 < heap.Count() ? heap[index * 2] : null);
 120            HeapItem<T> i3 = (index * 2 + 1 < heap.Count() ? heap[index * 2 + 1] : null);
 121
 122            if (i2 == null)
 123            {
 124                if (i3 == null)
 125                {
 126                    return;
 127                }
 128                if (i1.cost > i3.cost)
 129                {
 130                    heap[index] = i2;
 131                    heap[index * 2 + 1] = i1;
 132                    MoveDown(index * 2 + 1);
 133                }
 134                return;
 135            }
 136
 137            if (i3 == null)
 138            {
 139                if (i1.cost > i2.cost)
 140                {
 141                    heap[index] = i2;
 142                    heap[index * 2] = i3;
 143                    MoveDown(index * 2);
 144                }
 145                return;
 146            }
 147
 148            if (i1.cost <= i2.cost && i1.cost <= i2.cost)
 149            {
 150                return;
 151            }
 152
 153            if (i2.cost > i3.cost)
 154            {
 155                heap[index] = i3;
 156                heap[index * 2 + 1] = i1;
 157                MoveDown(index * 2 + 1);
 158            }
 159            else
 160            {
 161                heap[index] = i2;
 162                heap[index * 2 + 1] = i1;
 163                MoveDown(index * 2);
 164            }
 165
 166        }
 167
 168    }
 169
 170}