ceph/src/dmclock/support/src/heap.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 /*
   5  * Copyright (C) 2016 Red Hat Inc.
   6  */
   7
   8
   9 #pragma once
  10
  11
  12 #include <vector>
  13 #include <ostream>
  14
  15 #include "assert.h"
  16
  17
  18 namespace crimson {
  19
  20   /*
  21    * T : type of data held in the heap.
  22    *
  23    * C : class that implements operator() with two arguments and
  24    * returns a boolean when the first argument is greater than (higher
  25    * in priority than) the second.
  26    */
  27   template<typename T, typename C>
  28   class Heap {
  29
  30   public:
  31
  32     class iterator {
  33
  34       friend Heap<T,C>;
  35
  36       Heap<T,C>& heap;
  37       int        index;
  38
  39       iterator(Heap<T,C>& _heap, int _index) :
  40         heap(_heap),
  41         index(_index)
  42       {
  43         // empty
  44       }
  45
  46     public:
  47
  48       iterator(iterator&& other) :
  49         heap(other.heap),
  50         index(other.index)
  51       {
  52         // empty
  53       }
  54
  55       iterator& operator++() {
  56         ++index;
  57         return *this;
  58       }
  59
  60       bool operator==(const iterator& other) const {
  61         return index == other.index;
  62       }
  63
  64       bool operator!=(const iterator& other) const {
  65         return !(*this == other);
  66       }
  67
  68       T& operator*() {
  69         return heap.data[index];
  70       }
  71
  72       // the item this iterator refers to
  73       void increase() {
  74         heap.siftUp(index);
  75       }
  76     }; // class iterator
  77
  78     friend iterator;
  79
  80   protected:
  81
  82     std::vector<T> data;
  83     int count;
  84     C comparator;
  85
  86     // parent(0) should be a negative value, which it is due to
  87     // truncating towards negative infinity
  88     static inline int parent(int i) { return (i - 1) / 2; }
  89
  90     static inline int lhs(int i) { return 2*i + 1; }
  91
  92     static inline int rhs(int i) { return 2*i + 2; }
  93
  94     void siftUp(int i) {
  95       assert(i < count);
  96
  97       while (i > 0) {
  98         int pi = parent(i);
  99         if (!comparator(data[i], data[pi])) {
 100           break;
 101         }
 102
 103         std::swap(data[i], data[pi]);
 104         i = pi;
 105       }
 106     }
 107
 108     void siftDown(int i) {
 109       while (i < count) {
 110         int li = lhs(i);
 111         int ri = rhs(i);
 112
 113         if (li < count) {
 114           if (comparator(data[li], data[i])) {
 115             if (ri < count && comparator(data[ri], data[li])) {
 116               std::swap(data[i], data[ri]);
 117               i = ri;
 118             } else {
 119               std::swap(data[i], data[li]);
 120               i = li;
 121             }
 122           } else if (ri < count && comparator(data[ri], data[i])) {
 123             std::swap(data[i], data[ri]);
 124             i = ri;
 125           } else {
 126             break;
 127           }
 128         } else {
 129           break;
 130         }
 131       }
 132     }
 133
 134
 135   public:
 136
 137     Heap() :
 138       count(0)
 139     {
 140       // empty
 141     }
 142
 143     Heap(const Heap<T,C>& other) {
 144       data.resize(other.data.size());
 145       for (int i = 0; i < other.count; ++i) {
 146         data[i] = other.data[i];
 147       }
 148       count = other.count;
 149     }
 150
 151     const Heap<T,C>& operator=(const Heap<T,C>& other) {
 152       data.resize(other.data.size());
 153       for (int i = 0; i < other.count; ++i) {
 154         data[i] = other.data[i];
 155       }
 156       count = other.count;
 157       return *this;
 158     }
 159
 160     bool empty() const { return 0 == count; }
 161
 162     T& top() { return data[0]; }
 163
 164     void push(T item) {
 165       int i = count++;
 166       data.push_back(item);
 167       siftUp(i);
 168     }
 169
 170     void pop() {
 171       data[0] = data[--count];
 172       data.resize(count);
 173       siftDown(0);
 174     }
 175
 176     void updateTop() {
 177       siftDown(0);
 178     }
 179
 180     void clear() {
 181       count = 0;
 182       data.resize(0);
 183     }
 184
 185     iterator begin() {
 186       return iterator(*this, 0);
 187     }
 188
 189     iterator end() {
 190       return iterator(*this, count);
 191     }
 192
 193     std::ostream& displaySorted(std::ostream& out,
 194                                 std::function<bool(const T&)> filter,
 195                                 bool insert_line_breaks = true) const {
 196       Heap<T,C> temp = *this;
 197
 198       bool first = true;
 199       out << "[ ";
 200
 201       while(!temp.empty()) {
 202         const T& top = temp.top();
 203         if (filter(top)) {
 204           if (!first) {
 205             out << ", ";
 206           }
 207           if (insert_line_breaks) {
 208             out << std::endl << "    ";
 209           }
 210           out << temp.top();
 211           first = false;
 212         }
 213         temp.pop();
 214       }
 215
 216       out << " ]";
 217       if (insert_line_breaks) {
 218         out << std::endl;
 219       }
 220       return out;
 221     }
 222
 223     template<typename T1, typename T2>
 224     friend std::ostream& operator<<(std::ostream&, const Heap<T1,T2>&);
 225   }; // class Heap
 226
 227
 228   template<typename T1, typename T2>
 229   std::ostream& operator<<(std::ostream& out, const Heap<T1,T2>& h) {
 230     out << "[ ";
 231     if (h.count) {
 232       out << h.data[0];
 233     }
 234     for (int i = 1; i < h.count; i++) {
 235       out << ", " << h.data[i];
 236     }
 237     out << " ]";
 238     return out;
 239   }
 240 } // namespace