Strutture dati retroattive: queue
Prerequisiti
- avere una conoscenza generale delle strutture dati, in particolare la queue
Introduzione
Una struttura dati retroattiva permette di effettuare le stesse operazioni della sua variante “normale” (o anche cancellare una operazione), ma ad un tempo arbitrario (quindi anche nel passato).
Le principali ds in grado di lavorare nel passato sono 2: ds persistenti e ds retroattive. Le implementazioni sono molto diverse e anche le caratteristiche:
- ds persistenti: quando eseguono operazioni nel passato creano una copia della struttura dati. Le operazioni nel passato quindi non hanno influenza sul presente.
- ds retroattive: quando eseguono operazioni nel passato modificano direttamente la struttura dati principale. Le operazioni nel passato quindi hanno ripercussioni sul presente.
Le strutture retroattive si dividono in due tipi:
- ds parzialmente retroattive: permettono di effettuare update nel passato ma query solo nel presente
- ds retroattive: permettono di effettuare sia update che query nel passato
Notare che per tempo presente si intende un tempo t=\infty, ovvero quando tutte le operazioni viste fino ad adesso sono già state eseguite.
Per fare un esempio:
supponiamo di avere una queue, inizialmente vuota.
ogni operazione di inserimento è indicata con due valori {valore,tempo}, dove tempo indica in quale istante va effettuata questa operazione.
{1,10} ->all’istante 10 aggiungiamo 1 in fondo alla queue
queue: | 1 | in questo momento il primo valore è 1
{2,5} ->all’istante 5 aggiungiamo 2 in fondo alla queue. Dato che all’istante 5 la coda era vuota, 2 viene inserito come primo valore
queue: | 2 | 1 | in questo momento il primo valore è 2: l’aggiunta di un elemento nel passato ha modificato il presente.
Non è però possibile creare la versione retroattiva di tutte le strutture dati (o almeno non con una complessità tale da renderle utili):
quelle più interessanti sono queue, stack, deque, union-find e priority_queue. In questo post analizzeremo la queue.
Queue parzialente retroattiva
Una queue parzialente retroattiva supporta queste operazioni: aggiungi un elemento in fondo al tempo t, togli il primo elemento al tempo t, query sul primo e sull’ultimo elemento al tempo presente.
Inoltre permette di annullare le operazioni (ovviamente annullare una query non ha senso, mi riferisco alle altre due).
Dato che la queue della stl non è in grado di compiere queste operazioni, bisogna implementare una queue a mano.
Implementiamo una queue come double-linked list (per chi non la conoscesse link), dove gli elementi sono in ordine di tempo in cui vengono aggiunti in fondo alla queue.
Teniamo due puntatori: A alla testa della coda, e B all’elemento successivo alla fine della coda.
- Per togliere il primo elemento, in qualunque istante di tempo, basta spostare A avanti di 1. Per annulare questa operazione basta spostare A indietro di 1.
- Per fare una query basterà semplicemente prendere l’elemento puntato da A o quello precedente a B a seconda della richiesta.
- Ora se dobbiamo aggiungere un valore al tempo t bisogna:
- inserire il valore al suo posto nella lista (per trovare la posizione possiamo tenerci un set di puntatori agli elementi della lista ordinati per il t).
- Se il valore viene inserito prima di A, bisogna spostare A indietro di 1.
- Per annullare l’aggiunta di un valore bisogna eliminare l’elemento e, se era precedente a A, bisogna spostare A avanti di 1.
B deve sempre puntare all’elemento successivo alla fine della coda (non va mai spostato).
Spostare avanti o indietro un puntatore significa moverlo all’elemento successivo/precedente.
Dato che in una double-linked list inserire/eliminare un elemento impiega tempo costante, la queue parzialmente retroattiva effettua query in \mathcal O(1) e update in \mathcal O(\log N).
Per i dettagli dell’implementazione lascio il codice (notare che si presume che le operazioni siano sempre fattibili, ad esempio non viene mai chiesto di annullare una operazione che non è mai stata eseguita).
#include <bits/stdc++.h>
using namespace std;
class partial_retroactive_queue{
private:
struct node{// elementi della double linked list
node *prox=NULL;
node *prec=NULL;//puntatori ai valori successivi e recedenti della lista
int val;// valore del'elemento
int t;// istante in cui è stato inserito l'elemento
};
node inizio,fine;// nodi di inizio e fine della lista
node* A;// puntatore al primo elemento nella queue
node* B;// puntatore all' ultimo elemento della queue
set<pair<int,node*> > k;//il primo valore indica il tempo, il secondo è un puntatore al nodo aggiunto in quell'istante
node* get_pos(int t){//ritorna un puntatore al nodo da eliminare
auto pos=k.lower_bound({t,NULL});// elemento del set relativo al nodo da togliere
node* da_rimuovere=pos->second;// mi salvo il puntatore al nodo da rimuovere
k.erase(pos);// rimuovo l'elemento da togliere
return da_rimuovere;// ritorno il puntatore al nodo da eliminare
}
node* get_pos_prec(int t,node* nuovo){//ritorna un puntatore al nodo subito prima di quello nuovo da inserire
k.insert({t,nuovo});// inserisco il nuovo elemento
auto pos=k.find({t,nuovo});// prendo la posizione dell'elemento appena inserito
pos--;// trovo l'elemento subito prima dell'elemento appena inserito
return pos->second;//ritorno il puntatore al nodo subito prima di quello nuovo da aggiungere
}
public:
//PER PRIMA COSA BISOGNA SEMPRE CHIAMARE LA FUNZIONE INIZIALIZZA!!!!
void inizializza(){// crea la lista con i nodi di inizio e fine;
fine.t=1e9;
inizio.t=-1;
inizio.val=1;
fine.val=1000;
inizio.prox=&fine;
fine.prec=&inizio;
A=&fine;
B=&fine;
k.insert({-1,&inizio});
k.insert({1e9,&fine});
}
int query_primo(){//ritorna il valore del primo elemento della queue
return A->val;
}
int query_ultimo(){//ritorna il valore dell'ultimo elemento della queue
return B->prec->val;
}
void aggiungi_alla_coda(int val,int t){//aggiunge il valore val al tempo t
node* nuovo=new node();//crea il nuovo nodo
nuovo->val=val;
nuovo->t=t;
node* prima=get_pos_prec(t,nuovo);//prima è l'elemento dopo cui va inserito quello nuovo
node* dopo=prima->prox;//l'elemento nuovo va inserito tra prima e dopo
prima->prox=nuovo;
dopo->prec=nuovo;
nuovo->prec=prima;
nuovo->prox=dopo;
if(t<(A->t))A=A->prec;// se il valore viene inserito prima di A, sposto A indietro di 1;
}
void annulla_aggiungi_alla_coda(int val,int t){
node* curr=get_pos(t);//puntatore al nodo da eliminare
node* prima=curr->prec;
node* dopo=curr->prox;
prima->prox=dopo;
dopo->prec=prima;
delete(curr);
if(t<=(A->t))A=A->prox;// se il valore si trovava prima di A, sposto A avanti di 1;
}
void togli_primo_elemento(){// sposto A avanti di 1
A=A->prox;
}
void annulla_togli_primo_elemento(){// sposto A indietro di 1
A=A->prec;
}
void stampa(){// stampa la queue
cout<<"queue : ";
node *p=A;
while(p!=B){
cout<<p->val<<" ";
p=p->prox;
}
cout<<endl;
}
};
Queue retroattiva
Per poter rispondere a query nel passato, è necessario conoscere, per ogni valore di tempo t, quante valori sono stati aggiunti e quanti rimossi dalla queue fino a quel momento.
Per ottenere una complessità logaritmica sia nell’inserimento di un nuovo valore che in una query, la struttura dati necessaria è un albero binario bilanciato.
Per evitare lunghe implementazioni possiamo usare l’ordered set, ovvero un set che permette di conoscere un elemento in qualunque posizione in tempo logaritmico.
Questa struttura dati per fortuna è gia implementata (per chi non la conoscesse link, link).
Abbiamo bisogno di 2 ordered set:
- uno che chiamerò aggiunti, che contiene, ordinati per t, i valori che aggiungo in fondo alla coda
- uno che chiamerò tolti, che contienei valori di t in cui viene tolto il primo elemento
Le operazioni da svolgere sono le seguenti:
- Se dobbiamo aggiungere/rimuovere un elemento dalla coda basta semplicemente aggiungere l’elemento dall’ordered set corrispondente.
Analogamente per annullare una di queste operazioni basta rimuovere l’elemento dall’ordered set - Per fare una query al primo elemento al tempo t, dobbiamo:
- contare quanti elementi vengono tolti dall’inizio della queue prima del tempo t, chiamiamo questo valore K
- ora la nostra soluzione è il (K+1)-esimo valore che viene aggiunto in fondo alla coda
- Per fare una query all’ultimo elemento al tempo t, dobbiamo:
- contare quanti elementi vengono aggiunti alla queue prima del tempo t+1, chiamiamo questo valore K
- ora la nostra soluzione è il K-esimo valore che viene aggiunto in fondo alla coda
La complessità è \mathcal O(\log N) sia per query che per update.
Il mio codice (sempre assumendo che tutte le operazioni siano possibili):
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set_1 tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_set_2 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
class queue_retroattiva{
public:
ordered_set_1 aggiunti;// valori aggiunti alla queue ordinati per tempo
ordered_set_2 tolti;// momenti in cui tolgo il primo valore dalla coda
int query_primo(int t){//ritorna il valore del primo elemento della queue al tempo t
int K=tolti.order_of_key(t+1);// quante volte tolgo il primo elemento prima dell'istante t+1
return (*aggiunti.find_by_order(K)).second;// ritorna il (K+1)-esimo valore aggiunto alla coda (presupponendo che la coda non sia vouta all'istante t)
}
int query_ultimo(int t){//ritorna il valore dell'ultimo elemento della queue al tempo t
int K=aggiunti.order_of_key({t,2e9});// elementi aggiunti prima dell'istante t+1
return (*aggiunti.find_by_order(K-1)).second;// ultimo elemento aggiunto prima dell'istante t+1
}
void aggiungi_alla_coda(int val,int t){//aggiunge il valore val al tempo t
aggiunti.insert({t,val});
}
void annulla_aggiungi_alla_coda(int val,int t){// rimuove il valore val aggiunto al tempo t
aggiunti.erase({t,val});
}
void togli_primo_elemento(int t){// aggiunte il tempo t agli istanti in cui rimuovo il primo elemento
tolti.insert(t);
}
void annulla_togli_primo_elemento(int t){// rimuove il tempo t dagli istanti in cui rimuovo il primo elemento
tolti.erase(t);
}
void stampa(){// stampa la queue in questo istante
cout<<"queue : ";
for(int i=tolti.size();i<aggiunti.size();i++){
cout<<(*aggiunti.find_by_order(i)).second<<" ";
}
cout<<endl;
}
};