COSEQUENCIAL PROCESSING AND THE SORTING OF LARGE FILES

An Object Oriented Model for Implementing Cosequential Processes

cosequential operations

Operations which involve accessing two or more input files sequentially and in parallel, resulting in one or more output files produced by the combination of the input data.

---

 

 Considerations for Cosequential Algorithms

 

• Initialization - What has to be set up for the main loop to work correctly.
• Getting the next item on each list - This should be simple and easy, from the main algorithm.
• Synchronization - Progress of access in the lists should be coordinated.
• Handling End-Of-File conditions - For a match, processing can stop when the end of any list is reached.
• Recognizing Errors - Items out of sequence can "break" the synchronization.

¶ 8.1.2 Matching Names in Two Lists

 

T E R M S

match

The process of forming a list containing all items common to two or more lists.

---

   Cosequential Match Algorithm

 

• Initialize (open the input and output files.)
• Get the first item from each list.
• While there is more to do:
  • Compare the current items from each list.
  • If the items are equal,
    • Process the item.
    • Get the next item from each list.
    • Set more to true iff none of this lists is at end of file.
  • If the item from list A is less than the item from list B,
    • Get the next item from list A.
    • Set more to true iff list A is not at end-of-file.
  • If the item from list A is more than the item from list B,
    • Get the next item from list B.
    • Set more to true iff list B is not at end-of-file.
• Finalize (close the files.)

Cosequential Match Code

 

• void Match (char * InputName1, 
              char * InputName2,
              char * OutputName) {
    /* Local Declarations                      */
    OrderedFile Input1;
    OrderedFile Input2;
    OrderedFile Output;
    int Item1;
    int Item2;
    int more;
  
    /* Initialization                          */
    cout << "Data Matched:" << endl;
    Input1.open (InputName1, ios::in);
    Input2.open (InputName2, ios::in);
    Output.open (OutputName, ios::out);
    
    /* Algorithm                               */
    Input1 >> Item1;
    Input2 >> Item2;
    more = Input1.good() && Input2.good();
    while (more) {
      cout << Item1 << ':' << Item2 << " => " << flush;  /* DEMO only */
      if (Item1 < Item2) {
        Input1 >> Item1;
        cout << '\n';                           /* DEMO only */
      } else if (Item1 > Item2) {
        Input2 >> Item2;
        cout << '\n';                           /* DEMO only */
      } else {
        Output << Item1 << endl;
        cout << Item1 << endl;                  /* DEMO only */
        Input1 >> Item1;
        Input2 >> Item2;
      }
      more = Input1.good() && Input2.good();
    }
  
    /* Finalization                            */
    Input1.close ();
    Input2.close ();
    Output.close ();
  } 

  Heaps

   

  Logical Structue of a Heap

   
  
• A heap is a version of binary tree.
• A heap is ordered along each branch, from the root to any of the leaves.
• A heap is not ordered in the left-right method of a binary search tree.
• A heap is not ordered horizontally, within the tree levels.
• A heap is ordered vertically, from the leaves to the root.
• A heap is a complete binary tree.
• All levels of a heap are filled, except for the lowest.
• The lowest level is filled from left to right.
• The root of a heap is always the lowest (or highest) item in the heap.

 

Physical Structue of a Heap

 

• The nodes of a heap are stored physically in an array.
• The root of the tree is in the first element of the array.
• The children of the node at location n are at locations 2n and 2n + 1.
• The parent of the node at location n is at location n/2.

Building a Heap

 

• A heap is built by inserting elements at the end of the heap, as a new leaf, and then "sifting up," sorting the branch from the new leaf to the root.
• Example:
• Insert R: R
• Insert L: R L

• 	R
  L

• Sift L: L R

• 	L
  R

• Insert C: L R C

• 	L
  R		C

• Sift C: C R L

• 	C
  R		L

• Insert A: C R L A

• 		C
  	R		L
  A

• Sift A: A C L R

• 		A
  	C			L
  R

• Insert H: A C L R H

• 			A
  	C				L
  R		H

• Sift H: A C L R H

• 			A
  	C				L
  R		H

• Insert V: A C L R H V

• 			A
  	C				L
  R		H		V

• Sift V: A C L R H V

• 			A
  	C				L
  R		H		V

• Insert E: A C L R H V E

• 			A
  	C				L
  R		H		V		E

• Sift E: A C E R H V L

• 			A
  	C				E
  R		H		V		L