Help me rid this segmentation fault

[Nornny]

Sorry for the long post of code, but I have a programming assignment that is supposed to focus on heaps, inheritance, and I/O and command line arguments. I think I have the heaps and inheritance down but I'm still receiving a segmentation fault in the timestepping where (if time == inOffice->departuretime) and I have no idea.

I'm also pasting the test.txt file for further reference. Thanks in advance for any help or typos you can find.

/* 

This is the Office Hours simulation program. It simulates what happens 
during a professor's office hours, with students lining up and waiting. 
"Students" are read through a text file that contains lines of two ints, 
the arrival time and request time.

The simulation is to calculate the average wait time of all the students
in one text file, the wait time being how long a student has to wait before
he/she enters the office. This is done through a heap, with the priority
of each student being 1) the time they arrive (First Come First Served) and
then 2) their request time (Shortest Request First).  

*/
#include <iostream>
#include <fstream>
#include "heap.h"
#include <string>

using namespace std;

class student : public HeapItem {
 public:
  int ID;
  int arrivaltime;
  int requesttime;
  int waitingtime;
  int departuretime;

  int enteredOffice;

  student(int who, int a, int r);
};


student::student(int who, int a, int r) {
  ID = who;
  arrivaltime = a;
  requesttime = r;
}

int main(int argc, char *argv[]) {

  char inputFilename[] = "test.txt";
  ifstream inFile;
  int rt;
  int at;
  int sumInQueue = 0;
  int averageWaitTime;
  Heap of;

  student *next = NULL;
  student *inOffice = NULL;

  inFile.open(inputFilename, ios::in);     // Open up file
 
  // Error check.
   if (!inFile)
    cerr << "Can't open input file " << inputFilename << endl;

   int studentnumber = 0;            // Will give unique ID to each student
   

   // timestep


   inFile >> at >> rt;
   student first = student(studentnumber, at, rt);
   studentnumber++;
   inOffice = &first;
   inOffice->enteredOffice = 0;
   inOffice->departuretime = inOffice->requesttime + inOffice->enteredOffice;

   inFile >> at >> rt;
   student second = student(studentnumber, at, rt);
   studentnumber++;
   next = &second;

   for (int time = 0; (next != NULL or !(of.isEmpty()) or 
	  inOffice != NULL) and !inFile.eof(); time++) {

     inFile >> at >> rt;
     student a = student(studentnumber, at, rt);
     studentnumber++;
  
     // if time == arrival time of the next student
     if (time == next->arrivaltime and next != NULL) {

       // Insert student into heap
       of.insertHeapItem(a, at);
       // Report this event
       cout << time << "     Student " << a.ID << " enters queue.\n";
       // Read next student, if one exists, and calculate time
       if (next != NULL) {
	 HeapItem m = of.removeMin();
	 student &n = static_cast<student&>(m);
	 next = &n;
       }
       else 
	 next = &a;
     }  

     // If time == departure time
     if (time == inOffice->departuretime) {
       // Calculate wait time
       sumInQueue = sumInQueue + 
	 (inOffice->enteredOffice - inOffice->arrivaltime);   
       // Report the event
       cout << time << "     Student " << inOffice->ID << " leaves office.\n";
       // remove the student from the office
       inOffice = NULL;    
     }

    // If no student in office and heap is not empty
    if (inOffice = NULL and of.isEmpty() == false) {
      // Remove a student from heap and put into office
      HeapItem h = of.removeMin();
      student s = static_cast<student&>(h);
      inOffice = &s;
      inOffice->enteredOffice = time;
      // Calculates departure time
      inOffice->departuretime = inOffice->requesttime 
	+ inOffice->enteredOffice;
      // Report this 
      cout << time << "     Student " << inOffice->ID << " enters office\n";
    }
  }

  return 0;
}

0 30
10 20
30 10

[WDT]

There are a few things wrong here but could ye post the heap.h so that I can compile this and run it and better understand. Also what compiler you using??

[Nornny]

Sure thing. :) Thank you so much for your help. I use g++ as my compiler. Any help here would also be appreciated, especially with the exceptions. If you need the .cpp file, it's also below

/* This is the header file for the implementation of a heap, which 
   will be used for the office hours program */

#ifndef HEAP_H
#define HEAP_H

#include <iostream> 

const int heapMaxSize = 20;

class UnderflowException {
 public:
  UnderflowException() 
    { std::cout << "Heap Underflow Error \n"; }
};
class OverflowException {
 public:
  OverflowException() 
    { std::cout << "Heap is full \n"; }
};

class HeapItem {
 public:
  int priority;     // Priority in queue
};

class Heap {
 public:

  Heap();                      // Constructor

  int left(int p)  const;      // Returns left position
  int right(int p) const;      // Returns right position
  int parent(int p) const;     // Returns parent position

  // Inserts a HeapItem with priority i.
  void insertHeapItem(HeapItem i, int p) throw(OverflowException);  

  HeapItem removeMin();        // Removes smallest element

  bool isEmpty() const;        // Checks to see if heap is empty
  bool isFull() const;         // Checks to see if heap is full

  int heapS(void);             // Size of heap
  int priority(int p);         // Returns priority of heap

  void swap(HeapItem& a, HeapItem& b);     // Swaps two items

 private:
  HeapItem array[heapMaxSize];
  int heapSize;
};



/*
class HeapTree {
 public:
  class HeapTreeNode {
   public:
    HeapItem node;     // The node <THIS COULD BE WRONG>
    HeapItem* left;    
    HeapItem* right;   
  };

  HeapTreeNode *root;
  HeapTree();             // Sets root to NULL
  ~HeapTree();            // invokes removeAllNodes()
  void removeAllNodes(HeapTreeNode *p);  // Recursively deletes all nodes

  int size(HeapTreeNode *p);             // Size of tree

  HeapTreeNode* findTreeNode(int s) // finds HeapItem and returns a pointer
    throw(ItemNotFound);            // to it

 
  void addTreeNode(int s);    // Adds HeapItem s to next available position
                              // Will first check size and then traverse
                              // tree from left to right until next 
                              // open position.

  void removeTreeNode(int s); // Removes node.
 
 private:
   const int max_heap_size = 20;  // Size of queue
}
*/
#endif

#include "heap.h"
#include <iostream>

using namespace std;


Heap::Heap() {
  heapSize = 0;

  int t = 0;

  while (t <= heapMaxSize - 1) {
    array[t].priority = -1;
    t++;
  }

}
int Heap::left(int p) const {
  int i = (p * 2) + 1;
  assert((i > 0) and (i < heapSize)) ;
  return i;
}

int Heap::right(int p) const {
  assert(p < (heapSize - 1)/2);
  return (p * 2) + 2;
}

int Heap::parent(int p) const{
  assert (p != 0);
  return (p - 1) / 2;
}

void Heap::insertHeapItem(HeapItem i, int p) throw(OverflowException) {

  try {
  if (isFull())                  // Stack Overflow exception
    throw OverflowException();
  }
  catch(OverflowException) {};

  HeapItem newItem;              // Creates new item
  newItem.priority = p;          // Sets priority

  array[heapSize] = newItem;     // next open array position gets item

  int positionNew = heapSize;    // Moves position up one
  heapSize++;                    // increments size

  // while positionNew is not the root and is greater than its parent
  while (positionNew != 0 and (array[positionNew].priority 
	 < array[parent(positionNew)].priority)) {

    swap(array[positionNew], array[parent(positionNew)]);  
    // Swap positions
    positionNew = parent(positionNew);
  }  
}

HeapItem Heap::removeMin() {
  assert (!isEmpty());


  HeapItem temp = array[0];
  int i = 0;
  int j;
  array[0] = array[heapSize - 1];
  --heapSize;
  while (left(0) > heapSize) {
    j = left(i);
    if (right(i) > heapSize 
	and array[right(i)].priority < array[left(i)].priority)
      j = right(i);
    if (array[i].priority < array[j].priority)
      break;
    swap(array[i], array[j]);
    i = j;
  }
  return temp;

  /*

  heapSize--;

  if (heapSize != 0) {   // If there's more than just the  root
    swap(array[0].priority, array[heapSize].priority);   
    // Switch largest with smallest 
    reHeap(0);                         // rearrange to proper places
  }
  return array[heapSize];        // Take off last(lowest) heap item

  */

}

void Heap::swap(HeapItem& a, HeapItem& b) {
  HeapItem temp = a;
  a = b;
  b = temp;
}
bool Heap::isEmpty() const {
  if (heapSize == 0)
    return true;
  else 
    return false;
}

bool Heap::isFull() const {
  if (heapSize == heapMaxSize)
    return true;
  else
    return false;
}

int Heap::heapS() {
  return heapSize;
}

int Heap::priority(int p) {
  return array[p].priority;
}

[WDT]

Right two things:

for (int time = 0; (next != NULL or !(of.isEmpty()) or inOffice != NULL) and !inFile.eof(); time++)

Remember when you or multiple statements only one of them need be true for the whole line to evaluate to true. In this case so long as next != NULL the rest of the cases aren't evaluated.
Then there's this line:

// If no student in office and heap is not empty
if (inOffice = NULL and of.isEmpty() == false) { //<--- you effectively nullify the inOffice variable right here. That what you want??

When I run your program I make the first pass and crash halfway through the second pass.
So the reason why you crash at that line should now be obvious.
Suggest you logically psuedocode this properly. then compare it to what you got.
Sorry it took this long but I slept most of the whole day. I also haven't properly gone through your whole code yet.

[Nornny]

lol. Thank you so much, the help you've given me so far is great! And I slept through most of the night when I should've been programming and checking this messageboard. lol. Thank you so much. The pseudo-code I was given to work with for this assignment, btw, is

for(time = 0; (next student exists OR heap not empty 
                      OR is a student in the professor's office); time++) {

         if( time == arrival time of next student if such exists ) {
            Insert this student into the heap;
            Report this event;
            Read the next student from the input file (if such exists); 
         }

         if( time == departure time of a student in the office ) {
            Remove the student from the office;
            Report this event;
         }

         if( no student in office AND heap is not empty ) {
            Remove a student from heap and put him/her in the office; 
            Report this event;
         }

       }

It doesn't calculate average wait time, but that is what I tried to work with.

I'm still getting the segmentation fault after keeping the first line you talked about (because I do want those or statements, I believe). But I did change the second line, although I don't think I did it the way you were talking about. With that line, I want it to go through the actions if the next pointer is not pointing to anyone BUT the heap of waiting students isn't empty. I did find a typing error and that line is now:

    if (inOffice == NULL and !(of.isEmpty())) {

I realized I forget an extra equal sign. I hope this leads me somewhere out of the holes of segmentation faults. I can't thank you enough for looking this over.

[WDT]

I gotta go catch a very important Football game (Soccer to the Yanks ) now and I'll go through it properly in about 3 hours time.
Gooo Arsenal.....

[swoopy]

>    if (inOffice = NULL and of.isEmpty() == false) {

Use equality, not assignment:
    if (inOffice == NULL and of.isEmpty() == false) {

Your main loop has some problems, for example, you shouldn't be reading from the file each time through the loop, only when the previous student arrives at the office and is placed on the heap. Also, you should be adding next to the heap, not a.

Your heap class has bugs, because when I called of.removeMin(), the assert failed in Heap::left().

Hopefully WDT can help you fix the bugs in your heap.