Debian Codegraph @

engine/core/model/structures/cellcache.cpp

raw
1 /***************************************************************************
2 * Copyright (C) 2005-2019 by the FIFE team *
3 * http://www.fifengine.net *
4 * This file is part of FIFE. *
5 * *
6 * FIFE is free software; you can redistribute it and/or *
7 * modify it under the terms of the GNU Lesser General Public *
8 * License as published by the Free Software Foundation; either *
9 * version 2.1 of the License, or (at your option) any later version. *
10 * *
11 * This library is distributed in the hope that it will be useful, *
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14 * Lesser General Public License for more details. *
15 * *
16 * You should have received a copy of the GNU Lesser General Public *
17 * License along with this library; if not, write to the *
18 * Free Software Foundation, Inc., *
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20 ***************************************************************************/
21
22 // Standard C++ library includes
23
24 // 3rd party library includes
25
26 // FIFE includes
27 // These includes are split up in two parts, separated by one empty line
28 // First block: files included from the FIFE root src directory
29 // Second block: files included from the same folder
30 #include "model/metamodel/grids/cellgrid.h"
31 #include "util/log/logger.h"
32 #include "util/structures/purge.h"
33
34 #include "cellcache.h"
35 #include "cell.h"
36 #include "layer.h"
37 #include "instance.h"
38 #include "map.h"
39 #include "instancetree.h"
40
41 namespace FIFE {
42
43 static Logger _log(LM_STRUCTURES);
44
45 class CellCacheChangeListener : public LayerChangeListener {
46 public:
47 CellCacheChangeListener(Layer* layer) {
48 m_layer = layer;
49 }
50 virtual ~CellCacheChangeListener() {
51 }
52
53 virtual void onLayerChanged(Layer* layer, std::vector<Instance*>& instances) {
54 for(std::vector<Instance*>::iterator i = instances.begin(); i != instances.end(); ++i) {
55 if ((*i)->isMultiCell()) {
56 bool rotchange = ((*i)->getChangeInfo() & ICHANGE_ROTATION) == ICHANGE_ROTATION;
57 bool locchange = ((*i)->getChangeInfo() & ICHANGE_LOC) == ICHANGE_LOC;
58 bool celchange = ((*i)->getChangeInfo() & ICHANGE_CELL) == ICHANGE_CELL;
59 bool blochange = ((*i)->getChangeInfo() & ICHANGE_BLOCK) == ICHANGE_BLOCK;
60
61 if (!rotchange && !locchange && !celchange && !blochange) {
62 continue;
63 }
64
65 int32_t oldrotation = (*i)->getOldRotation();
66 int32_t newrotation = (*i)->getRotation();
67 if (!rotchange) {
68 oldrotation = newrotation;
69 }
70
71 if (rotchange || locchange || celchange) {
72 // update visual positions
73 (*i)->updateMultiInstances();
74 }
75 if (rotchange || celchange) {
76 // update cache positions
77 ModelCoordinate oldmc;
78 ModelCoordinate newmc;
79 if (m_layer == layer) {
80 oldmc = (*i)->getOldLocationRef().getLayerCoordinates();
81 newmc = (*i)->getLocationRef().getLayerCoordinates();
82 } else {
83 oldmc = m_layer->getCellGrid()->toLayerCoordinates(
84 layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef()));
85 newmc = m_layer->getCellGrid()->toLayerCoordinates(
86 layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef()));
87 }
88
89 if (!celchange) {
90 oldmc = newmc;
91 }
92
93 CellGrid* cg = m_layer->getCellGrid();
94 const std::vector<Instance*>& multiinstances = (*i)->getMultiInstances();
95 std::vector<Instance*>::const_iterator it = multiinstances.begin();
96 for (; it != multiinstances.end(); ++it) {
97 // remove
98 std::vector<ModelCoordinate> coordinates =
99 cg->toMultiCoordinates(oldmc, (*it)->getObject()->getMultiPartCoordinates(oldrotation));
100 std::vector<ModelCoordinate>::iterator mcit = coordinates.begin();
101 for (; mcit != coordinates.end(); ++mcit) {
102 Cell* cell = m_layer->getCellCache()->getCell(*mcit);
103 if (cell) {
104 cell->removeInstance(*it);
105 }
106 }
107 // add
108 coordinates = cg->toMultiCoordinates(newmc, (*it)->getObject()->getMultiPartCoordinates(newrotation));
109 mcit = coordinates.begin();
110 for (; mcit != coordinates.end(); ++mcit) {
111 Cell* cell = m_layer->getCellCache()->getCell(*mcit);
112 if (cell) {
113 cell->addInstance(*it);
114 }
115 }
116 }
117
118 if (celchange) {
119 // leader instance
120 Cell* oldcell = m_layer->getCellCache()->getCell(oldmc);
121 Cell* newcell = m_layer->getCellCache()->getCell(newmc);
122 if (oldcell == newcell) {
123 continue;
124 }
125 if (oldcell) {
126 oldcell->removeInstance(*i);
127 }
128 if (newcell) {
129 newcell->addInstance(*i);
130 }
131 }
132 }
133 continue;
134 }
135 if ((*i)->getObject()->isMultiPart()) {
136 continue;
137 }
138 if (((*i)->getChangeInfo() & ICHANGE_BLOCK) == ICHANGE_BLOCK) {
139 ModelCoordinate mc;
140 if (m_layer == layer) {
141 mc = (*i)->getLocationRef().getLayerCoordinates();
142 } else {
143 mc = m_layer->getCellGrid()->toLayerCoordinates(
144 layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef()));
145 }
146 Cell* cell = m_layer->getCellCache()->getCell(mc);
147 if (cell) {
148 cell->changeInstance(*i);
149 }
150 }
151 if (((*i)->getChangeInfo() & ICHANGE_CELL) == ICHANGE_CELL) {
152 ModelCoordinate oldmc;
153 ModelCoordinate newmc;
154 if (m_layer == layer) {
155 oldmc = (*i)->getOldLocationRef().getLayerCoordinates();
156 newmc = (*i)->getLocationRef().getLayerCoordinates();
157 } else {
158 oldmc = m_layer->getCellGrid()->toLayerCoordinates(
159 layer->getCellGrid()->toMapCoordinates((*i)->getOldLocationRef().getExactLayerCoordinatesRef()));
160 newmc = m_layer->getCellGrid()->toLayerCoordinates(
161 layer->getCellGrid()->toMapCoordinates((*i)->getLocationRef().getExactLayerCoordinatesRef()));
162 }
163
164 Cell* oldcell = m_layer->getCellCache()->getCell(oldmc);
165 Cell* newcell = m_layer->getCellCache()->getCell(newmc);
166 if (oldcell == newcell) {
167 continue;
168 }
169 if (oldcell) {
170 oldcell->removeInstance(*i);
171 }
172 if (newcell) {
173 newcell->addInstance(*i);
174 }
175 }
176 }
177 }
178
179 virtual void onInstanceCreate(Layer* layer, Instance* instance) {
180 ModelCoordinate mc;
181 if (m_layer == layer) {
182 mc = instance->getLocationRef().getLayerCoordinates();
183 } else {
184 mc = m_layer->getCellGrid()->toLayerCoordinates(
185 layer->getCellGrid()->toMapCoordinates(instance->getLocationRef().getExactLayerCoordinatesRef()));
186 }
187
188 CellCache* cache = m_layer->getCellCache();
189 Location loc(m_layer);
190 loc.setLayerCoordinates(mc);
191 if (!cache->isInCellCache(loc)) {
192 cache->resize();
193 }
194 if (instance->isMultiCell()) {
195 instance->updateMultiInstances();
196 CellGrid* cg = m_layer->getCellGrid();
197 const std::vector<Instance*>& multiinstances = instance->getMultiInstances();
198 std::vector<Instance*>::const_iterator it = multiinstances.begin();
199 for (; it != multiinstances.end(); ++it) {
200 std::vector<ModelCoordinate> coordinates =
201 cg->toMultiCoordinates(mc, (*it)->getObject()->getMultiPartCoordinates(instance->getRotation()));
202 std::vector<ModelCoordinate>::iterator mcit = coordinates.begin();
203 for (; mcit != coordinates.end(); ++mcit) {
204 loc.setLayerCoordinates(*mcit);
205 if (!cache->isInCellCache(loc)) {
206 cache->resize();
207 }
208 Cell* cell = cache->getCell(*mcit);
209 if (cell) {
210 cell->addInstance(*it);
211 }
212 }
213 }
214 }
215 Cell* cell = cache->getCell(mc);
216 if (cell) {
217 cell->addInstance(instance);
218 }
219 }
220
221 virtual void onInstanceDelete(Layer* layer, Instance* instance) {
222 ModelCoordinate mc;
223 if (m_layer == layer) {
224 mc = instance->getLocationRef().getLayerCoordinates();
225 } else {
226 mc = m_layer->getCellGrid()->toLayerCoordinates(
227 layer->getCellGrid()->toMapCoordinates(instance->getLocationRef().getExactLayerCoordinatesRef()));
228 }
229
230 CellCache* cache = m_layer->getCellCache();
231 if (instance->isMultiCell()) {
232 instance->updateMultiInstances();
233 CellGrid* cg = m_layer->getCellGrid();
234 const std::vector<Instance*>& multiinstances = instance->getMultiInstances();
235 std::vector<Instance*>::const_iterator it = multiinstances.begin();
236 for (; it != multiinstances.end(); ++it) {
237 std::vector<ModelCoordinate> coordinates =
238 cg->toMultiCoordinates(mc, (*it)->getObject()->getMultiPartCoordinates(instance->getRotation()));
239 std::vector<ModelCoordinate>::iterator mcit = coordinates.begin();
240 for (; mcit != coordinates.end(); ++mcit) {
241 Cell* cell = cache->getCell(*mcit);
242 if (cell) {
243 cell->removeInstance(*it);
244 }
245 }
246 }
247 }
248 Cell* cell = cache->getCell(mc);
249 if (cell) {
250 cell->removeInstance(instance);
251 }
252 // updates size on the next cache update (happens on same pump)
253 cache->setSizeUpdate(true);
254 }
255
256 private:
257 Layer* m_layer;
258 };
259
260 Zone::Zone(uint32_t id):
261 m_id(id) {
262 }
263
264 Zone::~Zone() {
265 for (std::set<Cell*>::iterator i = m_cells.begin(); i != m_cells.end(); ++i) {
266 (*i)->resetZone();
267 }
268 }
269
270 void Zone::addCell(Cell* cell) {
271 if (!cell->getZone()) {
272 cell->setZone(this);
273 m_cells.insert(cell);
274 }
275 }
276
277 void Zone::removeCell(Cell* cell) {
278 std::set<Cell*>::iterator i = m_cells.find(cell);
279 if (i != m_cells.end()) {
280 (*i)->resetZone();
281 m_cells.erase(i);
282 }
283 }
284
285 void Zone::mergeZone(Zone* zone) {
286 const std::set<Cell*>& cells = zone->getCells();
287 m_cells.insert(cells.begin(), cells.end());
288 for (std::set<Cell*>::const_iterator it = cells.begin(); it != cells.end(); ++it) {
289 (*it)->setZone(this);
290 }
291 zone->resetCells();
292 }
293
294 const std::set<Cell*>& Zone::getCells() const {
295 return m_cells;
296 }
297
298 void Zone::resetCells() {
299 m_cells.clear();
300 }
301
302 uint32_t Zone::getId() const {
303 return m_id;
304 }
305
306 uint32_t Zone::getCellCount() const {
307 return static_cast<uint32_t>(m_cells.size());
308 }
309
310 std::vector<Cell*> Zone::getTransitionCells(Layer* layer) {
311 std::vector<Cell*> transitions;
312 std::set<Cell*>::iterator it = m_cells.begin();
313 for (; it != m_cells.end(); ++it) {
314 TransitionInfo* trans = (*it)->getTransition();
315 if (!trans) {
316 continue;
317 }
318 if (layer) {
319 if (layer == (*it)->getLayer()) {
320 transitions.push_back(*it);
321 }
322 } else {
323 transitions.push_back(*it);
324 }
325 }
326 return transitions;
327 }
328
329 class ZoneCellChangeListener : public CellChangeListener {
330 public:
331 ZoneCellChangeListener(CellCache* cache) {
332 m_cache = cache;
333 }
334 virtual ~ZoneCellChangeListener() {
335 }
336
337 virtual void onInstanceEnteredCell(Cell* cell, Instance* instance) {
338
339 }
340
341 virtual void onInstanceExitedCell(Cell* cell, Instance* instance) {
342
343 }
344
345 virtual void onBlockingChangedCell(Cell* cell, CellTypeInfo type, bool blocks) {
346 if (blocks) {
347 cell->setZoneProtected(true);
348 m_cache->splitZone(cell);
349 } else {
350 Zone* z1 = cell->getZone();
351 Zone* z2 = NULL;
352 const std::vector<Cell*>& neighbors = cell->getNeighbors();
353 std::vector<Cell*>::const_iterator it = neighbors.begin();
354 for (; it != neighbors.end(); ++it) {
355 Zone* z = (*it)->getZone();
356 if (z && z != z1) {
357 z2 = z;
358 }
359 }
360 if (z1 && z2) {
361 cell->setZoneProtected(false);
362 m_cache->mergeZones(z1, z2);
363 }
364 }
365 }
366
367 private:
368 CellCache* m_cache;
369 };
370
371 CellCache::CellCache(Layer* layer):
372 m_layer(layer),
373 m_defaultCostMulti(1.0),
374 m_defaultSpeedMulti(1.0),
375 m_neighborZ(-1),
376 m_blockingUpdate(false),
377 m_sizeUpdate(false),
378 m_searchNarrow(true),
379 m_staticSize(false) {
380 // create cell change listener
381 m_cellZoneListener = new ZoneCellChangeListener(this);
382 // set base size
383 ModelCoordinate min, max;
384 m_layer->getMinMaxCoordinates(min, max);
385 m_size.w = max.x;
386 m_size.h = max.y;
387 m_size.x = min.x;
388 m_size.y = min.y;
389
390 // create and add layer listener
391 m_cellListener = new CellCacheChangeListener(m_layer);
392 m_layer->addChangeListener(m_cellListener);
393 const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
394 if (!interacts.empty()) {
395 std::vector<Layer*>::const_iterator layit = interacts.begin();
396 for(; layit != interacts.end(); ++layit) {
397 // set size
398 (*layit)->getMinMaxCoordinates(min, max, m_layer);
399 m_size.w = std::max(max.x, m_size.w);
400 m_size.h = std::max(max.y, m_size.h);
401 m_size.x = std::min(min.x, m_size.x);
402 m_size.y = std::min(min.y, m_size.y);
403 // add listener
404 (*layit)->addChangeListener(m_cellListener);
405 }
406 }
407
408 m_width = ABS(m_size.w - m_size.x) + 1;
409 m_height = ABS(m_size.h - m_size.y) + 1;
410
411 m_cells.resize(m_width);
412 for (uint32_t i = 0; i < m_width; ++i) {
413 m_cells[i].resize(m_height, NULL);
414 }
415 }
416
417 CellCache::~CellCache() {
418 // reset cache
419 reset();
420 // remove listener from layers
421 m_layer->removeChangeListener(m_cellListener);
422 const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
423 if (!interacts.empty()) {
424 std::vector<Layer*>::const_iterator layit = interacts.begin();
425 for(; layit != interacts.end(); ++layit) {
426 (*layit)->removeChangeListener(m_cellListener);
427 }
428 }
429 // delete listener
430 delete m_cellListener;
431 delete m_cellZoneListener;
432 }
433
434 void CellCache::reset() {
435 // delete zones
436 if (!m_zones.empty()) {
437 std::vector<Zone*>::iterator it = m_zones.begin();
438 for (; it != m_zones.end(); ++it) {
439 delete *it;
440 }
441 m_zones.clear();
442 }
443 // clear all containers
444 m_costsToCells.clear();
445 m_costsTable.clear();
446 m_costMultipliers.clear();
447 m_speedMultipliers.clear();
448 m_narrowCells.clear();
449 m_cellAreas.clear();
450 // delete cells
451 if (!m_cells.empty()) {
452 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
453 for (; it != m_cells.end(); ++it) {
454 std::vector<Cell*>::iterator cit = (*it).begin();
455 for (; cit != (*it).end(); ++cit) {
456 delete *cit;
457 }
458 }
459 m_cells.clear();
460 }
461 // reset default cost and speed
462 m_defaultCostMulti = 1.0;
463 m_defaultSpeedMulti = 1.0;
464 // reset size
465 m_size.x = 0;
466 m_size.y = 0;
467 m_size.w = 0;
468 m_size.h = 0;
469 m_width = 0;
470 m_height = 0;
471 }
472
473 void CellCache::resize() {
474 if (m_staticSize) {
475 return;
476 }
477 // get new size and check if it has changed
478 Rect newsize = calculateCurrentSize();
479 resize(newsize);
480 }
481
482 void CellCache::resize(const Rect& rec) {
483 // check if size has changed
484 Rect newsize = rec;
485 if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) {
486 uint32_t w = ABS(newsize.w - newsize.x) + 1;
487 uint32_t h = ABS(newsize.h - newsize.y) + 1;
488
489 std::vector<std::vector<Cell*> > cells;
490 cells.resize(w);
491 for (uint32_t i = 0; i < w; ++i) {
492 cells[i].resize(h, NULL);
493 }
494 const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
495 for(uint32_t y = 0; y < h; ++y) {
496 for(uint32_t x = 0; x < w; ++x) {
497 // transfer cells
498 ModelCoordinate mc(newsize.x+x, newsize.y+y);
499 Cell* cell = NULL;
500 int32_t old_x = mc.x - m_size.x;
501 int32_t old_y = mc.y - m_size.y;
502 // out of range in the old size, so we create a new cell
503 if (old_x < 0 || old_x >= static_cast<int32_t>(m_width) || old_y < 0 || old_y >= static_cast<int32_t>(m_height)) {
504 int32_t coordId = x + y * w;
505 cell = new Cell(coordId, mc, m_layer);
506 cells[x][y] = cell;
507
508 std::list<Instance*> cell_instances;
509 m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances);
510 if (!interacts.empty()) {
511 // fill interact Instances into Cell
512 std::vector<Layer*>::const_iterator it = interacts.begin();
513 std::list<Instance*> interact_instances;
514 for(; it != interacts.end(); ++it) {
515 // convert coordinates
516 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc));
517 ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc));
518 // check interact layer for instances
519 (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
520 if (!interact_instances.empty()) {
521 cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end());
522 interact_instances.clear();
523 }
524 }
525 }
526 if (!cell_instances.empty()) {
527 // add instances to cell
528 cell->addInstances(cell_instances);
529 }
530 // transfer ownership
531 } else {
532 cell = m_cells[static_cast<uint32_t>(old_x)][static_cast<uint32_t>(old_y)];
533 m_cells[static_cast<uint32_t>(old_x)][static_cast<uint32_t>(old_y)] = NULL;
534 cells[x][y] = cell;
535 int32_t coordId = x + y * w;
536 cell->setCellId(coordId);
537 cell->resetNeighbors();
538 }
539 }
540 }
541 // delete old unused cells
542 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
543 for (; it != m_cells.end(); ++it) {
544 std::vector<Cell*>::iterator cit = (*it).begin();
545 for (; cit != (*it).end(); ++cit) {
546 if (*cit) {
547 delete *cit;
548 *cit = NULL;
549 }
550 }
551 }
552 // use new values
553 m_cells = cells;
554 m_size = newsize;
555 m_width = w;
556 m_height = h;
557
558 bool zCheck = m_neighborZ != -1;
559 // fill neighbors into cells
560 it = m_cells.begin();
561 for (; it != m_cells.end(); ++it) {
562 std::vector<Cell*>::iterator cit = (*it).begin();
563 for (; cit != (*it).end(); ++cit) {
564 int32_t cellZ = (*cit)->getLayerCoordinates().z;
565 std::vector<ModelCoordinate> coordinates;
566 m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates);
567 for (std::vector<ModelCoordinate>::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) {
568 Cell* c = getCell(*mi);
569 if (*cit == c || !c) {
570 continue;
571 }
572 if (zCheck) {
573 if (ABS(c->getLayerCoordinates().z - cellZ) > m_neighborZ) {
574 continue;
575 }
576 }
577 (*cit)->addNeighbor(c);
578 }
579 }
580 }
581 }
582 }
583
584 void CellCache::createCells() {
585 const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
586 for(uint32_t y = 0; y < m_height; ++y) {
587 for(uint32_t x = 0; x < m_width; ++x) {
588 ModelCoordinate mc(m_size.x+x, m_size.y+y);
589 Cell* cell = getCell(mc);
590 if (!cell) {
591 cell = new Cell(convertCoordToInt(mc), mc, m_layer);
592 m_cells[x][y] = cell;
593 }
594 // fill Instances into Cell
595 std::list<Instance*> cell_instances;
596 m_layer->getInstanceTree()->findInstances(mc, 0, 0, cell_instances);
597 if (!interacts.empty()) {
598 // fill interact Instances into Cell
599 std::vector<Layer*>::const_iterator it = interacts.begin();
600 std::list<Instance*> interact_instances;
601 for(; it != interacts.end(); ++it) {
602 // convert coordinates
603 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc));
604 ModelCoordinate inter_mc = (*it)->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc));
605 // check interact layer for instances
606 (*it)->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
607 if (!interact_instances.empty()) {
608 cell_instances.insert(cell_instances.end(), interact_instances.begin(), interact_instances.end());
609 interact_instances.clear();
610 }
611 }
612 }
613 if (!cell_instances.empty()) {
614 // add instances to cell
615 cell->addInstances(cell_instances);
616 }
617 }
618 }
619 // fill neighbors into cells
620 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
621 for (; it != m_cells.end(); ++it) {
622 std::vector<Cell*>::iterator cit = (*it).begin();
623 for (; cit != (*it).end(); ++cit) {
624 uint8_t accessible = 0;
625 bool selfblocker = (*cit)->getCellType() == CTYPE_STATIC_BLOCKER || (*cit)->getCellType() == CTYPE_CELL_BLOCKER;
626 std::vector<ModelCoordinate> coordinates;
627 m_layer->getCellGrid()->getAccessibleCoordinates((*cit)->getLayerCoordinates(), coordinates);
628 for (std::vector<ModelCoordinate>::iterator mi = coordinates.begin(); mi != coordinates.end(); ++mi) {
629 Cell* c = getCell(*mi);
630 if (*cit == c || !c) {
631 continue;
632 }
633 if (!selfblocker && c->getCellType() != CTYPE_STATIC_BLOCKER &&
634 c->getCellType() != CTYPE_CELL_BLOCKER) {
635 ++accessible;
636 }
637 (*cit)->addNeighbor(c);
638 }
639 // add cell to narrow cells and add listener for zone change
640 if (m_searchNarrow && !selfblocker && accessible < 3) {
641 addNarrowCell(*cit);
642 }
643 }
644 }
645 // create Zones
646 it = m_cells.begin();
647 for (; it != m_cells.end(); ++it) {
648 std::vector<Cell*>::iterator cit = (*it).begin();
649 for (; cit != (*it).end(); ++cit) {
650 Cell* cell = *cit;
651 if (cell->getZone() || cell->isInserted()) {
652 continue;
653 }
654 if (cell->getCellType() == CTYPE_STATIC_BLOCKER || cell->getCellType() == CTYPE_CELL_BLOCKER) {
655 continue;
656 }
657 Zone* zone = createZone();
658 cell->setInserted(true);
659 std::stack<Cell*> cellstack;
660 cellstack.push(cell);
661 while(!cellstack.empty()) {
662 Cell* c = cellstack.top();
663 cellstack.pop();
664 zone->addCell(c);
665
666 const std::vector<Cell*>& neighbors = c->getNeighbors();
667 for (std::vector<Cell*>::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) {
668 Cell* nc = *nit;
669 if (!nc->isInserted() &&
670 nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) {
671 nc->setInserted(true);
672 cellstack.push(nc);
673 }
674 }
675 }
676 }
677 }
678 }
679
680 void CellCache::forceUpdate() {
681 std::vector<std::vector<Cell*> >::iterator it = m_cells.begin();
682 for (; it != m_cells.end(); ++it) {
683 std::vector<Cell*>::iterator cit = (*it).begin();
684 for (; cit != (*it).end(); ++cit) {
685 (*cit)->updateCellInfo();
686 }
687 }
688 }
689
690 void CellCache::addCell(Cell* cell) {
691 ModelCoordinate mc = cell->getLayerCoordinates();
692 m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell;
693 }
694
695 Cell* CellCache::createCell(const ModelCoordinate& mc) {
696 Cell* cell = getCell(mc);
697 if (!cell) {
698 cell = new Cell(convertCoordToInt(mc), mc, m_layer);
699 m_cells[(mc.x-m_size.x)][(mc.y-m_size.y)] = cell;
700 }
701 return cell;
702 }
703
704 Cell* CellCache::getCell(const ModelCoordinate& mc) {
705 int32_t x = mc.x - m_size.x;
706 int32_t y = mc.y - m_size.y;
707
708 if (x < 0 || x >= static_cast<int32_t>(m_width) || y < 0 || y >= static_cast<int32_t>(m_height)) {
709 return NULL;
710 }
711
712 return m_cells[static_cast<uint32_t>(x)][static_cast<uint32_t>(y)];
713 }
714
715 const std::vector<std::vector<Cell*> >& CellCache::getCells() {
716 return m_cells;
717 }
718
719 void CellCache::removeCell(Cell* cell) {
720 if (!m_costsToCells.empty()) {
721 removeCellFromCost(cell);
722 }
723 if (!m_costMultipliers.empty()) {
724 resetCostMultiplier(cell);
725 }
726 if (!m_speedMultipliers.empty()) {
727 resetSpeedMultiplier(cell);
728 }
729 if (!m_narrowCells.empty()) {
730 removeNarrowCell(cell);
731 }
732 if (!m_cellAreas.empty()) {
733 removeCellFromArea(cell);
734 }
735 }
736
737 void CellCache::addInteractOnRuntime(Layer* interact) {
738 interact->setInteract(true, m_layer->getId());
739 m_layer->addInteractLayer(interact);
740 interact->addChangeListener(m_cellListener);
741 Rect newsize = calculateCurrentSize();
742 if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) {
743 resize();
744 }
745 // not optimal but needed if the grids have different geometry
746 for(uint32_t y = 0; y < m_height; ++y) {
747 for(uint32_t x = 0; x < m_width; ++x) {
748 ModelCoordinate mc(m_size.x+x, m_size.y+y);
749 Cell* cell = getCell(mc);
750 if (cell) {
751 // convert coordinates
752 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc));
753 ModelCoordinate inter_mc = interact->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc));
754 // check interact layer for instances
755 std::list<Instance*> interact_instances;
756 interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
757 if (!interact_instances.empty()) {
758 // fill interact Instances into Cell
759 cell->addInstances(interact_instances);
760 }
761 }
762 }
763 }
764 }
765
766 void CellCache::removeInteractOnRuntime(Layer* interact) {
767 interact->setInteract(false, "");
768 m_layer->removeInteractLayer(interact);
769 Rect newsize = calculateCurrentSize();
770 if (newsize.x != m_size.x || newsize.y != m_size.y || newsize.w != m_size.w || newsize.h != m_size.h) {
771 resize();
772 }
773 // not optimal but needed if the grids have different geometry
774 for(uint32_t y = 0; y < m_height; ++y) {
775 for(uint32_t x = 0; x < m_width; ++x) {
776 ModelCoordinate mc(m_size.x+x, m_size.y+y);
777 Cell* cell = getCell(mc);
778 if (cell) {
779 // convert coordinates
780 ExactModelCoordinate emc(FIFE::intPt2doublePt(mc));
781 ModelCoordinate inter_mc = interact->getCellGrid()->toLayerCoordinates(m_layer->getCellGrid()->toMapCoordinates(emc));
782 // check interact layer for instances
783 std::list<Instance*> interact_instances;
784 interact->getInstanceTree()->findInstances(inter_mc, 0, 0, interact_instances);
785 if (!interact_instances.empty()) {
786 // remove interact Instances from Cell
787 for (std::list<Instance*>::iterator it = interact_instances.begin(); it != interact_instances.end(); ++it) {
788 cell->removeInstance(*it);
789 }
790 }
791 }
792 }
793 }
794 }
795
796 LayerChangeListener* CellCache::getCellCacheChangeListener() {
797 return m_cellListener;
798 }
799
800 Layer* CellCache::getLayer() {
801 return m_layer;
802 }
803
804 const Rect& CellCache::getSize() {
805 return m_size;
806 }
807
808 void CellCache::setSize(const Rect& rec) {
809 resize(rec);
810 }
811
812 uint32_t CellCache::getWidth() {
813 return m_width;
814 }
815
816 uint32_t CellCache::getHeight() {
817 return m_height;
818 }
819
820 bool CellCache::isInCellCache(const Location& location) const {
821 if (m_layer != location.getLayer()) {
822 return false;
823 }
824 int32_t x = location.getLayerCoordinates().x - m_size.x;
825 int32_t y = location.getLayerCoordinates().y - m_size.y;
826
827 if (x < 0 || x >= static_cast<int32_t>(m_width) || y < 0 || y >= static_cast<int32_t>(m_height)) {
828 return false;
829 }
830 return true;
831 }
832
833 int32_t CellCache::convertCoordToInt(const ModelCoordinate& coord) const {
834 ModelCoordinate newcoords(coord.x - m_size.x, coord.y - m_size.y);
835 return newcoords.x + newcoords.y*m_width;
836 }
837
838 ModelCoordinate CellCache::convertIntToCoord(const int32_t cell) const {
839 ModelCoordinate coord((cell % m_width) + m_size.x, (cell / m_width) + m_size.y);
840 return coord;
841 }
842
843 int32_t CellCache::getMaxIndex() const {
844 int32_t max_index = m_width*m_height;
845 return max_index;
846 }
847
848 void CellCache::setMaxNeighborZ(int32_t z) {
849 m_neighborZ = z;
850 }
851
852 int32_t CellCache::getMaxNeighborZ() {
853 return m_neighborZ;
854 }
855
856 std::vector<Cell*> CellCache::getCellsInLine(const ModelCoordinate& pt1, const ModelCoordinate& pt2, bool blocker) {
857 std::vector<Cell*> cells;
858 std::vector<ModelCoordinate> coords = m_layer->getCellGrid()->getCoordinatesInLine(pt1, pt2);
859 for (std::vector<ModelCoordinate>::iterator it = coords.begin(); it != coords.end(); ++it) {
860 Cell* c = getCell(*it);
861 if (c) {
862 if (blocker && c->getCellType() != CTYPE_NO_BLOCKER) {
863 return cells;
864 }
865 cells.push_back(c);
866 } else {
867 return cells;
868 }
869 }
870 return cells;
871 }
872
873 std::vector<Cell*> CellCache::getCellsInRect(const Rect& rec) {
874 std::vector<Cell*> cells;
875 cells.reserve(rec.w * rec.h);
876
877 ModelCoordinate current(rec.x, rec.y);
878 ModelCoordinate target(rec.x+rec.w, rec.y+rec.h);
879 for (; current.y < target.y; ++current.y) {
880 current.x = rec.x;
881 for (; current.x < target.x; ++current.x) {
882 Cell* c = getCell(current);
883 if (c) {
884 cells.push_back(c);
885 }
886 }
887 }
888 return cells;
889 }
890
891 std::vector<Cell*> CellCache::getBlockingCellsInRect(const Rect& rec) {
892 std::vector<Cell*> cells;
893 cells.reserve(rec.w * rec.h);
894
895 ModelCoordinate current(rec.x, rec.y);
896 ModelCoordinate target(rec.x + rec.w, rec.y + rec.h);
897 for (; current.y < target.y; ++current.y) {
898 current.x = rec.x;
899 for (; current.x < target.x; ++current.x) {
900 Cell* c = getCell(current);
901 if (c && c->getCellType() != CTYPE_NO_BLOCKER) {
902 cells.push_back(c);
903 }
904 }
905 }
906 return cells;
907 }
908
909 std::vector<Cell*> CellCache::getCellsInCircle(const ModelCoordinate& center, uint16_t radius) {
910 std::vector<Cell*> cells;
911 //radius power 2
912 uint16_t radiusp2 = (radius+1) * radius;
913
914 ModelCoordinate current(center.x-radius, center.y-radius);
915 ModelCoordinate target(center.x+radius, center.y+radius);
916 for (; current.y < center.y; current.y++) {
917 current.x = center.x-radius;
918 for (; current.x < center.x; current.x++) {
919 Cell* c = getCell(current);
920 if (c) {
921 uint16_t dx = center.x - current.x;
922 uint16_t dy = center.y - current.y;
923 uint16_t distance = dx*dx + dy*dy;
924 if (distance <= radiusp2) {
925 cells.push_back(c);
926
927 current.x = center.x + dx;
928 c = getCell(current);
929 if (c) cells.push_back(c);
930
931 current.y = center.y + dy;
932 c = getCell(current);
933 if (c) cells.push_back(c);
934
935 current.x = center.x-dx;
936 c = getCell(current);
937 if (c) cells.push_back(c);
938
939 current.y = center.y-dy;
940
941 }
942 }
943 }
944 }
945 current.x = center.x;
946 current.y = center.y-radius;
947 for (; current.y <= target.y; current.y++) {
948 Cell* c = getCell(current);
949 if (c) cells.push_back(c);
950 }
951
952 current.y = center.y;
953 current.x = center.x-radius;
954 for (; current.x <= target.x; current.x++) {
955 Cell* c = getCell(current);
956 if (c) cells.push_back(c);
957 }
958 return cells;
959 }
960
961 std::vector<Cell*> CellCache::getCellsInCircleSegment(const ModelCoordinate& center, uint16_t radius, int32_t sangle, int32_t eangle) {
962 std::vector<Cell*> cells;
963 ExactModelCoordinate exactCenter(center.x, center.y);
964 std::vector<Cell*> tmpCells = getCellsInCircle(center, radius);
965 int32_t s = (sangle + 360) % 360;
966 int32_t e = (eangle + 360) % 360;
967 bool greater = (s > e) ? true : false;
968 for (std::vector<Cell*>::iterator it = tmpCells.begin(); it != tmpCells.end(); ++it) {
969 int32_t angle = getAngleBetween(exactCenter, intPt2doublePt((*it)->getLayerCoordinates()));
970 if (greater) {
971 if (angle >= s || angle <= e) {
972 cells.push_back(*it);
973 }
974 } else {
975 if (angle >= s && angle <= e) {
976 cells.push_back(*it);
977 }
978 }
979 }
980 return cells;
981 }
982
983 void CellCache::registerCost(const std::string& costId, double cost) {
984 std::pair<std::map<std::string, double>::iterator, bool> insertiter;
985 insertiter = m_costsTable.insert(std::pair<std::string, double>(costId, cost));
986 if (insertiter.second == false) {
987 double& old_cost = insertiter.first->second;
988 old_cost = cost;
989 }
990 }
991
992 void CellCache::unregisterCost(const std::string& costId) {
993 std::map<std::string, double>::iterator it = m_costsTable.find(costId);
994 if (it != m_costsTable.end()) {
995 m_costsTable.erase(it);
996 m_costsToCells.erase(costId);
997 }
998 }
999
1000 double CellCache::getCost(const std::string& costId) {
1001 std::map<std::string, double>::iterator it = m_costsTable.find(costId);
1002 if (it != m_costsTable.end()) {
1003 return it->second;
1004 }
1005 return 0.0;
1006 }
1007
1008 bool CellCache::existsCost(const std::string& costId) {
1009 std::map<std::string, double>::iterator it = m_costsTable.find(costId);
1010 if (it != m_costsTable.end()) {
1011 return true;
1012 }
1013 return false;
1014 }
1015
1016 std::list<std::string> CellCache::getCosts() {
1017 std::list<std::string> costs;
1018 std::map<std::string, double>::iterator it = m_costsTable.begin();
1019 for (; it != m_costsTable.end(); ++it) {
1020 costs.push_back((*it).first);
1021 }
1022 return costs;
1023 }
1024
1025 void CellCache::unregisterAllCosts() {
1026 m_costsTable.clear();
1027 m_costsToCells.clear();
1028 }
1029
1030 void CellCache::addCellToCost(const std::string& costId, Cell* cell) {
1031 if (existsCost(costId)) {
1032 StringCellPair result = m_costsToCells.equal_range(costId);
1033 StringCellIterator it = result.first;
1034 for (; it != result.second; ++it) {
1035 if ((*it).second == cell) {
1036 return;
1037 }
1038 }
1039 m_costsToCells.insert(std::pair<std::string, Cell*>(costId, cell));
1040 }
1041 }
1042
1043 void CellCache::addCellsToCost(const std::string& costId, const std::vector<Cell*>& cells) {
1044 std::vector<Cell*>::const_iterator it = cells.begin();
1045 for (; it != cells.end(); ++it) {
1046 addCellToCost(costId, *it);
1047 }
1048 }
1049
1050 void CellCache::removeCellFromCost(Cell* cell) {
1051 StringCellIterator it = m_costsToCells.begin();
1052 for (; it != m_costsToCells.end();) {
1053 if ((*it).second == cell) {
1054 m_costsToCells.erase(it++);
1055 } else {
1056 ++it;
1057 }
1058 }
1059 }
1060
1061 void CellCache::removeCellFromCost(const std::string& costId, Cell* cell) {
1062 StringCellPair result = m_costsToCells.equal_range(costId);
1063 StringCellIterator it = result.first;
1064 for (; it != result.second; ++it) {
1065 if ((*it).second == cell) {
1066 m_costsToCells.erase(it);
1067 break;
1068 }
1069 }
1070 }
1071
1072 void CellCache::removeCellsFromCost(const std::string& costId, const std::vector<Cell*>& cells) {
1073 std::vector<Cell*>::const_iterator it = cells.begin();
1074 for (; it != cells.end(); ++it) {
1075 removeCellFromCost(costId, *it);
1076 }
1077 }
1078
1079 std::vector<Cell*> CellCache::getCostCells(const std::string& costId) {
1080 std::vector<Cell*> cells;
1081 StringCellPair result = m_costsToCells.equal_range(costId);
1082 StringCellIterator it = result.first;
1083 for (; it != result.second; ++it) {
1084 cells.push_back((*it).second);
1085 }
1086 return cells;
1087 }
1088
1089 std::vector<std::string> CellCache::getCellCosts(Cell* cell) {
1090 std::vector<std::string> costs;
1091 StringCellIterator it = m_costsToCells.begin();
1092 for (; it != m_costsToCells.end(); ++it) {
1093 if ((*it).second == cell) {
1094 costs.push_back((*it).first);
1095 }
1096 }
1097 return costs;
1098 }
1099
1100 bool CellCache::existsCostForCell(const std::string& costId, Cell* cell) {
1101 StringCellPair result = m_costsToCells.equal_range(costId);
1102 StringCellIterator it = result.first;
1103 for (; it != result.second; ++it) {
1104 if ((*it).second == cell) {
1105 return true;
1106 }
1107 }
1108 return false;
1109 }
1110
1111 double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next) {
1112 double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next);
1113 Cell* nextcell = getCell(next);
1114 if (nextcell) {
1115 if (!nextcell->defaultCost()) {
1116 cost *= nextcell->getCostMultiplier();
1117 } else {
1118 cost *= m_defaultCostMulti;
1119 }
1120 }
1121 return cost;
1122 }
1123
1124 double CellCache::getAdjacentCost(const ModelCoordinate& adjacent, const ModelCoordinate& next, const std::string& costId) {
1125 double cost = m_layer->getCellGrid()->getAdjacentCost(adjacent, next);
1126 Cell* nextcell = getCell(next);
1127 if (nextcell) {
1128 if (existsCostForCell(costId, nextcell)) {
1129 cost *= getCost(costId);
1130 } else {
1131 if (!nextcell->defaultCost()) {
1132 cost *= nextcell->getCostMultiplier();
1133 } else {
1134 cost *= m_defaultCostMulti;
1135 }
1136 }
1137 }
1138 return cost;
1139 }
1140
1141 bool CellCache::getCellSpeedMultiplier(const ModelCoordinate& cell, double& multiplier) {
1142 Cell* nextcell = getCell(cell);
1143 if (nextcell) {
1144 if (!nextcell->defaultSpeed()) {
1145 multiplier = nextcell->getSpeedMultiplier();
1146 return true;
1147 }
1148 }
1149 multiplier = m_defaultSpeedMulti;
1150 return false;
1151 }
1152
1153 void CellCache::setDefaultCostMultiplier(double multi) {
1154 m_defaultCostMulti = multi;
1155 }
1156
1157 double CellCache::getDefaultCostMultiplier() {
1158 return m_defaultCostMulti;
1159 }
1160
1161 void CellCache::setDefaultSpeedMultiplier(double multi) {
1162 m_defaultSpeedMulti = multi;
1163 }
1164
1165 double CellCache::getDefaultSpeedMultiplier() {
1166 return m_defaultSpeedMulti;
1167 }
1168
1169 bool CellCache::isDefaultCost(Cell* cell) {
1170 std::map<Cell*, double>::iterator it = m_costMultipliers.find(cell);
1171 if (it != m_costMultipliers.end()) {
1172 return false;
1173 }
1174 return true;
1175 }
1176
1177 void CellCache::setCostMultiplier(Cell* cell, double multi) {
1178 std::pair<std::map<Cell*, double>::iterator, bool> insertiter =
1179 m_costMultipliers.insert(std::pair<Cell*, double>(cell, multi));
1180 if (insertiter.second == false) {
1181 double& old = insertiter.first->second;
1182 old = multi;
1183 }
1184 }
1185
1186 double CellCache::getCostMultiplier(Cell* cell) {
1187 double cost = 1.0;
1188 std::map<Cell*, double>::iterator it = m_costMultipliers.find(cell);
1189 if (it != m_costMultipliers.end()) {
1190 cost = it->second;
1191 }
1192 return cost;
1193 }
1194
1195 void CellCache::resetCostMultiplier(Cell* cell) {
1196 m_costMultipliers.erase(cell);
1197 }
1198
1199 bool CellCache::isDefaultSpeed(Cell* cell) {
1200 std::map<Cell*, double>::iterator it = m_speedMultipliers.find(cell);
1201 if (it != m_speedMultipliers.end()) {
1202 return false;
1203 }
1204 return true;
1205 }
1206
1207 void CellCache::setSpeedMultiplier(Cell* cell, double multi) {
1208 std::pair<std::map<Cell*, double>::iterator, bool> insertiter =
1209 m_speedMultipliers.insert(std::pair<Cell*, double>(cell, multi));
1210 if (insertiter.second == false) {
1211 double& old = insertiter.first->second;
1212 old = multi;
1213 }
1214 }
1215
1216 double CellCache::getSpeedMultiplier(Cell* cell) {
1217 double speed = 1.0;
1218 std::map<Cell*, double>::iterator it = m_speedMultipliers.find(cell);
1219 if (it != m_speedMultipliers.end()) {
1220 speed = it->second;
1221 }
1222 return speed;
1223 }
1224
1225 void CellCache::resetSpeedMultiplier(Cell* cell) {
1226 m_speedMultipliers.erase(cell);
1227 }
1228
1229 void CellCache::addTransition(Cell* cell) {
1230 m_transitions.push_back(cell);
1231 }
1232
1233 void CellCache::removeTransition(Cell* cell) {
1234 std::vector<Cell*>::iterator it = m_transitions.begin();
1235 for (; it != m_transitions.end(); ++it) {
1236 if (cell == *it) {
1237 m_transitions.erase(it);
1238 break;
1239 }
1240 }
1241 }
1242
1243 std::vector<Cell*> CellCache::getTransitionCells(Layer* layer) {
1244 if (!layer) {
1245 return m_transitions;
1246 }
1247 std::vector<Cell*> cells;
1248 std::vector<Cell*>::iterator it = m_transitions.begin();
1249 for (; it != m_transitions.end(); ++it) {
1250 TransitionInfo* trans = (*it)->getTransition();
1251 if (trans) {
1252 if (trans->m_layer == layer) {
1253 cells.push_back(*it);
1254 }
1255 }
1256 }
1257 return cells;
1258 }
1259
1260 Zone* CellCache::createZone() {
1261 uint32_t id = 0;
1262 bool search = true;
1263 while (search) {
1264 bool found = false;
1265 if (!m_zones.empty()) {
1266 for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) {
1267 if ((*i)->getId() == id) {
1268 found = true;
1269 ++id;
1270 break;
1271 }
1272 }
1273 }
1274 search = found;
1275 }
1276 Zone* zi = new Zone(id);
1277 m_zones.push_back(zi);
1278
1279 return zi;
1280 }
1281
1282 const std::vector<Zone*>& CellCache::getZones() {
1283 return m_zones;
1284 }
1285
1286 Zone* CellCache::getZone(uint32_t id) {
1287 Zone* zi = 0;
1288 for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) {
1289 if ((*i)->getId() == id) {
1290 zi = (*i);
1291 break;
1292 }
1293 }
1294
1295 if (!zi) {
1296 zi = new Zone(id);
1297 m_zones.push_back(zi);
1298 }
1299
1300 return zi;
1301 }
1302
1303 void CellCache::removeZone(Zone* zone) {
1304 for (std::vector<Zone*>::iterator i = m_zones.begin(); i != m_zones.end(); ++i) {
1305 if (*i == zone) {
1306 delete *i;
1307 m_zones.erase(i);
1308 break;
1309 }
1310 }
1311 }
1312
1313 void CellCache::splitZone(Cell* cell) {
1314 Zone* currentZone = cell->getZone();
1315 if (!currentZone) {
1316 return;
1317 }
1318
1319 Zone* newZone = createZone();
1320 std::stack<Cell*> cellstack;
1321 const std::vector<Cell*>& neighbors = cell->getNeighbors();
1322 for (std::vector<Cell*>::const_iterator nit = neighbors.begin(); nit != neighbors.end(); ++nit) {
1323 Cell* nc = *nit;
1324 if (nc->isInserted() && !nc->isZoneProtected() &&
1325 nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) {
1326 cellstack.push(nc);
1327 break;
1328 }
1329 }
1330
1331 while(!cellstack.empty()) {
1332 Cell* c = cellstack.top();
1333 cellstack.pop();
1334
1335 currentZone->removeCell(c);
1336 newZone->addCell(c);
1337 c->setInserted(true);
1338 if (c->isZoneProtected()) {
1339 continue;
1340 }
1341 const std::vector<Cell*>& neigh = c->getNeighbors();
1342 for (std::vector<Cell*>::const_iterator nit = neigh.begin(); nit != neigh.end(); ++nit) {
1343 Cell* nc = *nit;
1344 if (nc->getZone() == currentZone && nc->isInserted() &&
1345 nc->getCellType() != CTYPE_STATIC_BLOCKER && nc->getCellType() != CTYPE_CELL_BLOCKER) {
1346 cellstack.push(nc);
1347 nc->setInserted(false);
1348 }
1349 }
1350 }
1351 if (currentZone->getCellCount() == 0) {
1352 removeZone(currentZone);
1353 }
1354 }
1355
1356 void CellCache::mergeZones(Zone* zone1, Zone* zone2) {
1357 if (!zone1 || !zone2) {
1358 return;
1359 }
1360 Zone* addZone = zone2;
1361 Zone* oldZone = zone1;
1362 if (zone1->getCellCount() > zone2->getCellCount()) {
1363 addZone = zone1;
1364 oldZone = zone2;
1365 }
1366 addZone->mergeZone(oldZone);
1367 removeZone(oldZone);
1368 }
1369
1370 void CellCache::addNarrowCell(Cell* cell) {
1371 std::pair<std::set<Cell*>::iterator, bool> insertiter = m_narrowCells.insert(cell);
1372 if (insertiter.second) {
1373 cell->addChangeListener(m_cellZoneListener);
1374 }
1375 }
1376
1377 const std::set<Cell*>& CellCache::getNarrowCells() {
1378 return m_narrowCells;
1379 }
1380
1381 void CellCache::removeNarrowCell(Cell* cell) {
1382 std::set<Cell*>::iterator it = m_narrowCells.find(cell);
1383 if (it != m_narrowCells.end()) {
1384 (*it)->removeChangeListener(m_cellZoneListener);
1385 m_narrowCells.erase(it);
1386 }
1387 }
1388
1389 void CellCache::resetNarrowCells() {
1390 std::set<Cell*>::const_iterator it = m_narrowCells.begin();
1391 for (; it != m_narrowCells.end(); ++it) {
1392 (*it)->removeChangeListener(m_cellZoneListener);
1393 }
1394 m_narrowCells.clear();
1395 }
1396
1397 bool CellCache::isSearchNarrowCells() {
1398 return m_searchNarrow;
1399 }
1400
1401 void CellCache::setSearchNarrowCells(bool search) {
1402 m_searchNarrow = search;
1403 }
1404
1405 void CellCache::addCellToArea(const std::string& id, Cell* cell) {
1406 m_cellAreas.insert(std::pair<std::string, Cell*>(id, cell));
1407 }
1408
1409 void CellCache::addCellsToArea(const std::string& id, const std::vector<Cell*>& cells) {
1410 std::vector<Cell*>::const_iterator it = cells.begin();
1411 for (; it != cells.end(); ++it) {
1412 addCellToArea(id, *it);
1413 }
1414 }
1415
1416 void CellCache::removeCellFromArea(Cell* cell) {
1417 StringCellIterator it = m_cellAreas.begin();
1418 while (it != m_cellAreas.end()) {
1419 if ((*it).second == cell) {
1420 m_cellAreas.erase(it++);
1421 } else {
1422 ++it;
1423 }
1424 }
1425 }
1426
1427 void CellCache::removeCellFromArea(const std::string& id, Cell* cell) {
1428 StringCellPair result = m_cellAreas.equal_range(id);
1429 StringCellIterator it = result.first;
1430 for (; it != result.second; ++it) {
1431 if ((*it).second == cell) {
1432 m_cellAreas.erase(it);
1433 break;
1434 }
1435 }
1436 }
1437
1438 void CellCache::removeCellsFromArea(const std::string& id, const std::vector<Cell*>& cells) {
1439 std::vector<Cell*>::const_iterator it = cells.begin();
1440 for (; it != cells.end(); ++it) {
1441 removeCellFromArea(id, *it);
1442 }
1443 }
1444
1445 void CellCache::removeArea(const std::string& id) {
1446 m_cellAreas.erase(id);
1447 }
1448
1449 bool CellCache::existsArea(const std::string& id) {
1450 StringCellIterator it = m_cellAreas.find(id);
1451 if (it == m_cellAreas.end()) {
1452 return false;
1453 }
1454 return true;
1455 }
1456
1457 std::vector<std::string> CellCache::getAreas() {
1458 std::vector<std::string> areas;
1459 std::string last("");
1460 StringCellIterator it = m_cellAreas.begin();
1461 for (; it != m_cellAreas.end(); ++it) {
1462 if (last != (*it).first) {
1463 last = (*it).first;
1464 areas.push_back(last);
1465 }
1466 }
1467 return areas;
1468 }
1469
1470 std::vector<std::string> CellCache::getCellAreas(Cell* cell) {
1471 std::vector<std::string> areas;
1472 StringCellIterator it = m_cellAreas.begin();
1473 for (; it != m_cellAreas.end(); ++it) {
1474 if ((*it).second == cell) {
1475 areas.push_back((*it).first);
1476 }
1477 }
1478 return areas;
1479 }
1480
1481 std::vector<Cell*> CellCache::getAreaCells(const std::string& id) {
1482 std::vector<Cell*> cells;
1483 StringCellPair result = m_cellAreas.equal_range(id);
1484 StringCellIterator it = result.first;
1485 for (; it != result.second; ++it) {
1486 cells.push_back((*it).second);
1487 }
1488 return cells;
1489 }
1490
1491 bool CellCache::isCellInArea(const std::string& id, Cell* cell) {
1492 StringCellPair result = m_cellAreas.equal_range(id);
1493 StringCellIterator it = result.first;
1494 for (; it != result.second; ++it) {
1495 if ((*it).second == cell) {
1496 return true;
1497 }
1498 }
1499 return false;
1500 }
1501
1502 Rect CellCache::calculateCurrentSize() {
1503 // set base size
1504 ModelCoordinate min, max;
1505 m_layer->getMinMaxCoordinates(min, max);
1506 Rect newsize(min.x, min.y, max.x, max.y);
1507
1508 const std::vector<Layer*>& interacts = m_layer->getInteractLayers();
1509 if (!interacts.empty()) {
1510 std::vector<Layer*>::const_iterator layit = interacts.begin();
1511 for(; layit != interacts.end(); ++layit) {
1512 // set size
1513 (*layit)->getMinMaxCoordinates(min, max, m_layer);
1514 newsize.w = std::max(max.x, newsize.w);
1515 newsize.h = std::max(max.y, newsize.h);
1516 newsize.x = std::min(min.x, newsize.x);
1517 newsize.y = std::min(min.y, newsize.y);
1518 }
1519 }
1520 return newsize;
1521 }
1522
1523 void CellCache::setStaticSize(bool staticSize) {
1524 m_staticSize = staticSize;
1525 }
1526
1527 bool CellCache::isStaticSize() {
1528 return m_staticSize;
1529 }
1530
1531 void CellCache::setBlockingUpdate(bool update) {
1532 m_blockingUpdate = update;
1533 }
1534
1535 void CellCache::setSizeUpdate(bool update) {
1536 m_sizeUpdate = update;
1537 }
1538
1539 void CellCache::update() {
1540 if (m_sizeUpdate) {
1541 resize();
1542 m_sizeUpdate = false;
1543 }
1544 m_blockingUpdate = false;
1545 }
1546 } // FIFE