Segmentation Fault in between loops

Hi SterlingMcClung,
Why are you using new and delete in this loop.
You should not use new and delete, unless you're sure your code requires it.
The above code does not require it, and you can use concrete type like itset X;

Cheers!

Yes I know it does not need it.  I did that because without calling delete that way the destructor for Px does not get called at the end of the loop.

Sterling

>>I did that because without calling delete that way the destructor for Px does not get called at the end of the loop.

You still don't need it for that.
You can accomplish the same thing, by putting it into an explicit scope using {}
Once the code gets out of the scope, the destructor will get called automatically.

for(int i = 0; test2(7) && i<this->count && this->itsets[i]!=NULL; i++)
{ //For loop scope
  itset X;
  { //Explicit scope
     itree Px(count-i);
     //.... other code
  } //End explicit scope
  //... other code
} //End for loop

Just tried it again with concrete type and I get the segmentation fault after the destructor for X is called, but before the destructor for Px is called.

Sterling

I guess my orginal question should have included my last comment.

Sterling

Please post the code for the X type.

I added another itree in an explicit scope at the end of the loop as follows:

. . .
 if(Px->Count()>0){
      Px->Sort(minSupp);
      Px->CharmExtend(C, minSupp);
      }
      delete Px;
      Px =NULL;
      cout << "End of loop... " << endl;
      //Add X to C
      //X = NULL;
     {
        itree test;
      }
   }
   cout << "Outside Loop" << endl;
}

and the test itree's destructor is called and completes, but I can't get Px to destroy.

Sterling

Here is the .h file.  
#pragma once

#include <queue>
#include <list>
#include <iostream>

using namespace std;

class itset{

 private:
  int transCount;
  int itemCount;
  int weight;
  list<int> items;
  list<int> transactions;
  bool weighed;
 
  int unions(list<int>& left, list<int>& right, list<int>& result);
  int difference(list<int>& left, list<int>& right, list<int>& result);
  int intersection(list<int>& left, list<int>& right, list<int>& result);

 public:
  itset();
  ~itset();

  list<int>& Items();
  list<int>& Transactions();
  int& Weight();
  int TransCount();

  void AddItem(int);
  void AddTransaction(int);
  void ItemUnion(itset& left, itset& right);
  void ItemDifference(itset& left, itset& right);
  void ItemIntersection(itset& left, itset&);
  void TransUnion(itset& left, itset& right);
  void TransDifference(itset& left, itset& right);
  void TransIntersection(itset& left, itset& right);


  bool operator<(itset) const;
  bool operator==(itset) const;
  itset operator+(itset&);
  friend ostream& operator<<(ostream&, const itset&);


};

I am going to have to clean up the .cpp file before I can post it...

I tried this with Px removed completely, as I am just trying to add it in now, and I still get the seg fault without itree Px.

Here is the cpp file.


#include "itset.h"
#include <queue>
#include <list>
#include <algorithm>

using namespace std;

itset::itset(){
  transCount=0;
  itemCount=0;
  weighed=false;
};
itset::~itset(){
   cout << "Destroying itset..." << endl;
   transCount=0;
   itemCount=0;
   weighed=false;
   cout << "Destroyed itset" << endl;
};

list<int>& itset::Items(){
  return this->items;
}

int itset::unions(list<int>& left, list<int>& right, list<int>& result){  
   set_union(left.begin(), left.end(),
                right.begin(), right.end(),
           result.begin());
   return result.size();
}

int itset::difference(list<int>& left, list<int>& right, list<int>& result){
   set_difference(left.begin(), left.end(),
              right.begin(), right.end(),
              result.begin());
   return result.size();
}

int itset::intersection(list<int>& left, list<int>& right, list<int>& result){

   int size=0;
   for(list<int>::iterator it=left.begin(); it!=left.end(); it++){
      for(list<int>::iterator it2=right.begin(); it2!=right.end(); it2++){
       if(*it==*it2){
          result.push_back(*it);
          size++;
       }
      }
   }
   return size;
}

list<int>& itset::Transactions(){
  return this->transactions;
}

int itset::TransCount(){
  return transCount;
}

int& itset::Weight(){
   return this->weight;
}

void itset::AddItem(int value){
  this->items.push_back(value);
  itemCount++;
}

void itset::AddTransaction(int value){
  this->transactions.push_back(value);
  transCount++;
}

void itset::ItemUnion(itset& left, itset& right){
   itemCount = unions(left.items, right.items, this->items);
}

void itset::ItemDifference(itset& left, itset& right){
   itemCount = difference(left.items, right.items, this->items);
}

void itset::ItemIntersection(itset& left, itset& right){
   itemCount = intersection(left.items, right.items, this->items);
}

void itset::TransUnion(itset& left, itset& right){
   transCount = unions(left.transactions,
                   right.transactions, this->transactions);
}

void itset::TransDifference(itset& left, itset& right){
   transCount = difference(left.transactions,
                     right.transactions, this->transactions);
}

void itset::TransIntersection(itset& left, itset& right){
   transCount = intersection(left.transactions,
                       right.transactions, this->transactions);
   
}


bool itset::operator<(itset right) const{
    return this->transCount < right.transCount;
}

bool itset::operator==(itset right) const{
  return this->transCount == right.transCount;
}

Just realized I have code in my ~itset that shouldn't be there.  I will remove and try(although I don't think it is causing problems).

With the following:
itset::~itset(){
   cout << "Destroying itset..." << endl;
//    transCount=0;
//    itemCount=0;
//    weighed=false;
   cout << "Destroyed itset" << endl;
};

I still get the segmentation fault inbetween loops.

Sterling

I don't see anything that stands out in the itset class.

Can you post the header for itree?

#pragma once

#include <queue>
#include "itset.h"

#define DEFAULT_ARRAY_SIZE 1000

using namespace std;

struct lessp{
  bool operator()(itset* left, itset* right){
    return (*left) < (*right);
  }
};

class itree{
 private:
  itset** itsets;
  int size;
  int count;

 public:
  //  itree();
  itree(int sz=DEFAULT_ARRAY_SIZE);
  ~itree();

  itset* Itsets();

  int Count(){return count;};

//  void AddItset(itset);
//  void AddItset(itset*);
  void AddItset(int item, int transaction);
  void AddItset(itset*, int);
  void RemoveItset(int);
//  void RemoveItset(itset*);
  void Sort();
  void Sort(int);
  void CharmExtend(list<int>&, int);
  void CalculateWeights(int);

  itset* operator[](int i){return itsets[i];};
 
  void DoForEachItset(void (*f)(itset&));
  void DoForEachItsetGreater(itset& Xi, void(*f)(itset&));

};

>>itset** itsets;

This is dangerous, and I'm pretty sure it's related to the runtime error.

I recommend using std::vector<itset> or std::vector<itset*> instead of a raw pointer of pointer type.

I was trying to avoid vectors due to speed concerns...  This array is used to translate a db from horizontal format to vertical format, so I need to do over 4,000,000 finds on this structure, which is going to take too long using a vector.  I am able to use the array as a perfect hashtable based on the item number in the db.  I have not come up with a better way of doing this.

Sterling

I have trouble using a sorted datastructure due to the fact that I don't know my sort criteria until after the db is read completly.

Sterling

>>I was trying to avoid vectors due to speed concerns...

vector is very fast and efficient, and on some implementations, vector is faster then using C style arrays.

On most implementations, there's very little difference in performance between a vector and a C style array.
You can verify this by doing a performance test on non-debug version of the code.  If you use debug version of the code, then vector will normally perform badly, but debug version of the code should never be used for performance test.

>>which is going to take too long using a vector.

It should not take any longer using a vector, if it's correctly implemented.
If you can determine your size at runtime, you can increase the vector efficiency by calling vector.reserve

>>I am able to use the array as a perfect hashtable based on the item number in the db
You may want to use std::map instead, which you can link directly to the item number in the db.

I just remembered that we had problems with calling the size() function on the list<int> transactions found in itset.h.  I found that I was still calling that function on the list<int> items found in the same file from the function unions() in itsets.cpp.  I rewrote the code and it works now.

I am still concerned about your concern for the pointer to pointer and will continue to look for a way to not use it, but for the moment it is working again....

Sterling

>>I just remembered that we had problems with calling the size() function on the list<int> transactions found in itset.h.

Calling the size function by itself, should never cause a runtime error, unless there is another problem that is currupting memory.
Just removing the size function, will only hide the real problem.
The real problem will probably cause other runtime errors in some other part of the code.

I will have to wait untill tomorrow night to work on switching things around.  As it is, I still don't really understand how this might be causing my problems.  I am able to loop thru my pointer to pointer array with other functions without problems.  It is just when I call the size() function on a list<int> that I am getting into trouble.  Is this dangerous only because it makes it difficult to follow the pointers properly, or does it make the compiler more suseptable to errors?

I thought that vectors suffered from slow lookup times.  Since I am able to use my pointer to pointer array as a perferct hash I get constant time lookups, while I thought vectors were much slower.

I am storing, something similar to, pair<int item, list<int>trans> in the array to begin with.  As I read a new item in a transaction, I must find that item pair in the array, or create it if it does not exist, and add another transaction number into the list.  With a vector won't this mean manually iterating through the vector each time?

I looked into the std::map as well, and decided it did not fit well due to the need to have the items ordered and maps inability to guarantee order.

Sterling

>>difficult to follow the pointers properly, or does it make the compiler more suseptable to errors?

It makes the code more suseptable to errors.

>>I thought that vectors suffered from slow lookup times.
No.  It has the fastest lookup time.  The C++ standard recommends it as the default container.


>>I am storing, something similar to, pair<int item, list<int>trans> in the array to begin with.  As I read a new item in a transaction, I must find that item pair in the
>>array, or create it if it does not exist, and add another transaction number into the list.  With a vector won't this mean manually iterating through the vector each
>>time?

For above requirement, a vector would not be the best choice, and it would be better to use a std::map.
An std::map should be far faster then using above method.
std::map<int item, vector<int> > itsets;

If your compiler or your STL library supports it, you can also think about using hash_map.
hash_map<int item, vector<int> > itsets;

But I suspect, that just using std::map will be a great improvement, and will make the code far safer then using a pointer of pointers.

>>I looked into the std::map as well, and decided it did not fit well due to the need to have the items ordered and maps inability to guarantee order.

I think you're misunderstanding std::map, and you're real requirement.

What you need is to be able to access the contents of the container in constant time.  It really shouldn't matter if the container has the contents in order, as long as the lookup time is fast.
So it shouldn't matter if std::map has the contents in order, as long as it can find the contents quickly.

If for what ever reason you still require the contents to be in order, then consider using std::hash_map.
If your implementation doesn't support it, you can download it from boost or other free STL libraries.

Your right, I don't really know the STL containers very well yet.  I have one question about map.  While I am reading the data from the file, I need to have things with quick lookup based on the item number, but after that I need this sorted based on the number of transactions a single item has.  After reading the file, I no longer need the constant lookup times, since all my calculations, quite a bit, will be based strictly on the order of the items, so I will be just iterating over the structure.  With map is it difficult to resort based on a new criteria?  Or might I be better off to use a vector and then sort using qsort?

Sterling

I don't have any time during the day to rewrite the code, but I will try some of these options early this evening.

I was able to switch things aroung last night.  I decided to use a vector<itset> and then call sort on it after I was finished reading.  While this may not be the best way to handle this, it did require the least amount of rewriting, and I need to show results today...  Thanx for everything. I now have this working better than I thought it would be.  Later I may try implementing this with the map as suggested, but for now, I have a program that runs.

Sterling