1 files changed, 142 insertions, 0 deletions
diff --git a/core/libraries/ORM_MPTT.php b/core/libraries/ORM_MPTT.php
new file mode 100644
index 00000000..6d3478ad
--- /dev/null
+++ b/core/libraries/ORM_MPTT.php
@@ -0,0 +1,142 @@
+<?php defined("SYSPATH") or die("No direct script access.");
+/**
+ * Gallery - a web based photo album viewer and editor
+ * Copyright (C) 2000-2008 Bharat Mediratta
+ *
+ * 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., 51 Franklin Street - Fifth Floor, Boston, MA  02110-1301, USA.
+ */
+/**
+ * Implement Modified Preorder Tree Traversal on top of ORM.
+ *
+ * MPTT is an efficient way to store and retrieve hierarchical data in a single database table.
+ * For a good description, read http://www.sitepoint.com/article/hierarchical-data-database/3/
+ *
+ * This code was heavily influenced by code from:
+ *  - http://code.google.com/p/kohana-mptt/
+ *  - http://code.google.com/p/kohana-mptt/wiki/Documentation
+ *  - http://code.google.com/p/s7ncms/source/browse/trunk/modules/s7ncms/libraries/ORM_MPTT.php
+ *
+ * Unfortunately that code was not ready for production and I did not want to absorb their code
+ * and licensing issues so I've reimplemented just the features that we need.
+ */
+class ORM_MPTT_Core extends ORM {
+  private $model_name = null;
+  private $parent = null;
+  private $parents = null;
+  private $children = null;
+
+  function __construct($id=null) {
+    parent::__construct($id);
+    $this->model_name = inflector::singular($this->table_name);
+  }
+
+  /**
+   * Add this node as a child of the parent provided.
+   *
+   * @param integer $parent_id the id of the parent node
+   * @return ORM
+   */
+  function add_to_parent($parent_id) {
+    $this->_lock();
+
+    try {
+      $parent = ORM::factory($this->model_name, $parent_id);
+      $parent->_grow();
+      $this->left = $parent->right - 2;
+      $this->right = $parent->right - 1;
+      $this->parent_id = $parent->id;
+      $this->level = $parent->level + 1;
+      $this->save();
+    } catch (Exception $e) {
+      $this->_unlock();
+      throw $e;
+    }
+
+    $this->_unlock();
+    return $this;
+  }
+
+  /**
+   * Return the parent of this node
+   *
+   * @return ORM
+   */
+  function parent() {
+    if (!isset($this->parent)) {
+      $this->parent =
+        ORM::factory($this->model_name)->where("id", $this->parent_id)->find();
+    }
+    return $this->parent;
+  }
+
+  /**
+   * Return all the parents of this node, in order from root to leaf.
+   *
+   * @return array ORM
+   */
+  function parents() {
+    if (!isset($this->parents)) {
+      $this->parents = $this->where("`left` <= {$this->left}")
+        ->where("`right` >= {$this->right}")
+        ->orderby("left", "ASC")
+        ->find_all();
+    }
+    return $this->parents;
+  }
+
+  /**
+   * Return all of the children of this node, unordered.
+   *
+   * @return array ORM
+   */
+  function children() {
+    if (!isset($this->children)) {
+      $this->children =
+        $this->where("parent_id", $this->id)->find_all();
+    }
+    return $this->children;
+  }
+
+  /**
+   * Grow this node's space enough to make room for 1 or more new nodes.
+   *
+   * @param integer $count the number of new nodes to add
+   */
+  private function _grow($count=1) {
+    $size = $count * 2;
+    $this->db->query(
+      "UPDATE `{$this->table_name}` SET `left` = `left` + $size WHERE `left` >= {$this->right}");
+    $this->db->query(
+      "UPDATE `{$this->table_name}` SET `right` = `right` + $size WHERE `right` >= {$this->right}");
+    $this->right += 2;
+  }
+
+  /**
+   * Lock the tree to prevent concurrent modification.
+   */
+  private function _lock() {
+    $result = $this->db->query("SELECT GET_LOCK('{$this->table_name}', 1) AS L")->current();
+    if (empty($result->L)) {
+      throw new Exception("@todo UNABLE_TO_LOCK_EXCEPTION");
+    }
+  }
+
+  /**
+   * Unlock the tree.
+   */
+  private function _unlock() {
+    $this->db->query("SELECT RELEASE_LOCK('{$this->table_name}')");
+  }
+}