1: <?php
  2: 
  3: namespace Alpha\Util\Graph;
  4: 
  5: use Alpha\Util\Logging\Logger;
  6: 
  7: /**
  8:  * Maintains the geometry for a tree graph.
  9:  *
 10:  * @since 1.0
 11:  *
 12:  * @author John Collins <dev@alphaframework.org>
 13:  * @license http://www.opensource.org/licenses/bsd-license.php The BSD License
 14:  * @copyright Copyright (c) 2015, John Collins (founder of Alpha Framework).
 15:  * All rights reserved.
 16:  *
 17:  * <pre>
 18:  * Redistribution and use in source and binary forms, with or
 19:  * without modification, are permitted provided that the
 20:  * following conditions are met:
 21:  *
 22:  * * Redistributions of source code must retain the above
 23:  *   copyright notice, this list of conditions and the
 24:  *   following disclaimer.
 25:  * * Redistributions in binary form must reproduce the above
 26:  *   copyright notice, this list of conditions and the
 27:  *   following disclaimer in the documentation and/or other
 28:  *   materials provided with the distribution.
 29:  * * Neither the name of the Alpha Framework nor the names
 30:  *   of its contributors may be used to endorse or promote
 31:  *   products derived from this software without specific
 32:  *   prior written permission.
 33:  *
 34:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 35:  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 36:  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 37:  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 38:  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 39:  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 40:  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 41:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 42:  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 43:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 44:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 45:  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 46:  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 47:  * </pre>
 48:  */
 49: class TreeGraph
 50: {
 51:     /**
 52:      * An array of nodes on the previous level.
 53:      *
 54:      * @var array
 55:      *
 56:      * @since 1.0
 57:      */
 58:     private $previousLevelNodes = array();
 59: 
 60:     /**
 61:      * An array of nodes in this graph.
 62:      *
 63:      * @var array
 64:      *
 65:      * @since 1.0
 66:      */
 67:     private $nodes = array();
 68: 
 69:     /**
 70:      * The root node of the graph.
 71:      *
 72:      * @var Alpha\Util\Graph\GraphNode
 73:      *
 74:      * @since 1.0
 75:      */
 76:     private $root;
 77: 
 78:     /**
 79:      * The amount of space between graph rows.
 80:      *
 81:      * @var int
 82:      *
 83:      * @since 1.0
 84:      */
 85:     private $rowSpace;
 86: 
 87:     /**
 88:      * The amount of space between graph columns.
 89:      *
 90:      * @var int
 91:      *
 92:      * @since 1.0
 93:      */
 94:     private $colSpace;
 95: 
 96:     /**
 97:      * The amount of space between graph branches.
 98:      *
 99:      * @var int
100:      *
101:      * @since 1.0
102:      */
103:     private $branchSpace;
104: 
105:     /**
106:      * Flag to track whether the chart is rendered or not.
107:      *
108:      * @var bool
109:      *
110:      * @since 1.0
111:      */
112:     private $isRendered = false;
113: 
114:     /**
115:      * The index of the current node in the graph we are inspecting.
116:      *
117:      * @var int
118:      *
119:      * @since 1.0
120:      */
121:     private $position = 0;
122: 
123:     /**
124:      * The height of the graph.
125:      *
126:      * @var int
127:      *
128:      * @since 1.0
129:      */
130:     private $height = 0;
131: 
132:     /**
133:      * The width of the graph.
134:      *
135:      * @var int
136:      *
137:      * @since 1.0
138:      */
139:     private $width = 0;
140: 
141:     /**
142:      * Trace logger.
143:      *
144:      * @var Alpha\Util\Logging\Logger
145:      *
146:      * @since 1.0
147:      */
148:     private static $logger = null;
149: 
150:     /**
151:      * Constructor.
152:      *
153:      * @param int $rowSpace
154:      * @param int $colSpace
155:      * @param int $branchSpace
156:      *
157:      * @since 1.0
158:      */
159:     public function __construct($rowSpace = 40, $colSpace = 40, $branchSpace = 80)
160:     {
161:         self::$logger = new Logger('TreeGraph');
162: 
163:         $this->root = new GraphNode(0, 0, 0);
164:         $this->rowSpace = $rowSpace;
165:         $this->colSpace = $colSpace;
166:         $this->branchSpace = $branchSpace;
167:     }
168: 
169:     /**
170:      * Add a new node to the graph.
171:      *
172:      * @param int    $id
173:      * @param int    $pid
174:      * @param string $message
175:      * @param int    $w
176:      * @param int    $h
177:      * @param array  $nodeColour
178:      * @param string $URL
179:      *
180:      * @since 1.0
181:      */
182:     public function add($id, $pid, $message = '', $w = 0, $h = 0, $nodeColour, $URL)
183:     {
184:         $node = new GraphNode($id, $w, $h, $message, $nodeColour, $URL);
185: 
186:         if (isset($this->nodes[$pid])) {
187:             $pnode = $this->nodes[$pid];
188:             $node->setParentNode($pnode);
189:             $pnode->addChild($node);
190:         } else {
191:             $pnode = $this->root;
192:             $node->setParentNode($pnode);
193:             $this->root->addChild($node);
194:         }
195: 
196:         $this->nodes[$id] = $node;
197:     }
198: 
199:     /**
200:      * Get the specified node from the graph.
201:      *
202:      * @param int    $id
203:      *
204:      * @return Alpha\Util\Graph\GraphNode
205:      *
206:      * @since 2.0.1
207:      */
208:     public function get($id)
209:     {
210:         if (isset($this->nodes[$id])) {
211:             return $this->nodes[$id];
212:         } else {
213:             return null;
214:         }
215:     }
216: 
217:     /**
218:      * The first pass of the graph.
219:      *
220:      * @param Alpha\Util\Graph\GraphNode $node
221:      * @param int                        $level
222:      *
223:      * @since 1.0
224:      */
225:     private function firstPass($node, $level)
226:     {
227:         $this->setNeighbours($node, $level);
228: 
229:         if ($node->childCount() == 0) {
230:             $leftSibling = $node->getLeftSibling();
231: 
232:             if (isset($leftSibling)) {
233:                 $node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
234:             } else {
235:                 $node->setOffset(0);
236:             }
237:         } else {
238:             $childCount = $node->childCount();
239: 
240:             for ($i = 0; $i < $childCount; ++$i) {
241:                 $this->firstPass($node->getChildAt($i), $level + 1);
242:             }
243: 
244:             $midPoint = $node->getChildrenCenter();
245:             $midPoint -= $node->getWidth() / 2;
246:             $leftSibling = $node->getLeftSibling();
247: 
248:             if (isset($leftSibling)) {
249:                 $node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
250:                 $node->setModifier($node->getOffset() - $midPoint);
251: 
252:                 $this->layout($node, $level);
253:             } else {
254:                 $node->setOffset($midPoint);
255:             }
256:         }
257: 
258:         self::$logger->debug('Memory usage at first scan ['.((memory_get_usage(true) / 1024) / 1024).' MB]');
259:     }
260: 
261:     /**
262:      * The second pass of the graph.
263:      *
264:      * @param Alpha\Util\Graph\GraphNode $node
265:      * @param int                        $level
266:      * @param int                        $x
267:      * @param int                        $y
268:      *
269:      * @since 1.0
270:      */
271:     private function secondPass($node, $level, $x = 0, $y = 0)
272:     {
273:         $nodeX = $node->getOffset() + $x;
274:         $nodeY = $y;
275: 
276:         $node->setX($nodeX);
277:         $node->setY($nodeY);
278: 
279:         $this->height = ($this->height > $node->getY() + $node->getWidth()) ? $this->height : $node->getY() + $node->getWidth();
280:         $this->width = ($this->width > $nodeX + $node->getWidth()) ? $this->width : $nodeX + $node->getWidth() + 10;
281: 
282:         if ($node->childCount() > 0) {
283:             $this->secondPass($node->getChildAt(0), $level + 1, $x + $node->getModifier(), $y + $node->getHeight() + $this->rowSpace);
284:         }
285: 
286:         $rightSibling = $node->getRightSibling();
287: 
288:         if (isset($rightSibling)) {
289:             $this->secondPass($rightSibling, $level, $x, $y);
290:         }
291: 
292:         self::$logger->debug('Memory usage at second scan ['.((memory_get_usage(true) / 1024) / 1024).' MB]');
293:     }
294: 
295:     /**
296:      * Handles the laying out of multi-branch trees.
297:      *
298:      * @param Alpha\Util\Graph\GraphNode $node
299:      * @param int                        $level
300:      *
301:      * @since 1.0
302:      */
303:     private function layout($node, $level)
304:     {
305:         $firstChild = $node->getChildAt(0);
306:         $firstChildLeftNeighbour = $firstChild->getLeftSibling();
307: 
308:         for ($j = 1; $j <= $level; ++$j) {
309:             $modifierSumRight = 0;
310:             $modifierSumLeft = 0;
311:             $rightAncestor = $firstChild;
312:             $leftAncestor = $firstChildLeftNeighbour;
313: 
314:             for ($l = 0; $l < $j; ++$l) {
315:                 $rightAncestor = $rightAncestor->getParentNode();
316:                 $leftAncestor = $leftAncestor->getParentNode();
317:                 $modifierSumRight += $rightAncestor->getModifier();
318:                 $modifierSumLeft += $leftAncestor->getModifier();
319:             }
320: 
321:             $totalGap = ($firstChildLeftNeighbour->getOffset() + $modifierSumLeft + $firstChildLeftNeighbour->getWidth() + $this->branchSpace) - ($firstChild->getOffset() + $modifierSumRight);
322: 
323:             if ($totalGap > 0) {
324:                 $subTree = $node;
325:                 $subTreesCount = 0;
326: 
327:                 while (isset($subTree) && $subTree !== $leftAncestor) {
328:                     $subTree = $subTree->getLeftSibling();
329:                     ++$subTreesCount;
330:                 }
331: 
332:                 $subTreeMove = $node;
333:                 $singleGap = $totalGap / $subTreesCount;
334: 
335:                 while (isset($subTreeMove) && $subTreeMove !== $leftAncestor) {
336:                     $subTreeMove = $subTreeMove->getLeftSibling();
337: 
338:                     if (isset($subTreeMove)) {
339:                         $subTreeMove->setOffset($subTreeMove->getOffset() + $totalGap);
340:                         $subTreeMove->setModifier($subTreeMove->getModifier() + $totalGap);
341:                         $totalGap -= $singleGap;
342:                     }
343:                 }
344:             }
345: 
346:             if ($firstChild->childCount() == 0) {
347:                 $firstChild = $this->getLeftmost($node, 0, $j);
348:             } else {
349:                 $firstChild = $firstChild->getChildAt(0);
350:             }
351: 
352:             if (isset($firstChild)) {
353:                 $firstChildLeftNeighbour = $firstChild->getLeftSibling();
354:             }
355:         }
356:     }
357: 
358:     /**
359:      * Setup neighbour nodes.
360:      *
361:      * @param Alpha\Util\Graph\GraphNode $node
362:      * @param int                        $level
363:      *
364:      * @since 1.0
365:      */
366:     private function setNeighbours($node, $level)
367:     {
368:         if (isset($this->previousLevelNodes[$level])) {
369:             $node->setLeftSibling($this->previousLevelNodes[$level]);
370:         }
371: 
372:         if ($node->getLeftSibling()) {
373:             $node->getLeftSibling()->setRightSibling($node);
374:         }
375:         $this->previousLevelNodes[$level] = $node;
376:     }
377: 
378:     /**
379:      * Get left most node in the branch.
380:      *
381:      * @param Alpha\Util\Graph\GraphNode $node
382:      * @param int                        $level
383:      * @param int                        $maxlevel
384:      *
385:      * @return Alpha\Util\Graph\GraphNode
386:      *
387:      * @since 1.0
388:      */
389:     private function getLeftmost($node, $level, $maxlevel)
390:     {
391:         if ($level >= $maxlevel) {
392:             return $node;
393:         }
394: 
395:         $childCount = $node->childCount();
396: 
397:         if ($childCount == 0) {
398:             return;
399:         }
400: 
401:         for ($i = 0; $i < $childCount; ++$i) {
402:             $child = $node->getChildAt($i);
403: 
404:             $leftmostDescendant = $this->getLeftmost($child, $level + 1, $maxlevel);
405: 
406:             if (isset($leftmostDescendant)) {
407:                 return $leftmostDescendant;
408:             }
409:         }
410: 
411:         return;
412:     }
413: 
414:     /**
415:      * Render the chart in memory.
416:      *
417:      * @since 1.0
418:      */
419:     protected function render()
420:     {
421:         $this->firstPass($this->root, 0);
422:         $this->secondPass($this->root, 0);
423: 
424:         foreach ($this->nodes as $node) {
425:             $node->setUpLinks();
426:         }
427: 
428:         $this->isRendered = true;
429:     }
430: 
431:     /**
432:      * Get the width of the graph, will invoke render() if not already rendered.
433:      *
434:      * @since 1.0
435:      */
436:     public function getWidth()
437:     {
438:         if (!$this->isRendered) {
439:             $this->render();
440:         }
441: 
442:         return $this->width;
443:     }
444: 
445:     /**
446:      * Get the heith of the graph, will invoke render() if not already rendered.
447:      *
448:      * @since 1.0
449:      */
450:     public function getHeight()
451:     {
452:         if (!$this->isRendered) {
453:             $this->render();
454:         }
455: 
456:         return $this->height;
457:     }
458: 
459:     /**
460:      * Get the next GraphNode instance in the graph, will invoke render() if not already rendered.
461:      *
462:      * @return Alpha\Util\Graph\GraphNode
463:      *
464:      * @since 1.0
465:      */
466:     public function next()
467:     {
468:         if (!$this->isRendered) {
469:             $this->render();
470:         }
471: 
472:         if (isset($this->nodes[$this->position + 1])) {
473:             ++$this->position;
474: 
475:             return $this->nodes[$this->position];
476:         } else {
477:             return;
478:         }
479:     }
480: 
481:     /**
482:      * Check to see if another GraphNode instance in the graph is available.
483:      *
484:      * @return bool
485:      *
486:      * @since 1.0
487:      */
488:     public function hasNext()
489:     {
490:         if (isset($this->nodes[$this->position + 1])) {
491:             return true;
492:         } else {
493:             return false;
494:         }
495:     }
496: }
497: