public interface Sequence<E> extends PositionList<E>, IndexList<E>
{
public Position<E> atIndex(int i) throws BoundaryViolationException;
public int indexOf(Position<E> p) throws InvalidPositionException;
public E getFirst() throws EmptySequenceException;
public E getLast() throws EmptySequenceException;
public E removeFirst() throws EmptySequenceException;
public E removeLast() throws EmptySequenceException;
}
public class NodeSequence<E> extends NodePositionList<E> implements Sequence<E>
{
public NodeSequence()
{
super();
}
protected void checkIndex(int index,int n) throws BoundaryViolationException
{
if (index < 0 || index >= n)
throw new BoundaryViolationException ("Indice " + index + " non valido");
}
public E get(int i) throws IndexOutOfBoundsException
{
checkIndex(i, size());
return (atIndex(i).element());
}
public E set(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i, size());
return set(atIndex(i), e);
}
public void add(int i, E e) throws IndexOutOfBoundsException
{
if (i==size())
{
addLast(e);
}
else
{
addBefore(atIndex(i), e);
}
}
public E remove(int i) throws IndexOutOfBoundsException
{
checkIndex(i, size());
return remove(atIndex(i));
}
public E getFirst() throws EmptySequenceException
{
return get(indexOf(first()));
}
public E getLast() throws EmptySequenceException
{
return get(indexOf(last()));
}
public E removeFirst() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return remove(indexOf(first())); }
public E removeLast() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return remove(indexOf(last()));
}
public Position<E> atIndex(int i) throws BoundaryViolationException
{
checkIndex(i,size());
DNode<E> node;
if (i <= size()/2)
{
node = (DNode<E>) first();
for (int j=0; j < i; j++)
node = node.getNext();
}
else
{
node = (DNode<E>) last();
for (int j=1; j < size()-i; j++)
node = node.getPrev();
}
return node;
}
public int indexOf(Position<E> p) throws InvalidPositionException
{
DNode<E> nodo = checkPosition(p);
DNode<E> aNode = (DNode<E>) first();
int index = 0;
while(aNode != nodo)
{
index++;
aNode = aNode.getNext();
}
return index;
}
public String toString()
{
String stringa = super.toString();
stringa = (String) stringa.subSequence(stringa.indexOf(" "), stringa.length());
stringa = "NodeSequence"+ stringa;
return stringa;
}
public void makeFirst(Position<E> p)
{
DNode<E> node = checkPosition(p);
node.getPrev().setNext(node.getNext());
node.getNext().setPrev(node.getPrev());
node.setNext(header.getNext());
node.setPrev(header);
node.getNext().setPrev(node);
header.setNext(node);
}
}
public class ArraySequence<E> implements Sequence<E>, Iterable<E>
{
private final static int CAPACITY = 1024;
private ArrayPosition<E> array[];
private int size, capacity, f;
//costruttori
public ArraySequence()
{
this(CAPACITY);
}
@SuppressWarnings("unchecked")
public ArraySequence(int cap)
{
capacity = cap;
array = new ArrayPosition[capacity];
size = f = 0;
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size==0);
}
public Position<E> first() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return array[map(0)];
}
public E getFirst() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return first().element();
}
public Position<E> last() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return array[map(size-1)];
}
public E getLast() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return last().element();
}
public E get(int i) throws IndexOutOfBoundsException
{
checkIndex(i, size);
return array[map(i)].element();
}
private void checkIndex(int i, int n) throws IndexOutOfBoundsException
{
if (i<0 || i>n)
throw new IndexOutOfBoundsException();
}
private ArrayPosition<E> checkPosition (Position<E> p) throws InvalidPositionException
{
if (p == null) throw new InvalidPositionException("null position");
try
{
ArrayPosition<E> temp = (ArrayPosition<E>) p;
boolean flag = false;
for(int i=0; i<size; i++)
{
if (array[map(i)].equals(temp))
flag = true;
}
if (flag)
return temp;
else
throw new InvalidPositionException("This element does not belog to this sequence");
}
catch (ClassCastException e)
{
throw new InvalidPositionException("not an ArrayPosition");
}
}
public Position<E> prev(Position<E> p) throws InvalidPositionException, BoundaryViolationException
{
ArrayPosition<E> tmp = checkPosition(p);
if(tmp.equals(first()))
if(tmp.equals(first()))
throw new InvalidPositionException("No Positions before the first");
int index = tmp.getIndex()-1;
return array[map(index)];
}
public Position<E> next(Position<E> p) throws InvalidPositionException, BoundaryViolationException
{
ArrayPosition<E> tmp = checkPosition(p);
if(tmp.equals(last()))
throw new InvalidPositionException("No Positions after the last");
int index = tmp.getIndex()+1;
return array[map(index)];
}
public void add(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i,size);
if (size() == capacity)
{
@SuppressWarnings("unchecked")
ArrayPosition<E> tmp[] = new ArrayPosition[capacity*2];
for(int j=0; j<capacity;j++)
tmp[j] = array[map(j)];
array = tmp;
capacity *=2;
f=capacity-1;
}
ArrayPosition<E> newElem = new ArrayPosition<E>(i,e);
if(i==0)
{
array[f]=newElem;
f=(f-1+capacity)%capacity;
}
if(i>0)
{
for(int j= size-1; j>= i; j--)
{
array[map(j+1)] = array[map(j)];
array[map(j+1)].setIndex(j+1);
}
array[map(i)] = newElem;
}
size++;
//aggiorno gli indici
for(int j=size()-1; j >= i; j--)
{
ArrayPosition<E> tmp = array[map(j)];
tmp.setIndex(j);
}
}
public Position<E> addBefore(Position<E> p, E e) throws InvalidPositionException
{
ArrayPosition<E> tmp = checkPosition(p);
int i = indexOf(tmp);
add(i,e);
return prev(tmp);
}
public Position<E> addAfter (Position<E> p, E e) throws InvalidPositionException
{
ArrayPosition<E> tmp = checkPosition(p);
int i = indexOf(tmp)+1;
add(i, e);
return next(tmp);
}
public void addFirst(E e)
{
add(0,e);
}
public void addLast(E e)
{
add(size,e);
}
public E remove(Position<E> p) throws InvalidPositionException
{
checkPosition(p);
return remove(indexOf(p));
}
public E remove(int i) throws IndexOutOfBoundsException
{
checkIndex(i,size);
E e = array[map(i)].element();
if(i==0)
f=(f+1)%capacity;
else
for(int j = i; j<size-1; j++)
array[map(j)] = array[map(j+1)];
size--;
for(int j=size()-1; j >= i; j--)
{
ArrayPosition<E> tmp = array[map(j)];
tmp.setIndex(j);
}
if (size<capacity/3)
{
@SuppressWarnings("unchecked")
ArrayPosition<E> nuovoArray[] = new ArrayPosition[capacity/2];
for(int j=0; j<size; j++)
nuovoArray[j] = array[map(j)];
array = nuovoArray;
capacity /= 2;
f = capacity-1;
}
return e;
}
public E removeFirst() throws EmptySequenceException
{
return remove(0);
}
public E removeLast() throws EmptySequenceException
{
return remove(size-1);
}
public E set(Position<E> p, E e) throws InvalidPositionException
{
ArrayPosition<E> tmp = checkPosition(p);
return set(indexOf(tmp),e);
}
public E set(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i,size);
ArrayPosition<E> newEl = new ArrayPosition<E>(i,e);
array[map(i)] = newEl;
return e;
}
public Position<E> atIndex(int i) throws BoundaryViolationException
{
try
{
checkIndex(i, size());
}
catch(IndexOutOfBoundsException e)
{
throw new BoundaryViolationException("atIndex non possibile.");
}
return array[map(i)];
}
public int indexOf(Position<E> p) throws InvalidPositionException
{
ArrayPosition<E> tmp = checkPosition(p);
return tmp.getIndex();
}
public int map(int i)
{
return(i+f+1)%capacity;
}
public Iterator<E> iterator()
{
return new ElementIterator<E>(this);
}
public Iterable<Position<E>> positions()
{
PositionList<Position<E>> tmp = new ArraySequence<Position<E>>();
for(int i=0; i<size; i++)
tmp.addLast(array[map(i)]);
return tmp;
}
public String toString()
{
String retVal = "[ ";
for(int i=0; i<size(); i++)
{
retVal += array[map(i)] +" ";
}
retVal += "] size:"+size+" capacity:"+capacity;
return retVal;
}
}
public class ArrayIndexSequence<E> implements Sequence<E>
{
private ArrayIndexList<ArrayPosition<E>> array;
public void makeFirst(Position<E> p)
{
checkPosition(p);
E tmp = remove(p);
addFirst(tmp);
}
public ArrayIndexSequence()
{
array = new ArrayIndexList<ArrayPosition<E>>();
}
public ArrayIndexSequence(int cap)
{
array = new ArrayIndexList<ArrayPosition<E>>(cap);
}
public int size()
{
return array.size();
}
public boolean isEmpty()
{
return array.isEmpty();
}
public Position<E> first() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return array.get(0);
}
public Position<E> last() throws EmptySequenceException
{
if (isEmpty())
throw new EmptySequenceException();
return array.get(array.size()-1);
}
public E getFirst() throws EmptySequenceException
{
return first().element();
}
public E getLast() throws EmptySequenceException
{
return last().element();
}
public Position<E> prev(Position<E> p) throws InvalidPositionException, BoundaryViolationException
{
ArrayPosition<E> tmp = checkPosition(p);
return array.get(indexOf(tmp)-1);
}
public Position<E> next(Position<E> p) throws InvalidPositionException,BoundaryViolationException
{
ArrayPosition<E> tmp = checkPosition(p);
return array.get(indexOf(tmp)+1);
}
public void add(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i, array.size());
ArrayPosition<E> newElement = new ArrayPosition<E>(i,e);
array.add(i,newElement);
//aggiorno gli indici
for(int j=array.size()-1; j >= i; j--)
array.get(j).setIndex(j);
}
public Position<E> addBefore(Position<E> p, E e) throws InvalidPositionException
{
ArrayPosition<E> tmp = checkPosition(p);
int i = indexOf(tmp);
add(i,e);
return array.get(i);
}
public Position<E> addAfter(Position<E> p, E e) throws InvalidPositionException
{
ArrayPosition<E> tmp = checkPosition(p);
int i = indexOf(tmp)+1;
add(i, e);
return array.get(i);
}
public void addFirst(E e)
{
add(0, e);
}
public void addLast(E e)
{
add(array.size(), e);
}
public E set(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i, array.size());
ArrayPosition<E> newElement = new ArrayPosition<E>(i,e);
array.set(i,newElement).element();
return e;
}
public E set(Position<E> p, E e) throws InvalidPositionException
{
ArrayPosition<E> newElement = checkPosition(p);
newElement.setElement(e);
return array.set(indexOf(p), newElement).element();
}
public E get(int i) throws IndexOutOfBoundsException
{
checkIndex(i, array.size());
return array.get(i).element();
}
public E remove(int i) throws IndexOutOfBoundsException
{
if (isEmpty())
throw new EmptySequenceException();
checkIndex(i, array.size());
E tmp = array.remove(i).element();
//aggiorno gli indici
for(int j=array.size()-1; j >= i; j--)
array.get(j).setIndex(j);
return tmp;
}
public E remove(Position<E> p) throws InvalidPositionException
{
E tmp =remove(indexOf(p));
return tmp;
}
public E removeFirst() throws EmptySequenceException
{
E tmp = remove(0);
return tmp;
}
public E removeLast() throws EmptySequenceException
{
E tmp = remove(array.size()-1);
return tmp;
}
public Position<E> atIndex(int i) throws BoundaryViolationException
{
checkIndex(i,array.size());
return array.get(i);
}
public int indexOf(Position<E> p) throws InvalidPositionException
{
try
{
ArrayPosition<E> tmp = (ArrayPosition<E>)p;
return tmp.getIndex();
}
catch(InvalidPositionException e)
{
return -1;
}
}
private ArrayPosition<E> checkPosition(Position<E> p) throws InvalidPositionException
{
if (p == null) throw new InvalidPositionException("null position");
try
{
ArrayPosition<E> temp = (ArrayPosition<E>) p;
if (indexOf(temp)<0)
throw new InvalidPositionException();
return temp;
}
catch (ClassCastException e)
{
throw new InvalidPositionException("Cast Error: it's not an ArrayPosition");
}
}
private void checkIndex(int i, int n) throws BoundaryViolationException
{
if(i<0 || i>n)
throw new BoundaryViolationException("Indice "+i+" non valido");
}
public String toString()
{
return "ArrayIndexSequence ["+ array.toString().subSequence(array.toString().indexOf(" "), array.toString().length());
}
public Iterator<E> iterator()
{
return new IndexListIterator<E>((IndexList<E>) array);
}
public Iterable<Position<E>> positions()
{
IndexList<Position<E>> tmp = new ArrayIndexList<Position<E>>();
for(int i=0; i<array.size(); i++)
tmp.add(i, array.get(i));
return tmp;
}
}
/*
Scrivere la funzione ricorsiva
boolean search(Sequence<E>S, E x)
che restituisce true se la sequenza S contiene l’elemento x.
Definizione ricorsiva: search(<s1,...,sn>, x) restituisce
false, se n=0
true, se s1=x
Il valore restituito da search(<s2,...,sn>, x), altrimenti
*/
public static <E> boolean search(Sequence<E> S, E x)
{
if (S.size()==0)
return false;
if (S.get(0).equals(x))
return true;
E tmp = S.removeFirst();
boolean ris = search(S, x);
S.addFirst(tmp);
return ris;
}
Questa è l'implementazione di ArraySequence di Valerio, che ringrazio per le correzioni al mio codice.
Questa è l'implementazione di ArraySequence di Valerio, che ringrazio per le correzioni al mio codice.
/**
* Implementazione dell'interfaccia Sequence mediante
* un array circolare ed estendibile di ArrayPosition.
*
* @see EmptyListException
* @see EmptySequenceException
* @see IndexOutOfBoundsException
* @see InvalidPositionException
*/
public class ArraySequence<E> implements Sequence<E> {
// Array circolare contenente la sequenza.
private ArrayPosition<E> S[];
// Indice della prima posizione.
private int first = 0;
// Indice della prima posizione libera dopo l'ultimo elemento.
private int last = 0;
// Capacit‡ dell'array.
private int capacity;
// Capacit‡ di default dell'array.
public static final int CAPACITY = 1024;
/**
* Costruttore di default.
*/
public ArraySequence() {
this(CAPACITY);
}
/**
* Inizializza l'array con una grandezza specificata.
*
* @param cap la lunghezza dell'array
*/
@SuppressWarnings("unchecked")
public ArraySequence(int cap) {
capacity = cap;
S = new ArrayPosition[capacity];
}
/**
* Restituisce il numero di posizioni della sequenza.
*
* @return il numero di posizioni
*/
public int size() {
return (capacity-first+last) % capacity;
}
/**
* Verifica se la sequenza Ë vuota.
*
* @return true se la sequenza Ë vuota, false altrimenti
*/
public boolean isEmpty() {
return (first == last);
}
/**
* Restituisce l'elemento della prima posizione.
*
* @return il primo elemento
* @throws EmptySequenceException se la sequenza Ë vuota
*/
public E getFirst() throws EmptySequenceException {
return first().element();
}
/**
* Restituisce l'elemento dell'ultima posizione.
*
* @return l'ultimo elemento
* @throws EmptySequenceException se la sequenza Ë vuota
*/
public E getLast() throws EmptySequenceException {
return last().element();
}
/**
* Inserisce una nuova posizione con elemento dato
* all'inizio della sequenza.
*
* @param element l'elemento da memorizzare nella nuova posizione
*/
public void addFirst(E elem) {
add(0, elem);
}
/**
* Inserisce una nuova posizione con elemento dato
* alla fine della sequenza.
*
* @param element l'elemento da memorizzare nella nuova posizione
*/
public void addLast(E elem) {
add(size(), elem);
}
/**
* Rimuove la prima posizione della sequenza e
* restituisce l'elemento memorizzato in essa.
*
* @return l'elemento memorizzato
* @throws EmptySequenceException se la sequenza Ë vuota
*/
public E removeFirst() throws EmptySequenceException {
return remove(0);
}
/**
* Rimuove l'ultima posizione della sequenza e
* restituisce l'elemento memorizzato in essa.
*
* @return l'elemento memorizzato
* @throws EmptySequenceException se la sequenza Ë vuota
*/
public E removeLast() throws EmptySequenceException {
return remove(size() - 1);
}
/**
* Restituisce la prima posizione della sequenza.
*
* @return la prima posizione
* @throws EmptySequenceException se la sequenza Ë vuota
*/
public Position<E> first() throws EmptySequenceException {
if (isEmpty())
throw new EmptySequenceException();
return S[first];
}
/**
* Restituisce l'ultima posizione della sequenza.
*
* @return l'ultima posizione
* @throws EmptySequenceException se la sequenza Ë vuota
*/
public Position<E> last() throws EmptySequenceException {
if (isEmpty())
throw new EmptySequenceException();
return S[map(size()-1)];
}
/**
* Restituisce la posizione precedente a quella data.
*
* @param p la posizione di partenza
* @return la posizione precedente
* @throws InvalidPositionException se la posizione non Ë valida
* @throws BoundaryViolationException se fuori range
*/
public Position<E> prev(Position<E> p)
throws InvalidPositionException, BoundaryViolationException {
ArrayPosition<E> pos = checkPosition(p);
checkIndex(indexOf(pos), size());
if (pos.equals(first()))
throw new BoundaryViolationException("Nessuna posizione prima del primo.");
return atIndex(indexOf(pos) - 1);
}
/**
* Restituisce la posizione successiva a quella data.
*
* @param p la posizione di partenza
* @return la posizione successiva
* @throws InvalidPositionException se la posizione non Ë valida
* @throws BoundaryViolationException se fuori range
*/
public Position<E> next(Position<E> p)
throws InvalidPositionException, BoundaryViolationException {
ArrayPosition<E> pos = checkPosition(p);
checkIndex(indexOf(pos), size());
if (pos.equals(last()))
throw new BoundaryViolationException("Nessuna posizione dopo l'ultimo.");
return atIndex(indexOf(pos) + 1);
}
/**
* Inserisce una nuova posizione con elemento dato
* prima la posizione specificata.
*
* @param p la posizione che deve succedere
* @param elem l'elemento da memorizzare
* @return la nuova posizione
* @throws InvalidPositionException se la posizione non Ë valida
*/
public Position<E> addBefore(Position<E> p, E elem) throws InvalidPositionException {
ArrayPosition<E> pos = checkPosition(p);
int i = indexOf(pos);
add(i, elem);
return prev(pos);
}
/**
* Inserisce una nuova posizione con elemento dato
* dopo la posizione specificata.
*
* @param p la posizione che deve precedere
* @param elem l'elemento da memorizzare
* @return la nuova posizione
* @throws InvalidPositionException se la posizione non Ë valida
*/
public Position<E> addAfter(Position<E> p, E elem) throws InvalidPositionException {
ArrayPosition<E> pos = checkPosition(p);
int i = indexOf(pos) + 1;
add(i, elem);
return next(pos);
}
/**
* Rimuove la posizione data e restituisce l'elemento
* in essa memorizzato.
*
* @param p la posizione da rimuovere
* @return l'elemento memorizzato
* @throws InvalidPositionException se la posizione non Ë valida
*/
public E remove(Position<E> p) throws InvalidPositionException {
ArrayPosition<E> pos = checkPosition(p);
return remove(indexOf(pos));
}
/**
* Rimpiazza l'elemento memorizzato nella posizione data
* con un nuovo elemento e lo restituisce.
*
* @param p la posizione in cui rimpiazzare l'elemento
* @param elem il nuovo elemento da settare
* @return il vecchio elemento
* @throws InvalidPositionException se la posizione non Ë valida
*/
public E set(Position<E> p, E elem) throws InvalidPositionException {
ArrayPosition<E> pos = checkPosition(p);
E oldElem = pos.element();
pos.setElement(elem);
return oldElem;
}
/**
* Restituisce l'elemento della posizione di indice dato.
*
* @param index l'indice della posizione
* @return l'elemento della posizione
* @throws IndexOutOfBoundsException se fuori range
*/
public E get(int index) throws IndexOutOfBoundsException {
checkIndex(index, size());
return atIndex(index).element();
}
/**
* Rimpiazza l'elemento della posizione di indice dato
* con un nuovo elemento e restituisce il vecchio elemento.
*
* @param index l'indice della posizione
* @param elem il nuovo elemento
* @return il vecchio elemento
* @throws IndexOutOfBoundsException se fuori range
*/
public E set(int index, E elem) throws IndexOutOfBoundsException {
checkIndex(index, size());
ArrayPosition<E> pos = (ArrayPosition<E>) atIndex(index);
return set(pos, elem);
}
/**
* Inserisce una nuova posizione di indice specificato.
*
* @param index l'indice della posizione
* @param elem l'elemento da memorizzare
* @throws IndexOutOfBoundsException se fuori range
*/
public void add(int index, E elem) throws IndexOutOfBoundsException {
checkIndex(index, size());
if (size() == capacity-1)
raddoppia();
ArrayPosition<E> newPos = new ArrayPosition<E>(index, elem);
if (index == 0) {
first = (first-1+capacity) % capacity;
S[first] = newPos;
// Aggiorno gli indici
for (int j=1; j<size(); j++)
S[map(j)].setIndex(j);
}
else {
for (int j=size()-1; j>=index; j--) {
S[map(j+1)] = S[map(j)];
S[map(j+1)].setIndex(j+1);
}
S[map(index)] = newPos;
last = (last + 1) % capacity;
}
}
/**
* Rimuove la posizione di indice dato e ne restituisce l'elemento.
*
* @param index l'indice della posizione
* @return l'elemento memorizzato
* @throws IndexOutOfBoundsException se fuori range
*/
public E remove(int index) throws IndexOutOfBoundsException {
checkIndex(index, size());
E elem = atIndex(index).element();
if (index == 0) {
S[first] = null;
first = (first+1) % capacity;
// Vengono aggiornati gli indici.
for (int j=0; j<size(); j++)
S[map(j)].setIndex(j);
}
else {
last = (last-1+capacity) % capacity;
// Gli elementi vengono shiftati a sinistra
// e vengono aggiornati gli indici.
for (int h=index; h<size(); h++) {
S[map(h)] = S[map(h+1)];
S[map(h)].setIndex(h);
}
}
return elem;
}
/**
* Restituisce una rappresentazione testuale di un ArraySequence
* come una lista di elementi: [primo, secondo, ... , ultimo].
*
* @return una rappresentazione testuale della lista
*/
public String toString() {
String s = "[";
int i = 0;
if (size() > 0)
s += get(i);
if (size() > 1)
for (i=1; i<size(); i++)
s += ", " + get(i);
s += "]";
return s;
}
/**
* Metodo di servizio che controlla che l'indice sia nel range [0, n-1].
*
* @param index l'indice da controllare
* @param n il valore del range
* @throws IndexOutOfBoundsException se indice < 0 oppure indice > n
*/
protected void checkIndex(int index, int n) throws IndexOutOfBoundsException {
if (index < 0 || index > n)
throw new IndexOutOfBoundsException ("Líindice " +index+
" non Ë valido per questa sequenza.");
}
/**
* Metodo di servizio che controlla se la posizione Ë valida
* per questa sequenza e la converte in ArrayPosition in caso positivo.
*
* @param p la posizione da controllare
* @return la posizione convertita nel tipo ArrayPosition
* @throws InvalidPositionException se la posizione non Ë valida
*/
protected ArrayPosition<E> checkPosition(Position<E> p)
throws InvalidPositionException {
if (p == null)
throw new InvalidPositionException("Posizione nulla.");
try {
ArrayPosition<E> pos = (ArrayPosition<E>) p;
return pos;
}
catch (ClassCastException e) {
throw new InvalidPositionException();
}
}
/**
* Restituisce la posizione dell'elemento con indice dato.
*
* @param index l'indice dell'elemento
* @return la posizione dell'elemento
* @throws BoundaryViolationException se fuori range
*/
public Position<E> atIndex(int index) throws BoundaryViolationException {
checkIndex(index, size());
return S[map(index)];
}
/**
* Restituisce l'indice della posizione data.
*
* @param p la posizione dell'elemento
* @return l'indice dell'elemento
* @throws InvalidPositionException se la posizione non Ë valida
*/
public int indexOf(Position<E> p) throws InvalidPositionException {
ArrayPosition<E> pos = checkPosition(p);
return pos.getIndex();
}
/**
* Metodo di servizio che raddoppia la capacit‡
* dell'array in caso non vi siano pi˘ posti liberi.
*/
@SuppressWarnings("unchecked")
protected void raddoppia() {
// Numero di elementi nell'array prima di
// modificare il valore di capacity
int numElem = size();
int oldCap = capacity;
capacity *= 2;
ArrayPosition<E> S2[] = new ArrayPosition[capacity];
// Gli elementi vengono copiati nel nuovo array
// ponendo il first a partire da 0 e scorrendo il
// vecchio array dal first in poi
int i,j;
for (i=0,j=first; i<numElem; i++,j=(j+1)%oldCap)
S2[i] = S[j];
// Nuovo valore del first
first = 0;
// Nuovo valore del last
last = numElem;
S = S2;
}
/**
* Metodo di servizio che restituisce l'indice della posizione
* all'interno dell'array.
*
* @param index l'indice della posizione
* @return l'indice all'interno dell'array
*/
protected int map(int index) {
return (first + index) % capacity;
}
/**
* Sposta l'elemento di posizione data all'inizio della sequenza
* lasciando inalterato l'ordine dei rimanenti elementi.
*
* @param p la posizione da spostare
*/
public void makeFirst(Position<E> p) throws InvalidPositionException {
ArrayPosition<E> pos = checkPosition(p);
addFirst(remove(pos));
}
}
Post
Ciao, ma non manca l'implementazione di ArraySequence?
RispondiEliminain effetti si, non l'ho ancora aggiunta per via di uno strano errore che mi viene dato dal costruttore.
RispondiEliminal'errore è il seguente:
Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Lposition.ArrayPosition;
e la riga di codice che causa l'eccezione è questa:
array = (ArrayPosition []) new Object[capacity];
sinceramente non ho capito il problema, e accetterei volentieri suggerimenti per risolverlo, oppure se avete un'implementazione di ArraySequence (TDA Sequence implementato con un array circolare ed estendibile) scrivetela nei commenti, io la testo e se funziona la aggiungo al post.
Non c'è bisogno di creare un oggetto Object e castarlo; nelle altre implementazioni lo facevamo perché non esiste un costruttore della classe generica, ma in questo caso è un array di ArrayPosition. Perciò
RispondiElimina// array contenente la sequenza
private ArrayPosition array[];
public ArraySequence(int cap) {
capacity = cap;
S = new ArrayPosition[capacity];
}
Scusami ho sbagliato:
RispondiElimina// array contenente la sequenza
private ArrayPosition < E > array[];
public ArraySequence(int cap) {
capacity = cap;
array = new ArrayPosition[capacity];
}
Grazie Anonimo! ho aggiornato il post aggiungendo ArraySequence
RispondiEliminaCiao, stavo leggendo il codice, ma non capisco il controllo sull'indice passato a prev o a next dove viene fatto.
RispondiEliminaHai provato a chiamarli rispettivamente sulla prima e ultima posizione?
Poi nel metodo map perché aggiungi 1?
Ciao Valerio, grazie per la correzione, ho aggiunto i controlli sull'indice nei metodi prev e next di ArraySequence.
RispondiEliminaPer quanto riguarda il metodo map aggiunto 1 perchè in questa implementazione l'array viene riempito dalla fine all'inizio, ad esempio
se provi ad istanziare un ArraySequence con capacità 20, e fai un addFirst(x), il valore di f == 19; se ne fai un altro, f==18 e così via.
Scusami, ma f è l'indice della cella dell'array con la prima posizione della sequenza o l'indice della cella dell'array che si trova immediatamente prima della prima posizione della sequenza?
RispondiEliminaeffettivamente punta alla cella dell'array che si trova immediatamente prima della prima posizione della sequenza.
RispondiEliminaOk, perciò non mi trovavo ;). Sulle slide f lo considera come prima posizione, ma alla fine è la stessa cosa
RispondiEliminaTi ho postato la mia classe ArraySequence.
RispondiEliminaFirst rappresenta la cella dell'array con il primo elemento della sequenza e last la prima cella libera dopo l'ultimo elemento della sequenza e non uso variabili per il numero di elementi.
Per motivi di numero di caratteri ammessi, non ho copiato i metodi di servizio (checkPosition, checkIndex, ...). Cmq dalle uno sguardo e fammi sapere se qualcosa non ti è chiara o non va bene.
Ciao
PS: Modifica il tuo metodo toString perché così stampa la locazione di memoria
Grazie per la collaborazione Valerio, ho aggiunto il tuo codice di ArraySequence al post.
RispondiEliminaragazzi ma l'implementazione di ArrayPosition dov'è e dove la chiede?
RispondiEliminaPuoi scaricare tutto il progetto con tutte le classi da questo post. La classe ArrayPosition si trova nel pacchetto position.
RispondiElimina