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