/*		CPSC 215 LAB 10 : Heaps, 11/18/99


For this lab you need to implement the heap data strucuture and the
basic operations of insert and delete, culminating in a sorting method
that uses heaps and runs in worst case O(n log n) time.  The heaps you
use will have the LARGEST element stored at the root, and consequently
the "heap property" will be that the both children of a node will have
values LESS than their parent.  You may need to define supporting
methods to complete the assignment.

You also need to implement the various data structures using an 
object-oriented class strucure. In particular, you should hide the
details of the array implementation of heaps by declaring them as private.  

Instead of using just integers like the examples in class, you
are to store the following data type into your heaps:        */

class employee
{ String name;
  int salary;
  public employee(String s, int i) 
    { name = s; salary = i; }
  public void display()
    { System.out.println(name + " earns $" + salary + " per year."); }
}

/* That is, to represent a "heap of employees" in an array, you need
to create an array of employee objects (more precisely, an array of
pointers to empolyee objects).  Make the maximum size of your array 100.
Note that, since the array does not store integers, you can not use 
(easily) array cell at index 0 to store the last valid index of the array.
You'll have to define another varible for this purpose.

You are to make up most of the details of the assignment on your own.
However, I've given you methods that lets you read employee
information from a file.  You should try to understand how it works.
You will have to implement all the "private" details. The only things
"public" should be those listed in the template.  Note that these
methods are NOT static - so you will have to create an instance of the
employee_heap class in order to call them.
*/

import java.io.*;   // needed for file IO
public class employee_heap
{ 
  private BufferedReader filereader;  // read employee data from file

  employee[] heap;       // your array-represented heap - note NOT STATIC!
 
  employee_heap()   // constructor, opens file for IO
   { try {
     FileInputStream fis = new FileInputStream("payroll");
     filereader = new BufferedReader(new InputStreamReader(fis));
         } catch (Exception E) {}
   }

  // The following method will read the next employee info from the 
  // "payroll" file.  It will return an employee object, or null if 
  // there is no more data.
  public employee getEmployee()
   { String name, temp;  
     int salary;
   try {
     name = filereader.readLine();
     if (name == null) return null;
      else 
       { salary = Integer.parseInt(filereader.readLine());
         return new employee(name,salary);
       } // else
       } catch (Exception E) { return null; }
   } // getEmployee


 // public employee deletemax()   // deletes and returns employee with 
                                // largest salary.
//  public void insert(employee e) // inserts new employee into heap.


  /* To sort using a heap, first insert all data (read from file)
     into a heap, then keep deleting the maximum element.  As you
     delete a max element from the root, don't just throw it away, 
     but put it at the FORMER last position in the array. Let's say
     the current last valid index is 8, the algorithm described in
     class says, to delete the root, move heap[8] to the root (heap[1]),
     then propagate downwards.  If you instead SWAP heap[8] with heap[1],
     which you know has the largest value, then you have effectively put
     the largest element at the end of the array.  Subsequent operations
     should never effect this node, since the last valid index would have
     been decremented.
  */

//  public void heapsort()  // heapsort the empolyees by the salaries they earn
                          // in DECREMENTAL order, printing out the sorted
                          // list of employees.

  public static void main(String[] args)  // demonstration.
  {}
} // end employee_heap


  /* NOTE: unlike the previous definition of trees (using pointers), here
     the left and right descendents of a node are only singular nodes, and
     not subtrees.  The definition of the structure is not as "recursive"
     as before, and as a result, you won't really have to use recursion
     that much in this lab. */
 

/*   -- Heaps are covered in the textbook starting at page 250 --   */