hierarchy.php

<?php

public function fakeplastictrees() {
		$fields = array(
			'ID', 'Title', 'MenuTitle', 'URLSegment', 'ParentID', 'CanViewType'
		);

		$query = new SQLQuery($fields, 'SiteTree');
		$query = $query->setOrderBy('ParentID', 'ASC');
		$query->addWhere('"CanViewType" NOT IN (\'LoggedInUsers\', \'OnlyTheseUsers\')');
		$query->addWhere('"ShowInMenus" = 1');
		$results = $query->execute();
		
		
		$all = array();
		$allids = array();
		
		foreach ($results as $row) {
			$allids[$row['ID']] = true;
			$all[] = $row;
		}
		
		$deferred = array();
		$final = array();
		$hierarchy = array();
		
		$counter = 0;
		
		$this->counter = 0;
		
		$this->loopstuff($final, $all, $allids, 0);
		
		$ordered = ArrayList::create();
		// start at 0
		if (isset($final[0]['kids'])) {
			foreach ($final[0]['kids'] as $id) {
				$node = $final[$id];
				
				$this->buildLinks($node, null, $ordered, $final);
			}
		}
		
		print_r($ordered->toArray());
	}
	
	protected function buildLinks($node, $parent, $out, $nodemap) {
		$kids = isset($node['kids']) ? $node['kids'] : array();
		$node = ArrayData::create($node);
		$out->push($node);
		$node->Link = $parent ? $parent->Link . '/' . $node->URLSegment : $node->URLSegment;
		
		foreach ($kids as $id) {
			$n = $nodemap[$id];
			$this->buildLinks($n, $node, $out, $nodemap);
		}
	}
	
	protected function loopstuff (&$final, $remaining, $ids, $lastcount) {
		$deferred = array();

		foreach ($remaining as $row) {
			// orphan
			if ($row['ParentID'] && !isset($ids[$row['ParentID']])) {
				continue;
			}

			if (!isset($final[$row['ID']])) {
				$final[$row['ID']] = $row;
			}

			if ($row['ParentID'] && !isset($final[$row['ParentID']])) {
				$deferred[$row['ID']] = $row;
			} else {
				
				// add to the hierarchy of things
				$existing = isset($final[$row['ParentID']]['kids']) ? $final[$row['ParentID']]['kids'] : array();
				$existing[] = $row['ID'];
				$final[$row['ParentID']]['kids'] = $existing;
			}
		}
		
		if (count($deferred) == $lastcount) {
			return;
		}
		
		$lastcount = count($deferred);

		if (count($deferred)) {
			$this->loopstuff($final, $deferred, $ids, $lastcount);
		}
	}