1 // variant on serials.java with ArrayList by Andy Harrington
 2 import java.io.*;
 3 import java.util.*;
 4 
 5 class as {
 6   static ArrayList<Rec> rec = new ArrayList<Rec>();
 7 
 8   public static void main( String[] args ) throws Exception {
 9     String inFile = args.length > 0 ? args[0] : "serials.in";
10     Scanner in = new Scanner( new File( inFile ) );
11     String s = in.nextLine();
12     while ( !s.equals( "END" ) ) {
13       System.out.println( s );
14       rec.clear(); 
15       rec.add(new Rec(0,0,'0', 0)); // dummy header, before everything real
16       int a = in.nextInt();
17       while ( a != 0 ) {
18         insert(new Rec(a, in.nextInt(), in.next().charAt(0), in.nextInt()));
19         a = in.nextInt();
20       }
21       for (Rec r : rec)
22          if (r.c != '0')
23              System.out.format( "%d %d %c %d%n", r.a, r.b, r.c, r.t );
24       in.nextLine();
25       s = in.nextLine();
26     }
27   }
28 
29   static void insert(Rec r) { 
30     int i = 1;  // adjusted to be the index where r inserted
31     while (i < rec.size() && rec.get(i).a <= r.a)
32       i++;
33     Rec p = rec.get(i-1),  // starts no later than r does
34         q = new Rec(r.b+1, p.b,p.c,p.t);  // in case p goes past r
35     if ( p.a < r.a ) // keep part before
36         p.b = java.lang.Math.min(p.b, r.a-1);
37     else  // quick and dirty - deletions not minimized
38         rec.remove(--i);  // i still where r will go
39     if (q.b > r.b) // add part of p extending past r        
40         rec.add(i, q);
41     while (i < rec.size() && rec.get(i).b <= r.b)
42         rec.remove(i); // remove all totally superceded later ones
43     if (i < rec.size() && rec.get(i).a <= r.b)
44         rec.get(i).a = r.b + 1; // if part overlap next
45     // merge adjacent serial number ranges with identical codes
46     p = rec.get(i-1);
47     if ( p.b + 1 == r.a && p.c == r.c && p.t == r.t ) {
48         r.a = p.a;   // extend r, remove previous Rec
49         rec.remove(--i);  // i still index of r
50     }
51     if (i < rec.size()){
52         p = rec.get(i);  
53         if ( r.b + 1 == p.a && p.c == r.c && p.t == r.t ) {
54             r.b = p.b;  // extend r, remove following Rec
55             rec.remove(i);
56         }
57     }
58     rec.add(i, r);
59   }
60 }
61 
62 class Rec {
63   int a;  // beginning serial number
64   int b;  // ending serial number
65   char c; // status code
66   int t;  // transfer code;
67 
68   Rec( int aIn, int bIn, char cIn, int tIn) {
69     a = aIn;
70     b = bIn;
71     c = cIn;
72     t = tIn;
73   }
74 }