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