libs/canvas/lookup_table.cc

   1 #include "canvas/lookup_table.h"
   2 #include "canvas/group.h"
   3
   4 using namespace std;
   5 using namespace ArdourCanvas;
   6
   7 LookupTable::LookupTable (Group const & group)
   8         : _group (group)
   9 {
  10
  11 }
  12
  13 LookupTable::~LookupTable ()
  14 {
  15
  16 }
  17
  18 DumbLookupTable::DumbLookupTable (Group const & group)
  19         : LookupTable (group)
  20 {
  21
  22 }
  23
  24 vector<Item *>
  25 DumbLookupTable::get (Rect const &)
  26 {
  27         list<Item *> const & items = _group.items ();
  28         vector<Item *> vitems;
  29         copy (items.begin(), items.end(), back_inserter (vitems));
  30         return vitems;
  31 }
  32
  33 /* XXX: what coordinate system is the point in? parent of our group I think */
  34 vector<Item *>
  35 DumbLookupTable::items_at_point (Duple point) const
  36 {
  37         list<Item *> items = _group.items ();
  38         vector<Item *> vitems;
  39
  40         for (list<Item *>::const_iterator i = items.begin(); i != items.end(); ++i) {
  41                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
  42                 if (item_bbox) {
  43                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
  44                         if (parent_bbox.contains (point)) {
  45                                 vitems.push_back (*i);
  46                         }
  47                 }
  48         }
  49
  50         return vitems;
  51 }
  52
  53 OptimizingLookupTable::OptimizingLookupTable (Group const & group, int items_per_cell)
  54         : LookupTable (group)
  55         , _items_per_cell (items_per_cell)
  56         , _added (false)
  57 {
  58         list<Item*> const & items = _group.items ();
  59
  60         /* number of cells */
  61         int const cells = items.size() / _items_per_cell;
  62         /* hence number down each side of the table's square */
  63         _dimension = max (1, int (rint (sqrt (cells))));
  64
  65         _cells = new Cell*[_dimension];
  66         for (int i = 0; i < _dimension; ++i) {
  67                 _cells[i] = new Cell[_dimension];
  68         }
  69
  70         /* our group's bounding box in its coordinates */
  71         boost::optional<Rect> bbox = _group.bounding_box ();
  72         if (!bbox) {
  73                 return;
  74         }
  75
  76         _cell_size.x = bbox.get().width() / _dimension;
  77         _cell_size.y = bbox.get().height() / _dimension;
  78         _offset.x = bbox.get().x0;
  79         _offset.y = bbox.get().y0;
  80
  81 //      cout << "BUILD bbox=" << bbox.get() << ", cellsize=" << _cell_size << ", offset=" << _offset << ", dimension=" << _dimension << "\n";
  82
  83         for (list<Item*>::const_iterator i = items.begin(); i != items.end(); ++i) {
  84
  85                 /* item bbox in its own coordinates */
  86                 boost::optional<Rect> item_bbox = (*i)->bounding_box ();
  87                 if (!item_bbox) {
  88                         continue;
  89                 }
  90
  91                 /* and in the group's coordinates */
  92                 Rect const item_bbox_in_group = (*i)->item_to_parent (item_bbox.get ());
  93
  94                 int x0, y0, x1, y1;
  95                 area_to_indices (item_bbox_in_group, x0, y0, x1, y1);
  96
  97                 /* XXX */
  98                 assert (x0 >= 0);
  99                 assert (y0 >= 0);
 100                 assert (x1 >= 0);
 101                 assert (y1 >= 0);
 102                 //assert (x0 <= _dimension);
 103                 //assert (y0 <= _dimension);
 104                 //assert (x1 <= _dimension);
 105                 //assert (y1 <= _dimension);
 106
 107                 if (x0 > _dimension) {
 108                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x0 - bbox.get().x0) << "\n";
 109                         x0 = _dimension;
 110                 }
 111                 if (x1 > _dimension) {
 112                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.x1 - bbox.get().x1) << "\n";
 113                         x1 = _dimension;
 114                 }
 115                 if (y0 > _dimension) {
 116                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y0 - bbox.get().y0) << "\n";
 117                         y0 = _dimension;
 118                 }
 119                 if (y1 > _dimension) {
 120                         cout << "WARNING: item outside bbox by " << (item_bbox_in_group.y1 - bbox.get().y1) << "\n";
 121                         y1 = _dimension;
 122                 }
 123
 124                 for (int x = x0; x < x1; ++x) {
 125                         for (int y = y0; y < y1; ++y) {
 126                                 _cells[x][y].push_back (*i);
 127                         }
 128                 }
 129         }
 130 }
 131
 132 void
 133 OptimizingLookupTable::area_to_indices (Rect const & area, int& x0, int& y0, int& x1, int& y1) const
 134 {
 135         if (_cell_size.x == 0 || _cell_size.y == 0) {
 136                 x0 = y0 = x1 = y1 = 0;
 137                 return;
 138         }
 139
 140         Rect const offset_area = area.translate (-_offset);
 141
 142         x0 = floor (offset_area.x0 / _cell_size.x);
 143         y0 = floor (offset_area.y0 / _cell_size.y);
 144         x1 = ceil  (offset_area.x1 / _cell_size.x);
 145         y1 = ceil  (offset_area.y1 / _cell_size.y);
 146 }
 147
 148 OptimizingLookupTable::~OptimizingLookupTable ()
 149 {
 150         for (int i = 0; i < _dimension; ++i) {
 151                 delete[] _cells[i];
 152         }
 153
 154         delete[] _cells;
 155 }
 156
 157 void
 158 OptimizingLookupTable::point_to_indices (Duple point, int& x, int& y) const
 159 {
 160         if (_cell_size.x == 0 || _cell_size.y == 0) {
 161                 x = y = 0;
 162                 return;
 163         }
 164
 165         Duple const offset_point = point - _offset;
 166
 167         x = floor (offset_point.x / _cell_size.x);
 168         y = floor (offset_point.y / _cell_size.y);
 169 }
 170
 171 vector<Item*>
 172 OptimizingLookupTable::items_at_point (Duple point) const
 173 {
 174         int x;
 175         int y;
 176         point_to_indices (point, x, y);
 177
 178         if (x >= _dimension) {
 179                 cout << "WARNING: x=" << x << ", dim=" << _dimension << ", px=" << point.x << " cellsize=" << _cell_size << "\n";
 180         }
 181
 182         if (y >= _dimension) {
 183                 cout << "WARNING: y=" << y << ", dim=" << _dimension << ", py=" << point.y << " cellsize=" << _cell_size << "\n";
 184         }
 185
 186         /* XXX: hmm */
 187         x = min (_dimension - 1, x);
 188         y = min (_dimension - 1, y);
 189
 190         assert (x >= 0);
 191         assert (y >= 0);
 192
 193         Cell const & cell = _cells[x][y];
 194         vector<Item*> items;
 195         for (Cell::const_iterator i = cell.begin(); i != cell.end(); ++i) {
 196                 boost::optional<Rect> const item_bbox = (*i)->bounding_box ();
 197                 if (item_bbox) {
 198                         Rect parent_bbox = (*i)->item_to_parent (item_bbox.get ());
 199                         if (parent_bbox.contains (point)) {
 200                                 items.push_back (*i);
 201                         }
 202                 }
 203         }
 204
 205         return items;
 206 }
 207
 208 /** @param area Area in our owning group's coordinates */
 209 vector<Item*>
 210 OptimizingLookupTable::get (Rect const & area)
 211 {
 212         list<Item*> items;
 213         int x0, y0, x1, y1;
 214         area_to_indices (area, x0, y0, x1, y1);
 215
 216         /* XXX: hmm... */
 217         x0 = min (_dimension - 1, x0);
 218         y0 = min (_dimension - 1, y0);
 219         x1 = min (_dimension, x1);
 220         y1 = min (_dimension, y1);
 221
 222         for (int x = x0; x < x1; ++x) {
 223                 for (int y = y0; y < y1; ++y) {
 224                         for (Cell::const_iterator i = _cells[x][y].begin(); i != _cells[x][y].end(); ++i) {
 225                                 if (find (items.begin(), items.end(), *i) == items.end ()) {
 226                                         items.push_back (*i);
 227                                 }
 228                         }
 229                 }
 230         }
 231
 232         vector<Item*> vitems;
 233         copy (items.begin (), items.end (), back_inserter (vitems));
 234
 235         return vitems;
 236 }
 237