Help me rid this segmentation fault

This is a discussion on Help me rid this segmentation fault within the C++ Programming forums, part of the General Programming Boards category; Sorry for the long post of code, but I have a programming assignment that is supposed to focus on heaps, ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    8

    Help me rid this segmentation fault

    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.

    Code:
    /* 
    
    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;
    }
    Code:
    0 30
    10 20
    30 10

  2. #2
    WDT
    WDT is offline
    Tha 1 Sick RAT
    Join Date
    Dec 2003
    Posts
    271
    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??
    A hundred Elephants can knock down the walls of a fortress... One diseased rat can kill everyone inside

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    8
    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

    Code:
    /* 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
    Code:
    #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;
    }

  4. #4
    WDT
    WDT is offline
    Tha 1 Sick RAT
    Join Date
    Dec 2003
    Posts
    271
    Right two things:
    Code:
    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:
    Code:
    // 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.
    Last edited by WDT; 03-24-2004 at 10:49 AM.
    A hundred Elephants can knock down the walls of a fortress... One diseased rat can kill everyone inside

  5. #5
    Registered User
    Join Date
    Mar 2004
    Posts
    8
    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

    Code:
    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:

    Code:
        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.

  6. #6
    WDT
    WDT is offline
    Tha 1 Sick RAT
    Join Date
    Dec 2003
    Posts
    271
    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.....
    A hundred Elephants can knock down the walls of a fortress... One diseased rat can kill everyone inside

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Code:
    >    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Re: Segmentation fault
    By turkish_van in forum C Programming
    Replies: 8
    Last Post: 01-20-2007, 05:50 PM
  2. Segmentation fault
    By bennyandthejets in forum C++ Programming
    Replies: 7
    Last Post: 09-07-2005, 06:04 PM
  3. Segmentation fault
    By NoUse in forum C Programming
    Replies: 4
    Last Post: 03-26-2005, 03:29 PM
  4. Locating A Segmentation Fault
    By Stack Overflow in forum C Programming
    Replies: 12
    Last Post: 12-14-2004, 01:33 PM
  5. Segmentation fault...
    By alvifarooq in forum C++ Programming
    Replies: 14
    Last Post: 09-26-2004, 01:53 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21