Naviguer manuellement avec un curseur dans des listes imbriquées en fournissant uniquement les commandes "left()" et "right()" ?

Question

Bien que j'écrive en python, je pense que le concept abstrait est plus intéressant pour moi et pour les autres. Donc pseudocode s'il vous plaît si vous aimez :)

J'ai une liste avec des articles d'un de mes cours. Faisons-le avec des chaînes de caractères et des nombres, ça n'a pas vraiment d'importance. Elle est imbriquée à n'importe quelle profondeur. (Ce n'est pas vraiment une liste mais une classe conteneur qui est basée sur une liste).

Exemple : [1, 2, 3, ['a', 'b', 'c'] 4 ['d', 'e', [100, 200, 300]] 5, ['a', 'b', 'c'], 6]

Notez que les deux ['a', 'b', 'c'] sont en réalité le même conteneur. Si vous en modifiez un, vous modifiez l'autre. Les conteneurs et les éléments peuvent être édités, les éléments insérés et, plus important encore, les conteneurs peuvent être utilisés plusieurs fois. Pour éviter la redondance, il n'est pas possible d'aplatir la liste (je pense !) car vous perdez la possibilité d'insérer des éléments dans un conteneur et ils apparaissent automatiquement dans tous les autres conteneurs.

Le problème : Pour le frontal (juste une ligne de commande avec le module python "cmd"), je veux naviguer dans cette structure avec un curseur qui pointe toujours sur l'élément en cours afin qu'il puisse être lu ou modifié. Le curseur peut aller à gauche et à droite (point de vue de l'utilisateur) et doit se comporter comme si la liste n'était pas une liste imbriquée mais une liste plate.

Pour un humain, c'est très facile à faire. Il suffit de faire comme si les sous-listes n'existaient pas dans la liste ci-dessus et d'aller de gauche à droite et inversement.

Par exemple, si vous êtes à la position "3" dans la liste ci-dessus et que vous allez à droite, vous obtenez "a" comme prochain élément, puis "b", "c", puis "4", etc. Ou si vous allez à droite à partir du "300", vous obtenez le "5" suivant.

Et à l'envers : Si vous allez à gauche de "6", le prochain est "C". Si vous allez à gauche de "5", c'est "300".

Alors comment faire en principe ? J'ai une approche ici mais elle est erronée et la question est déjà si longue que je crains que la plupart des gens ne la lisent pas :(. Je peux la poster plus tard.

P.S. Même si c'est difficile de résister : La réponse à cette question n'est pas "Pourquoi voulez-vous faire cela, pourquoi organisez-vous vos données de cette façon, pourquoi n'avez-vous pas [aplatir la liste| quelque chose sorti de mon imagination] d'abord ? Le problème est exactement ce que j'ai décrit ici, rien d'autre. Les données sont structurées par la nature du problème de cette façon.

Answer 1

Une solution serait de stocker les informations relatives à l'index et/ou à la profondeur et de les utiliser pour parcourir la liste imbriquée. Mais cela semble être une solution qui nécessiterait beaucoup de bifurcations compliquées - tester les fins de listes, etc. Au lieu de cela, j'ai trouvé un compromis. Au lieu d'aplatir la liste de listes, j'ai créé un générateur qui crée une liste plate d'indices dans la liste de listes :

def enumerate_nested(nested, indices):
    for i, item in enumerate(nested):
        if isinstance(item, collections.Iterable) and not isinstance(item, basestring):
            for new_indices in enumerate_nested(item, indices + (i,)):
                yield new_indices
        else:
            yield indices + (i,)

Ensuite, une fonction simple qui extrait un élément le plus intérieur de la liste des listes en fonction d'un tuple d'index :

def tuple_index(nested_list, index_tuple):
    for i in index_tuple:
        nested_list = nested_list[i]
    return nested_list

Il ne vous reste plus qu'à parcourir la liste des index plats, de la manière qui vous convient.

>>> indices = list(enumerate_nested(l, tuple()))
>>> print l
[1, 2, 3, ['a', 'b', 'c'], 4, ['d', 'e', [100, 200, 300]], 5, ['a', 'b', 'c'], 6]
>>> for i in indices:
...     print tuple_index(l, i),
... 
1 2 3 a b c 4 d e 100 200 300 5 a b c 6

---

Puisque cette réponse a été acceptée pour la solution basée sur la pile que j'ai postée sur ideone dans les commentaires, et puisqu'il est préférable de ne pas utiliser de pastebins externes pour le code de la réponse, veuillez noter que cette réponse contient également ma solution basée sur la pile.

Answer 2

Je laisserais le curseur avoir une pile des indices des tableaux.

Exemples :

[1, 2, 3, ['a', 'b', 'c'], 4 ]

Si le curseur se trouve sur le 1 (à l'index 0), la position du curseur est [0].

Si le curseur est sur le 2 (à l'index 1), la position du curseur est [1].

Si le curseur se trouve sur le 'a' (à l'indice 3 au niveau le plus élevé et à l'indice 0 au deuxième niveau), la position du curseur sera [3, 0].

Si le curseur se trouve sur le "b" (à l'indice 3 au niveau le plus élevé et à l'indice 1 au deuxième niveau), la position du curseur sera [3, 1].

etc.

Pour déplacer le curseur vers la droite, il suffit d'augmenter l'indice le plus à droite de la position. Ainsi, lorsque vous passez de 'b' à 'c', l'indice passe de [3, 1] à [3, 2]. Si l'indice devient alors hors de portée, vous sortez la valeur la plus à droite de la pile d'indices et vous augmentez la valeur la plus à droite. Ainsi, si vous passez de 'c' à 4, vous passez de [3, 2] à [4].

Lorsque vous vous déplacez, si vous rencontrez une position avec un tableau imbriqué, vous l'entrez. Ainsi, si vous allez à droite à partir de 3 (à l'indice [2]), vous entrez dans le premier élément du tableau ['a', 'b', 'c'], qui est à l'indice [3, 0].

Un déplacement vers la gauche ne ferait que l'inverse d'un déplacement vers la droite.

Answer 3

Essentiellement, je baserais ma propre solution sur la récursion. J'étendrais la classe conteneur avec ce qui suit :

1. cursor_position - Propriété qui stocke l'index de l'élément mis en évidence (ou l'élément qui contient l'élément qui contient l'élément mis en évidence, ou tout niveau de récurrence au-delà).
2. repr_with_cursor - Cette méthode doit renvoyer une version imprimable du contenu du conteneur, en mettant déjà en évidence l'élément actuellement sélectionné.
3. mov_right - Cette méthode doit être invoquée lorsque le curseur se déplace vers la droite. Retourne le nouvel indice du curseur dans l'élément ou None si le curseur tombe "à l'extérieur" du conteneur actuel (si vous passez le dernier élément du conteneur).
4. mov_left - Idem, mais vers la gauche.

La récursion devrait fonctionner de la manière suivante : pour chaque méthode, en fonction de la valeur de l'option type de la méthode mise en évidence, vous devriez avoir deux comportements différents :

• si le curseur est sur un conteneur il doit invoquer la méthode du conteneur "pointé".
• si le curseur est sur un sans conteneur il devrait être aussi performant que le "vrai".

EDIT J'avais une demi-heure de libre et j'ai donc créé une classe d'exemple qui met en œuvre mon idée. Elle n'est pas complète (par exemple, elle ne gère pas bien le fait d'atteindre l'une des extrémités du plus grand conteneur, et nécessite que chaque instance de la classe ne soit utilisée qu'une seule fois dans la plus grande séquence) mais elle fonctionne suffisamment pour démontrer le concept. Je le répète avant que les gens ne fassent des commentaires à ce sujet : il s'agit d'un code de preuve de concept, il n'est en aucun cas prêt à être utilisé !

#!/usr/bin/env python
# -*- coding: utf-8  -*-

class C(list):

    def __init__(self, *args):
        self.cursor_position = None
        super(C, self).__init__(*args)

    def _pointed(self):
        '''Return currently pointed item'''
        if self.cursor_position == None:
            return None
        return self[self.cursor_position]

    def _recursable(self):
        '''Return True if pointed item is a container [C class]'''
        return (type(self._pointed()) == C)

    def init_pointer(self, end):
        '''
        Recursively set the pointers of containers in a way to point to the
        first non-container item of the nested hierarchy.
        '''
        assert end in ('left', 'right')
        val = 0 if end == 'left' else len(self)-1
        self.cursor_position = val
        if self._recursable():
            self.pointed._init_pointer(end)

    def repr_with_cursor(self):
        '''
        Return a representation of the container with highlighted item.
        '''
        composite = '['
        for i, elem in enumerate(self):
            if type(elem) == C:
                composite += elem.repr_with_cursor()
            else:
                if i != self.cursor_position:
                    composite += str(elem)
                else:
                    composite += '**' + str(elem) + '**'
            if i != len(self)-1:
                composite += ', '
        composite += ']'
        return composite

    def mov_right(self):
        '''
        Move pointer to the right.
        '''
        if self._recursable():
            if self._pointed().mov_right() == -1:
                if self.cursor_position != len(self)-1:
                    self.cursor_position += 1
        else:
            if self.cursor_position != len(self)-1:
                self.cursor_position += 1
                if self._recursable():
                    self._pointed().init_pointer('left')
            else:
                self.cursor_position = None
                return -1

    def mov_left(self):
        '''
        Move pointer to the left.
        '''
        if self._recursable():
            if self._pointed().mov_left() == -1:
                if self.cursor_position != 0:
                    self.cursor_position -= 1
        else:
            if self.cursor_position != 0:
                self.cursor_position -= 1
                if self._recursable():
                    self._pointed().init_pointer('right')
            else:
                self.cursor_position = None
                return -1

Un simple test script :

# Create the nested structure
LevelOne = C(('I say',))
LevelTwo = C(('Hello', 'Bye', 'Ciao'))
LevelOne.append(LevelTwo)
LevelOne.append('!')
LevelOne.init_pointer('left')
# The container's content can be seen as both a regualar list or a
# special container.
print(LevelOne)
print(LevelOne.repr_with_cursor())
print('---')
# Showcase the effect of moving the cursor to right
for i in range(5):
    print(LevelOne.repr_with_cursor())
    LevelOne.mov_right()
print('---')
# Showcase the effect of moving the cursor to left
LevelOne.init_pointer('right')
for i in range(5):
    print(LevelOne.repr_with_cursor())
    LevelOne.mov_left()

Il sort :

['I say', ['Hello', 'Bye', 'Ciao'], '!']
[**I say**, [Hello, Bye, Ciao], !]
---
[**I say**, [Hello, Bye, Ciao], !]
[I say, [**Hello**, Bye, Ciao], !]
[I say, [Hello, **Bye**, Ciao], !]
[I say, [Hello, Bye, **Ciao**], !]
[I say, [Hello, Bye, Ciao], **!**]
---
[I say, [Hello, Bye, Ciao], **!**]
[I say, [Hello, Bye, **Ciao**], !]
[I say, [Hello, **Bye**, Ciao], !]
[I say, [**Hello**, Bye, Ciao], !]
[**I say**, [Hello, Bye, Ciao], !]

Un problème amusant ! Ma question OS préférée du jour ! :)

Answer 4

Bien que j'aime l'idée d'aplatir la liste d'index, cela rend impossible la modification de la longueur de toute sous-liste tout en itérant dans la liste imbriquée. Si ce n'est pas la fonctionnalité dont vous avez besoin, je m'en contenterais.

Sinon, j'implémenterais également un pointeur dans la liste sous la forme d'un tuple d'indices, et je m'appuierais sur la récursion. Pour vous aider à démarrer, voici une classe qui implémente right() et la lecture de la valeur du pointeur via deref() . (J'utilise None pour représenter un pointeur au-delà de la fin d'une liste). Je laisserai comme un exercice la façon d'implémenter left() et l'affectation aux éléments. Et vous devrez décider du comportement que vous souhaitez avoir si vous remplacez l'élément que vous pointez actuellement par une autre liste. Bonne chance !

def islist(seq):
    return isinstance(seq, (list, tuple))

class nav:
    def __init__(self, seq):
        self.seq = seq
        self.ptr = self.first()
    def __nonzero__(self):
        return bool(self.ptr)
    def right(self):
        """Advance the nav to the next position"""
        self.ptr = self.next()
    def first(self, seq=None):
        """pointer to the first element of a (possibly empty) sequence"""
        if seq is None: seq = self.seq
        if not islist(seq): return ()
        return (0,) + self.first(seq[0]) if seq else None
    def next(self, ptr=None, seq=None):
        """Return the next pointer"""
        if ptr is None: ptr = self.ptr
        if seq is None: seq = self.seq
        subnext = None if len(ptr) == 1 else self.next(ptr[1:], seq[ptr[0]])
        if subnext is not None: return (ptr[0],) + subnext
        ind = ptr[0]+1
        return None if ind >= len(seq) else (ind,) + self.first(seq[ind])
    def deref(self, ptr=None, seq=None):
        """Dereference given pointer"""
        if ptr is None: ptr = self.ptr
        if seq is None: seq = self.seq
        if not ptr: return None
        subseq = seq[ptr[0]]
        return subseq if len(ptr) == 1 else self.deref(ptr[1:], subseq)

abc = ['a', 'b', 'c']
a = [1, 2, 3, abc, 4, ['d', 'e', [100, 200, 300]], 5, abc, 6]
n = nav(a)

while n:
    print n.ptr, n.deref()
    n.right()