<?php

class treesort
{
	public static function sort($items, $addHelpers = true)
	{
		$children = array();    // Parent's children
		$itemsize = array();    // Family sizes
		
		// Get children by parent
		foreach ($items as $item) {
			if ($item['parent_id'] != 0) {
				$children[$item['parent_id']][] = $item['id'];
			}
			$itemsize[$item['id']] = 1;
		}
		
		$adopted = array();     // Children that have been adopted
		for ($i = 0; count($children) != 0; $i++) {
			$itemId = $items[$i]['id'];
			//echo "id: {$itemId}\n";
			
			// If I have children
			if (isset($children[$itemId])) {
				//echo "\tchildren: " . count($children[$itemId]) . "\n";
				$offset = 1;
				
				// Loop through children and append them after me
				foreach ($children[$itemId] as $id) {
					$itemsize[$itemId] += $itemsize[$id];  // Update my family size
					$adopted[$id] = true;
					$childIndex = self::getIndexInArray($items, $id);
					//echo "\t\tchild size/id/index: $itemsize[$id] $id $childIndex\n";
					// Move child with family
					for ($j = 0; $j < $itemsize[$id]; $j++) {
						if ($childIndex + $j < $i + $offset) {
							$childIndexReal = $childIndex;  // When we move a child, the next will come to into position
							$i--;   // If child is before me, I should adjust my index pointer
						} else {
							$childIndexReal = $childIndex + $j;
						}
						$child = array($items[$childIndexReal]);
						unset($items[$childIndexReal]);
						array_splice($items, $i + $offset++, 0, $child);
						/*if ($itemId == 2) {
							self::debug($items, $itemsize);
						}*/
					}
				}
				
				// Resize parent if it has adopted me
				$thisId = $itemId;
				while (isset($adopted[$thisId])) {
					$parentId = $items[self::getIndexInArray($items, $thisId)]['parent_id'];
					$itemsize[$parentId] += $itemsize[$itemId];
					$thisId = $parentId;
				}
				
				unset($children[$itemId]);
				/*if ($itemId == 2) {
					var_dump($items);var_dump($children);var_dump($itemsize);var_dump($adopted);die;
				}*/
			}
			/*if ($i == count($items) - 1) {
				$items = array_merge($items, array());
				
				$i = -1;
				if ($break) {var_dump($items);var_dump($children);var_dump($itemsize);var_dump($adopted);
					break;
				}
				$break = true;
			}*/
		}
		
		if ($addHelpers) {
			return self::addHelpers($items);
		} else {
			return $items;
		}
	}
	
	public static function getIndexInArray(&$items, $id)
	{
		foreach ($items as $index => $item) {
			if ($item['id'] == $id) {
				return $index;
			}
		}
		return null;
	}
	
	public static function addHelpers($items)
	{
		$level = 0;
		$parentIds = array(0);
		$lastParentId = 0;
		$last = null;
		$first = true;
		foreach ($items as &$item) {
			if ($item['parent_id'] != $lastParentId) {
				if (in_array($item['parent_id'], $parentIds)) {
					if (isset($lastIndex)) {
						$items[$lastIndex] = true;
					}
					for ($i = count($parentIds) - 1; $item['parent_id'] != $parentIds[$i]; $i--) {
						$level--;
						unset($parentIds[$i]);
					}
				
				} else {
					if (isset($last)) {
						$last['has_children'] = true;
					}
					$parentIds[count($parentIds)] = $item['parent_id'];
					$level++;
				}
			}
			
			$item['level'] = $level;
			$item['first'] = $first;
			$item['has_children'] = false;
			$lastParentId = $item['parent_id'];
			$first = false;
			$last = &$item;
		}
		
		return $items;
	}
	
	private static function _debug($items, $itemsize)
	{
		echo "----\n";
		foreach ($items as $item) {
			echo "$item[id]:$item[name] - {$itemsize[$item['id']]}\n";
		}
		echo "----\n";
	}
}




/*$sorted = array();        1
$idToIndex = array();
$orphans = array();

foreach ($categories as $category) {
	if ($category['parent_id'] == 0) {
		$sorted[] = $category;
		$idToIndex[$category['id']] = count($sorted) - 1;
		if (isset($orphans[$category['id']])) {
			// If orphans exist, append them
			$index = $idToIndex[$category['id']] + 1;
			array_splice($sorted, $index, 0, $orphans[$category['id']]);
			foreach ($orphans[$category['id']] as $orphan) {
				$idToIndex[$orphan['id']] = $index++;
			}
			unset($orphans[$category['id']]);
		}
	} else {
		if ($category['parent_id'] == 2) {var_dump($idToIndex);}
		if (isset($idToIndex[$category['parent_id']])) {
			if (count($sorted) > 1) {
				for ($index = $idToIndex[$category['parent_id']] + 1;
						isset($sorted[$index]) && 
						$sorted[$index]['parent_id'] == $category['parent_id'];
					$index++) {}
			} else {
				$index = 1;
			}
			array_splice($sorted, $index, 0, array($category));
			$idToIndex[$category['id']] = $index;
		
		} else {
			$orphans[$category['parent_id']][] = $category;
		}
	}
}*/