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));
}
}
Continua...
Post
