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.example;
021 import java.util.List;
022
023 import ch.bfh.algo.Position;
024 import ch.bfh.algo.Sequence;
025 import ch.bfh.algo.sequence.ArraySequence;
026 import ch.bfh.algo.sequence.LinkedSequence;
027
028 /**
029 * The class <code>SequencesSortExamples</code> contains samples of
030 * the use of a <code>Sequence</code>.
031 *
032 * This class has no mean of being used, it is only a sample of
033 * possible applications of the <code>ch.bfh.algo</code> algorithmic
034 * framework.
035 *
036 * @author <a href="mailto:">Emmanuel Benoist</a>
037 * @version 1.0
038 */
039 public class SequencesSortExamples{
040
041 private class MyString{
042 Position<MyString> positionInList1;
043 Position<MyString> positionInList2;
044
045 String str;
046
047 MyString(String s){
048 str=s;
049
050 }
051
052
053 /**
054 * Get the PositionInList1 value.
055 * @return the PositionInList1 value.
056 */
057 public Position<MyString> getPositionInList1() {
058 return positionInList1;
059 }
060
061 /**
062 * Set the PositionInList1 value.
063 * @param newPositionInList1 The new PositionInList1 value.
064 */
065 public void setPositionInList1(Position<MyString> newPositionInList1) {
066 this.positionInList1 = newPositionInList1;
067 }
068
069
070 /**
071 * Get the PositionInList2 value.
072 * @return the PositionInList2 value.
073 */
074 public Position<MyString> getPositionInList2() {
075 return positionInList2;
076 }
077
078 /**
079 * Set the PositionInList2 value.
080 * @param newPositionInList2 The new PositionInList2 value.
081 */
082 public void setPositionInList2(Position<MyString> newPositionInList2) {
083 this.positionInList2 = newPositionInList2;
084 }
085
086 public String toString(){
087 return str;
088 }
089 }
090
091
092 /**
093 * The method <code>bubbleSortArrayLike</code> is a very simple
094 * Bubble Sort written for the Java Collection Framework.
095 *
096 * This method does not include any reference to the
097 * *<code>ch.bfh.algo</code> framework. However, this works fine
098 * *with an <code>ArraySequence</code> since it is fully Java
099 * *Collection Framework compatible.
100 *
101 */
102 public static void bubbleSortArrayLike(List<Integer> list){
103 int size = list.size();
104 for (int pass=0; pass < size ; pass++){
105 for(int index = 0; index< size-(pass+1);index++){
106 if(list.get(index)>list.get(index+1)){
107 Integer tmp = list.get(index);
108 list.set(index,list.get(index+1));
109 list.set(index+1,tmp);
110 }
111 }
112 }
113
114 }
115
116
117 /**
118 * This Bubble sort algorithm has been implemented using a
119 * <code>Sequence</code>.
120 *
121 * It is using also the <code>Position</code>s that are the
122 * place-holders of a <code>Sequence</code>
123 *
124 */
125 public static void bubbleSortSequence(Sequence<Integer> seq){
126 Position<Integer> pos1,pos2;
127 boolean unsorted=false;
128 while(unsorted){
129 unsorted=true;
130 pos1 = seq.first();
131 while(pos1!=seq.last()){
132 pos2=seq.after(pos1);
133 if( pos1.element()> pos2.element()){
134 Integer tmp = pos1.element();
135 seq.replace(pos1,pos2.element());
136 seq.replace(pos2,tmp);
137 }
138 }
139 }
140 }
141
142
143 /**
144 * This method <code>bubbleSortExamples</code> is used to run the
145 * two other methods: <code>bubbleSortArrayLike</code> and
146 * <code>bubbleSortSequence</code>.
147 *
148 * The first method is using only the standard Collection
149 * Framework syntax and interfaces. Whereas the second is using a
150 * syntax typical for the <code>ch.bfh.algo</code> framework.
151 */
152 public static void bubbleSortExamples(){
153 System.out.println("Example Using Bubble Sort: O(n^2)");
154 System.out.println("Creation of an Integer ArraySequence:");
155 List<Integer> seq1 = new ArraySequence<Integer>();
156 seq1.add(10);
157 seq1.add(20);
158 seq1.add(30);
159 seq1.add(40);
160 seq1.add(1);
161 System.out.println(seq1);
162 System.out.println("we use a standard (Java Collection Framework) algorithm");
163 bubbleSortArrayLike(seq1);
164 System.out.println("After Sort:");
165 System.out.println(seq1);
166 System.out.println("");
167
168 }
169
170 /**
171 * The method <code>removeFirstThreeOfL1FromL2</code> removes the
172 * tree first elements of the sequence1 from the sequence2.
173 *
174 * This is can not be done efficiently using classes of the java
175 * collection framework and is very efficient in our case
176 * (regardless of the number of elements in sequence1 or
177 * sequence2, this operation is O(1)).
178 *
179 */
180 public static void removeFirstThreeOfL1FromL2(Sequence<MyString> sequence1,
181 Sequence<MyString> sequence2){
182 Position<MyString> pos=sequence1.first();
183 for(int i=0;i<3;i++){
184 MyString s=sequence1.element(pos);
185 sequence2.delete(s.getPositionInList2());
186 pos=sequence1.after(pos);
187 }
188
189 }
190
191
192 /**
193 * The method <code>positionEfficiencyExample</code> shows the
194 * advantage of the <code>Sequence</code> compared to standard
195 * structures such as <code>java.util.List</code>.
196 *
197 * We create two lists containing the same items. In each Item we
198 * save its <code>Position</code> in both of the lists. Afterwhat,
199 * it is possible to remove an item from a list in time
200 * O(1). Doing the same with <code>java.util.LinkedList</code>
201 * requires O(n), since it can not use a way to refere to an item
202 * inside a list (there is no place-holder like the
203 * <code>Position</code>).
204 *
205 */
206 public void positionEfficiencyExample(){
207 MyString s1=new MyString("1");
208 MyString s2=new MyString("2");
209 MyString s3=new MyString("3");
210 MyString s4=new MyString("4");
211 MyString s5=new MyString("5");
212 MyString s6=new MyString("6");
213 Sequence<MyString> seq1 = new ArraySequence<MyString>();
214 s1.setPositionInList1(seq1.insert(s1));
215 s2.setPositionInList1(seq1.insert(s2));
216 s3.setPositionInList1(seq1.insert(s3));
217 s4.setPositionInList1(seq1.insert(s4));
218 s5.setPositionInList1(seq1.insert(s5));
219 s6.setPositionInList1(seq1.insert(s6));
220
221 Sequence<MyString> seq2 = new LinkedSequence<MyString>();
222 s1.setPositionInList2(seq2.insert(s1));
223 s6.setPositionInList2(seq2.insert(s6));
224 s5.setPositionInList2(seq2.insert(s5));
225 s4.setPositionInList2(seq2.insert(s4));
226 s2.setPositionInList2(seq2.insert(s2));
227 s3.setPositionInList2(seq2.insert(s3));
228
229 System.out.println("----------------");
230 System.out.println("Example for comparing two sequences: Remove elements from L1 in L2");
231 System.out.println("Each removal is done in time O(1), which can not be done with other data structures in Java.");
232 System.out.println("Start");
233 System.out.println("L1="+seq1);
234 System.out.println("L2="+seq2);
235 removeFirstThreeOfL1FromL2(seq1,seq2);
236 System.out.println("Result:");
237 System.out.println("L1="+seq1);
238 System.out.println("L2="+seq2);
239 System.out.println("----------------");
240
241 }
242
243
244 public static Sequence<Integer> mergeUsingPositions(Sequence<Integer> seq1,
245 Sequence<Integer> seq2,
246 Sequence<Integer> result){
247 // We first expurgate the content of the result sequence
248 /*if(!result.isEmpty()){
249 Position<Integer> pos = result.first();
250 while (pos!=null){
251 if(pos == result.last()){
252 result.delete(pos);
253 pos = null;
254 }
255 else{
256 Position<Integer> after = result.after(pos);
257 result.delete(pos);
258 pos=after;
259 }
260 }
261 }*/
262 result.clear();
263 Position<Integer> posSeq1,posSeq2;
264 posSeq1=seq1.first();
265 posSeq2=seq2.first();
266 while(posSeq1!=null && posSeq2!=null){
267 if(posSeq1.element() < posSeq2.element()){
268 result.add(posSeq1.element());
269 if(posSeq1 != seq1.last()){
270 posSeq1 = seq1.after(posSeq1);
271 }
272 else{
273 posSeq1 = null;
274 }
275 }
276 else{
277 result.add(posSeq2.element());
278 if(posSeq2 != seq2.last()){
279 posSeq2 = seq2.after(posSeq2);
280 }
281 else{
282 posSeq2 = null;
283 }
284 }
285
286 }
287
288 if(posSeq2==null){
289 while(posSeq1!=null){
290 result.add(posSeq1.element());
291 if(posSeq1 != seq1.last()){
292 posSeq1 = seq1.after(posSeq1);
293 }
294 else{
295 posSeq1 = null;
296 }
297 }
298 }
299 else{
300 while(posSeq2!=null){
301 result.add(posSeq2.element());
302 if(posSeq2 != seq2.last()){
303 posSeq2 = seq2.after(posSeq2);
304 }
305 else{
306 posSeq2 = null;
307 }
308 }
309 }
310 return result;
311 }
312
313 public static void splitUsingIterator(List<Integer> seq,
314 List<Integer> res1,
315 List<Integer> res2){
316 int i=0;
317 for (Integer item : seq){
318 if(i++%2==0){
319 res1.add(item);
320 }
321 else{
322 res2.add(item);
323 }
324
325 }
326
327 }
328
329
330 /**
331 * The method <code>mergeSort</code> implements the merge sort
332 * algorithm using the <code>Sequence</code> interface.
333 *
334 * It uses on one side the compatibility with the java collection
335 * framework in the function <code>splitUsingIterator</code>.
336 *
337 *The second part, merging is done using <code>Position</code>s
338 */
339 public static void mergeSort(Sequence<Integer> seq){
340 if(seq.size()< 2){
341 return;
342 }
343 Sequence<Integer> seq1 = new LinkedSequence<Integer>();
344 Sequence<Integer> seq2 = new LinkedSequence<Integer>();
345 splitUsingIterator(seq,seq1,seq2);
346 mergeSort(seq1);
347 mergeSort(seq2);
348 mergeUsingPositions(seq1,seq2,seq);
349
350 }
351
352 public static void testMerge(){
353 ArraySequence<Integer> seq1 = new ArraySequence<Integer>();
354 seq1.add(10);
355 seq1.add(20);
356 seq1.add(30);
357 seq1.add(40);
358 seq1.add(100);
359 LinkedSequence<Integer> seq2 = new LinkedSequence<Integer>();
360 seq2.add(1);
361 seq2.add(2);
362 seq2.add(3);
363 seq2.add(43);
364 seq2.add(130);
365 seq2.add(132);
366 seq2.add(133);
367
368 Sequence<Integer> seq = new LinkedSequence<Integer>();
369 mergeUsingPositions(seq1,seq2,seq);
370 System.out.println("----------------");
371 System.out.println("Start Merge Test");
372 System.out.println("L1="+seq1);
373 System.out.println("L2="+seq2);
374 System.out.println("Result="+seq);
375 System.out.println("----------------");
376 System.out.println(" ");
377
378 }
379
380 /**
381 * This method tests if the method split
382 * (<code>splitUsingIterator()</code>) works as expected
383 *
384 *
385 */
386 public static void testSplit(){
387
388 LinkedSequence<Integer> seq = new LinkedSequence<Integer>();
389 seq.add(10);
390 seq.add(20);
391 seq.add(30);
392 seq.add(40);
393 seq.add(100);
394 seq.add(1);
395 seq.add(2);
396 seq.add(3);
397 seq.add(43);
398 seq.add(130);
399 seq.add(132);
400 seq.add(133);
401
402 LinkedSequence<Integer> seqRes1 = new LinkedSequence<Integer>();
403
404 LinkedSequence<Integer> seqRes2 = new LinkedSequence<Integer>();
405
406 splitUsingIterator(seq,seqRes1,seqRes2);
407
408 System.out.println("----------------");
409 System.out.println("Start Split Test");
410 System.out.println("L="+seq);
411 System.out.println("Result1="+seqRes1);
412 System.out.println("Result2="+seqRes2);
413 System.out.println("----------------");
414 System.out.println(" ");
415
416
417 }
418
419
420 /**
421 * This method tests if the merge sort algorithm
422 * (<code>mergeSort()</code>) works as expected
423 *
424 *
425 */
426 public static void testMergeSort(){
427 LinkedSequence<Integer> seq = new LinkedSequence<Integer>();
428 seq.add(10);
429 seq.add(20);
430 seq.add(30);
431 seq.add(40);
432 seq.add(100);
433 seq.add(1);
434 seq.add(2);
435 seq.add(3);
436 seq.add(43);
437 seq.add(130);
438 seq.add(132);
439 seq.add(133);
440
441
442 System.out.println("----------------");
443 System.out.println("Start MergeSort");
444 System.out.println("L_Init="+seq);
445 mergeSort(seq);
446 System.out.println("L_Result="+seq);
447 System.out.println("----------------");
448 System.out.println(" ");
449
450
451 }
452
453
454 public void run(){
455 bubbleSortExamples();
456 positionEfficiencyExample();
457 testMerge();
458 testSplit();
459 testMergeSort();
460 }
461
462 public static void main(String[] args){
463 System.out.println("Start of the Examples");
464 new SequencesSortExamples().run();
465 }
466
467 }