src/Util/AllocatedGrid.hpp

   1 /*
   2  * Copyright (C) 2010 Max Kellermann <max@duempel.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * - Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the
  14  * distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  20  * FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  27  * OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #ifndef XCSOAR_ALLOCATED_GRID_HPP
  31 #define XCSOAR_ALLOCATED_GRID_HPP
  32
  33 #include "AllocatedArray.hpp"
  34
  35 #include <assert.h>
  36
  37 /**
  38  * A two dimensional array allocated on the heap with a length
  39  * determined at runtime.
  40  */
  41 template<class T>
  42 class AllocatedGrid {
  43 protected:
  44   AllocatedArray<T> array;
  45   unsigned width, height;
  46
  47 public:
  48   typedef typename AllocatedArray<T>::iterator iterator;
  49   typedef typename AllocatedArray<T>::const_iterator const_iterator;
  50
  51   constexpr AllocatedGrid():width(0), height(0) {}
  52   AllocatedGrid(unsigned _width, unsigned _height)
  53     :array(_width * _height), width(_width), height(_height) {}
  54
  55   constexpr bool IsDefined() const {
  56     return array.size() > 0;
  57   }
  58
  59   constexpr unsigned GetWidth() const {
  60     return width;
  61   }
  62
  63   constexpr unsigned GetHeight() const {
  64     return height;
  65   }
  66
  67   constexpr unsigned GetSize() const {
  68     return width * height;
  69   }
  70
  71   const T &Get(unsigned x, unsigned y) const {
  72     assert(x < width);
  73     assert(y < height);
  74
  75     return array[y * width + x];
  76   }
  77
  78   T &Get(unsigned x, unsigned y) {
  79     assert(x < width);
  80     assert(y < height);
  81
  82     return array[y * width + x];
  83   }
  84
  85   const T &GetLinear(unsigned i) const {
  86     assert(i < GetSize());
  87
  88     return array[i];
  89   }
  90
  91   T &GetLinear(unsigned i) {
  92     assert(i < GetSize());
  93
  94     return array[i];
  95   }
  96
  97   iterator begin() {
  98     return array.begin();
  99   }
 100
 101   constexpr const_iterator begin() const {
 102     return array.begin();
 103   }
 104
 105   iterator end() {
 106     return begin() + GetSize();
 107   }
 108
 109   constexpr const_iterator end() const {
 110     return begin() + GetSize();
 111   }
 112
 113   iterator GetPointerAt(unsigned x, unsigned y) {
 114     assert(x < width);
 115     assert(y < height);
 116
 117     return begin() + y * width + x;
 118   }
 119
 120   const_iterator GetPointerAt(unsigned x, unsigned y) const {
 121     assert(x < width);
 122     assert(y < height);
 123
 124     return begin() + y * width + x;
 125   }
 126
 127   void Reset() {
 128     width = height = 0;
 129     array.ResizeDiscard(0);
 130   }
 131
 132   void GrowDiscard(unsigned _width, unsigned _height) {
 133     array.GrowDiscard(_width * _height);
 134     width = _width;
 135     height = _height;
 136   }
 137
 138   /**
 139    * Resize the grid, preserving as many old values as fit into the
 140    * new dimensions, and fill newly allocated array slots.
 141    */
 142   void GrowPreserveFill(unsigned _width, unsigned _height, const T &fill=T()) {
 143     if (_width < width) {
 144       const unsigned h = std::min(height, _height);
 145       const auto end = array.begin() + h * width;
 146
 147       for (auto in = array.begin() + width, out = array.begin() + _width;
 148            in < end; in += width) {
 149         out = std::move(in, in + _width, out);
 150       }
 151
 152       width = _width;
 153     }
 154
 155     array.GrowPreserve(_width * _height, width * height);
 156
 157     if (_width > width) {
 158       const unsigned h = std::min(height, _height);
 159       const auto end = array.begin();
 160
 161       for (auto in = array.begin() + (h - 1) * width,
 162              out = array.begin() + (h - 1) * _width + width;
 163            in < end; in -= width, out -= _width) {
 164         std::move_backward(in, in + width, out);
 165         std::fill(out, out + _width - width, fill);
 166       }
 167
 168       width = _width;
 169     }
 170
 171     std::fill(array.begin() + width * height, array.end(), fill);
 172
 173     height = _height;
 174   }
 175 };
 176
 177 #endif