Aidez-moi mettre en œuvre un tampon rembobinable

Question

C'est là où je suis jusqu'à présent:

je le suivant le cas d'utilisation suivante (comme test JUnit impartial) pour montrer ce que je veux atteindre:

buffer.add(o1); 
assertEquals(1, buffer.size()); 
buffer.mark(); 
buffer.add(o2); 
assertEquals(2, buffer.size()); 
buffer.add(o3); 
assertEquals(3, buffer.size()); 
assertSame(o1, buffer.get()); 
assertSame(o2, buffer.get()); 
assertSame(o3, buffer.get()); 
buffer.rewind(); 
// NOTE: It must be possible to enter the same object multiple times 
//  into the buffer. 
buffer.add(o2); 
assertSame(o2, buffer.get()); 
assertSame(o3, buffer.get()); 
assertSame(o2, buffer.get()); 

J'ai essayé de résoudre ceci en utilisant une liste enveloppée (presque réinventé la roue), la double file d'attente enveloppée (celle-ci était un désordre complet), et ma troisième tentative avec laquelle j'ai juste échoué était une LinkedList enveloppée dans laquelle j'ai tout travaillé sauf rembobiner(). Le pseudocode pour ma dernière tentative était quelque chose comme ceci:

if [backBuffer is empty] 
    [get latest object] 
    increment currentIndex 
    if [markIndex < currentIndex] 
     [put object to backbuffer] 
    return object 
else 
    [get object from backbuffer at index backBufferIndex] 
    increment backBufferIndex 
    return object 

Cela ne fonctionne pas du tout et après quelques modifications que je réussi à obtenir la lecture de travailler jusqu'à ce que rewind() a été appelé alors essentiellement j'ai fait un tas de redondance code pour la troisième fois. Je me sens un peu frustré à ce stade puisque je n'ai jamais été bon avec les algorithmes et c'est pourquoi je viens à vous maintenant: S'il vous plaît aidez-moi à implémenter cela et/ou de me signaler la solution API Java native Je me sens perplexe parce que je n'arrive pas à faire fonctionner ça.

Answer 1

En supposant que vous avez un objet simple FIFO qui implémente add, get et size opérations, vous pouvez mettre en œuvre cette FIFO étendue en pseudocode comme suit:

constructor() 
{ 
    FIFO current = new FIFO(); 
    FIFO alternate = new FIFO(); 
} 

add(Object x) 
{ 
    return current.add(x); 
} 

get() 
{ 
    Object x = current.get(); 
    alternate.add(x); 
    return x; 
} 

size() 
{ 
    return current.size(); 
} 

mark() 
{ 
    alternate = new FIFO(); 
} 

rewind() 
{ 
    while (current.size > 0) 
    { 
     alternate.add(current.get()); 
    } 
    current = alternate; 
    alternate = new FIFO(); 
} 

Je pense que c'est une mise en œuvre assez propre.

Answer 2

Pourriez-vous élaborer un peu plus sur l'exigence. J'étais incapable de comprendre ce que devrait faire le rembobinage. Devrait-il ajouter tous les éléments qui ont été ajoutés depuis mark()?

Answer 3

Avez-vous essayé d'envelopper un des types de collection Java avec quelques paramètres supplémentaires. Par exemple, créez une nouvelle classe qui enveloppe une ArrayList. En plus de la liste de tableau, gardez les variables membres privées

• marque - le dernier indice qui a été marquée pour un retour rapide
• courant - le prochain index retreive sur get()

Vous feriez ajouter également les méthodes suivantes

• get() - Retourne l'objet dans la liste de tableau à un courant d'index et par incréments de courant
• marque() - ensembles marque à la valeur de retour rapide en cours
• () - fixe en cours à la valeur de la marque

Il y a encore quelques détails à régler (comment sont-index non valides traités, ce qui est jeu de marque au départ, etc.) mais cela pourrait vous donner un bon départ.