001 /*
002 * www.ti.bfh.ch
003 *
004 * Copyright 2007, Berne University of Applied Sciences,
005 * School of Engineering and Information Technology
006 * and individual contributors as indicated by the @authors tag.
007 *
008 * This is free software; you can redistribute it and/or modify it under the terms of the
009 * GNU Lesser General Public License as published by the Free Software Foundation;
010 * either version 3 of the License, or (at your option) any later version.
011 *
012 * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
013 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
014 * See the GNU Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public License along with this software;
017 * if not, see <http://www.gnu.org/licenses/>.
018 *
019 */
020 package ch.bfh.algo.core.sequence;
021
022
023 import java.util.AbstractSequentialList;
024 import java.util.ListIterator;
025
026 import ch.bfh.algo.BoundaryViolationException;
027 import ch.bfh.algo.EmptySequenceException;
028 import ch.bfh.algo.InvalidAccessorException;
029 import ch.bfh.algo.Position;
030 import ch.bfh.algo.core.GenericSequence;
031 import ch.bfh.algo.core.position.PositionIterator;
032 import ch.bfh.algo.core.position.PositionListIterator;
033 import ch.bfh.algo.sequence.SequenceFactory;
034
035
036 public class GenericLinkedSequence<E,P extends GenericLinkedPosition<E,P>> extends AbstractSequentialList<E> implements GenericSequence<E,P>{
037
038 private int size;
039 final private P head,tail;
040 final private SequenceFactory<P> factory;
041
042 public GenericLinkedSequence(SequenceFactory<P> factory){
043 this.factory=factory;
044 this.head=this.factory.createPosition();
045 this.tail=this.factory.createPosition();
046 this.head.setNext(this.tail);
047 this.tail.setPrevious(this.head);
048 this.size=0;
049 }
050
051 public int size() {
052 return this.size;
053 }
054
055 protected P head(){
056 return this.head;
057 }
058
059 protected P tail(){
060 return this.tail;
061 }
062
063 public P first() throws EmptySequenceException{
064 if(this.isEmpty()) throw new EmptySequenceException();
065 else return this.head.getNext();
066 }
067
068 public P last() throws EmptySequenceException{
069 if(this.isEmpty()) throw new EmptySequenceException();
070 else return this.tail.getPrevious();
071 }
072
073 public P before(Position<?> position) throws InvalidAccessorException, BoundaryViolationException {
074 try{return this.before(this.factory.cast(position));}
075 catch(ClassCastException e){throw new InvalidAccessorException();}
076 }
077
078 public P before(P position) throws InvalidAccessorException, BoundaryViolationException{
079 this.validate(position);
080 position=position.getPrevious();
081 if(position==this.head) throw new BoundaryViolationException();
082 else return position;
083 }
084
085 public P after(Position<?> position) throws InvalidAccessorException, BoundaryViolationException {
086 try{return this.after(this.factory.cast(position));}
087 catch(ClassCastException e){throw new InvalidAccessorException();}
088 }
089
090 public P after(P position) throws InvalidAccessorException, BoundaryViolationException{
091 this.validate(position);
092 position=position.getNext();
093 if(position==this.tail) throw new BoundaryViolationException();
094 else return position;
095 }
096
097 protected P insertBetween(P previous, P next, E element){
098 return this.insertBetween(previous,next,element,this.factory.createPosition());
099 }
100
101 protected synchronized P insertBetween(P previous, P next, E element, P position){
102 ConcreteLocator<E,P> locator=new ConcreteLocator<E,P>();
103 locator.setElement(element);
104 locator.setPosition(position);
105 position.setContainer(this);
106 position.setLocator(locator);
107 position.setNext(next);
108 position.setPrevious(previous);
109 previous.setNext(position);
110 next.setPrevious(position);
111 this.size++;
112 next.notifyBefore();
113 return position;
114 }
115
116 public P insertBefore(Position<?> position, E element) throws InvalidAccessorException {
117 try{return this.insertBefore(this.factory.cast(position),element);}
118 catch(ClassCastException e){throw new InvalidAccessorException();}
119 }
120
121 public P insertBefore(P position, E element) throws InvalidAccessorException{
122 this.validate(position);
123 return this.insertBetween(position.getPrevious(),position,element);
124 }
125
126 public P insertAfter(Position<?> position, E element) throws InvalidAccessorException {
127 try{return this.insertAfter(this.factory.cast(position),element);}
128 catch(ClassCastException e){throw new InvalidAccessorException();}
129 }
130
131 public P insertAfter(P position, E element) throws InvalidAccessorException{
132 this.validate(position);
133 return this.insertBetween(position,position.getNext(),element);
134 }
135
136 public P insert(E element){
137 return this.insert(element,this.factory.createPosition());
138 }
139
140 protected P insert(E element, P newPosition){
141 return this.insertBetween(this.tail.getPrevious(),this.tail,element,newPosition);
142 }
143
144 public E replace(Position<?> position, E element) throws InvalidAccessorException{
145 try{return this.replace(this.factory.cast(position),element);}
146 catch(ClassCastException e){throw new InvalidAccessorException();}
147 }
148
149 public E replace(P position, E element) throws InvalidAccessorException{
150 this.validate(position);
151 return position.replace(position,element);
152 }
153
154 public E delete(Position<?> position) throws InvalidAccessorException {
155 try{return this.delete(this.factory.cast(position));}
156 catch(ClassCastException e){throw new InvalidAccessorException();}
157 }
158
159 public synchronized E delete(P position) throws InvalidAccessorException{
160 this.validate(position);
161 E element=position.element();
162 P p0=position.getPrevious(), p1=position.getNext();
163 p0.setNext(p1);
164 p1.setPrevious(p0);
165 this.size--;
166 position.notifyAfter();
167 position.notifyBefore();
168 position.locator().setPosition(null);
169 position.setLocator(null);
170 position.setContainer(null);
171 return element;
172 }
173
174 public void swap(Position<?> position0, Position<?> position1) throws InvalidAccessorException {
175 try{this.swap(this.factory.cast(position0),this.factory.cast(position1));}
176 catch(ClassCastException e){throw new InvalidAccessorException();}
177 }
178
179 public void swap(P position0, P position1) throws InvalidAccessorException{
180 this.validate(position0);
181 this.validate(position1);
182 position0.swap(position0,position1);
183 }
184
185 public boolean encloses(Position<?> position) {
186 try{return this.encloses(this.factory.cast(position));}
187 catch(ClassCastException e){return false;}
188 }
189
190 public boolean encloses(P position){
191 try{this.validate(position); return true;}
192 catch(InvalidAccessorException e){return false;}
193 }
194
195 public E element(Position<?> position){
196 try{return this.element(this.factory.cast(position));}
197 catch(ClassCastException e){throw new InvalidAccessorException();}
198 }
199
200 public E element(P position){
201 this.validate(position);
202 return position.element();
203 }
204
205 protected void validate(P position) throws InvalidAccessorException{
206 if(position==null || this!=position.container()) throw new InvalidAccessorException();
207 }
208
209 public P position(int rank) throws IndexOutOfBoundsException{
210 if(rank<0 || this.size<=rank) throw new IndexOutOfBoundsException();
211 P p=this.head;
212 for(int i=0;i<=rank;i++) p=p.getNext();
213 return p;
214 }
215
216 public int rank(Position<?> position) {
217 try{return this.rank(this.factory.cast(position));}
218 catch(ClassCastException e){return -1;}
219 }
220
221 public int rank(P position){
222 P tmp=this.head.getNext();
223 for(int rank=0; rank<this.size; rank++,tmp=tmp.getNext()){
224 if(position==tmp) return rank;
225 }
226 return -1;
227 }
228
229 public PositionListIterator<E,P> positionListIterator(int rank){
230 P position;
231 try{position=this.position(rank);}
232 catch(IndexOutOfBoundsException e){
233 if(rank==0 || rank==this.size) position=this.tail;
234 else throw new IndexOutOfBoundsException();
235 }
236 return new LinkedPositionIterator<E,P>(this,position.getPrevious(),position);
237 }
238
239 public PositionListIterator<E,P> positionListIterator(){
240 return this.positionListIterator(0);
241 }
242
243 public ListIterator<E> listIterator(int index) throws IndexOutOfBoundsException{
244 P position;
245 try{position=this.position(index);}
246 catch(IndexOutOfBoundsException e){
247 if(index==0 || index==this.size) position=this.tail;
248 else throw new IndexOutOfBoundsException();
249 }
250 return new LinkedElementIterator<E,P>(this,position.getPrevious(),position);
251 }
252
253 public PositionIterator<E,P> positionIterator(){
254 return this.positionListIterator();
255 }
256 }
257