Alternate data structures

[melix]

As a followup to this thread, here's a proposal for a hierarchical page content data structure. This is the basics, and I'm quite sure it could be tweaked for better memory consumption.

Class ContentNode

Code: Select all

<?php
class ContentNode {
  var $content;
  var $parentNode;
  var $children;
  var $level;

  function ContentNode($content, $parentNode=null) {
    $this->content = &$content;
    $this->parentNode = &$parentNode;
    $this->children = array();
    $this->level = $parentNode?($parentNode->getLevel()+1):0;
  }

  function getChildrenCount() {
    return count($this->children);
  }
  
  function getContent() {
    return $this->content;
  }
  
  function getParentNode() {
    return $this->parentNode;
  }
  
  function getChildren() {
    return $this->children;
  }
  
  function hasChildren() {
    return (count($this->children)>0);
  }
  
  function getLevel() {
    return $this->level;
  }

  function addChild($node) {
    $this->children[] = &$node;
  }
  
}
?>

And add the following method to the ContentManager :

Code: Select all

<?php
...

function GetAllContentAsHierarchy($loadprops=true) {
		global $gCms;
		$db = &$gCms->db;

       if (isset($gCms->ContentCache) &&
            ($loadprops == false || $gCms->variables['cachedprops'] == true))
            {
            return $gCms->ContentCache;
            }

    $currentNode = new ContentNode(null);
		$level =0;
    $gCms->ContentCache = &$currentNode;
		
    $gCms->variables['cachedprops'] = $loadprops;
		$query = "SELECT * FROM ".cms_db_prefix()."content ORDER BY hierarchy";
		$dbresult = $db->Execute($query);

		if ($dbresult && $dbresult->RowCount() > 0)
		{
			while ($row = $dbresult->FetchRow())
			{
				#Make sure the type exists.  If so, instantiate and load
				if (in_array($row['type'], array_keys(@ContentManager::ListContentTypes())))
				{
					$contentobj = new $row['type'];
					$contentobj->LoadFromData($row, $loadprops);
          $curlevel = substr_count($contentobj->Hierarchy(),".")+1;
          if ($curlevel>$level) { // going farther in hierarchy
            $level = $curlevel;
            $node = new ContentNode($contentobj,$currentNode);
            $currentNode->addChild($node);
            $currentNode = &$node;
          } else if ($curlevel<$level) { // going upper
            while ($currentNode->getLevel()!=$curlevel) {
              $currentNode = &$currentNode->getParentNode();
            }
            $node = new ContentNode($contentobj,$currentNode->getParentNode());
            $currentNode->getParentNode()->addChild($node);
            $level=$curlevel;
            $currentNode = $node;
          } else {// same level
            $node = new ContentNode($contentobj,$currentNode->getParentNode());
            $currentNode->getParentNode()->addChild($node);
          }
				}
			}
		}
		return $gCms->ContentCache;
  
  }

...
?>

WDYT ?

As an improvement we would be have some kind of hierarchy class (not written yet) which would provide indexed (direct) access to nodes :

Code: Select all

<?php

...

function getNodeByContentID($id)

..

function getNodeByContentAlias($alias)

...
?>

Edit : fix in hierarchy building

[melix]

ok, I've played around with 0.11b6, to create an alternate content list that would use this hierarchical structure.

If you know me, you'd probably know that :

- my site has more than 300 pages
- I had a problem of empty list with 0.11b6 due to the fact that node were not collapsed by default

I've just found the reason for the second problem : the script died before end, because it took too long to perform (>60 seconds). The main reason is the horrific embedded loop that determines if pages can be moved up or down.

My script makes use of the hierarchical data structure to make this faster. Expanding the whole tree is possible, while the other way it wasn't (well, it takes 45s to display the page...). Moreover, the algorithm itself is more simple.

There are still many improvements I'll try to improve at least the following bottleneck :

- the scripts loads the whole tree while it is not necessary when elements are collapsed

Here's the quickly modified listcontent.php

Code: Select all

<?php
#CMS - CMS Made Simple
#(c)2004 by Ted Kulp (wishy@users.sf.net)
#This project's homepage is: http://cmsmadesimple.sf.net
#
#This program is free software; you can redistribute it and/or modify
#it under the terms of the GNU General Public License as published by
#the Free Software Foundation; either version 2 of the License, or
#(at your option) any later version.
#
#This program is distributed in the hope that it will be useful,
#but WITHOUT ANY WARRANTY; without even the implied warranty of
#MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#GNU General Public License for more details.
#You should have received a copy of the GNU General Public License
#along with this program; if not, write to the Free Software
#Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#
#$Id: listcontent.php 2206 2005-11-23 02:14:00Z wishy $

$mtime = microtime();
   $mtime = explode(" ",$mtime);
   $mtime = $mtime[1] + $mtime[0];
   $starttime = $mtime; 
   
$CMS_ADMIN_PAGE=1;

require_once("../include.php");

check_login();
$userid = get_userid();
include_once("header.php");

if (isset($_GET["message"])) {
	$message = preg_replace('/\</','',$_GET['message']);
	echo '<div class="pagemcontainer"><p class="pagemessage">'.$message.'</p></div>';
}
/*
function hierarchyToHTML($h) {
  $nodes = $h->getChildren();
	echo "<ul>";
	foreach ($nodes as $node) {
    echo "<li>".$node->getContent()->Hierarchy()." ".$node->getContent()->Alias()." (".$node->getChildrenCount().")</li>";
    if ($node->hasChildren()) {
      hierarchyToHTML($node);
    }
  }
	echo "</ul>";
}

$hierarchy = ContentManager::GetAllContentAsHierarchy(false);
hierarchyToHTML($hierarchy);
exit(0);*/
?>
<div class="pagecontainer">
	<div class="pageoverflow">
<?php

	$modifyall = check_permission($userid, 'Modify Any Page');
	//$content_array = ContentManager::GetAllContent(false);
  $mypages = author_pages($userid);
  $hierarchy = ContentManager::GetAllContentAsHierarchy(false);
	
  if ($modifyall)
	{
		if (isset($_GET["makedefault"]))
		{
			foreach ($content_array as $key=>$value_copy)
			{
				if ($value_copy->Id() == $_GET["makedefault"])
				{
					$value =& $content_array[$key];
					if ($value->DefaultContent() != true)
					{
						$value->SetDefaultContent(true);
						$value->Save();
					}
				}
				else
				{
					$value =& $content_array[$key];
					if ($value->DefaultContent() != false)
					{
						$value->SetDefaultContent(false);
						$value->Save();
					}
				}
			}
		}
	}
    // check if we're activating a page
    if (isset($_GET["setactive"])) 
	{
      	// to activate a page, you must be admin, owner, or additional author
		$permission = ($modifyall || 
			check_ownership($userid,$_GET["setactive"]) ||
			check_authorship($userid,$_GET["setactive"]));

		if($permission) 
		{
			foreach ($content_array as $key=>$value_copy)
			{
				if ($value_copy->Id() == $_GET["setactive"])
				{
					#Modify the object inline
					$value =& $content_array[$key];
					$value->SetActive(true);
					$value->Save();
				}
			}
    	}
    }

    // perhaps we're deactivating a page instead?
    if (isset($_GET["setinactive"])) 
	{
      	// to deactivate a page, you must be admin, owner, or additional author
      	$permission = ($modifyall || 
			check_ownership($userid,$_GET["setinactive"]) || 
			check_authorship($userid,$_GET["setinactive"]));
      	if($permission) 
		{
			foreach ($content_array as $key=>$value_copy)
			{
				if ($value_copy->Id() == $_GET["setinactive"])
				{
					#Modify the object inline
					$value =& $content_array[$key];
					$value->SetActive(false);
					$value->Save();
				}
			}
	    }
    }

	$page = 1;
	if (isset($_GET['page'])) $page = $_GET['page'];
	$limit = get_preference($userid, 'paging', 0);

	$thelist = '';
	$count = 0;

	$currow = "row1";
		
	// construct true/false button images
    $image_true = $themeObject->DisplayImage('icons/system/true.gif', lang('true'),'','','systemicon');
    $image_false = $themeObject->DisplayImage('icons/system/false.gif', lang('false'),'','','systemicon');

	$counter = 0;

	#Setup array so we don't load more templates than we need to
	$templates = array();

	#Ditto with users
	$users = array();

	$menupos = array();


function display_hierarchy($root) {
  global $templates;
  global $users;
  global $modifyall;
  global $userid;
  global $mypages;
  global $currow;
  global $themeObject;
  global $image_true;
  global $image_false;
  global $config;
  global $page;
  global $indent;
  
  $one = $root->getContent();
  $children = $root->getChildren();
  $thelist ="";
    
  if ($one) {
    if (!array_key_exists($one->TemplateId(), $templates)) {
  	 $templates[$one->TemplateId()] = TemplateOperations::LoadTemplateById($one->TemplateId());
  	}
  	
    if (!array_key_exists($one->Owner(), $users))	{
  		$users[$one->Owner()] = UserOperations::LoadUserById($one->Owner());
  	} 		
  }
  $subhier = "";
  if (!isset($one) || (!$one->Collapsed())) {
      foreach ($children as $child) { 
        $subhier .= display_hierarchy($child);
      }
  }
  
  if (isset($one) && ($modifyall || check_ownership($userid,$one->Id()) || quick_check_authorship($one->Id(), $mypages))) {
        $thelist .= "<tr class=\"$currow\" onmouseover=\"this.className='".$currow.'hover'."';\" onmouseout=\"this.className='".$currow."';\">\n";
        $thelist .= "<td>";
        if ($root->getChildrenCount() > 0) {
          if ($one->Collapsed()) {
            $thelist .= "<a href=\"setexpand.php?content_id=".$one->Id()."&col=0&page=".$page."\">";
            $thelist .= $themeObject->DisplayImage('icons/system/expand.gif', lang('expand'),'','','systemicon');
            $thelist .= "</a>";
          } else {
            $thelist .= "<a href=\"setexpand.php?content_id=".$one->Id()."&col=1&page=".$page."\">";
            $thelist .= $themeObject->DisplayImage('icons/system/contract.gif', lang('contract'),'','','systemicon');
            $thelist .= "</a>";
          }
        }
        $thelist .= "</td><td>".$one->Hierarchy()."</td>\n";
        
        $thelist .= "<td>";
        
        if ($indent) {
          for ($i=1;$i < $root->getLevel();$i++) {
            $thelist .= "-   ";
          }
        } ## if indent

        $thelist .= "<a href=\"editcontent.php?content_id=".$one->Id()."&page=".$page."\">".$one->Name()."</a></td>\n";
  			if (isset($templates[$one->TemplateId()]->name) && $templates[$one->TemplateId()]->name) {
  						 $thelist .= "<td>".$templates[$one->TemplateId()]->name."</td>\n";
  			}	else {
	  				$thelist .= "<td> </td>\n";
	  		}

	  		$thelist .= "<td>".$one->FriendlyName()."</td>\n";
  
 				if ($one->Owner() > -1)	{
  				$thelist .= "<td>".$users[$one->Owner()]->username."</td>\n";
	  		}	else {
  						$thelist .= "<td> </td>\n";
  			}

  			if($one->Active()) {
  				$thelist .= "<td class=\"pagepos\">".($one->DefaultContent() == 1?$image_true:"<a href=\"listcontent.php?setinactive=".$one->Id()."\">".$image_true."</a>")."</td>\n";
  			}	else {
  					$thelist .= "<td class=\"pagepos\"><a href=\"listcontent.php?setactive=".$one->Id()."\">".$image_false."</a></td>\n";
  			}
  	
				if ($one->IsDefaultPossible() == TRUE) {
  						$thelist .= "<td class=\"pagepos\">".($one->DefaultContent() == true?$image_true:"<a href=\"listcontent.php?makedefault=".$one->Id()."\" onclick=\"return confirm('".lang("confirmdefault")."');\">".$image_false."</a>")."</td>\n";
  			}	else {
  						$thelist .= "<td> </td>";
  			}   
        
        // code for move up is simple
        if ($modifyall) {
        $thelist .= "<td>";
          $parentNode = $root->getParentNode();
          if ($parentNode!=null) {
            $sameLevel = $parentNode->getChildren();
            if (count($sameLevel)>1) {
              if ($sameLevel[0]==$root) { // first 
                $thelist .= "<a href=\"movecontent.php?direction=down&content_id=".$one->Id()."&parent_id=".$one->ParentId()."&page=".$page."\">";
    						$thelist .= $themeObject->DisplayImage('icons/system/arrow-d.gif', lang('down'),'','','systemicon');
    						$thelist .= "</a>";
              } else if ($sameLevel[count($sameLevel)-1]==$root) { // last
                $thelist .= "<a href=\"movecontent.php?direction=up&content_id=".$one->Id()."&parent_id=".$one->ParentId()."&page=".$page."\">";
    						$thelist .= $themeObject->DisplayImage('icons/system/arrow-u.gif', lang('up'),'','','systemicon');
    						$thelist .= "</a>";
              } else { // middle
                $thelist .= "<a href=\"movecontent.php?direction=down&content_id=".$one->Id()."&parent_id=".$one->ParentId()."&page=".$page."\">";
    						$thelist .= $themeObject->DisplayImage('icons/system/arrow-d.gif', lang('down'),'','','systemicon');
    						$thelist .= "</a> <a href=\"movecontent.php?direction=up&content_id=".$one->Id()."&parent_id=".$one->ParentId()."&page=".$page."\">";
    						$thelist .= $themeObject->DisplayImage('icons/system/arrow-u.gif', lang('up'),'','','systemicon');
    						$thelist .= "</a>";
              }
            }
          }
          $thelist .= "</td>";
        }
        // end of move code
        
        if ($config["query_var"] == "")	{
  						$thelist .= "<td class=\"pagepos\"><a href=\"".$config["root_url"]."/index.php/".$one->Id()."\" rel=\"external\">";
  						$thelist .= $themeObject->DisplayImage('icons/system/view.gif', lang('view'),'','','systemicon');
              $thelist .= "</a></td>\n";
  			}	else if ($one->Alias() != "")	{
  						$thelist .= "<td class=\"pagepos\"><a href=\"".$config["root_url"]."/index.php?".$config['query_var']."=".$one->Alias()."\" rel=\"external\">";
                    	$thelist .= $themeObject->DisplayImage('icons/system/view.gif', lang('view'),'','','systemicon');
                    	$thelist .= "</a></td>\n";
  			}	else {
  						$thelist .= "<td class=\"pagepos\"><a href=\"".$config["root_url"]."/index.php?".$config['query_var']."=".$one->Id()."\" rel=\"external\">";
              $thelist .= $themeObject->DisplayImage('icons/system/view.gif', lang('view'),'','','systemicon');
              $thelist .= "</a></td>\n";
  			}
  			
        $thelist .= "<td class=\"pagepos\"><a href=\"editcontent.php?content_id=".$one->Id()."\">";
  			$thelist .= $themeObject->DisplayImage('icons/system/edit.gif', lang('edit'),'','','systemicon');
        $thelist .= "</a></td>\n";
  			$thelist .= "<td class=\"pagepos\"><a href=\"deletecontent.php?content_id=".$one->Id()."\" onclick=\"return confirm('".lang('deleteconfirm')."');\">";
        $thelist .= $themeObject->DisplayImage('icons/system/delete.gif', lang('delete'),'','','systemicon');
        $thelist .= "</a></td>\n";
  			$thelist .= "</tr>\n";  	
				($currow == "row1"?$currow="row2":$currow="row1");
			}
  return $thelist.$subhier;
}

	$indent = get_preference($userid, 'indent', true);

	if ($hierarchy->hasChildren())
	{
    $thelist .= display_hierarchy($hierarchy);
 		$thelist .= '</tbody>';
		$thelist .= "</table>\n";

	}
	$counter = 1;
	if (! $counter)
	{
		$thelist = "<p>".lang('noentries')."</p>";
	}

	$headoflist = '';
	
	if ($limit != 0 && $counter > $limit)
	{
		$headoflist .= "<p class=\"pageshowrows\">".pagination($page, $counter, $limit)."</p>";
	}

	$headoflist .= '<p class="pageheader">'.lang('currentpages').'</p></div>';
	if ($counter)
	{
		
		$headoflist .= '<table cellspacing="0" class="pagetable">'."\n";
		$headoflist .= '<thead>';
		$headoflist .= "<tr>\n";
		$headoflist .= "<th> </th>";
		$headoflist .= "<th> </th>";
		$headoflist .= "<th class=\"pagew25\">".lang('title')."</th>\n";
		$headoflist .= "<th>".lang('template')."</th>\n";
		$headoflist .= "<th>".lang('type')."</th>\n";
		$headoflist .= "<th>".lang('owner')."</th>\n";
		$headoflist .= "<th class=\"pagepos\">".lang('active')."</th>\n";
		$headoflist .= "<th class=\"pagepos\">".lang('default')."</th>\n";
		if ($modifyall)
		{
			$headoflist .= "<th class=\"pagepos\">".lang('move')."</th>\n";
		}
		$headoflist .= "<th class=\"pageicon\"> </th>\n";
		$headoflist .= "<th class=\"pageicon\"> </th>\n";
		$headoflist .= "<th class=\"pageicon\"> </th>\n";
		$headoflist .= "</tr>\n";
		$headoflist .= '</thead>';
		$headoflist .= '<tbody>';
	}
	echo $headoflist . $thelist;
	
	if (check_permission($userid, 'Add Pages'))
	{
?>
	<div class="pageoptions">
		<p class="pageoptions">
			<a href="addcontent.php">
				<?php 
					echo $themeObject->DisplayImage('icons/system/newobject.gif', lang('addcontent'),'','','systemicon').'</a>';
					echo ' <a class="pageoptions" href="addcontent.php">'.lang("addcontent");
				?>
			</a>   
			<a href="setexpand.php?expandall=1">
				<?php 
					echo $themeObject->DisplayImage('icons/system/expandall.gif', lang('expandall'),'','','systemicon').'</a>';
					echo ' <a class="pageoptions" href="setexpand.php?expandall=1">'.lang("expandall");
				?>
			</a>   
			<a href="setexpand.php?collapseall=1">
				<?php 
					echo $themeObject->DisplayImage('icons/system/contractall.gif', lang('contractall'),'','','systemicon').'</a>';
					echo ' <a class="pageoptions" href="setexpand.php?collapseall=1">'.lang("contractall");
				?>
			</a>
		</p>
	</div>
</div>
<p class="pageback"><a class="pageback" href="<?php echo $themeObject->BackUrl(); ?>">« <?php echo lang('back')?></a></p>
<?php
	}
$mtime = microtime();
   $mtime = explode(" ",$mtime);
   $mtime = $mtime[1] + $mtime[0];
   $endtime = $mtime;
   $totaltime = ($endtime - $starttime);
   echo "This page was created in ".$totaltime." seconds"; 
include_once("footer.php");

# vim:ts=4 sw=4 noet
?>

[Ted]

Melix.  You're ideas are REALLY good.

Can you do me a favor and develop against svn checkouts?  I would REALLY love the hierarchy manager fully worked out if possible.  I think that would be brilliant for listcontent and all of the horrific menu code that we have.  Moving something like this into the core would do wonders for speed.

And, of course, you're always welcome to join the IRC channel and talk with us.

Thanks!

[melix]

I'd be glad to help. Could you send me an MP to explain to me how I should work ?

[mosh]

did you guys ever consider the nested set approach to your problems? you will fetch the whole tree, no matter how nested it may be with only ONE database query. and all the problems due to your recursions are gone. there's a great PEAR class available which is based on PEAR::DB (but which in this case has to be ported to adodb first).

http://pear.php.net/package/DB_NestedSet

[Ted]

@mosh: Actually, my changes after beta6 do just that.  It grabs all of the content and props in 2 queries, and caches it all between requests.  It improved performance a LOT.

@melix: What OS are you working with?

[melix]

I'm using more than one OS, but mainly on Linux RH Fedora Core 4.

[Ted]

Well, first thing to do is install subversion.  For fedora, I think it's

Code: Select all

yum install subversion

.

Then you'll want to checkout the source code. 

Code: Select all

svn co http://svn.cmsmadesimple.org/svn/cmsmadesimple/trunk cms

Then modify your code against that.  Every once in awhile, you update the code to the latest by running this while in cms directory:

Code: Select all

svn update

If you want to send me a patch, first make it with:

Code: Select all

svn diff > cmspatch.diff

and then send me that file.

The workflow is very similar to CVS, if you've used that before.  You can also look at this page, which is written for tortoisesvn on the window platform for an idea of how it works.  http://dev.cmsmadesimple.org/docman/vie ... isesvn.htm and more importantly, http://svnbook.red-bean.com/en/1.1/index.html, which is the official svn book and geared to command line use.

Thanks!

[melix]

ok so the basics is that you are responsible for commits.

[Ted]

For now.  I usually hand out commit access after I get a few patches first.  Just a little precaution I like to make.

[melix]

That's quite legitimate

I'll do my best to get a first patch ASAP.

[melix]

Released a "patch" to wishy

Now I'm waiting for feedback. Basically there are two new classes :

- ContentNode, which encapsulates some Content, giving access to parent node and children nodes.
- ContentHierarchyManager, which takes a root node as constructor, and allows direct access to named content (by Alias) or by id.

To retrieve a hierarchy, you have to use this method :

Code: Select all

ContentManager::GetAllContentAsHierarchy($loadProps, $openNodes)

where $loadProps is a boolean (do I have to load all properties ?) and $openNodes is an array of ids which tells what nodes are expanded. If not set, the whole tree is loaded. The method returns the root node of the hierarchy.

If necessary, this root node can be managed :

Code: Select all

$manager = new ContentHierarchyManager($root);

there you are