1# (C) Copyright 2005-2020 Enthought, Inc., Austin, TX 2# All rights reserved. 3# 4# This software is provided without warranty under the terms of the BSD 5# license included in LICENSE.txt and may be redistributed only under 6# the conditions described in the aforementioned license. The license 7# is also available online at http://www.enthought.com/licenses/BSD.txt 8# 9# Thanks for using Enthought open source! 10""" 11Index Managers 12============== 13 14This module provides a number of classes for efficiently managing the 15mapping between different ways of representing indices. To do so, each 16index manager provides an intermediate, opaque index object that is 17suitable for use in these situations and is guaranteed to have a long 18enough life that it will not change or be garbage collected while a C++ 19object has a reference to it. 20 21The wx DataView classes expect to be given an integer id value that is 22stable and can be used to return the parent reference id. 23 24And Qt's ModelView system expects to be given a pointer to an object 25that is long-lived (in particular, it will not be garbage-collected 26during the lifetime of a QModelIndex) and which can be used to find 27the parent object of the current object. 28 29The default representation of an index from the point of view of the 30data view infrastructure is a sequence of integers, giving the index at 31each level of the hierarchy. DataViewModel classes can then use these 32indices to identify objects in the underlying data model. 33 34There are three main classes defined in the module: AbstractIndexManager, 35IntIndexManager, and TupleIndexManager. 36 37AbstractIndexManager 38 An ABC that defines the API 39 40IntIndexManager 41 An efficient index manager for non-hierarchical data, such as 42 lists, tables and 2D arrays. 43 44TupleIndexManager 45 An index manager that handles non-hierarchical data while trying 46 to be fast and memory efficient. 47 48The two concrete subclasses should be sufficient for most cases, but advanced 49users may create their own if for some reason the provided managers do not 50work well for a particular situation. Developers who implement this API 51need to be mindful of the requirements on the lifetime and identity 52constraints required by the various toolkit APIs. 53 54""" 55 56from abc import abstractmethod 57 58from traits.api import ABCHasStrictTraits, Dict, Int, Tuple 59 60 61#: The singular root object for all index managers. 62Root = () 63 64 65class AbstractIndexManager(ABCHasStrictTraits): 66 """ Abstract base class for index managers. 67 """ 68 69 @abstractmethod 70 def create_index(self, parent, row): 71 """ Given a parent index and a row number, create an index. 72 73 The internal structure of the index should not matter to 74 consuming code. However obejcts returned from this method 75 should persist until the reset method is called. 76 77 Parameters 78 ---------- 79 parent : index object 80 The parent index object. 81 row : int 82 The position of the resuling index in the parent's children. 83 84 Returns 85 ------- 86 index : index object 87 The resulting opaque index object. 88 89 Raises 90 ------ 91 IndexError 92 Negative row values raise an IndexError exception. 93 RuntimeError 94 If asked to create a persistent index for a parent and row 95 where that is not possible, a RuntimeError will be raised. 96 """ 97 raise NotImplementedError() 98 99 @abstractmethod 100 def get_parent_and_row(self, index): 101 """ Given an index object, return the parent index and row. 102 103 Parameters 104 ---------- 105 index : index object 106 The opaque index object. 107 108 Returns 109 ------- 110 parent : index object 111 The parent index object. 112 row : int 113 The position of the resuling index in the parent's children. 114 115 Raises 116 ------ 117 IndexError 118 If the Root object is passed as the index, this method will 119 raise an IndexError, as it has no parent. 120 """ 121 raise NotImplementedError() 122 123 def from_sequence(self, indices): 124 """ Given a sequence of indices, return the index object. 125 126 The default implementation starts at the root and repeatedly calls 127 create_index() to find the index at each level, returning the final 128 value. 129 130 Parameters 131 ---------- 132 indices : sequence of int 133 The row location at each level of the hierarchy. 134 135 Returns 136 ------- 137 index : index object 138 The persistent index object associated with this sequence. 139 140 Raises 141 ------ 142 RuntimeError 143 If asked to create a persistent index for a sequence of indices 144 where that is not possible, a RuntimeError will be raised. 145 """ 146 index = Root 147 for row in indices: 148 index = self.create_index(index, row) 149 return index 150 151 def to_sequence(self, index): 152 """ Given an index, return the corresponding sequence of row values. 153 154 The default implementation repeatedly calls get_parent_and_row() 155 to walk up the hierarchy and push the row values into the start 156 of the sequence. 157 158 Parameters 159 ---------- 160 index : index object 161 The opaque index object. 162 163 Returns 164 ------- 165 sequence : tuple of int 166 The row location at each level of the hierarchy. 167 """ 168 result = () 169 while index != Root: 170 index, row = self.get_parent_and_row(index) 171 result = (row,) + result 172 return result 173 174 @abstractmethod 175 def from_id(self, id): 176 """ Given an integer id, return the corresponding index. 177 178 Parameters 179 ---------- 180 id : int 181 An integer object id value. 182 183 Returns 184 ------- 185 index : index object 186 The persistent index object associated with this id. 187 """ 188 raise NotImplementedError() 189 190 @abstractmethod 191 def id(self, index): 192 """ Given an index, return the corresponding id. 193 194 Parameters 195 ---------- 196 index : index object 197 The persistent index object. 198 199 Returns 200 ------- 201 id : int 202 The associated integer object id value. 203 """ 204 raise NotImplementedError() 205 206 def reset(self): 207 """ Reset any caches and other state. 208 209 Resettable traits in subclasses are indicated by having 210 ``can_reset=True`` metadata. This is provided to allow 211 toolkit code to clear caches to prevent memory leaks when 212 working with very large tables. 213 214 Care should be taken when calling this method, as Qt may 215 crash if a QModelIndex is referencing an index that no 216 longer has a reference in a cache. 217 218 For some IndexManagers, particularly for those which are flat 219 or static, reset() may do nothing. 220 """ 221 resettable_traits = self.trait_names(can_reset=True) 222 self.reset_traits(resettable_traits) 223 224 225class IntIndexManager(AbstractIndexManager): 226 """ Efficient IndexManager for non-hierarchical indexes. 227 228 This is a simple index manager for flat data structures. The 229 index values returned are either the Root, or simple integers 230 that indicate the position of the index as a child of the root. 231 232 While it cannot handle nested data, this index manager can 233 operate without having to perform any caching, and so is very 234 efficient. 235 """ 236 237 def create_index(self, parent, row): 238 """ Given a parent index and a row number, create an index. 239 240 This should only ever be called with Root as the parent. 241 242 Parameters 243 ---------- 244 parent : index object 245 The parent index object. 246 row : non-negative int 247 The position of the resulting index in the parent's children. 248 249 Returns 250 ------- 251 index : index object 252 The resulting opaque index object. 253 254 Raises 255 ------ 256 IndexError 257 Negative row values raise an IndexError exception. 258 RuntimeError 259 If the parent is not the Root, a RuntimeError will be raised 260 """ 261 if row < 0: 262 raise IndexError("Row must be non-negative. Got {}".format(row)) 263 if parent != Root: 264 raise RuntimeError( 265 "{} cannot create persistent index value for {}.".format( 266 self.__class__.__name__, 267 (parent, row) 268 ) 269 ) 270 return row 271 272 def get_parent_and_row(self, index): 273 """ Given an index object, return the parent index and row. 274 275 Parameters 276 ---------- 277 index : index object 278 The opaque index object. 279 280 Returns 281 ------- 282 parent : index object 283 The parent index object. 284 row : int 285 The position of the resuling index in the parent's children. 286 287 Raises 288 ------ 289 IndexError 290 If the Root object is passed as the index, this method will 291 raise an IndexError, as it has no parent. 292 """ 293 if index == Root: 294 raise IndexError("Root index has no parent.") 295 return Root, int(index) 296 297 def from_id(self, id): 298 """ Given an integer id, return the corresponding index. 299 300 Parameters 301 ---------- 302 id : int 303 An integer object id value. 304 305 Returns 306 ------- 307 index : index object 308 The persistent index object associated with this id. 309 """ 310 if id == 0: 311 return Root 312 return id - 1 313 314 def id(self, index): 315 """ Given an index, return the corresponding id. 316 317 Parameters 318 ---------- 319 index : index object 320 The persistent index object. 321 322 Returns 323 ------- 324 id : int 325 The associated integer object id value. 326 """ 327 if index == Root: 328 return 0 329 return index + 1 330 331 332class TupleIndexManager(AbstractIndexManager): 333 334 #: A dictionary that maps tuples to the canonical version of the tuple. 335 _cache = Dict(Tuple, Tuple, {Root: Root}, can_reset=True) 336 337 #: A dictionary that maps ids to the canonical version of the tuple. 338 _id_cache = Dict(Int, Tuple, {0: Root}, can_reset=True) 339 340 def create_index(self, parent, row): 341 """ Given a parent index and a row number, create an index. 342 343 Parameters 344 ---------- 345 parent : index object 346 The parent index object. 347 row : non-negative int 348 The position of the resulting index in the parent's children. 349 350 Returns 351 ------- 352 index : index object 353 The resulting opaque index object. 354 355 Raises 356 ------ 357 IndexError 358 Negative row values raise an IndexError exception. 359 """ 360 if row < 0: 361 raise IndexError("Row must be non-negative. Got {}".format(row)) 362 363 index = (parent, row) 364 canonical_index = self._cache.setdefault(index, index) 365 self._id_cache[self.id(canonical_index)] = canonical_index 366 return canonical_index 367 368 def get_parent_and_row(self, index): 369 """ Given an index object, return the parent index and row. 370 371 Parameters 372 ---------- 373 index : index object 374 The opaque index object. 375 376 Returns 377 ------- 378 parent : index object 379 The parent index object. 380 row : int 381 The position of the resuling index in the parent's children. 382 383 Raises 384 ------ 385 IndexError 386 If the Root object is passed as the index, this method will 387 raise an IndexError, as it has no parent. 388 """ 389 if index == Root: 390 raise IndexError("Root index has no parent.") 391 return index 392 393 def from_id(self, id): 394 """ Given an integer id, return the corresponding index. 395 396 Parameters 397 ---------- 398 id : int 399 An integer object id value. 400 401 Returns 402 ------- 403 index : index object 404 The persistent index object associated with this id. 405 """ 406 return self._id_cache[id] 407 408 def id(self, index): 409 """ Given an index, return the corresponding id. 410 411 Parameters 412 ---------- 413 index : index object 414 The persistent index object. 415 416 Returns 417 ------- 418 id : int 419 The associated integer object id value. 420 """ 421 if index == Root: 422 return 0 423 canonical_index = self._cache.setdefault(index, index) 424 return id(canonical_index) 425