Chapter 10: Case Studies II


10.1 Case Study 2

10.1.1 The Program

The case studies in this book are intended to demonstrate the use of some of the concepts presented in the preceding chapters of this section of the book. The defects analyzed are the actual mistakes made by the author when developing this software. Different people are prone to make different mistakes. Focus on the method used in debugging, rather than the particular error in question.

This example presents a lexicographic sort that works on arrays of integers written in Java. The original design for this algorithm can be found in Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms [AHU74]. A lexicographic sort orders a set of tuples or strings of values. Dictionaries for natural languages have entries sorted in lexicographic order. The tuples do not have to be the same length, and in general they are not the same length. Given the following set of integer tuples,

 2 4  3 2 1  1 2 3 5  3 1 2 4  1 3 5  3 4 2  2 3 5  2 5 

performing a lexicographic sort of this set produces the following output:

 1 2 3 4 5  1 3 5  2 3 5  2 4  2 5  3 1 2 4  3 2 1  3 4 2 

The algorithm works as follows:

  1. Find the length of the longest tuple.

  2. Make lists of value and location pairs that appear in the tuples.

  3. Bucket sort the lists of value and location pairs.

  4. Create lists of unique values at each location.

  5. Make lists of all strings of the same length.

  6. Process each group of tuples of the same length from longest to shortest.

  7. Add to the queue the tuples of the same length.

  8. Sort the tuples in the queue into buckets according to the value at the current position.

  9. Read the tuples from buckets that contain partially sorted tuples and write them to the queue for more processing.

The code for the original program is listed as follows:

 import java.util.Vector;  //------------------------------------------------------ // Input:  //   A sequence of string (tuples), A[1], A[2], ..  //    A[n-1],  //   whose components are integers in the range 0 to  //    m-1. Let l[i] be the  //   length of A[i] = (a[ill, a[i2l, ., a[il,i]).  // Output:   //   A permutation B[1], B[2], ., B[n]  //   of the A[i]’s such that B[1] <= B[2] <= ... <= B[n]  //  //------------------------------------------------------ public final class Sort {      public static Vector lexSortTuples(                           int [][] tupleList) {          // find the length of the longest tuple          int maxLen= -1;          int tupleListLen= tupleList.length;          for ( int j= 0; j<tupleListLen; ++j ) {              int [] tuple= tupleList[j];              maxLen= Math.max(maxLen, tuple.length);          }          // make list of value/location pairs that          // appear in the tuples          int maxVal= -1;          Vector pairList= new Vector();          for ( int j=0; j<tupleListLen; ++j ) {              int [] tuple= tupleList[j];              int tupleLen= tuple.length;              for ( int k=0; k<tupleLen; ++k ) {                  int value= tuple[k];                  maxVal= Math.max(maxVal, value);                  int [] pair= new int[2];                  pair[0]= k+1;                  pair[1]= value;                  pairList.addElement(pair);              }          }          // bucket sort lists of value/location pairs          Vector bucket2= new Vector(1+maxVal);          for ( int i=0; i<bucket2.size(); ++i ) {               bucket2.setElementAt(new Vector(), i);          }          Vector bucket1= new Vector(1+maxLen);          for ( int i=0; i<bucket1.size(); ++i ) {              bucket1.setElementAt(new Vector(), i);          }          for ( int j=0; j<pairList.size(); ++j) {              int [] pair= (int [])pairList.                            elementAt(j);              Vector bucket= (Vector)bucket2.                              elementAt(pair[1]);              bucket.addElement(pair);              bucket2.setElementAt(bucket, pair[1]);          }          for ( int j=0; j<bucket2.size(); ++j) {              pairList= (Vector) bucket2.elementAt(j);              for ( int k=0; k<pairList.size(); ++k) {                  int [] pair= (int [])pairList.                                elementAt(k);                  Vector bucket= (Vector)bucket1.                                  elementAt(pair[0]);                  bucket.addElement(pair);                  bucket1.setElementAt(bucket, pair[0]);              }          }          // create lists of unique values at          // each location          Vector unique= new Vector(1+maxLen);          for ( int i= 0; i<unique.size(); ++i ) {              unique.setElementAt(new Vector(), i);          }          for ( int j= 0; j<bucket1.size(); ++j ) {              pairList= (Vector)bucket1.elementAt(j);              int [] prev= new int[2];              prev[0]= -1;              prev[1]= -1;              for ( int k= 0; k < pairList.size(); ++k ) {                  int [] curr= (int [])pairList.                              elementAt(k);                 if ( prev[1] != curr[1] ) {                     Vector update= (Vector)unique.                                     elementAt(j);                     update.addElement(new Integer(                                        curr[1]));                     unique.setElementAt(update, j);                 }                 prev= curr;              }          }          // make lists of all strings of same length          Vector sameLen= new Vector();          for ( int i= 0; i<maxLen+1; ++i ) {              sameLen.addElement(new Vector());          }          for ( int j=0; j<tupleListLen; ++j ) {              int [] tuple= tupleList[j];              int tupleLen= tuple.length;              Vector update= (Vector)sameLen.                              elementAt(tupleLen);              update.addElement( tuple );              sameLen.setElementAt(update, tupleLen);          }          Vector buckets= new Vector(maxVal);          for ( int i=0; i<buckets.size(); ++i ) {              buckets.addElement(new Vector());          }          Vector queue= new Vector();          // process each group of tuples of the same          // length from longest to shortest          for ( int k=maxLen; k>=0; --k ) {              // add to the queue tuples of length k               queue.addElement( sameLen.elementAt(k) );              // sort tuples in queue into buckets              // according to value at this position              while ( 0 != queue.size() ) {                  int [] tuple= (int []) queue.                                elementAt(0);                  int index= tuple[k-1] - 1;                  queue.removeElementAt(0);                  Vector update= (Vector)buckets.                                  elementAt(index);                  update.addElement(tuple);                  buckets.setElementAt(update, index);              }              // read tuples from buckets that contain              // partially sortedtuples and write them              // to the queue for more processing              Vector group= (Vector)unique.elementAt(k);              for ( int j=0; j<group.size(); ++j ) {                  int index= ((Integer)group.                            elementAt(j)).intValue() - 1;                  int [] tuple= (int []) buckets.                                 elementAt(index);                  queue.addElement(tuple);                  buckets.setElementAt(null, index);              }          }          return queue;      }  } 

10.1.2 Bug 1

10.1.2.1 The evidence

The first debugging session began by running the application. The test input and test driver are shown as follows:

 import java.util.Vector;  public final class AlgRec {      static int [] [] tuples= {          {2, 4}, {3, 2, 1}, {1, 2, 3, 5},          {3, 1, 2, 4}, {1, 3, 5}, {3, 4, 2}, {2, 3, 5},          {2, 5} };      public static void main(String args[]) {          Vector out= Sort.lexSortTuples(tuples);          for( int i=0; i<out.size(); ++i ) {              int [] tuple= (int [])out.elementAt(i);              for( int j=0; j<tuple.length; ++j ) {                  System.err.print(tuple[j]+" ");              }              System.err.print("\n");          }      }  }   The results of executing this test are shown below.  Exception in thread "main" java.lang.ArrayIndexOutOfBounds                                           Exception: 2 >= 0          at java.util.Vector.elementAt(Vector.java:427)          at Sort.lexSortTuples(Sort.java:57)          at AlgRec.test(AlgRec.java:33)          at AlgRec.main(AlgRec.java:7) 

10.1.2.2 The investigation

We do not need to create a test case or cut down the input data set, since we already have a test case with a handful of data elements. We decide to use the observation-hypothesis-experiment method for investigating this problem.

Observation 1: Our initial observation is that we have an ArrayIndexOutOf

BoundsException event, in which index 2 is specified, but the length of the vector is 0. This occurs in method LexSortTuples at line 57.

Hypothesis 1: Our initial hypothesis is that the variable maxVal is not computed correctly. This variable is used in the construction of the vector that we are having problems accessing.

Experiment 1: Our first experiment is to print values of maxVal and maxLen after they are computed.

Observation 2: Our next observation is that maxLen =4 and maxVal =4 . These are correct.

Hypothesis 2: Since our first hypothesis was not correct, we fall back on a more general assertion that bucket2 is not constructed correctly.

Experiment 2: Our next experiment is to print the size of bucket1 and bucket2 after their construction.

Observation 3: The results of this experiment are that both vectors have a size of 0.

Hypothesis 3: Our next hypothesis is that we have used the method Vector.setElement when we should have used Vector.addElement.

Experiment 3: We change the source to use addElement instead.

Observation 4: The results of this experiment are that both vectors still have a size of 0. Clearly, elements are not getting added to the vectors.

Hypothesis 4: If the body of the loop is not the problem, then it must be the controls. We assert that the loop limits are incorrect.

Experiment 4: We look at the code and see that the loop is controlled by an upper limit based on the size() of the vector, instead of its capacity(). Since we have not added any elements to the vector, the size() will always be zero.

10.1.2.3 The fault and the correction

Since the loops in this code were cloned from an initial exemplar, we assume that we have made the same mistake elsewhere. This turns out to be true. The loops that initialize the variables unique and sameLen have the exact same problem.

We change three loops to use a different upper limit and a different method for adding elements, like the following:

 for ( int i=0; i<bucket2.capacity(); ++i ) {       bucket2.addElement(new Vector()); 

We change one loop to use a different upper limit, per the following:

 for ( int i=0; i<buckets.capacity(); ++i ) { 

These errors are more characteristic of a novice than an expert. Unfortunately, when it comes to bugs, a moment of fatigue, illness, or distraction can turn any expert into an amateur.

In this round of debugging, we applied the following methods from Chapter 9:

  • Use runtime subscript checking.

  • Display variable values.

We found two defects that both had the same root causes, which are explained in Chapter 11:

  • Initialization errors—aggregate variable always uninitialized

  • Reference errors—wrong procedure called

10.1.3 Bug 2

10.1.3.1 The evidence

The next debugging session began by running the same test application. The results of executing this test are shown as follows:

 Exception in thread "main" java.lang.ClassCastException:                             java.util.Vector          at Sort.lexSortTuples(Sort.java:130)          at AlgRec.test(AlgRec.java:33)          at AlgRec.main(AlgRec.java:7) 

10.1.3.2 The investigation

Observation 1: Our initial observation is that we have a ClassCastException: java.util.Vector event, with a java.util.Vector object. This occurs in method lexSortTuples at line 130.

Hypothesis 1: The wrong object has been appended to the vector being referenced.

Experiment 1: There are two statements that append elements to the variable in question. We replace each with a call to a procedure that displays the type of the arguments before appending the value.

10.1.3.3 The fault and correction

The code is trying to convert a vector to an array of int because an entire vector was appended to another vector (the queue) as a single element. Instead, each int array tuple should have been appended separately to the queue.

We replace the following statement

 queue.addElement( sameLen.elementAt(k) ); 

with a loop that does the appropriate initialization:

 Vector tupleSet= (Vector)sameLen.elementAt(k);  for ( int i=0; i<tupleSet.size(); ++i) {      queue.addElement( (int [])tupleSet.elementAt(i) );  } 

We use almost identical code to replace the second statement that adds elements to the end of the queue variable.

In this round of debugging, we applied the following method from Chapter 9:

  • Display procedure arguments.

We found two defects that had the following root causes, explained in Chapter 11:

  • Dynamic data-structure problems—invalid type conversion

  • Initialization errors—aggregate variable initialized with wrong values

10.1.4 Bug 3

10.1.4.1 The evidence

The next debugging session began by running the same application. The results of executing this test are shown as follows:

 Exception in thread "main" java.lang.NullPointerException          at Sort.lexSortTuples(Sort.java:135)          at AlgRec.test(AlgRec.java:33)          at AlgRec.main(AlgRec.java:7) 

10.1.4.2 The investigation

Observation 1: The variable that is a null reference, update, is created by extracting an element from the buckets vector. There is one statement that appends elements to this variable. It always appends a new vector, so it cannot be the cause of the problem. There are two places that set the elements of this vector. One of them always assigns a null pointer to the element it sets.

Hypothesis 1: The statement that sets elements of the variable in question to null pointers should instead be setting them to empty vectors.

Experiment 1: Change the statement and rerun the program.

10.1.4.3 The fault and correction

We change the assignment of the buckets variable to use empty vectors instead of null references.

 buckets.setElementAt(new Vector(), index); 

In this round of debugging, we applied the following methods from Chapters 2 and 3:

  • Eliminate impossible causes

  • Use a system for organizing facts

We found one defect that had the following root causes, which are explained in Chapter 11:

  • Dynamic data-structure errors—uninitialized pointer dereferenced

  • Initialization errors—aggregate variable initialized with wrong value

10.1.5 Bug 4

10.1.5.1 The evidence

The next debugging session began by running the application. The results of executing this test are shown as follows:

 Exception in thread "main"  java.lang.ArrayIndexOutOfBoundsException          at Sort.lexSortTuples(Sort.java:132)          at AlgRec.test(AlgRec.java:33)          at AlgRec.main(AlgRec.java:7) 

10.1.5.2 The investigation

Observation 1: The variable that was used in the array index is k, which is a loop index running from maxLen to 0.

Hypothesis 1: There are invalid values in the tuples.

Experiment 1: We insert code to print tuple values as they are picked from

 queue.  for( int z=0; z<tuple.length; ++z) {      System.err.print(tuple[z]+" ");  }  System.err.print("\n"); 

Observation 2: All tuple values are all valid.

Hypothesis 2: Since the arrays are valid, the array indices must be invalid. The loop counter k’s last value should be 1, not 0, since the index variable is having 1 subtracted from it.

Experiment 2: We change the loop control accordingly. We also print the value of k before the array reference that caused a problem, just in case our hypothesis is not correct.

10.1.5.3 The fault and correction

We change the loop limit per the following:

 for ( int k=maxLen; k>=1; --k ) { 

In this round of debugging, we applied the following methods from Chapter 9:

  • Use runtime subscript checking.

  • Display data structures.

Of course, we did not actually have to do anything to get the runtime subscript checking, since Java does it automatically. Still, we should get credit for using it, since we chose the implementation language for this program.

We found one defect that had the following root cause, explained in Chapter 11:

  • Control-flow problems—loop iterations off by one

10.1.5.4 Final test

The debugging process is not complete until the changes have been thoroughly tested. We present as follows a set of interesting tuples to exercise the sort program. While this set of test cases is far from exhaustive, it is suggestive of the kind of approach to take in unit testing. We have omitted the results of the tests from the book in the interest of brevity. The listing takes several pages, and all the tests passed.

 import java.util.Vector;  public final class AlgRec {      public static void main(String args[]) {          test(tuples01);          test(tuples02);          test(tuples03);          test(tuples04);          test(tuples05);          test(tuples06);          test(tuples07);          test(tuples08);          test(tuples09);          test(tuples10);          test(tuples11);          test(tuples12);          test(tuples13);          test(tuples14);          test(tuples15);          test(tuples16);          test(tuples17);          test(tuples18);          test(tuples19);          test(tuples20);          test(tuples21);          test(tuples22);      }      private static void test(int [][] tuples) {          Vector out= Sort.lexSortTuples(tuples);          for( int i=0; i<out.size(); ++i ) {              int [] tuple= (int [])out.elementAt(i);              for( int j=0; j<tuple.length; ++j ) {                  System.err.print(tuple[j]+" ");              }              System.err.print("\n");          }          System.err.println("----------\n");      }  //------------------------------------------------------ // ----- same length tuples  //       ascending values  static int [] []  tuples01=  { { 3,2,1 }, { 6,5,4 }, { 9,8,7 } };  //       descending values  static int [] [] tuples02=  { { 9,8,7 }, { 6,5,4 }, { 3,2,1 } };  //       "V" pattern values  static int [] [] tuples03=  { { 19,20,21 }, { 10,11,12 }, { 7,8,9 }, { 1,2,3  },    { 4,5,6 }, { 13,14,15 }, { 16,17,18 } };  //       inverse "V" pattern values  static int [] [] tuples04=  { { 4,5,6 }, { 10,11,12 }, { 16,17,18 }, { 19,20,21 },    { 13,14,15 }, { 7,8,9 }, { 1,2,3 } };  //       random values  static int [] [] tuples05=  { { 2, 71, 3 }, { 67, 5, 61 }, { 7, 59, 11 },     { 57, 13, 53 },  { 17, 47, 23 }, { 43, 29, 41 },     { 31, 37, 71 } };  // ----- random length tuples  //       ascending values  static int [] [] tuples06=  { { 2, 3 }, { 5, 7, 11, 13 },    { 17, 19, 23, 29, 31, 37 },  { 41, 43, 47 },    { 53, 57, 59, 61, 67 },    { 71, 73, 79, 83, 87, 89, 97 },    { 101, 103, 107, 109, 111, 113, 127, 131 } };  //       descending values  static int [] [] tuples07=  { { 131, 127, 113 },    { 111, 109, 107, 103, 101, 97, 89 },    { 87, 83, 79, 73, 71 },    { 67, 61, 59, 57, 53, 47, 43 },    { 41, 37, 31, 29, 23 }, { 19, 17, 13 },    { 11, 7, 5, 3, 2 } };  //       "V" pattern values  static int [] [] tuples08=  { { 109, 103, 97 }, { 87, 79, 71, 61 }, { 57, 47 },    { 43, 53, 59 },   { 2, 3, 5, 7, 11, 13 },    { 17, 19, 23 }, { 29, 31, 37, 41 },    { 67, 73, 83, 89, 101, 107 }, { 111, 113, 127, 131 } };  //       inverse "V" pattern values  static int [] [] tuples09=  { { 5, 7, 17, 19, 31, 37, 47, 53},    { 61, 67, 79, 83, 97, 101 },    { 109, 111, 113, 127, 131 }, { 57, 87, 89, 103, 107 },    { 73, 59, 71, 41 }, { 43, 23, 29, 11 }, { 13, 2, 3 } };  //       random values  static int [] [] tuples10=  { {43, 29, 41, 31, 37 }, {2, 71 }, {3, 67, 5, 61, 7 },    {59, 11, 57 }, {13, 53, 17, 47, 23 } };  // ----- ascending length tuples  //       ascending values  static int [] [] tuples11=  { { 2, 3 }, { 5, 7, 11 }, { 13, 17, 19, 23 },    { 29, 31, 37, 43, 41 },  { 43, 47, 53, 57, 59, 61 },    { 67, 71, 73, 79, 83, 87, 89 },    { 97, 101, 103, 107, 109, 111, 113, 127 } };  //       descending values  static int [] [] tuples12=  { { 131, 127 }, { 113, 111, 109 },    { 107, 103, 101, 97 },  { 89, 87, 83, 79, 73 },    { 71, 67, 61, 59, 57, 53 },    { 47, 43, 41, 37, 31, 29, 23 },    { 19, 17, 13, 11, 7, 5, 3, 2  } };  //       "V" pattern values  static int [] [] tuples13=  { { 109, 103 }, { 97, 87, 79} , { 71, 61, 57, 47} ,    { 5, 2, 3, 7, 13} , { 19, 41, 31, 23, 17, 11} ,    { 29, 37, 43, 53, 59, 67, 73} ,    { 83, 89, 101, 107, 111, 113, 127, 131 } };  //       inverse "V" pattern values  static int [] [] tuples14=  { { 5, 7 }, { 17, 19, 31 }, { 37, 47, 53, 61 },    { 67, 79, 83, 97, 101 }, { 109, 111, 113, 127, 131 },    { 57, 87, 89, 103, 107 }, { 59, 71, 41, 43, 73 },    { 23, 29, 11 }, { 13, 2, 3 } };  //       random values  static int [] [] tuples15=  { { 109, 103, }, { 97, 87, 79, }, { 71, 61, 57, 47 },    { 5, 2, 3, 7, 13, }, { 19, 41, 31, 23, 17, 11, },    { 29, 37, 43, 53, 59, 67, 73, },    { 83, 89, 101, 107, 111, 113, 127 } };  // ----- descending length tuples  //       ascending values  static int [] [] tuples16=  { { 2, 3, 5, 7, 11, 13, 17, 19 },    { 23, 29, 31, 37, 43, 41, 43 },    { 47, 53, 57, 59, 61, 67 }, { 71, 73, 79, 83, 87 },    { 89, 97, 101, 103 }, { 107, 109, 111 }, { 113, 127 } };  //       descending values  static int [] [] tuples17=  { { 131, 127, 113, 111, 109, 107, 103, 101 },    { 97, 89, 87, 83, 79, 73, 71 },    { 67, 61, 59, 57, 53, 47 }, { 43, 41, 37, 31, 29 },    { 23, 19, 17, 13 }, { 11, 7, 5 }, { 3, 2 } };  //       "V" pattern values  static int [] [] tuples18=  { { 109, 103, 97, 87, 79, 71, 61, 57 },    { 47, 5, 2, 3, 7, 13, 19, 41 },    { 31, 23, 17, 11, 29, 37 }, { 43, 53, 59, 67, 73 },    { 83, 89, 101, 107 },    { 111, 113, 127 } };  //       inverse "V" pattern values  static int [] [] tuples19=  { { 5, 7, 17, 19, 31, 37, 47, 53},    { 61, 67, 79, 83, 97, 101 },    { 109, 111, 113, 127, 131 }, { 57, 87, 89, 103, 107 },    { 73, 59, 71, 41 }, { 43, 23, 29, 11 }, { 13, 2, 3 } };  //       random values  static int [] [] tuples20=  { { 83, 89, 101, 107, 111, 113, 127 },    { 29, 37, 43, 53, 59, 67, 73, },    { 19, 41, 31, 23, 17, 11, }, { 5, 2, 3, 7, 13, },    { 71, 61, 57, 47 }, { 97, 87, 79, }, { 109, 103, } };  // ----- duplicates  static int [] [] tuples21=  { { 109, 103, 97 }, { 87, 79, 71, 61 },    { 89, 101, 107, 111 },{ 57, 47, 41 },    { 31, 23, 17, 11 }, { 5, 2, 3 }, { 7, 13, 19, 29 },    { 57, 47, 41 }, { 37, 43, 53 }, { 59, 67, 73, 83 },    { 109, 103, 97 }, { 89, 101, 107, 111 } };  // ----- singleton  static int [] [] tuples22=  { { 109, 103, 97, 87, 79, 71, 61, 57, 47, 41, 31, 23,      17, 11, 5, 2, 3, 7, 13, 19, 29, 37, 43, 53, 59,      67, 73, 83, 89, 101, 107, 111 } };  } 

10.1.5.5 Final source

The code for the final program is listed as follows:

 import java.util.Vector;  //======================================================  // Sort  // this class contains specialized sorting methods to  // be called statically  //======================================================  public final class Sort {  //------------------------------------------------------ // Input:  //   A sequence of string (tuples),  //    A[0], A[1], .. A[n-1],  //   whose components are integers in the range 0 to  //    m-1. Let l[i] be the  //   length of A[i] = (a[il], a[i2], ., a[il,i]).  // Output:  //   A permutation B[1], B[2], ., B[n]  //   of the A[i]’s such that B[1] <= B[2] <= ... <= B[n]  //  //------------------------------------------------------     public static Vector lexSortTuples(                           int [][] tupleList) {          // find the length of the longest tuple          int maxLen= -1;          int tupleListLen= tupleList.length;          for ( int j= 0; j<tupleListLen; ++j ) {              int [] tuple= tupleList[j];              maxLen= Math.max(maxLen, tuple.length);          }          // make list of value/location pairs that          // appear in the tuples          int maxVal= -1;          Vector pairList= new Vector();          for ( int j=0; j<tupleListLen; ++j ) {              int [] tuple= tupleList[j];              int tupleLen= tuple.length;              for ( int k=0; k<tupleLen; ++k ) {                  int value= tuple[k];                  maxVal= Math.max(maxVal, value);                  int [] pair= new int[2];                  pair[0]= k+1;                  pair[1]= value;                  pairList.addElement(pair);              }          }          // bucket sort lists of value/location pairs          Vector bucket2= new Vector(1+maxVal);          for ( int i=0; i<bucket2.capacity(); ++i ) {              bucket2.addElement(new Vector());          }          Vector bucket1= new Vector(1+maxLen);          for ( int i=0; i<bucket1.capacity(); ++i ) {              bucket1.addElement(new Vector());          }          for ( int j=0; j<pairList.size(); ++j) {              int [] pair= (int [])pairList.                            elementAt(j);              Vector bucket= (Vector)bucket2.                              elementAt(pair[1]);              bucket.addElement(pair);              bucket2.setElementAt(bucket, pair[1]);          }          for ( int j=0; j<bucket2.size(); ++j) {              pairList= (Vector) bucket2.elementAt(j);              for ( int k=0; k<pairList.size(); ++k) {                  int [] pair= (int [])pairList.                                elementAt(k);                  Vector bucket= (Vector)bucket1.                                  elementAt(pair[0]);                  bucket.addElement(pair);                  bucket1.setElementAt(bucket, pair[0]);              }          }          // create lists of unique values at          // each location          Vector unique= new Vector(1+maxLen);          for ( int i= 0; i<unique.capacity(); ++i ) {              unique.addElement(new Vector());          }          for ( int j= 0; j<bucket1.size(); ++j ) {              pairList= (Vector)bucket1.elementAt(j);              int [] prev= new int[2];              prev[0]= -1;              prev[1]= -1;              for ( int k= 0; k < pairList.size(); ++k ) {                 int [] curr= (int [])pairList.                               elementAt(k);                 if ( prev[1] != curr[1] ) {                     Vector update= (Vector)unique.                                     elementAt(j);                     update.addElement(new Integer(                                       curr[1]));                     unique.setElementAt(update, j);                 }                 prev= curr;              }          }          // make lists of all strings of same length          Vector sameLen= new Vector();          for ( int i= 0; i<maxLen+1; ++i ) {              sameLen.addElement(new Vector());          }          for ( int j=0; j<tupleListLen; ++j ) {              int [] tuple= tupleList[j];              int tupleLen= tuple.length;              Vector update= (Vector)sameLen.                             elementAt(tupleLen);              update.addElement( tuple );              sameLen.setElementAt(update, tupleLen);          }          Vector buckets= new Vector(maxVal);          for ( int i=0; i<buckets.capacity(); ++i ) {              buckets.addElement(new Vector());          }          Vector queue= new Vector();          // process each group of tuples of the          // same length from longest to shortest          for ( int k=maxLen; k>=1; --k ) {              // add to the queue tuples of length k              Vector tupleSet= (Vector)sameLen.                               elementAt(k);              for ( int i=0; i<tupleSet.size(); ++i) {                  queue.addElement( (int [])tupleSet.                                    elementAt(i) );              }              // sort tuples in queue into buckets              // according to value at this position              while ( 0 != queue.size() ) {                  int [] tuple= (int []) queue.                                 elementAt(0);                  int index= tuple[k-1] - 1;                  queue.removeElementAt(0);                  Vector update= (Vector)buckets.                                  elementAt(index);                  update.addElement(tuple);                  buckets.setElementAt(update, index);              }              // read tuples from buckets that contain              // partially sorted tuples and write them              // to the queue for more processing              Vector group= (Vector)unique.elementAt(k);              for ( int j=0; j<group.size(); ++j ) {                  int index= ((Integer)group.                             elementAt(j)).intValue() - 1;                  tupleSet= (Vector) buckets.                                     elementAt(index);                  for ( int i=0; i<tupleSet.size(); ++i) {                      queue.addElement( (int [])tupleSet.                                        elementAt(i) );                  }                  buckets.setElementAt(new Vector(),                                         index);              }          }          return queue;      }  } 




Debugging by Thinking. A Multidisciplinary Approach
Debugging by Thinking: A Multidisciplinary Approach (HP Technologies)
ISBN: 1555583075
EAN: 2147483647
Year: 2002
Pages: 172

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net