Package muntjac :: Package data :: Package util :: Module hierarchical_container
[hide private]
[frames] | no frames]

Source Code for Module muntjac.data.util.hierarchical_container

  1  # Copyright (C) 2012 Vaadin Ltd.  
  2  # Copyright (C) 2012 Richard Lincoln 
  3  #  
  4  # Licensed under the Apache License, Version 2.0 (the "License");  
  5  # you may not use this file except in compliance with the License.  
  6  # You may obtain a copy of the License at  
  7  #  
  8  #     http://www.apache.org/licenses/LICENSE-2.0  
  9  #  
 10  # Unless required by applicable law or agreed to in writing, software  
 11  # distributed under the License is distributed on an "AS IS" BASIS,  
 12  # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  
 13  # See the License for the specific language governing permissions and  
 14  # limitations under the License. 
 15   
 16  """A specialized container whose contents can be accessed like it was a 
 17  tree-like structure.""" 
 18   
 19  from muntjac.util import OrderedSet 
 20   
 21  from muntjac.data.container import IContainer, IHierarchical 
 22  from muntjac.data.util.indexed_container import IndexedContainer 
 23   
 24   
25 -class HierarchicalContainer(IndexedContainer, IHierarchical, IContainer):
26 """A specialized Container whose contents can be accessed like it was a 27 tree-like structure. 28 29 @author: Vaadin Ltd. 30 @author: Richard Lincoln 31 """ 32
33 - def __init__(self):
34 super(HierarchicalContainer, self).__init__() 35 36 #: Set of IDs of those contained Items that can't have children. 37 self._noChildrenAllowed = set() 38 39 #: Mapping from Item ID to parent Item ID. 40 self._parent = dict() 41 42 #: Mapping from Item ID to parent Item ID for items included in 43 # the filtered container. 44 self._filteredParent = None 45 46 #: Mapping from Item ID to a list of child IDs. 47 self._children = dict() 48 49 #: Mapping from Item ID to a list of child IDs when filtered 50 self._filteredChildren = None 51 52 #: List that contains all root elements of the container. 53 self._roots = list() 54 55 #: List that contains all filtered root elements of the container. 56 self._filteredRoots = None 57 58 #: Determines how filtering of the container is done. 59 self._includeParentsWhenFiltering = True 60 61 self._contentChangedEventsDisabled = False 62 63 self._contentsChangedEventPending = None 64 65 self._filterOverride = None
66 67
68 - def areChildrenAllowed(self, itemId):
69 # Can the specified Item have any children? 70 if itemId in self._noChildrenAllowed: 71 return False 72 73 return self.containsId(itemId)
74 75
76 - def getChildren(self, itemId):
77 # Gets the IDs of the children of the specified Item. 78 if self._filteredChildren is not None: 79 c = self._filteredChildren.get(itemId) 80 else: 81 c = self._children.get(itemId) 82 83 if c is None: 84 return None 85 86 return list(c)
87 88
89 - def getParent(self, itemId):
90 # Gets the ID of the parent of the specified Item. 91 if self._filteredParent is not None: 92 return self._filteredParent.get(itemId) 93 94 return self._parent.get(itemId)
95 96
97 - def hasChildren(self, itemId):
98 # Is the Item corresponding to the given ID a leaf node? 99 if self._filteredChildren is not None: 100 return itemId in self._filteredChildren 101 else: 102 return itemId in self._children
103 104
105 - def isRoot(self, itemId):
106 # Is the Item corresponding to the given ID a root node? 107 108 # If the container is filtered the itemId must be among filteredRoots 109 # to be a root. 110 if self._filteredRoots is not None: 111 if itemId not in self._filteredRoots: 112 return False 113 elif itemId in self._parent: 114 return False 115 116 # Container is not filtered 117 return self.containsId(itemId)
118 119
120 - def rootItemIds(self):
121 # Gets the IDs of the root elements in the container. 122 if self._filteredRoots is not None: 123 return list(self._filteredRoots) 124 else: 125 return list(self._roots)
126 127
128 - def setChildrenAllowed(self, itemId, childrenAllowed):
129 """Sets the given Item's capability to have children. If the Item 130 identified with the itemId already has children and the 131 areChildrenAllowed is false this method fails and C{False} 132 is returned; the children must be first explicitly removed with 133 L{setParent} or L{IContainer.removeItem}. 134 135 @param itemId: 136 the ID of the Item in the container whose child capability 137 is to be set. 138 @param childrenAllowed: 139 the boolean value specifying if the Item can have children 140 or not. 141 @return: C{True} if the operation succeeded, C{False} if not 142 """ 143 # Checks that the item is in the container 144 if not self.containsId(itemId): 145 return False 146 147 # Updates status 148 if childrenAllowed: 149 if itemId in self._noChildrenAllowed: 150 self._noChildrenAllowed.remove(itemId) 151 else: 152 self._noChildrenAllowed.add(itemId) 153 154 return True
155 156
157 - def setParent(self, itemId, newParentId):
158 """Sets the parent of an Item. The new parent item must exist and be 159 able to have children. (C{canHaveChildren(newParentId) == True}). It 160 is also possible to detach a node from the hierarchy (and thus make 161 it root) by setting the parent C{None}. 162 163 @param itemId: 164 the ID of the item to be set as the child of the Item 165 identified with newParentId. 166 @param newParentId: 167 the ID of the Item that's to be the new parent of the Item 168 identified with itemId. 169 @return: C{True} if the operation succeeded, C{False} if not 170 """ 171 # Checks that the item is in the container 172 if not self.containsId(itemId): 173 return False 174 175 # Gets the old parent 176 oldParentId = self._parent.get(itemId) 177 178 # Checks if no change is necessary 179 if ((newParentId is None and oldParentId is None) 180 or (newParentId is not None) 181 and (newParentId == oldParentId)): 182 return True 183 184 # Making root? 185 if newParentId is None: 186 # The itemId should become a root so we need to 187 # - Remove it from the old parent's children list 188 # - Add it as a root 189 # - Remove it from the item -> parent list (parent is null for 190 # roots) 191 192 # Removes from old parents children list 193 l = self._children.get(oldParentId) 194 if l is not None: 195 l.remove(itemId) 196 if len(l) == 0: 197 del self._children[oldParentId] 198 199 # Add to be a root 200 self._roots.append(itemId) 201 202 # Updates parent 203 del self._parent[itemId] 204 205 if self.hasFilters(): 206 # Refilter the container if setParent is called when filters 207 # are applied. Changing parent can change what is included in 208 # the filtered version (if includeParentsWhenFiltering==true). 209 self.doFilterContainer(self.hasFilters()) 210 211 self.fireItemSetChange() 212 213 return True 214 215 # We get here when the item should not become a root and we need to 216 # - Verify the new parent exists and can have children 217 # - Check that the new parent is not a child of the selected itemId 218 # - Updated the item -> parent mapping to point to the new parent 219 # - Remove the item from the roots list if it was a root 220 # - Remove the item from the old parent's children list if it was not a 221 # root 222 223 # Checks that the new parent exists in container and can have 224 # children 225 if ((not self.containsId(newParentId)) 226 or (newParentId in self._noChildrenAllowed)): 227 return False 228 229 # Checks that setting parent doesn't result to a loop 230 o = newParentId 231 while (o is not None) and (o != itemId): 232 o = self._parent.get(o) 233 234 if o is not None: 235 return False 236 237 # Updates parent 238 self._parent[itemId] = newParentId 239 pcl = self._children.get(newParentId) 240 if pcl is None: 241 # Create an empty list for holding children if one were not 242 # previously created 243 pcl = list() 244 self._children[newParentId] = pcl 245 pcl.append(itemId) 246 247 # Removes from old parent or root 248 if oldParentId is None: 249 self._roots.remove(itemId) 250 else: 251 l = self._children.get(oldParentId) 252 if l is not None: 253 l.remove(itemId) 254 if len(l) == 0: 255 del self._children[oldParentId] 256 257 if self.hasFilters(): 258 # Refilter the container if setParent is called when filters 259 # are applied. Changing parent can change what is included in 260 # the filtered version (if includeParentsWhenFiltering==true). 261 self.doFilterContainer(self.hasFilters()) 262 263 self.fireItemSetChange() 264 265 return True
266 267
268 - def hasFilters(self):
269 return self._filteredRoots is not None
270 271
272 - def moveAfterSibling(self, itemId, siblingId):
273 """Moves a node (an Item) in the container immediately after a sibling 274 node. The two nodes must have the same parent in the container. 275 276 @param itemId: 277 the identifier of the moved node (Item) 278 @param siblingId: 279 the identifier of the reference node (Item), after which the 280 other node will be located 281 """ 282 parent2 = self.getParent(itemId) 283 if parent2 is None: 284 childrenList = self._roots 285 else: 286 childrenList = self._children.get(parent2) 287 288 if siblingId is None: 289 childrenList.remove(itemId) 290 childrenList.insert(0, itemId) 291 292 else: 293 oldIndex = childrenList.index(itemId) 294 indexOfSibling = childrenList.index(siblingId) 295 if (indexOfSibling != -1) and (oldIndex != -1): 296 if oldIndex > indexOfSibling: 297 newIndex = indexOfSibling + 1 298 else: 299 newIndex = indexOfSibling 300 301 del childrenList[oldIndex] 302 childrenList.insert(newIndex, itemId) 303 else: 304 raise ValueError('Given identifiers do not have the ' 305 'same parent.') 306 307 self.fireItemSetChange()
308 309
310 - def addItem(self, itemId=None):
311 if itemId is None: 312 self.disableContentsChangeEvents() 313 itemId = super(HierarchicalContainer, self).addItem() 314 if itemId is None: 315 return None 316 if itemId not in self._roots: 317 self._roots.append(itemId) 318 if self._filteredRoots is not None: 319 if self.passesFilters(itemId): 320 self._filteredRoots.append(itemId) 321 self.enableAndFireContentsChangeEvents() 322 return itemId 323 else: 324 self.disableContentsChangeEvents() 325 item = super(HierarchicalContainer, self).addItem(itemId) 326 if item is None: 327 return None 328 self._roots.append(itemId) 329 if self._filteredRoots is not None: 330 if self.passesFilters(itemId): 331 self._filteredRoots.append(itemId) 332 self.enableAndFireContentsChangeEvents() 333 return item
334 335
336 - def fireItemSetChange(self, event=None):
337 if event is not None: 338 if self.contentsChangeEventsOn(): 339 super(HierarchicalContainer, self).fireItemSetChange(event) 340 else: 341 self._contentsChangedEventPending = True 342 else: 343 super(HierarchicalContainer, self).fireItemSetChange()
344 345
346 - def contentsChangeEventsOn(self):
347 return not self._contentChangedEventsDisabled
348 349
351 self._contentChangedEventsDisabled = True
352 353
355 self._contentChangedEventsDisabled = False 356 if self._contentsChangedEventPending: 357 self.fireItemSetChange() 358 self._contentsChangedEventPending = False
359 360
361 - def removeAllItems(self):
362 self.disableContentsChangeEvents() 363 success = super(HierarchicalContainer, self).removeAllItems() 364 365 if success: 366 del self._roots[:] 367 self._parent.clear() 368 self._children.clear() 369 self._noChildrenAllowed.clear() 370 if self._filteredRoots is not None: 371 self._filteredRoots = None 372 373 if self._filteredChildren is not None: 374 self._filteredChildren = None 375 376 if self._filteredParent is not None: 377 self._filteredParent = None 378 379 self.enableAndFireContentsChangeEvents() 380 381 return success
382 383
384 - def removeItem(self, itemId):
385 self.disableContentsChangeEvents() 386 success = super(HierarchicalContainer, self).removeItem(itemId) 387 388 if success: 389 # Remove from roots if this was a root 390 if itemId in self._roots: 391 self._roots.remove(itemId) 392 393 # If filtering is enabled we might need to remove it from the 394 # filtered list also 395 if self._filteredRoots is not None: 396 self._filteredRoots.remove(itemId) 397 398 # Clear the children list. Old children will now become root nodes 399 childNodeIds = self._children.pop(itemId, None) 400 if childNodeIds is not None: 401 if self._filteredChildren is not None: 402 del self._filteredChildren[itemId] 403 404 for childId in childNodeIds: 405 self.setParent(childId, None) 406 407 # Parent of the item that we are removing will contain the item id 408 # in its children list 409 parentItemId = self._parent.get(itemId) 410 if parentItemId is not None: 411 c = self._children.get(parentItemId) 412 if c is not None: 413 c.remove(itemId) 414 if len(c) == 0: 415 del self._children[parentItemId] 416 417 # Found in the children list so might also be in the 418 # filteredChildren list 419 if self._filteredChildren is not None: 420 f = self._filteredChildren.get(parentItemId) 421 if f is not None: 422 f.remove(itemId) 423 if len(f) == 0: 424 del self._filteredChildren[parentItemId] 425 426 if itemId in self._parent: 427 del self._parent[itemId] 428 429 if self._filteredParent is not None: 430 # Item id no longer has a parent as the item id is not in the 431 # container. 432 del self._filteredParent[itemId] 433 434 if itemId in self._noChildrenAllowed: 435 self._noChildrenAllowed.remove(itemId) 436 437 self.enableAndFireContentsChangeEvents() 438 439 return success
440 441
442 - def removeItemRecursively(self, *args):
443 """Removes the Item identified by given itemId and all its children 444 from the given Container. 445 446 @see: L{removeItem} 447 @param args: tuple of the form 448 - (itemId) 449 - the identifier of the Item to be removed 450 - (container, itemId) 451 - the container where the item is to be removed 452 - the identifier of the Item to be removed 453 @return: true if the operation succeeded 454 """ 455 nargs = len(args) 456 if nargs == 1: 457 itemId, = args 458 self.disableContentsChangeEvents() 459 removeItemRecursively = self.removeItemRecursively(self, itemId) 460 self.enableAndFireContentsChangeEvents() 461 return removeItemRecursively 462 elif nargs == 2: 463 container, itemId = args 464 success = True 465 children2 = container.getChildren(itemId) 466 if children2 is not None: 467 arry = list(children2) 468 for i in range(len(arry)): 469 removeItemRecursively = self.removeItemRecursively( 470 container, arry[i]) 471 if not removeItemRecursively: 472 success = False 473 474 # remove the root of subtree if children where succesfully removed 475 if success: 476 success = container.removeItem(itemId) 477 478 return success
479 480
481 - def doSort(self):
482 super(HierarchicalContainer, self).doSort() 483 self._roots.sort(cmp=self.getItemSorter()) 484 for childList in self._children.values(): 485 childList.sort(cmp=self.getItemSorter())
486 487
489 """Used to control how filtering works. @see 490 L{setIncludeParentsWhenFiltering} for more information. 491 492 @return: true if all parents for items that match the filter are 493 included when filtering, false if only the matching items 494 are included 495 """ 496 return self._includeParentsWhenFiltering
497 498
499 - def setIncludeParentsWhenFiltering(self, includeParentsWhenFiltering):
500 """Controls how the filtering of the container works. Set this to true 501 to make filtering include parents for all matched items in addition to 502 the items themselves. Setting this to false causes the filtering to 503 only include the matching items and make items with excluded parents 504 into root items. 505 506 @param includeParentsWhenFiltering: 507 true to include all parents for items that match the filter, 508 false to only include the matching items 509 """ 510 self._includeParentsWhenFiltering = includeParentsWhenFiltering 511 if self._filteredRoots is not None: 512 # Currently filtered so needs to be re-filtered 513 self.doFilterContainer(True)
514 515
516 - def doFilterContainer(self, hasFilters):
517 if not hasFilters: 518 # All filters removed 519 self._filteredRoots = None 520 self._filteredChildren = None 521 self._filteredParent = None 522 523 return super(HierarchicalContainer, 524 self).doFilterContainer(hasFilters) 525 526 # Reset data structures 527 self._filteredRoots = list() 528 self._filteredChildren = dict() 529 self._filteredParent = dict() 530 531 if self._includeParentsWhenFiltering: 532 # Filter so that parents for items that match the filter are also 533 # included 534 includedItems = set() 535 for rootId in self._roots: 536 if self.filterIncludingParents(rootId, includedItems): 537 self._filteredRoots.append(rootId) 538 self.addFilteredChildrenRecursively(rootId, includedItems) 539 540 # includedItemIds now contains all the item ids that should be 541 # included. Filter IndexedContainer based on this 542 self._filterOverride = includedItems 543 super(HierarchicalContainer, self).doFilterContainer(hasFilters) 544 self._filterOverride = None 545 546 return True 547 else: 548 # Filter by including all items that pass the filter and make items 549 # with no parent new root items 550 551 # Filter IndexedContainer first so getItemIds return the items that 552 # match 553 super(HierarchicalContainer, self).doFilterContainer(hasFilters) 554 555 filteredItemIds = OrderedSet(self.getItemIds()) 556 for itemId in filteredItemIds: 557 itemParent = self._parent.get(itemId) 558 if (itemParent is None or itemParent not in filteredItemIds): 559 # Parent is not included or this was a root, in both cases 560 # this should be a filtered root 561 self._filteredRoots.append(itemId) 562 else: 563 # Parent is included. Add this to the children list (create 564 # it first if necessary) 565 self.addFilteredChild(itemParent, itemId) 566 567 return True
568 569
570 - def addFilteredChild(self, parentItemId, childItemId):
571 """Adds the given childItemId as a filteredChildren for the 572 parentItemId and sets it filteredParent. 573 """ 574 parentToChildrenList = self._filteredChildren.get(parentItemId) 575 if parentToChildrenList is None: 576 parentToChildrenList = list() 577 self._filteredChildren[parentItemId] = parentToChildrenList 578 self._filteredParent[childItemId] = parentItemId 579 parentToChildrenList.append(childItemId)
580 581
582 - def addFilteredChildrenRecursively(self, parentItemId, includedItems):
583 """Recursively adds all items in the includedItems list to the 584 filteredChildren map in the same order as they are in the children map. 585 Starts from parentItemId and recurses down as long as child items that 586 should be included are found. 587 588 @param parentItemId: 589 The item id to start recurse from. Not added to a 590 filteredChildren list 591 @param includedItems: 592 Set containing the item ids for the items that should be 593 included in the filteredChildren map 594 """ 595 childList = self._children.get(parentItemId) 596 if childList is None: 597 return 598 599 for childItemId in childList: 600 if childItemId in includedItems: 601 self.addFilteredChild(parentItemId, childItemId) 602 self.addFilteredChildrenRecursively(childItemId, includedItems)
603 604
605 - def filterIncludingParents(self, itemId, includedItems):
606 """Scans the itemId and all its children for which items should be 607 included when filtering. All items which passes the filters are 608 included. Additionally all items that have a child node that should be 609 included are also themselves included. 610 611 @return: true if the itemId should be included in the filtered 612 container. 613 """ 614 toBeIncluded = self.passesFilters(itemId) 615 616 childList = self._children.get(itemId) 617 if childList is not None: 618 for childItemId in self._children.get(itemId): 619 toBeIncluded = toBeIncluded | self.filterIncludingParents( 620 childItemId, includedItems) 621 if toBeIncluded: 622 includedItems.add(itemId) 623 624 return toBeIncluded
625 626
627 - def passesFilters(self, itemId):
628 if self._filterOverride is not None: 629 return itemId in self._filterOverride 630 else: 631 return super(HierarchicalContainer, self).passesFilters(itemId)
632