Sto provando a costruire una struttura dati generica che deve contenere chiavi e valori e, allo stesso tempo, tenere traccia dell'indice in cui le chiavi e i valori sono stati inseriti come un arraylist proprio in una complessità di O (log n) o Di meno.È possibile creare una mappa con proprietà ArrayList con log (n) complessità?
Ho provato a risolvere una soluzione a questo problema e ho creato varie TreeMaps con Integer - index e valuse e vise-versa, e lo stesso con le chiavi.
Giusto per rendere più chiaro, l'indice simboleggia l'ordine di inserimento da parte dell'utente. quindi se avessi 3 elementi allora il loro indice è 0 1 2 e se l'elemento 0 è stato cancellato allora ho bisogno di premere 1 a 0 e 2 a 1 e un nuovo elemento sarebbe aggiunto con l'indice 2.
Il mio problema è quando Rimuovo una chiave e il suo valore, se voglio inserire la chiave successiva e il valore nell'indice corretto devo assicurarmi che tutti i vecchi siano stati ripristinati di 1. Non so come farlo e non cadere in O (n) complessità.
Il mio obiettivo è utilizzare le strutture dati esistenti e mescolarle per ottenere questo risultato, per favore date un'occhiata ai metodi che ho implementato come ho bisogno di quelli.
Aggiungo il mio codice per riferimento, qualsiasi aiuto sarebbe molto apprezzato.
Grazie
Tom
import java.util.Collection;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map;
public class SuperStruct<K,V>
{
private Map<K,V> mInternalKeyToValueMap;//all the keys and their values
private Map<Integer,V> mIndexToValueMap;//index's for values according to the entrance order to
private Map<V,Integer> mValueToIndexMap;//values and their index's
private Map<Integer,K> mIndexToKeyMap;//index's and their keys according to entrance order
private Map<K,Integer> mKeyToIndexMap;//keys and their index's
private int mNextIndex;//index for the data structure according to the order data was received by user
public SuperStruct(){
mInternalKeyToValueMap = new TreeMap<K,V>();
mIndexToValueMap = new TreeMap<Integer,V>();
mValueToIndexMap = new TreeMap <V,Integer>();
mIndexToKeyMap = new TreeMap <Integer, K>();
mKeyToIndexMap = new TreeMap <K,Integer>();
}
public boolean containsKey(Object key) {
boolean containable = mInternalKeyToValueMap.containsKey(key);
return containable;
}
public boolean containsValue(Object value) {
boolean containable = mValueToIndexMap.containsKey(value);
return containable;
}
public V get(Object key) {
if(mInternalKeyToValueMap.containsKey(key)){
V value = mInternalKeyToValueMap.get(key);
return value;
}
return null;
}
public Collection<K> keySet() {
return mInternalKeyToValueMap.keySet();
}
/**
* This method is putting the key and the value in the main TreeMap "mInternalKeyToValueMap", while on the mean time updating 4 other TreeMaps
* with data regarding to the index in which data was received from the user.
* all in all this method runs in complexity of 6*(O(log n)) that sums down to O(log n) cause constants don't calculate over the whole
* Complexity calculation
* In case that a key already had a mapping to it and we overwrite the value we will run in complexity of 11*(O(log n)) which still sums down to O(log n)
* cause constants don't calculate over the whole
*/
public V put(K key, V value) {
if(mValueToIndexMap.containsKey(value))//preventing duplications of value
return value;
if(mInternalKeyToValueMap.containsKey(key)){//when a key already exist in system and we want to overwrite its value
int indexToDelete = mKeyToIndexMap.get(key);//we get the index of the value we over-write
V value1 = mIndexToValueMap.get(indexToDelete);//using this index we get the value
mValueToIndexMap.remove(value1);//we remove the value and its index
mIndexToValueMap.remove(indexToDelete);//we remove the index and its value
}
mInternalKeyToValueMap.put(key, value);//putting the new value for the key in the main TreeMap
mValueToIndexMap.put(value, mNextIndex);//populating the TreeMap of values and their index's - the order we received them from the user
mIndexToValueMap.put(mNextIndex, value);//This TreeMap holds the index's for each value according to the order of insertion by user
mIndexToKeyMap.put(mNextIndex, key);//This TreeMap holds the index's for each key according to the order of insertion by user
mKeyToIndexMap.put(key,mNextIndex);//populating the TreeMap of keys and their index's - the order we received them from the user
++mNextIndex;//advancing the index which mark the insertion order of arguments to structure
return null;
}
public V remove(Object key) {
if(mInternalKeyToValueMap.containsKey(key)==true && (mInternalKeyToValueMap.get(key)!=null))
{
V value = mInternalKeyToValueMap.get(key);
mInternalKeyToValueMap.remove(key);//removing map for the value
int mIndexToRemoveValue = mValueToIndexMap.get(value);//getting the right index to remove the value
mIndexToValueMap.remove(mIndexToRemoveValue);//vacating the value for this index
mIndexToKeyMap.remove(mIndexToRemoveValue);//vacating the key for this index
mKeyToIndexMap.remove(key);//removing a key and index in the keyToIndex Map
mValueToIndexMap.remove(value);//removing a key and index in the ValueToIndex Map
return value;
}
return null;
}
public Collection<V> values() {
return mInternalKeyToValueMap.values();
}
public Collection<V> getStrcutureSorted(){
return mValueToIndexMap.keySet();
}
public V getValueByIndex(int index){//return the index in which the value sits in, if not present null
V value = mIndexToValueMap.get(index);
return value;
}
public Integer getIndexByKey(K key){
Integer returnable = mKeyToIndexMap.get(key);
if(returnable == null)
return -1;
return returnable;
}
public K getKeyByIndex(int index){
return mIndexToKeyMap.get(index);
}
}
https://stackoverflow.com/questions/44170832/access-tree-with-ordinal-index –