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;
021
022 import java.util.List;
023 import java.util.ListIterator;
024
025 /**
026 * The {@link Sequence} interface is used to store elements in a flat
027 * datastructure. Its implementation can be done using a doubly linked
028 * list or an array.
029 *
030 * In the following example, we use two positions to visit a sequence
031 *
032 * <pre>
033 Position<Integer> pos1 = seq.first();
034 while(pos1!=seq.last()){
035 pos2=seq.after(pos1);
036 if( pos1.element()> pos2.element()){
037 Integer tmp = pos1.element();
038 seq.replace(pos1,pos2.element());
039 seq.replace(pos2,tmp);
040 }
041 }
042 * </pre>
043 *
044 * But since a sequence is also a <code>java.util.List</code>, one
045 * can use the programs written for such datastructures. We can for
046 * instance use the foreach loops:
047 * <pre>
048 Sequence<String> seq = ...;
049 for(String s : seq){
050 System.out.prinln(s);
051 }
052 * </pre>
053 * @author <a href="http://www.iam.unibe.ch/til/staff/kraehenbuehl">Juerg
054 * Kraehenbuehl</a> (code) and <a href="http://prof.hti.bfh.ch/bie1">Emmanuel
055 * Benoist</a> (Javadoc)
056 * @version 1.0
057 */
058
059 public interface Sequence<E> extends Container<E>, List<E> {
060
061 /**
062 * The method <code>first()</code> returns the
063 * <code>Position</code> containing the first element of the
064 * sequence.
065 *
066 * It throws an <code>EmptySequenceException</code> if the
067 * sequence is empty.
068 *
069 * @return the first <code>Position</code>
070 * @throws EmptySequenceException if the sequence is empty.
071 */
072 public Position<E> first() throws EmptySequenceException;
073
074 /**
075 * The method <code>last()</code> returns the
076 * <code>Position</code> containing the last element of the
077 * sequence.
078 *
079 * It throws an <code>EmptySequenceException</code> if the
080 * sequence is empty.
081 *
082 * @return the last <code>Position</code> in the sequence.
083 * @throws EmptySequenceException if the sequence is empty.
084 */
085 public Position<E> last() throws EmptySequenceException;
086
087 /**
088 * This method returns the position that is placed before the one
089 * given as argument in the sequence.
090 *
091 * @param position Position
092 * @return the <code>Position</code> that is before the given one
093 * @throws InvalidAccessorException if <code>position</code> does not belong to this sequence.
094 * @throws BoundaryViolationException if the given position is the
095 * first one (there is nothing before it in this case).
096 */
097 public Position<E> before(Position<?> position) throws InvalidAccessorException, BoundaryViolationException;
098
099 /**
100 * returns the Position that is placed after <code>position</code>
101 * in the sequence
102 *
103 * @param position a <code>Position<?></code>
104 * @return the Position after <code>position</code>
105 * @throws InvalidAccessorException if <code>position</code> does not belong to this sequence.
106 * @throws BoundaryViolationException if the given position is the
107 * last one (there is nothing after it in this case).
108 */
109 public Position<E> after(Position<?> position) throws InvalidAccessorException, BoundaryViolationException;
110
111 /**
112 * This method insert <code>element</code> in the sequence. It
113 * creates a new <code>Position</code> that is inserted before
114 * <code>position</code>. The new position contains the new
115 * <code>element</code> and is returned by the method.
116 *
117 * @param position a <code>Position<?></code>
118 * @return the new <code>Position</code> containing <code>element</code>
119 * @throws InvalidAccessorException if <code>position</code> does
120 * not belong to this sequence.
121 */
122 public Position<E> insertBefore(Position<?> position, E element) throws InvalidAccessorException;
123 /**
124 * This method insert <code>element</code> in the sequence. It
125 * creates a new <code>Position</code> that is inserted after
126 * <code>position</code>. The new position contains the new
127 * <code>element</code> and is returned by the method.
128 *
129 * @param position a <code>Position<?></code>
130 * @return the new <code>Position</code> containing <code>element</code>
131 * @throws InvalidAccessorException if <code>position</code> does
132 * not belong to this sequence.
133 */
134 public Position<E> insertAfter(Position<?> position, E element) throws InvalidAccessorException;
135
136 /**
137 * The <code>position</code> method returns the
138 * <code>Position</code> corresponding to a given
139 * <code>rank</code>.
140 *
141 * This method is a bridge between the methods of the
142 * <code>List</code> interface and the ones of the
143 * <code>Sequence</code>.
144 *
145 * @param rank an <code>int</code> that denotes the index of the researched position in the sequence.
146 * @return the new <code>Position</code> containing <code>element</code>
147 * @throws IndexOutOfBoundsException if <code>rank</code> is smaller than 0 or larger than or equal to the number of elements in the sequence.
148 */
149 public Position<E> position(int rank) throws IndexOutOfBoundsException;
150
151 /**
152 * The <code>rank</code> method returns the rank of the given
153 * <code>position</code>, analogous to the method <code>indexOf</code> in the <code>List</code> interface.
154 *
155 * This method is a bridge between the methods of the
156 * <code>List</code> interface and the ones of the
157 * <code>Sequence</code>.
158 *
159 * @param position a <code>Position<?></code> of the sequence
160 * @return the rank of this <code>position</code> (i.e. its index in the sequence).
161 * If <code>position</code> is not in the sequence then its rank is <code>-1</code>.
162 */
163 public int rank(Position<?> position);
164
165 /**
166 * The <code>positionListIterator</code> method creates and return a <code>ListIterator</code> for the <code>Position</code>s contained in the sequence.
167 *
168 * This method gives the possibility to iterate over all the
169 * Positions in the sequence.
170 *
171 * @return a <code>ListIterator<Position<E>></code> of all the <code>Position</code>s in the sequence.
172 */
173 public ListIterator<Position<E>> positionListIterator();
174
175 /**
176 * The <code>positionListIterator</code> method creates and return a <code>ListIterator</code> for the <code>Position</code>s contained in the sequence. This iterator is initially placed at the rank given as a parmeter
177 *
178 * This method gives the possibility to iterate over all the
179 * Positions in the sequence.
180 *
181 * @param rank an <code>int</code> denoting the initial position
182 * of the pointer of the iterator.
183 * @return a <code>ListIterator<Position<E>></code> of
184 * all the <code>Position</code>s in the sequence.
185 * @throws IndexOutOfBoundsException if <code>rank</code> is smaller than 0 or larger than the number of elements in the sequence.
186 */
187 public ListIterator<Position<E>> positionListIterator(int rank) throws IndexOutOfBoundsException;
188 }