| 1 | <?php |
| 2 | /* |
| 3 | +--------------------------------------------------------------------+ |
| 4 | | CiviCRM version 4.5 | |
| 5 | +--------------------------------------------------------------------+ |
| 6 | | Copyright CiviCRM LLC (c) 2004-2014 | |
| 7 | +--------------------------------------------------------------------+ |
| 8 | | This file is a part of CiviCRM. | |
| 9 | | | |
| 10 | | CiviCRM is free software; you can copy, modify, and distribute it | |
| 11 | | under the terms of the GNU Affero General Public License | |
| 12 | | Version 3, 19 November 2007 and the CiviCRM Licensing Exception. | |
| 13 | | | |
| 14 | | CiviCRM is distributed in the hope that it will be useful, but | |
| 15 | | WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 16 | | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
| 17 | | See the GNU Affero General Public License for more details. | |
| 18 | | | |
| 19 | | You should have received a copy of the GNU Affero General Public | |
| 20 | | License and the CiviCRM Licensing Exception along | |
| 21 | | with this program; if not, contact CiviCRM LLC | |
| 22 | | at info[AT]civicrm[DOT]org. If you have questions about the | |
| 23 | | GNU Affero General Public License or the licensing of CiviCRM, | |
| 24 | | see the CiviCRM license FAQ at http://civicrm.org/licensing | |
| 25 | +--------------------------------------------------------------------+ |
| 26 | */ |
| 27 | |
| 28 | /** |
| 29 | * |
| 30 | * @package CRM |
| 31 | * @copyright CiviCRM LLC (c) 2004-2014 |
| 32 | * $Id$ |
| 33 | * |
| 34 | */ |
| 35 | class CRM_Contact_BAO_GroupNestingCache { |
| 36 | static public function update() { |
| 37 | // lets build the tree in memory first |
| 38 | |
| 39 | $sql = " |
| 40 | SELECT n.child_group_id as child , |
| 41 | n.parent_group_id as parent |
| 42 | FROM civicrm_group_nesting n, |
| 43 | civicrm_group gc, |
| 44 | civicrm_group gp |
| 45 | WHERE n.child_group_id = gc.id |
| 46 | AND n.parent_group_id = gp.id |
| 47 | "; |
| 48 | |
| 49 | $dao = CRM_Core_DAO::executeQuery($sql); |
| 50 | |
| 51 | $tree = array(); |
| 52 | while ($dao->fetch()) { |
| 53 | if (!array_key_exists($dao->child, $tree)) { |
| 54 | $tree[$dao->child] = array('children' => array(), |
| 55 | 'parents' => array(), |
| 56 | ); |
| 57 | } |
| 58 | |
| 59 | if (!array_key_exists($dao->parent, $tree)) { |
| 60 | $tree[$dao->parent] = array('children' => array(), |
| 61 | 'parents' => array(), |
| 62 | ); |
| 63 | } |
| 64 | |
| 65 | $tree[$dao->child]['parents'][] = $dao->parent; |
| 66 | $tree[$dao->parent]['children'][] = $dao->child; |
| 67 | } |
| 68 | |
| 69 | if (self::checkCyclicGraph($tree)) { |
| 70 | CRM_Core_Error::fatal(ts('We detected a cycle which we cant handle. aborting')); |
| 71 | } |
| 72 | |
| 73 | // first reset the current cache entries |
| 74 | $sql = " |
| 75 | UPDATE civicrm_group |
| 76 | SET parents = null, |
| 77 | children = null |
| 78 | "; |
| 79 | CRM_Core_DAO::executeQuery($sql); |
| 80 | |
| 81 | $values = array(); |
| 82 | foreach (array_keys($tree) as $id) { |
| 83 | $parents = implode(',', $tree[$id]['parents']); |
| 84 | $children = implode(',', $tree[$id]['children']); |
| 85 | $parents = $parents == NULL ? 'null' : "'$parents'"; |
| 86 | $children = $children == NULL ? 'null' : "'$children'"; |
| 87 | $sql = " |
| 88 | UPDATE civicrm_group |
| 89 | SET parents = $parents , |
| 90 | children = $children |
| 91 | WHERE id = $id |
| 92 | "; |
| 93 | CRM_Core_DAO::executeQuery($sql); |
| 94 | } |
| 95 | |
| 96 | // this tree stuff is quite useful, so lets store it in the cache |
| 97 | CRM_Core_BAO_Cache::setItem($tree, 'contact groups', 'nestable tree hierarchy'); |
| 98 | } |
| 99 | |
| 100 | /** |
| 101 | * @param $tree |
| 102 | * |
| 103 | * @return bool |
| 104 | */ |
| 105 | static function checkCyclicGraph(&$tree) { |
| 106 | // lets keep this simple, we should probably use a graph algoritm here at some stage |
| 107 | |
| 108 | // foreach group that has a parent or a child, ensure that |
| 109 | // the ancestors and descendants dont intersect |
| 110 | foreach ($tree as $id => $dontCare) { |
| 111 | if (self::isCyclic($tree, $id)) { |
| 112 | return TRUE; |
| 113 | } |
| 114 | } |
| 115 | |
| 116 | return FALSE; |
| 117 | } |
| 118 | |
| 119 | /** |
| 120 | * @param $tree |
| 121 | * @param $id |
| 122 | * |
| 123 | * @return bool |
| 124 | */ |
| 125 | static function isCyclic(&$tree, $id) { |
| 126 | $parents = $children = array(); |
| 127 | self::getAll($parent, $tree, $id, 'parents'); |
| 128 | self::getAll($child, $tree, $id, 'children'); |
| 129 | |
| 130 | $one = array_intersect($parents, $children); |
| 131 | $two = array_intersect($children, $parents); |
| 132 | if (!empty($one) || |
| 133 | !empty($two) |
| 134 | ) { |
| 135 | CRM_Core_Error::debug($id, $tree); |
| 136 | CRM_Core_Error::debug($id, $one); |
| 137 | CRM_Core_Error::debug($id, $two); |
| 138 | return TRUE; |
| 139 | } |
| 140 | return FALSE; |
| 141 | } |
| 142 | |
| 143 | /** |
| 144 | * @param $id |
| 145 | * @param $groups |
| 146 | * |
| 147 | * @return array |
| 148 | */ |
| 149 | static function getPotentialCandidates($id, &$groups) { |
| 150 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 151 | |
| 152 | if ($tree === NULL) { |
| 153 | self::update(); |
| 154 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 155 | } |
| 156 | |
| 157 | $potential = $groups; |
| 158 | |
| 159 | // remove all descendants |
| 160 | self::invalidate($potential, $tree, $id, 'children'); |
| 161 | |
| 162 | // remove all ancestors |
| 163 | self::invalidate($potential, $tree, $id, 'parents'); |
| 164 | |
| 165 | return array_keys($potential); |
| 166 | } |
| 167 | |
| 168 | /** |
| 169 | * @param $potential |
| 170 | * @param $tree |
| 171 | * @param $id |
| 172 | * @param $token |
| 173 | */ |
| 174 | static function invalidate(&$potential, &$tree, $id, $token) { |
| 175 | unset($potential[$id]); |
| 176 | |
| 177 | if (!isset($tree[$id]) || |
| 178 | empty($tree[$id][$token]) |
| 179 | ) { |
| 180 | return; |
| 181 | } |
| 182 | |
| 183 | foreach ($tree[$id][$token] as $tokenID) { |
| 184 | self::invalidate($potential, $tree, $tokenID, $token); |
| 185 | } |
| 186 | } |
| 187 | |
| 188 | /** |
| 189 | * @param $all |
| 190 | * @param $tree |
| 191 | * @param $id |
| 192 | * @param $token |
| 193 | */ |
| 194 | static function getAll(&$all, &$tree, $id, $token) { |
| 195 | // if seen before, dont do anything |
| 196 | if (isset($all[$id])) { |
| 197 | return; |
| 198 | } |
| 199 | |
| 200 | $all[$id] = 1; |
| 201 | if (!isset($tree[$id]) || |
| 202 | empty($tree[$id][$token]) |
| 203 | ) { |
| 204 | return; |
| 205 | } |
| 206 | |
| 207 | foreach ($tree[$id][$token] as $tokenID) { |
| 208 | self::getAll($all, $tree, $tokenID, $token); |
| 209 | } |
| 210 | } |
| 211 | |
| 212 | /** |
| 213 | * @return string |
| 214 | */ |
| 215 | static function json() { |
| 216 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 217 | |
| 218 | if ($tree === NULL) { |
| 219 | self::update(); |
| 220 | $tree = CRM_Core_BAO_Cache::getItem('contact groups', 'nestable tree hierarchy'); |
| 221 | } |
| 222 | |
| 223 | // get all the groups |
| 224 | $groups = CRM_Core_PseudoConstant::group(); |
| 225 | |
| 226 | foreach ($groups as $id => $name) { |
| 227 | $string = "id:'$id', name:'$name'"; |
| 228 | if (isset($tree[$id])) { |
| 229 | $children = array(); |
| 230 | if (!empty($tree[$id]['children'])) { |
| 231 | foreach ($tree[$id]['children'] as $child) { |
| 232 | $children[] = "{_reference:'$child'}"; |
| 233 | } |
| 234 | $children = implode(',', $children); |
| 235 | $string .= ", children:[$children]"; |
| 236 | if (empty($tree[$id]['parents'])) { |
| 237 | $string .= ", type:'rootGroup'"; |
| 238 | } |
| 239 | else { |
| 240 | $string .= ", type:'middleGroup'"; |
| 241 | } |
| 242 | } |
| 243 | else { |
| 244 | $string .= ", type:'leafGroup'"; |
| 245 | } |
| 246 | } |
| 247 | else { |
| 248 | $string .= ", children:[], type:'rootGroup'"; |
| 249 | } |
| 250 | $values[] = "{ $string }"; |
| 251 | } |
| 252 | |
| 253 | $items = implode(",\n", $values); |
| 254 | $json = "{ |
| 255 | identifier:'id', |
| 256 | label:'name', |
| 257 | items:[ $items ] |
| 258 | }"; |
| 259 | return $json; |
| 260 | } |
| 261 | } |
| 262 | |