Convert array of paths into UL list

I have a table in a database that contains a variety of paths to pages of my website. Each path is listed only one time. I currently have a very long and convoluted series of queries and PHP to pull all these and rewrite the data into an unordered list (to create a menu for my website). It seems that there is probably a relatively simple looping approach that would work MUCH more efficiently, but I cannot seem to get anything working. I have found TONS of PHP scripts that create UL lists from file trees, but all of them either don't work or can't handle the inherently not recursive nature of my query results (some require multi-dimensional arrays of my paths, which would be fine except for my trouble with creating those). I did find a script that works pretty close, but it formats the <ul> portion incorrectly by placing sub-lists outside of the <li> section (I will explain below)

Here is a sample:

DB returns the following in results array:

about/contact/
about/contact/form/
about/history/
about/staff/
about/staff/bobjones/
about/staff/sallymae/
products/
products/gifts/
products/widgets/

and I want to create the following output:

<ul>
  <li>about/
  <ul>
    <li>about/contact/
    <ul>
      <li>about/contact/form/</li>
    </ul>
    </li>
    <li>about/history/</li>
    <li>about/staff/
    <ul>
      <li>about/staff/bobjones/</li>
      <li>about/staff/sallymae/</li>
    </ul>
    </li>
  </ul>
  </li>
  <li>products/
  <ul>
    <li>products/gifts/</li>
    <li>products/widgets/</li>
  </ul>
  </li>
</ul>

So I got very close with a script found here: http://www.daniweb.com/forums/thread285916.html but I have run into a problem. It turns out that the script that I found creates improperly formatted UL lists. In a CORRECT situation, a sub-list is contained within the <li> of the parent element. In this scripting, the parent <li> is closed and then a <ul> block is inserted. The overall script is actually fairly elegant in the way that it keeps up with the levels and such, but I cannot wrap my head around it enough to figure out how to fix it. I have the whole thing in a function here:

function generateMainMenu()
{
  global $db;

  $MenuListOutput = '';
  $PathsArray = array();

  $sql = "SELECT PageUrlName FROM `table`";
  $result = mysql_query($sql, $db) or die('MySQL error: ' . mysql_error());
  while ($PageDataArray = mysql_fetch_array($result))
  {
    $PathsArray[] = rtrim($PageDataArray['PageUrlName'],"/"); //this function does not like paths to end in a slash, so remove trailing slash before saving to array
  }

  sort($PathsArray);// These need to be sorted.
  $MenuListOutput .= '<ul id="nav">'."\n";//get things started off right
  $directories=array ();
  $topmark=0;
  $submenu=0;
  foreach ($PathsArray as $value) {
    // break up each path into it's constituent directories
    $limb=explode("/",$value);
    for($i=0;$i<count($limb);$i++) {
      if ($i+1==count($limb)){
        // It's the 'Leaf' of the tree, so it needs a link
        if ($topmark>$i){
          // the previous path had more directories, therefore more Unordered Lists.
          $MenuListOutput .= str_repeat("</ul>",$topmark-$i); // Close off the Unordered Lists
          $MenuListOutput .= "\n";// For neatness
        }
        $MenuListOutput .= '<li><a href="/'.$value.'">'.$limb[$i]."</a></li>\n";// Print the Leaf link
        $topmark=$i;// Establish the number of directories in this path
      }else{
        // It's a directory
        if($directories[$i]!=$limb[$i]){
          // If the directory is the same as the previous path we are not interested.
          if ($topmark>$i){// the previous path had more directories, therefore more Unordered Lists.
            $MenuListOutput .= str_repeat("</ul>",$topmark-$i);// Close off the Unordered Lists
            $MenuListOutput .= "\n";// For neatness
          }

          // (next line replaced to avoid duplicate listing of each parent)
          //$MenuListOutput .= "<li>".$limb[$i]."</li>\n<ul>\n";
          $MenuListOutput .= "<ul>\n";
          $submenu++;// Increment the dropdown.
          $directories[$i]=$limb[$i];// Mark it so that if the next path's directory in a similar position is the same, it won't be processed.
        }
      }
    }
  }
  $MenuListOutput .= str_repeat("</ul>",$topmark+1);// Close off the Unordered Lists

  return $MenuListOutput."\n\n\n";
}

and it returns something like this:

<ul id="nav">
<li><a href="/about">about</a&g开发者_如何学编程t;</li>
<ul>
<li><a href="/about/history">history</a></li>
<li><a href="/about/job-opportunities">job-opportunities</a></li>
<li><a href="/about/mission">mission</a></li>
<li><a href="/about/privacy-policy">privacy-policy</a></li>
</ul>
<li><a href="/giftcards">giftcards</a></li>
<li><a href="/locations">locations</a></li>
<ul>
<li><a href="/locations/main-office">main-office</a></li>
<li><a href="/locations/branch-office">branch-office</a></li>
</ul>
<li><a href="/packages">packages</a></li>
</ul>

Anyone have an idea of where I need to add in some additional logic and how I can accomplish this? Other ideas on a better way to do this? It seems like this is such a common issue that there would be a simple/standard method of handling something like this. Maybe if I could figure out how to create a multi-dimensional array from my paths then those could be iterated to make this work?

---

EDIT: More Complex :-(

I tried casablanca's response and it worked perfectly...except I then realized that now I have a follow-up to make things more difficult. In order to display the "name" of the page, I need to also have that info in the array, thus the path probably works better as the array key and the name in the value. Any thoughts on changing like this:

$paths = array(
    "about/contact/ " => "Contact Us", 
    "about/contact/form/ " => "Contact Form",
    "about/history/ " => "Our History",
    "about/staff/ " => "Our Staff",
    "about/staff/bobjones/ " => "Bob",
    "about/staff/sallymae/ " => "Sally",
    "products/ " => "All Products",
    "products/gifts/ " => "Gift Ideas!",
    "products/widgets/ " => "Widgets"
);

and then using something like this line within the buildUL function:

echo '<a href="'.$prefix.$key.'/">'.$paths[$prefix.$key].'</a>';

---

Edit:

Changed to cater for updated question.

I'm using an array index of __title to hold the page title. As long as you never have a directory in your tree called __title this should be fine. You're free to change this sentinel value to anything you wish however.

I have also changed it so the list building function returns a string, so that you can store the value for use later in your page. (You can of course just do echo build_list(build_tree($paths)) to output the list directly.

<?php

$paths = array(
    'about/contact/' => 'Contact Us', 
    'about/contact/form/' => 'Contact Form',
    'about/history/' => 'Our History',
    'about/staff/' => 'Our Staff',
    'about/staff/bobjones/' => 'Bob',
    'about/staff/sallymae/' => 'Sally',
    'products/' => 'All Products',
    'products/gifts/' => 'Gift Ideas!',
    'products/widgets/' => 'Widgets'
);

function build_tree($path_list) {
    $path_tree = array();
    foreach ($path_list as $path => $title) {
        $list = explode('/', trim($path, '/'));
        $last_dir = &$path_tree;
        foreach ($list as $dir) {
            $last_dir =& $last_dir[$dir];
        }
        $last_dir['__title'] = $title;
    }
    return $path_tree;
}

function build_list($tree, $prefix = '') {
    $ul = '';
    foreach ($tree as $key => $value) {
        $li = '';
        if (is_array($value)) {
            if (array_key_exists('__title', $value)) {
                $li .= "$prefix$key/ <a href=\"/$prefix$key/\">${value['__title']}</a>";
            } else {
                $li .= "$prefix$key/";
            }
            $li .= build_list($value, "$prefix$key/");
            $ul .= strlen($li) ? "<li>$li</li>" : '';
        }
    }
    return strlen($ul) ? "<ul>$ul</ul>" : '';
}

$tree = build_tree($paths);
$list = build_list($tree);
echo $list;

?>

---

Indeed a multi-dimensional would help here. You can build one by splitting each path into components and using those to index into the array. Assuming $paths is your initial array, the code below will build a multi-dimensional array $array with keys corresponding to the path components:

$array = array();
foreach ($paths as $path) {
  $path = trim($path, '/');
  $list = explode('/', $path);
  $n = count($list);

  $arrayRef = &$array; // start from the root
  for ($i = 0; $i < $n; $i++) {
    $key = $list[$i];
    $arrayRef = &$arrayRef[$key]; // index into the next level
  }
}

You can then iterate over this array using a recursive function, which you can use to naturally build a recursive UL list as in your example. In each recursive call, $array is a sub-array of the entire array this is being currently processed and $prefix is the path from the root to the current sub-array:

function buildUL($array, $prefix) {
  echo "\n<ul>\n";
  foreach ($array as $key => $value) {
    echo "<li>";
    echo "$prefix$key/";
    // if the value is another array, recursively build the list
    if (is_array($value))
      buildUL($value, "$prefix$key/");
    echo "</li>\n";
  }
  echo "</ul>\n";
}

The initial call would simply be buildUL($array, '').