[eluser]danoph[/eluser]
I tried for a few hours searching for algorithms and trying to come up with my own and eventually gave up. Didn't know what to do.
@dtrenz:
With your solution, I noticed that if threads have parents they must be located AFTER the parent in the original array.
Can someone go through that code and explain it in pseudo-code or logic? Thanks 
@dtrenz, did you come up with that algorithm yourself or is that one of the sorting algorithms that I couldn't figure out?
http://en.wikipedia.org/wiki/Sorting_algorithm
[eluser]dtrenz[/eluser]
Yes, there are a couple of assumptions required for my code to work. These should probably be addressed so that the function is more generic.
(1) The original array element order matters.
The elements need to be in order, so that no element should be listed until it's parent element has been added.
(2) The first element must be the top most parent
The elements need to be in order, so that the first element is the top-most parent.
There are obvious flaws to this logic, but it should be simple enough to fix these restrictions. I'll see if I can't fix these.
This sorting algorithm was just done on-the-fly and from scratch.
[eluser]danoph[/eluser]
If a sorting algorithm could be matched up to the one dtrenz created, there is probably a standard way of sorting arrays like this. I couldn't figure it out though.
[eluser]christian.schorn[/eluser]
One other thing I noted: For this to work there can be only one top-level object.
(This was something I just explicitly checked for, because I have a similar problem but with several top-level objects (CS-speak: I don't have a tree, but a forest ))
But this is the easiest thing to fix:
Code: // snip
$new_page_array = array();
foreach ($page_array as $page) {
if (!isset($page->parent_thread)) {
$new_page_array[$page->permalink] = $page;
} else {
// snip
And just because it keeps bugging me, I'll try to find a way, where the order of the elements doesn't matter ...
[eluser]dtrenz[/eluser]
Yep, I've already fixed that part... I'm working on the strict ordering fix now, then I'll post the revised code.
[eluser]dtrenz[/eluser]
OK, here we go....
You can now have multiple top-level pages, in any order, and can refer to a parent_permalink page at any point in the array, even if you haven't listed the parent yet.
In this revision, I got rid of the ids (since order no longer matters), and used the permalinks as associative array keys. This meant that the permalink property in the Page class was now redundant.
New Page class:
Code: /*****************************************
* Page Class
*****************************************/
class Page
{
public $title;
public $parent_permalink;
public $children;
public function __construct($title = '', $parent_permalink = NULL)
{
$this->title = $title;
$this->parent_permalink = $parent_permalink;
}
}
Custom multi_array_key_exists function, as found in the PHP docs (thanks alishahnovin). This function is necessary to allow us to search the multi-dim array:
Code: /*****************************************
* multi_array_key_exists(mixed, array)
* ----------------------------------
* Array_key_exists() for multi-dim arrays.
*****************************************/
function multi_array_key_exists($needle, $haystack) {
foreach ($haystack as $key=>$value) {
if ($needle==$key) {
return true;
}
if (is_array($value)) {
multi_array_key_exists($needle, $value);
}
}
return false;
}
And here is the new site_map_sort function (basically the revised foreach block from before, in a function):
Code: /*****************************************
* sort_site_menu(array)
* ----------------------------------
* Sorts page object array into parent-child
* site menu array.
*****************************************/
function sort_site_menu($page_array)
{
$new_page_array = array();
foreach ($page_array as $permalink => $page)
{
if (!multi_array_key_exists($permalink, $new_page_array))
{
if (!isset($page->parent_permalink)) // Top-level element
{
$new_page_array[$permalink] = $page;
}
else // Child element element
{
$parent_permalink = $page->parent_permalink;
$level_map = array($parent_permalink);
while (isset($page_array[$parent_permalink]->parent_permalink))
{
$parent_permalink = $page_array[$parent_permalink]->parent_permalink;
$level_map[] = $parent_permalink;
}
$level_map = array_reverse($level_map);
$top_level = array_shift($level_map);
if (!isset($new_page_array[$top_level]))
{
$new_page_array[$top_level] = $page_array[$top_level];
}
$parent_array =& $new_page_array[$top_level];
foreach ($level_map as $level)
{
$parent_array->children[$level] = $page_array[$level];
$parent_array =& $parent_array->children[$level];
}
$parent_array->children[$permalink] = $page;
}
}
}
return $new_page_array;
}
Now we have the unsorted page_array (note that I have changed some things around to demonstrate the new flexibility of the algorithm) and the function call:
Code: $page_array = array(
'entrepreneurship' => new Page('Entrepreneurship', 'home'),
'home' => new Page('Moneypete'),
'ideas_business_advice_franchises' => new Page('Ideas, Business Advices, and Franchises', 'entrepreneurship'),
'practical-help-for-entrepreneur-startups' => new Page('Practical help for Entrepreneur Startups', 'entrepreneurship'),
'management_leadership' => new Page('Management & Leadership', 'entrepreneurship'),
'real_estate' => new Page('Real Estate'),
'stocks_bonds' => new Page('Stocks & Bonds', 'home'),
'financial_education' => new Page('Financial Education', 'home'),
'residential' => new Page('Residential', 'videos'),
'commercial' => new Page('Commercial', 'home'),
'ecommerce' => new Page('E-Commerce', 'home'),
'videos' => new Page('Videos', 'ecommerce')
);
print_r($page_array);
$new_page_array = sort_site_menu($page_array);
print_r($new_page_array);
Slap all of this in a PHP page and load... voila!
if you really want/need the page ids and/or permalink, simply add them back into the Page class and into the page array, like so...
Code: class Page
{
public $title;
public $parent_permalink;
public $permalink;
public $id;
public $children;
public function __construct($title = '', $parent_permalink = NULL, $permalink = '', $id = 0)
{
$this->title = $title;
$this->parent_permalink = $parent_permalink;
$this->permalink = $permalink;
$this->id = $id;
}
}
$page_array = array(
'entrepreneurship' => new Page('Entrepreneurship', 'home', 'entrepreneurship', 2),
ETC...
Sorry there aren't more comments. Documenting or writing up pseudo-code would be a task unto itself. If I can find time I might give it a shot. If you have any specific questions, I'd be happy to explain. -d
[eluser]Unknown[/eluser]
I know it's late but I've only just seen this thread  Here's what I came up with:
Code: $refs = array();
$list = array();
foreach($pages as $page) {
$thisref = &$refs[ $page['id'] ];
$thisref['parent_thread'] = $page['parent_thread'];
$thisref['title'] = $page['title'];
$thisref['permalink'] = $page['permalink'];
if($page['parent_thread'] == NULL) {
$list[$page['id']] = &$thisref;
} else {
$refs[$page['parent_thread']]['children'][$page['id']] = &$thisref;
}
}
That's the code that does all the work. Here's the complete test code I used which has the starting array and also the print_sitemap() function. The children of parents can appear anywhere in the array not just after the parent.
Code: <?php
function print_sitemap($pages, $level=0) {
$return = '';
foreach ($pages as $id => $page) {
$return .= str_repeat(' ', 4*$level);
$return .= '- '.$page['title'].'<br />';
if(!empty($page['children'])) $return .= print_sitemap($page['children'], ($level+1));
}
return $return;
}
$pages = array(
array('id' => 1,
'parent_thread' => NULL,
'title' => 'Moneypete',
'permalink' => 'home'
),
array('id' => 2,
'parent_thread' => 1,
'title' => 'Entrepreneurship',
'permalink' => 'entrepreneurship'
),
array('id' => 3,
'parent_thread' => 2,
'title' => 'Ideas, Business Advices, and Franchises',
'permalink' => 'ideas_business_advice_franchises'
),
array('id' => 4,
'parent_thread' => 2,
'title' => 'Practical help for Entrepreneur Startups',
'permalink' => 'practical-help-for-entrepreneur-startups'
),
array('id' => 5,
'parent_thread' => 2,
'title' => 'Management & Leadership',
'permalink' => 'management_leadership'
),
array('id' => 6,
'parent_thread' => 1,
'title' => 'Real Estate',
'permalink' => 'real_estate'
),
array('id' => 7,
'parent_thread' => 1,
'title' => 'Stocks & Bonds',
'permalink' => 'stocks_bonds'
),
array('id' => 8,
'parent_thread' => 1,
'title' => 'Financial Education',
'permalink' => 'financial_education'
),
array('id' => 9,
'parent_thread' => 1,
'title' => 'Residential',
'permalink' => 'residential'
),
array('id' => 12,
'parent_thread' => 1,
'title' => 'Commercial',
'permalink' => 'commercial'
),
array('id' => 15,
'parent_thread' => 1,
'title' => 'E-Commerce',
'permalink' => 'ecommerce'
),
array('id' => 16,
'parent_thread' => 15,
'title' => 'Videos',
'permalink' => 'videos'
)
);
$refs = array();
$list = array();
foreach($pages as $page) {
$thisref = &$refs[ $page['id'] ];
$thisref['parent_thread'] = $page['parent_thread'];
$thisref['title'] = $page['title'];
$thisref['permalink'] = $page['permalink'];
if($page['parent_thread'] == NULL) {
$list[$page['id']] = &$thisref;
} else {
$refs[$page['parent_thread']]['children'][$page['id']] = &$thisref;
}
}
echo print_sitemap($list);
?>
|
