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