Using queues...

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 991 Views - Last Post: 26 June 2013 - 11:44 AM Rate Topic: -----

#1 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Using queues...

Posted 24 June 2013 - 06:04 PM

Hey everyone,

I have an assignment to complete a program whose job is to write out the makefile rule for a given .cpp file. The bulk of the code is provided and really our only task is to use the proper queue manipulations. To my knowledge they are similar to stacks but are FIFO instead of LIFO. In my files could someone see if I am even remotely close to the proper manipulations? *Note* Main focus is on makemake.cpp, headers are included but aren't changed so I won't post unless requested *End Note*

Everywhere we were supposed to add something you will see /*...*/ save the first encounter which is a description of the program.

makemake.cpp
/**
 *  makemake.exe foo.cpp
 *    Emits a make dependency rule for determining when to compile foo.cpp
 *    by analyzing and listing all .h files #included by foo.cpp (and by
 *    other .h files #included by it, in the order they would be loaded
 *    by the compiler.
 **/

#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <list>
#include "cs361set.h"


using namespace std;

typedef CS361Set<string> FileNameSet;
/** insert std::queue declaration here **/
typedef queue <string, list <string> >FileNameCollection;

FileNameCollection q;

void processSourceCodeFile (string fileName,
			    FileNameSet& alreadyProcessed,
			    FileNameCollection& stillToBeProcessed)
{
  const string INCLUDE = "#include";
  const string PATHSEP = "/";  // "\\" for Windows compilers
  //
  // Most of this function is involved with scanning a file of C++
  // source code, looking for lines containing #include directives.
  //

  string pathToThisFile = (fileName.find(PATHSEP) != string::npos) ?
    fileName.substr(0, fileName.rfind(PATHSEP)+1) : string();

  ifstream sourceIn (fileName.c_str());
  while (sourceIn) {
    // Read line of source code
    string line;
    getline (sourceIn, line);
    // Does it begin with #include?
    string::size_type includeStart = line.find_first_not_of(" \t");
    if (includeStart != string::npos &&
	line.substr(includeStart,INCLUDE.length()) == INCLUDE) {
      // Isthefilename inside < > or " " ?
      string::size_type filenameStart =
	line.find_first_of("<\"",
			   includeStart+INCLUDE.length());
      if (filenameStart != string::npos && line[filenameStart] == '"') {
	// We have located a file name inside a #include "..."
	// Extract the filename.
	++filenameStart;
	string::size_type filenameEnd = line.find(string(1,'"'), filenameStart);
	if (filenameEnd != string::npos) {
	  string includedFileName =
	    pathToThisFile +
	    line.substr(filenameStart, filenameEnd-filenameStart);

	  // We have located a file name inside a #include "..."
	  if (!alreadyProcessed.contains(includedFileName)) {
	    alreadyProcessed.add(includedFileName);
	    /** Insert code here to guarantee that includedFileName
                will eventually be processed. **/
             q.push (includedFileName);
                }

	  	}
      }
    }
  }
}


int main(int argc, char** argv)
{
  if (argc != 2) {
    cerr << "Usage: " << argv[0] << " cppFileName" << endl;
    return -1;
  }

  string cppFileName (argv[1]);

  cout << cppFileName << ": " << flush;

  FileNameSet alreadyProcessed;
  FileNameCollection stillToBeProcessed;

  processSourceCodeFile (cppFileName, alreadyProcessed, stillToBeProcessed);

  while (q.empty()/** insert code here to determine when we are done processing **/) {
    string headerFileName = (argv[1])/** Insert code here to get
                                file name for processing **/;

    cout << "\\\n    " << headerFileName << flush;
    processSourceCodeFile (headerFileName,
			   alreadyProcessed,
			   stillToBeProcessed);

    /** Insert code here to advance the loop to the
        next file for processing **/
q.pop();

  }
  cout << endl;
  return 0;
}



Thanks guys.

Is This A Good Question/Topic? 0
  • +

Replies To: Using queues...

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3574
  • View blog
  • Posts: 11,112
  • Joined: 05-May 12

Re: Using queues...

Posted 24 June 2013 - 07:22 PM

Did you try running your code? Did you encounter any behavior that you were not expecting? (Just taking a quick scan, I can already spot an error.)
Was This Post Helpful? 1
  • +
  • -

#3 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 24 June 2013 - 08:00 PM

Well when I run the code I get this error:

Usage: C:\(my comps folders leading to program location)\makeassignment.exe cppFileName
Process returned blah blah

This tells me that I need to focus on this, or at least think about why its being used:
int main(int argc, char** argv)
{
  if (argc != 2) {
    cerr << "Usage: " << argv[0] << " cppFileName" << endl;
    return -1;
  }



So if my argument count is not two....then it returns argv [0] which is just my program name.

Should I have more arguments somewhere? Perhaps include an argv[2] for the headerFileName section?
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3574
  • View blog
  • Posts: 11,112
  • Joined: 05-May 12

Re: Using queues...

Posted 24 June 2013 - 10:42 PM

No. You should run your program and make sure that you pass a command line parameter. If you are running on the command line, obviously pass in the name of the file that you want to parse. If you are using an IDE, you'll have to go to your projects setting and ensure that you pass in the name of the file that you want to parse when running the program in run or debug mode.
Was This Post Helpful? 1
  • +
  • -

#5 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 25 June 2013 - 07:29 AM

When I run in cmd my program crashes. However when I run the provided solution's .exe the program spits out the following.
Say I run this:

makemake.exe balance.cpp
balance.cpp:
Was This Post Helpful? 0
  • +
  • -

#6 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 25 June 2013 - 08:57 AM

I'm also going to include all of the original files I was given. This may be of some assistance.

arrayops.h
#ifndef ARRAYOPS_H
#define ARRAYOPS_H

template <class T>
int sequentialInsert
  (T a[], unsigned& n, const T& x)
// insert x into sorted position within a,
//   with a already containing n items.
//   Return the position where inserted.
{
  int i = n;
  while ((i > 0) && (x < a[i-1]))
      {
       a[i] = a[i-1];
       i = i - 1;
      }
  a[i] = x;
  ++n;
  return i;
}


template <class T>
int sequentialSearch
  (const T a[], unsigned n, const T& x)
// Look for x within a sorted array a, containing n items.
// Return the position where found, or -1 if not found.
{
  int i;
  for (i = 0; ((i < n) && (a[i] < x)); i++) ;
  if ((i >= n) || (a[i] != x))
    i = -1;
  return i;
}


template <class T>
int unorderedSearch
  (const T a[], unsigned n, const T& x)
// Look for x within an unsorted array a, containing n items.
// Return the position where found, or -1 if not found.
{
  int i;
  for (i = 0; ((i < n) && (a[i] != x)); i++) ;
  if (i >= n)
    i = -1;
  return i;
}


template <class T>
unsigned int binarySearch (T v[], unsigned int n, const T& value)
    // search for value in ordered array of data
    // return index of value, or index of
    // next smaller value if not in collection
{
  unsigned int low = 0;
  unsigned int high = n;

  // repeatedly reduce the area of search
  // until it is just one value
  while (low < high) {
     unsigned mid = (low + high) / 2;
     if (v[mid] < value)
        low = mid + 1;
     else
        high = mid;
     }

  // return the lower value
  return low;
}

#endif



cs361set.h
#ifndef CS361SET_H
#define CS361SET_H

#include <string>
#include <iostream>
#include <cassert>

#include "arrayops.h"



template <class Element>
class CS361Set
{
public:
  typedef const Element* const_iterator;
  typedef const Element* iterator;


  CS361Set ();
  CS361Set (unsigned int maxSizeDesired);
  CS361Set (const CS361Set<Element>&);

  ~CS361Set();

  CS361Set<Element>& operator= (const CS361Set<Element>& ws);
  //pre: maxSize() <= ws.size()

  unsigned int size() const;
  // How many words in the set?

  unsigned int maxSize() const;
  // How many words could be put into a set?

  void add (const Element& word);
  //pre: contains(word) || size() < maxSize()

  bool contains (const Element& word) const;

  const_iterator find (const Element& key) const;

  const_iterator begin() const;
  const_iterator end() const;


  void print(std::ostream& out) const;

  bool operator== (const CS361Set<Element>&) const;
  bool operator< (const CS361Set<Element>&) const;

private:
  const unsigned int maxNumberOfElements;
  unsigned int numberOfElements;
  Element *elements;
};

template <class Element>
inline
std::ostream& operator<< (std::ostream& out, const CS361Set<Element>& set)
{
  set.print (out);
  return out;
}

template <class Element>
inline
unsigned int CS361Set<Element>::size() const
{
  return numberOfElements;
}

template <class Element>
inline
unsigned int CS361Set<Element>::maxSize() const
{
  return maxNumberOfElements;
}



template <class Element>
CS361Set<Element>::CS361Set ()
  : maxNumberOfElements(500)
{
  numberOfElements = 0;
  elements = new Element [maxNumberOfElements];
}


template <class Element>
CS361Set<Element>::CS361Set (unsigned int maxSizeDesired)
  : maxNumberOfElements(maxSizeDesired)
{
  numberOfElements = 0;
  elements = new Element [maxSizeDesired];
}


template <class Element>
CS361Set<Element>::~CS361Set()
{
  delete [] elements;
}

template <class Element>
CS361Set<Element>::CS361Set (const CS361Set<Element>& oldSet)
  : maxNumberOfElements(oldSet.maxNumberOfElements),
    numberOfElements(oldSet.numberOfElements)
{
  elements = new Element[maxNumberOfElements];
  for (int i = 0; i < numberOfElements; ++i)
    elements[i] = oldSet.elements[i];
}


template <class Element>
CS361Set<Element>& CS361Set<Element>::operator= (const CS361Set<Element>& oldSet)
{
  if (this != &oldSet)
  {
    assert (maxNumberOfElements >= oldSet.numberOfElements);
    numberOfElements = oldSet.numberOfElements;

    for (int i = 0; i < numberOfElements; ++i)
    elements[i] = oldSet.elements[i];
  }
  return *this;
}


template <class Element>
void CS361Set<Element>::add (const Element& word)
{
  if (((size() > 0) && (elements[size()-1] < word))
      ||  (!contains(word)))
    {
      assert (size() < maxSize());
      sequentialInsert (elements, numberOfElements, word);
    }
}

template <class Element>
bool CS361Set<Element>::contains (const Element& word) const
{
  if (numberOfElements > 0)
    {
      int pos = binarySearch (elements, numberOfElements, word);
      return ((pos >= 0) && (elements[pos] == word));
    }
  else
    return false;
}


template <class Element>
typename CS361Set<Element>::const_iterator
  CS361Set<Element>::find (const Element& key) const
{
  if (numberOfElements > 0)
    {
      int pos = binarySearch (elements, numberOfElements, key);
      if ((pos >= 0) && (elements[pos] == key))
	{
	  return elements+pos;
	}
      else
	return end();
    }
  else
    return end();
}



template <class Element>
inline
typename CS361Set<Element>::const_iterator
  CS361Set<Element>::begin () const
{
  return elements;
}


template <class Element>
inline
typename CS361Set<Element>::const_iterator
  CS361Set<Element>::end () const
{
  return elements + numberOfElements;
}






template <class Element>
void CS361Set<Element>::print(std::ostream& out) const
{
  using namespace std;

  string separator = "";
  out << "{";
  for (int i = 0; i < numberOfElements; ++i)
    {
      out << separator << elements[i];
      separator = ", ";
    }
  out << "}";
}


template <class Element>
bool CS361Set<Element>::operator== (const CS361Set<Element>& ws) const
{
  if (numberOfElements == ws.numberOfElements)
    {
     for (int i = 0; i < numberOfElements; ++i)
       {
         if (!(elements[i] == ws.elements[i]))
           return false;
       }
     return true;
    }
  else
    return false;
}


template <class Element>
bool CS361Set<Element>::operator< (const CS361Set<Element>& ws) const
{
  if (numberOfElements == ws.numberOfElements)
    {
     for (int i = 0; i < numberOfElements; ++i)
       {
         if (elements[i] != ws.elements[i])
           return elements[i] < ws.elements[i];
       }
     return false;
    }
  else
    return numberOfElements < ws.numberOfElements;
}

#endif



original makemake.cpp
/**
 *  makemake.exe foo.cpp 
 *    Emits a make dependency rule for determining when to compile foo.cpp
 *    by analyzing and listing all .h files #included by foo.cpp (and by 
 *    other .h files #included by it, in the order they would be loaded
 *    by the compiler.
 **/

#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include "cs361set.h"


using namespace std;

typedef CS361Set<string> FileNameSet;
typedef /** insert std::queue declaration here **/ FileNameCollection;

void processSourceCodeFile (string fileName,
			    FileNameSet& alreadyProcessed,
			    FileNameCollection& stillToBeProcessed)
{
  const string INCLUDE = "#include";
  const string PATHSEP = "/";  // "\\" for Windows compilers
  //
  // Most of this function is involved with scanning a file of C++
  // source code, looking for lines containing #include directives.
  //

  string pathToThisFile = (fileName.find(PATHSEP) != string::npos) ?
    fileName.substr(0, fileName.rfind(PATHSEP)+1) : string();

  ifstream sourceIn (fileName.c_str());
  while (sourceIn) {
    // Read line of source code
    string line;
    getline (sourceIn, line);
    // Does it begin with #include?
    string::size_type includeStart = line.find_first_not_of(" \t");
    if (includeStart != string::npos &&
	line.substr(includeStart,INCLUDE.length()) == INCLUDE) {
      // Isthefilename inside < > or " " ?
      string::size_type filenameStart =
	line.find_first_of("<\"",
			   includeStart+INCLUDE.length());
      if (filenameStart != string::npos && line[filenameStart] == '"') {
	// We have located a file name inside a #include "..."
	// Extract the filename.
	++filenameStart;
	string::size_type filenameEnd = line.find(string(1,'"'), filenameStart);
	if (filenameEnd != string::npos) {
	  string includedFileName =
	    pathToThisFile +
	    line.substr(filenameStart, filenameEnd-filenameStart);

	  // We have located a file name inside a #include "..."
	  if (!alreadyProcessed.contains(includedFileName)) {
	    alreadyProcessed.add(includedFileName);
	    /** Insert code here to guarantee that includedFileName
                will eventually be processed. **/
	  }
	}
      }
    }
  }
}


int main(int argc, char** argv)
{
  if (argc != 2) {
    cerr << "Usage: " << argv[0] << " cppFileName" << endl;
    return -1;
  }

  string cppFileName (argv[1]);

  cout << cppFileName << ": " << flush;

  FileNameSet alreadyProcessed;
  FileNameCollection stillToBeProcessed;

  processSourceCodeFile (cppFileName, alreadyProcessed, stillToBeProcessed);

  while (/** insert code here to determine when we are done processing **/) {
    string headerFileName = /** Insert code here to get 
                                file name for processing **/;

    cout << "\\\n    " << headerFileName << flush;
    processSourceCodeFile (headerFileName,
			   alreadyProcessed,
			   stillToBeProcessed);

    /** Insert code here to advance the loop to the 
        next file for processing **/
  }
  cout << endl;
  return 0;
}



Hopefully this makes things easier.
Was This Post Helpful? 1
  • +
  • -

#7 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Using queues...

Posted 25 June 2013 - 06:31 PM

I don't see that you need to create q.

085	  processSourceCodeFile (cppFileName, alreadyProcessed, stillToBeProcessed);



Each filename is searched, when a included filename is encountered it will be added to stillToBeProcessed, so that eventually it can be searched also.
Was This Post Helpful? 2
  • +
  • -

#8 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 25 June 2013 - 06:41 PM

O wow. I think I see what you mean. What i did with FileNameCollection q; had already been done with FileNameCollection stillToBeProcessed; correct? So I will be replacing my q's with stillTo"...".

Thank you for your insight.
Was This Post Helpful? 0
  • +
  • -

#9 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Using queues...

Posted 25 June 2013 - 06:54 PM

Just about, the logic is not exactly the same as you have.
Was This Post Helpful? 1
  • +
  • -

#10 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 25 June 2013 - 07:11 PM

if (!alreadyProcessed.contains(includedFileName)) {

        alreadyProcessed.add(includedFileName);

        /** Insert code here to guarantee that includedFileName

                will eventually be processed. **/
stillToBeProcessed.push(includedFileName);



processSourceCodeFile (cppFileName, alreadyProcessed, stillToBeProcessed);
 
  while (stillToBeProcessed.empty()/** insert code here to determine when we are done processing **/) {

    string headerFileName = stillToBeProcessed.push(headerFileName);/** Insert code here to get

                                file name for processing **/;


cout << "\\\n    " << headerFileName << flush;

    processSourceCodeFile (headerFileName,

               alreadyProcessed,

               stillToBeProcessed);

    /** Insert code here to advance the loop to the
        next file for processing **/
stillToBeProcessed.pop(); //Something else is needed here yes?  A push maybe for the next file which will probably be a header file?  stillToBeProcessed.push(headerFileName);


Was This Post Helpful? 0
  • +
  • -

#11 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Using queues...

Posted 25 June 2013 - 07:22 PM

What is the logic here? Try writing it as a sentence.

3    while ( stillToBeProcessed.empty() ) {




Do you get any errors when compiling?
Was This Post Helpful? 1
  • +
  • -

#12 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 25 June 2013 - 07:35 PM

While stillToBeProcessed is empty do whatever is below. After the above changes had been made I got this error

error: conversion from 'void' to non-scalar type 'std::string' requested at line 93.

while (stillToBeProcessed.empty() ).....that won't ever happen will it? Because we didn't pop anything prior?
*Edit* perhaps this:
while (stillToBeProcessed.front() != cppFileName) {


This post has been edited by R2B Boondocks: 25 June 2013 - 07:51 PM

Was This Post Helpful? 0
  • +
  • -

#13 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Using queues...

Posted 25 June 2013 - 08:15 PM

If there is something stillToBeProcessed ...
if stillToBeProcessed is empty then ...
Was This Post Helpful? 1
  • +
  • -

#14 R2B Boondocks  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 12
  • View blog
  • Posts: 195
  • Joined: 19-September 12

Re: Using queues...

Posted 25 June 2013 - 08:26 PM

>> If there is something stillToBeProcessed ...
Then we are still processing

>> if stillToBeProcessed is empty then ...
Then we are done processing
Was This Post Helpful? 0
  • +
  • -

#15 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1344
  • View blog
  • Posts: 4,608
  • Joined: 19-February 09

Re: Using queues...

Posted 25 June 2013 - 08:58 PM

View PostR2B Boondocks, on 26 June 2013 - 04:26 AM, said:

>> If there is something stillToBeProcessed ...
Then we are still processing

>> if stillToBeProcessed is empty then ...
Then we are done processing


Yes, good - translate to the code.

if stillToBeProcessed is not empty then ...

---

error: conversion from 'void' to non-scalar type 'std::string' requested at line 93.

    /** Insert code here to get file name for processing **/;
    string headerFileName = stillToBeProcessed.push(headerFileName); 



The instruction says Insert code here to get file name for processing, does push get a filename?


queue

This post has been edited by #define: 25 June 2013 - 09:02 PM

Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2