Solved

Code Repair

Posted on 2004-09-30
9
347 Views
Last Modified: 2010-04-01
# Makefile:
#        It uses the C++ Compiler with all warnings and
#        full debugging; will create a single executable called 'main'
# ---------------------------------------------------------------
# the compiler
CPP = cxx
# compiler flags
CFLAGS = -L/usr/lib/cmplrs/cxx -DPOSIX_4D9 -w1 -gall
# linker flags to link in the libraries libm.a and libtask.a
LFLAGS = -lm -ltask
#
RM = rm -f
# ----------------------------------------------------------------
# Explanation of macros:
#     $< is any dependent file which is out of file1
#     $* is the target's basename (without extension)
#     $@ is the target's fullname
#
# add suffix .cpp since it is not a default with make utility
.SUFFIXES:      .cpp .o
#
# implicit rule for compilation only:
.cpp.o:
      ${CPP} -c ${CFLAGS} $<

OFILES=            main.o deque.o queue.o util.o safeio.o

HFILES=            deque.h queue.h  util.h safeio.h

# dependencies
#
default:      main      
#
main:           $(OFILES)
            ${CPP} ${CFLAGS} ${LFLAGS} $(OFILES) -o $@

main.o:            main.cpp
deque.o:            deque.cpp deque.h
queue.o:            queue.cpp queue.h
util.o:            util.cpp util.h
safeio.o:      safeio.cpp safeio.h

#
clean:
      ${RM} *.o
      ${RM} core
#
veryclean:      clean
      ${RM}  main  

// util.h

#ifndef UTIL_H  
#define UTIL_H

#define NULL 0L
#define STDSCREEN 80        
#define DOWN 0                        
#define UP   1
#define END   0
#define START 1
#define FAIL    0
#define SUCCESS 1
#define MISS -1
#define HIT   1

enum Error_code { success, fail, range_error, underflow, overflow, fatal,
                  not_present, duplicate_error, entry_inserted, entry_found,
                  internal_error };

void clearScreen ();                    
void clearTop();                        
void clearBelowTop();                  
void goTop();                              
void topLine(const char * text = " "  );    
void bottomLine (char * text = " ");  

 
void hitAnyKey ();                    
void flushInput ();                    
void Warning(char *);                  
void Error(char *);                    
bool promptYesNo(char * prompt="");      
void EatWhiteSpace(void);              

#endif

// end of util.h

// util.cpp

#include <iostream>
#include <ctype.h>
#include <stdlib.h>
#include "util.h"
 
void clearScreen (void) {

  cout << "\033[2J";          
  cout << "\033[;f";          

}

void clearTop()
 
  {cout << "\033[0;0f" << "\033[0K";}

void clearBelowTop()
 
  {cout << "\033[1;0f" << "\033[1B" << "\033[J";}

void goTop ()
 
  {cout << "\033[0;0f";}

void topLine(const char str[])
 
  {cout << "\033[0;0f" << "\033[0K" << str;}

void bottomLine (char * str)
 
  {cout << "\033[23;0Hf" << "\033[2K" << str;}

void hitAnyKey ()
{
   char ch;
   bottomLine ("Hit any key to continue...");
   cin.get(ch);
   clearScreen();

}

void flushInput () {
 
   char buff[81];
   if (cin)
      cin.getline(buff,80);    

}

void Warning(char *message) {

   cerr << message;
}

void Error(char *message) {

   cerr << message;
   exit(1);

}

void EatWhiteSpace() {

    char ch;
    do {
      cin.get(ch);
    }
    while(isspace(ch));

    if(ch != EOF)
      cin.putback(ch);
}

bool promptYesNo(char * c) {

   char ch;
   cout << c << " [y|n]?";
   do {
      cin.get(ch);  
      tolower(ch);
      } while (ch != 'y' && ch != 'n');
   return (ch == 'y');

}

// end of util.cpp

// deque.h

#ifndef DEQUE_H
#define DEQUE_H

#include "queue.h"

class Deque : public Queue {

public:

  Deque();
 
  Error_code serve_rear();
  Error_code retrieve_rear(Entry_type &);
  void display();

};

#endif

// end of deque.h

// deque.cpp

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

Deque::Deque() {

  count = 0;

}

Error_code Deque::serve_rear() {

  if(count <= 0)
    return underflow;
  count--;
  queue[ rear ] = -1;
  if (rear == 0 )
      rear = MAXSIZE -1;
  else
      rear--;
  return success;

}

Error_code Deque::retrieve_rear(Entry_type &item) {

  if (count <= 0)
     return underflow;
  item = queue[rear];
  return success;

}

void Deque::display() {

  for(int i = 0; i < MAXSIZE; i++) {

    if(queue[i] == -1)
      cout << "* ";
    else
      cout << queue[i] << ' ';
  }
  cout << endl;

}

// end of deque.cpp

// queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include "util.h"

typedef int Entry_type;
const int MAXSIZE = 10;

class Queue {

public:

   Queue();
   Error_code  serve();
   Error_code  retrieve(Entry_type &) const;
   Error_code  serve_retrieve(Entry_type &);
   Error_code  append(const Entry_type  &);
   bool empty() const;
   bool full() const;
   int size() const;
   void display() const;

protected:

   int front, rear, count;
   Entry_type  queue[MAXSIZE];

};

#endif

// end of queue.h

// queue.cpp

#include <iostream>
#include "queue.h"
      
Queue::Queue() {
 
   for (int i = 0; i<MAXSIZE; i++)
      queue[i] = -1;

   front = count = 0;
   rear = -1;

}

Error_code Queue::serve() {

   if (empty())
     return underflow;
   else
   {
     queue[front]=-1;  
     front = ++front % MAXSIZE;
     count --;
   }
   return success;

}

Error_code Queue::retrieve(Entry_type & value) const {

   if (empty())
      return underflow;
   else
      value = queue[front];
   return success;

}

Error_code Queue::serve_retrieve(Entry_type & value) {

   if (empty())
     return underflow;
   else  
   {
      value = queue[front];
      front = (++front) % MAXSIZE;
      count --;
   }
   return success;

}

Error_code Queue::append(const Entry_type &value) {

   if (full())
     return overflow;
   else  
   {
      rear = ++rear % MAXSIZE;
      queue[rear] = value;
      count ++;
   }
   return success;
}

bool Queue::empty() const {

   if (count == 0)
      return true;
   else
      return false;
}

bool Queue::full() const {
 
   if (count == MAXSIZE)
      return true;
   else
     return false;

}

int Queue::size() const
 
   {return count;}

void Queue::display() const {

  clearScreen();
  for (int i = 0; i<MAXSIZE; i++)
     if (queue[i] != -1)
         cout << queue[i] << " ";
     else
          cout << "  ";

}

// end of queue.cpp

// safeio.h

#ifndef _IO_H
#define _IO_H

#include <iostream>
#include <iomanip>
#include <assert.h>
#include <math.h>

class String {

   friend ostream &operator<<(ostream &, const String &);
   friend istream &operator>>(istream &, String &);

public:

   String(const char * = "");       
   String(const String &);
   ~String();                    
   const String & getString() const {return *this;}
   int getLength() const;                
   const String &operator=(const String &);  
   void setString(const String &s) {*this = s;}
   void setString(const char *);  
   const String &operator+=(const String &);
   bool operator!() const;
   bool operator==(const String &) const;  
   bool operator<(const String &) const;  
   bool operator!=(const String &right) const
      {return !(*this == right);}
   bool operator>(const String &right) const
      {return right < *this;}
   bool operator<=(const String &right) const
      {return !(right < *this );}
   bool operator>=(const String &right) const
      {return !(*this < right);}
   char &operator[]( int );              
   const char &operator[](int) const;  
   String operator()(int, int);        

private:

   int length;
   char *sPtr;                    

};

enum {ITOKEN,DTOKEN,STOKEN};

class Token {

public:

   Token() {};
   virtual ~Token() {};
   virtual void display(ostream &) = 0;
   virtual int getType()const = 0;  
   virtual void getData( void * ) = 0;

};

class IToken: public Token {

public:

   IToken(int i = 0) {data = i;}
   IToken (const IToken * in) {data = in->data;}  
   ~IToken() {};
   void display(ostream &);
   virtual int getType() const {return ITOKEN;}
   virtual void getData(void * i) ;

private:

   int data;

};

class DToken: public Token {

public:

   DToken(double d = 0) {data = d;}
   DToken (const DToken * in) { data = in->data; }  
   ~DToken() {};
   void display(ostream &);
   virtual int getType() const {return DTOKEN;}
   virtual void getData(void *d);

private:

   double data;

};

class SToken: public Token {

public:

   SToken(char * s="") {data = s;}
   SToken (const SToken * in) {data = in->data;}  
   ~SToken() {};
   void display(ostream &);
   virtual int getType() const {return STOKEN;}
   virtual void getData(void *s);

private:

   String data;

};

class SafeIO {

public:

   SafeIO();
   SafeIO(const SafeIO &);
   ~SafeIO();
   void clear();

   int getCount() const;
   const Token * getToken (int) const;
   int getType (int);
   void getData (int*,int);
   void getData (String*,int);
   void getData (double*,int);
   void input();  
   void read(istream &);
   void display();
   void write(ostream &);
   operator void *( ) const;
   SafeIO & operator  = (const SafeIO &);

private:

   enum {MAXARRAY = 200};
   Token * list[MAXARRAY];
   int count;

};

#endif

// end of safeio.h

// safeio.cpp

#include <fstream>
#include <strstream>
#include <iomanip>
#include <math.h>
#include "safeio.h"

SafeIO::SafeIO() {

   list[0] = NULL;  
   count = 0;

}  

SafeIO::SafeIO(const SafeIO & in)

   { *this = in; }  

SafeIO::~SafeIO()

   {clear();}

void SafeIO::clear()  {

  for (int i = 0; i < count; i++)
    delete list[i];
  count = 0;

}

int SafeIO::getCount() const

   {return count;}

const Token * SafeIO::getToken (int i) const

   {return list[i];}

void SafeIO::getData (int * the_data, int i) {

  int * local_ptr = new int;
  list[i]->getData((void *)local_ptr);
  *the_data = *local_ptr;

}

void SafeIO::getData (String * the_data, int i) {  

   String *local_ptr = new String;
   list[i]->getData((void *)local_ptr );
   *the_data = *local_ptr;

}

void SafeIO::getData (double * the_data, int i){
 
   double * local_ptr = new double;
   list[i]->getData((void *)local_ptr);
   *the_data = *local_ptr;

}

int SafeIO::getType (int i)

   {return list[i]->getType();}

SafeIO::operator void *( ) const

   {return list[0];}

SafeIO & SafeIO::operator = (const SafeIO & rt) {
 
  const Token *ptr;  
  int tokenType;
  if (count!=0)  
    clear();
  count = rt.getCount();  

  for (int i=0; i < count; i++) {
     ptr = rt.getToken(i);
    tokenType = ptr->getType();      

    if (tokenType == ITOKEN)    
       list[i] = new IToken(static_cast<const IToken *>(ptr));

    else if (tokenType == DTOKEN)
       list[i] = new DToken(static_cast<const DToken *>(ptr) );

    else
       list[i] = new SToken(static_cast<const SToken *>(ptr) );
   }
   return *this;
}

void SafeIO::display() {

  char ans;
  cout << "Display to a file(y/n)?:" << endl;
  cin >> ans;

  if (ans == 'y')
  {
  ofstream oFile("outfile");
  if (!oFile) {
       cerr << "outfile could not be opened" << endl;
       exit(1);
     }
     write(oFile);
     oFile.close();
  }
  else
    write(cout);
}

void SafeIO::write( ostream  & out)
{
  for (int i = 0; i < count; i++){

     list[i]->display(out);
     cout << " ";
  }
  out << endl;
}

void SafeIO::input( ) {

  char ans;
  cout << "Read from a file(y/n)?:" << endl;
  cin >> ans;

  if (ans == 'y')
  {
     ifstream iFile("infile");
     if (!iFile) {
       cerr << "Infile could not be opened" << endl;
       exit(1);
     }
     read(iFile);
     iFile.close();
  }
  else
  {
    cout << "Type input followed by CTRL-D:\n";
    read(cin);
    cin.clear();  
  }

}

void SafeIO::read(istream & instream)
{
 
  char buff[81];
  double num=0;
  char ch;
  char string[80];

  while (instream)
  {
 
     instream.getline(buff,81);    
     istrstream instr(buff);  

     while (instr)              
     {
         while (( ch=instr.get()) == ' ')          
         ;
         instr.putback(ch);
         if (static_cast<int>(instr.peek()) > 64 )  
         {
             instr >> string;
             list[count++] = new SToken(string);
         }
         else      
         {                                      
            instr >> num;
            if (!instr.fail())                    
            {
               if (floor(num)  < num)
               list[count++] = new DToken(num);
            else  
               list[count++] = new IToken(num);
            }
          }  
      }      
   }          
}

// TOKEN CLASS
 
void IToken::display(ostream & out) {

   out << setiosflags( ios::right |ios::fixed | ios::showpoint )
       << setprecision( 2 );
   out << data;

}
 
void DToken::display(ostream & out) {

   out << setiosflags( ios::right |ios::fixed | ios::showpoint )
       << setprecision( 2 );
   out << data;

}

void SToken::display(ostream & out)

   {out << setiosflags(ios::left) << data;}

void SToken::getData(void * out_data) {
 
   String *local_ptr = new String(data);
   *(String *)out_data = *local_ptr;

}

void DToken::getData(void * out_data) {
 
   double *local_ptr = new double(data);
   *(double *)out_data = *local_ptr;

}

void IToken::getData(void * out_data) {

   int *local_ptr = new int(data);
   *(int *)out_data = *local_ptr;

}


// STRING CLASS
 
String::String(const char *s):length(strlen(s)) {
 
   setString(s);        

}

String::String(const String &copy):length(copy.length) {

    setString(copy.sPtr);

}

String::~String() {
 
   delete [] sPtr;        

}

const String &String::operator=(const String &right) {

   if (&right != this) {        
      delete [] sPtr;              
      length = right.length;        
      setString( right.sPtr );      
   }
   else
      cout << "Attempted assignment of a String to itself\n";

   return *this;  

}

const String &String::operator+=( const String &right ) {

   char *tempPtr = sPtr;        
   length += right.length;      
   sPtr = new char[length + 1];
   assert(sPtr != 0);    
   strcpy(sPtr, tempPtr);    
   strcat( sPtr, right.sPtr );  
   delete [] tempPtr;            
   return *this;                

}

bool String::operator!() const {return length == 0;}
bool String::operator==(const String &right) const
   {return strcmp(sPtr, right.sPtr) == 0;}
bool String::operator<(const String &right) const
   {return strcmp( sPtr, right.sPtr ) < 0;}

char &String::operator[]( int subscript ) {

 
   assert(subscript >= 0 && subscript < length);
   return sPtr[subscript];  

}

const char &String::operator[](int subscript) const {
 
   assert(subscript >= 0 && subscript < length);
   return sPtr[subscript];  

}

String String::operator()(int index, int subLength) {

    assert(index >= 0 && index < length && subLength >= 0);

    int len;

   if ((subLength == 0) || (index + subLength > length))
      len = length - index;
   else
      len = subLength;

   char *tempPtr = new char[len + 1];
   assert(tempPtr != 0);  

   strncpy(tempPtr, &sPtr[ index ], len);
   tempPtr[ len ] = '\0';

   String tempString(tempPtr);
   delete [] tempPtr;  
   return tempString;  

}

int String::getLength() const {return length;}

void String::setString( const char *string2 ) {

   sPtr = new char[length + 1];  
   assert(sPtr != 0);  
   strcpy(sPtr, string2);        

}

ostream &operator<<(ostream &output, const String &s) {

   output << s.sPtr;
   return output;    

}

istream &operator>>(istream &input, String &s) {

   char buff[ 100 ];  
   input >> setw( 100 ) >> buff;
   s = buff;        
   return input;    

}

// end of safeio.cpp

// main.cpp

#include <iostream>
#include <fstream>
#include "deque.h"
#include "safeio.h"

void optionlist();

int main()
{
   Deque queue;
   int option;
   Entry_type item;


   clearScreen();
   optionlist();
   cin >> option;
   while (option != 9)
   {

//SERVE
       if ( option == 1 ) {
            clearScreen();
            if (!queue.empty()) {
              queue.serve();
              cout << "Served Successfully";
            }
            else
                cout << "Queue is Empty";
        }  

//RETRIEVE
       else if ( option == 2 ) {
            clearScreen();
            if (!queue.empty()) {
               queue.retrieve(item);  
               cout << "Value at Front of Queue is: " << item;
            }
            else
               cout << "Queue is Empty";
        }

//SERVE_RETRIEVE
       else if ( option == 3 ) {
            clearScreen();
            if (!queue.empty()){
               queue.serve_retrieve(item);  
               cout << "Value at Front of Queue is: " << item;
            }
            else
               cout << "Queue is Empty";
        }

// SERVE REAR
       else if ( option == 4 ) {
            clearScreen();
            if ( !queue.empty() ) {
              queue.retrieve_rear(item);  
              queue.serve_rear();
              cout << item << " Successfully Served from Rear";
            }
            else
                cout << "Queue is Empty";
       }

//APPEND
       else if ( option == 5 ) {
            clearScreen();
            if (!queue.full())
            {
               cout << "Enter Value to add to Queue: ";
               cin >> item;
               queue.append(item);
               cout << "\n" << item << " Successfully Appended to Queue";
            }
            else
               cout << "Stack is Full, Could Not Append";
       }

//FULL OR EMPTY?
       else if ( option == 6 ) {
            clearScreen();
            if (queue.empty())    
               cout << "Queue is Empty";
            else if (queue.full())
               cout << "Queue is Full";
            else
               cout << "Queue is Not Empty or Full";
        }

//SIZE
       else if ( option == 7 ) {
            clearScreen();
            if (!queue.empty())
               cout << "The Size of The Queue is: " << queue.size();
            else
               cout << "The Queue is Empty";
        }


// READ FROM FILE
       else if ( option == 8 ) {
          int n_tokens, count = 0;
          void * v_ptr;
          SafeIO data;
          String * str_ptr = new String;
          int * int_ptr = new int;
          String A("A"), S("S"), R("R");
          char filename[30];
          cout << "Enter Filename: ";
          cin >> filename;
          ifstream inFile(filename);
          clearScreen();
          flushInput();

           if (!inFile) {
                cerr << "Data file could not be opened" << endl;
            exit(1);
            }

            data.read(inFile);
            n_tokens = data.getCount();
 
            while ( count < n_tokens )
            {
               if ( data.getType(count) == STOKEN )
               {
                   data.getData(str_ptr,count);
                   if ( *str_ptr == A )
                   {
                      count++;
                      data.getData(int_ptr,count);
                      queue.append(*int_ptr);
                      queue.display();
                      flushInput();
                   }          
                   else if ( *str_ptr == R ){
                      queue.serve_rear();
                      queue.display();
                      flushInput();
                   }
                   else if ( *str_ptr == S ){
                      queue.serve();
                      queue.display();
                      flushInput();
                   }
             }
             count++;
          }
          inFile.close();
      }

//QUIT
      else if ( option == 9 )
            return 0;
       else  
            cout << "Invalid Option, Please Choose Again";

      optionlist();
      cin >> option;
   }  // end while
   return 0;
}

void optionlist()
{
   cout << "\n\n\t\tQUEUE OPERATIONS\n";
   cout << "\n\n\t\t1: Serve\n";
   cout << "\t\t2: Retrieve\n";
   cout << "\t\t3: Serve and Retrieve\n";
   cout << "\t\t4: Serve Rear\n";
   cout << "\t\t5: Append\n";
   cout << "\t\t6: Full or Empty?\n";
   cout << "\t\t7: Size\n";
   cout << "\t\t8: Read from File\n";
   cout << "\t\t9: Quit\n";
   cout << "\n\n\t\tEnter Option: ";
}  

// end of main.cpp

This is the output that I am getting:

QUEUE OPERATIONS


                1: Serve
                        2: Retrieve
                                   3: Serve and Retrieve
                                                        4: Serve Rear
                                                                     5: Append
                                                                              6:
 Full or Empty?
               7: Size
                      8: Read from File
                                       9: Quit


                                              Enter Option:

// Here is the wanted program behavior:

Sample Output:
A: 1 * * * * * * * * *
A: 1 1 * * * * * * * *
A: 1 1 1 * * * * * * *
S: * 1 1 * * * * * * *
R: * 1 * * * * * * * *
S: * * * * * * * * * *
S: main.cpp:61:underflow
A: * * 1 * * * * * * *
A: * * 1 1 * * * * * *
A: * * 1 1 1 * * * * *
A: * * 1 1 1 1 * * * *
A: * * 1 1 1 1 1 * * *
A: * * 1 1 1 1 1 1 * *
A: * * 1 1 1 1 1 1 1 *
A: * * 1 1 1 1 1 1 1 1
A: 1 * 1 1 1 1 1 1 1 1
A: 1 1 1 1 1 1 1 1 1 1
A: main.cpp:47:overflow
S: 1 1 * 1 1 1 1 1 1 1

// Please advise

0
Comment
Question by:edelossantos
  • 4
  • 3
  • 2
9 Comments
 
LVL 17

Assisted Solution

by:rstaveley
rstaveley earned 100 total points
Comment Utility
There are quite a few wheels that you are reinventing here. Is this an academic exercise, or could you be talked into using the standard library for strings and containers?
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 400 total points
Comment Utility
My output is

                QUEUE OPERATIONS


                1: Serve
                2: Retrieve
                3: Serve and Retrieve
                4: Serve Rear
                5: Append
                6: Full or Empty?
                7: Size
                8: Read from File
                9: Quit


                Enter Option: 8
Enter Filename:


Looks ok for me. Your output is wrong as your monitor seems to make strange things when getting a <tab> character (== '\t' == ASCII 9"). As you are using tabs only at begin of line you may simply replace them by a number of spaces.

>>>> // Here is the wanted program behavior:
>>>> A: 1 * * * * * * * * *
 
Could you post an appropriate input file or give a description of the expected format?

Regards, Alex
0
 
LVL 17

Assisted Solution

by:rstaveley
rstaveley earned 100 total points
Comment Utility
I get the same output as Alex too.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 400 total points
Comment Utility
Ok, some debugging gives the following:

With option 8 and a input file containing a line like that:

  A A A R A A A A R R A A S A

i found errors in class SToken The constructors don't use the initializer list to initialize their String member (that would invoke the copy constructor of class String), however class String has no operator== defined, so it is a binary copy and we have two String objects sharing the same char* pointer. If one of them is running out of scope: kaboom! Del seemed to have recognized the problem and  created some *local_ptr* objects using 'new', those never were deleted anymore (That didn't help me as i have thrown them off). The way out naturally is to provide a String::operator= or - as a first approach - to change the SToken constructors to that:

    SToken(char * s="") : data(s) {}
    SToken (const SToken * in) : data(in->data) {}  

Now, the copy constructor could work and the (first) reason for crashing was solved.

However, the next crash immediately follows. Here:

               if ( data.getType(count) == STOKEN )
               {
                   data.getData(str_ptr,count);
                   if ( *str_ptr == A )
                   {
                      count++;
                      data.getData(int_ptr,count);   // HERE IS THE CRASH
                      queue.append(*int_ptr);
                      queue.display();
                      flushInput();
                   }          

We have a S(tring)Token and first call of data.getData fills str_ptr, that is a String*. OK.  However, next call to data.getData (why do we need a second call????) uses an 'int_ptr'. Kaboom again. Actually, i don't know what should happen here. So it is difficult to go further.

Regards, Alex
0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

Author Comment

by:edelossantos
Comment Utility
o.k....back online...this is an academic excercise; however,...I would like to see the standard libraries for string and containers.  Del
0
 

Author Comment

by:edelossantos
Comment Utility
// expected format:

PART I.
A deque ("deck" or DQ) is a double-ended queue. In addition to supporting all the standard operations of a queue, entries can also be removed or retrieved from the end of the queue. Thus, a deque is both FIFO and LIFO. Additional operations are:

serve_rear
retrieve_rear

* Implement a deque as a derived class from your Queue class. Recall that your Queue is implemented as circular static array. Continue to use a typedef to set the datatype of the Queue. We will use templates in the future.
* For demonstration purposes make your deque size 10 and code an operation 'display' that will display the entire deque including empty slots. This operation essentially violates the queue ADT, but is useful for "testing" purposes.

* From main read the queue operations from a file. This should be done outside your Queue since I/O is not part of the ADT and should be left to a higher layer (information hiding). You can assume the format of the file will follow this pattern exactly ( A = append, S = serve, R = serve_rear ); e.g:

A 10
A 50
S
R
R

Display the deque after every operation. This will allow you to see the 'snaking' behavior of a circular deque. Your code must test and display an error message for underflow and underflow conditions. DO NOT USE A MENU FOR THIS ASSIGNMENT. Sample output is as follows:
 Homework 3 Sample Output:
A: 1 * * * * * * * * *
A: 1 1 * * * * * * * *
A: 1 1 1 * * * * * * *
S: * 1 1 * * * * * * *
R: * 1 * * * * * * * *
S: * * * * * * * * * *
S: main.cpp:61:underflow
A: * * 1 * * * * * * *
A: * * 1 1 * * * * * *
A: * * 1 1 1 * * * * *
A: * * 1 1 1 1 * * * *
A: * * 1 1 1 1 1 * * *
A: * * 1 1 1 1 1 1 * *
A: * * 1 1 1 1 1 1 1 *
A: * * 1 1 1 1 1 1 1 1
A: 1 * 1 1 1 1 1 1 1 1
A: 1 1 1 1 1 1 1 1 1 1
A: main.cpp:47:overflow
S: 1 1 * 1 1 1 1 1 1 1

can you also recommend a url for part 2:

PART II.
Answer the following questions in a text file or turn in a hard copy.

1. Assume you have an input stream '1 2 3 4 5 6' reading from left to right. By using (1) a queue and (2) a deque, which of the following rearrangements can be obtained for output, reading from left-to-right?

a)  1 2 3 4 5 6           b) 2 4 3 6 5 1         c) 1 5 2 4 3 6
d)  4 2 1 3 5 6           e) 1 2 6 4 5 3         f) 5 2 6 3 4 1

2. Compute log2 1000 if all you know is log2 10. Show your work and justify why it is correct.

3. Show how logs "turn" multiplication into addition, division into subtraction, and exponentiation into multiplication.

4. A fully populated binary tree has all nodes (vertices) present. Assuming a tree with one node has height 1, what is the height of a fully populated tree with n nodes? A well-behaved binary tree may not have all levels fully populated, but all leaves in the tree will be on the same or on adjacent levels. What is the height of a well-behaved binary tree with n nodes? (hint: use the floor or ceil function from the math library.)




0
 

Author Comment

by:edelossantos
Comment Utility
o.k....with you so far:

   QUEUE OPERATIONS


   1: Serve
   2: Retrieve
   3: Serve and Retrieve
   4: Serve Rear
   5: Append
   6: Full or Empty?
   7: Size
   8: Read from File
   9: Quit


   Enter Option:
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
Hints to Part II:

(1)  

Actually the problem isn't well defined. A dequeue has the advantage that you either could insert at front or at the rear. But, if you think a queue being a ring there is no difference between inserting at the front or at the rear as turning the ring by one position would make both operations equivalent. So as long as you are allowed to turn the ring before inserting next number you may obtain any sequence you want. So, the question only makes sense if you are *not* allowed to turn the ring while inserting. Then, a queue only can obtain the trivial solution, and a dequeue only one of tthe sequences above (try to construct the given sequence by starting with 1 and adding the next numbers at the front or at the back.

(2)

log2 (a *b) == log2 a + log2 b

Applying that rule should easily give the solution.


(3)

Look at rule (2). You simply have to add the rules for divison and exponantion same way.


(4)

The height of a full populated tree is simple to compute. Look at the number of nodes for height = 1,..4

1  :  1
2  :  3
3:    7
4:   15

(Hint: add 1 to number of nodes)

Unfortunately, the next problem isn't well defined: "A well-behaved binary tree may not have all levels fully populated, but all leaves in the tree will be on the same or on adjacent levels."

If we take "leave" as a node that has no child nodes, the definition above would cover trees like that:

         O                                    O
            \                                /   \
              O                            O    O
                \
                  O

You see, both have 3 nodes and the leaves all are on the lowest level, but the heights are 3 and 2. So, actually i don't unterstand the problem as you only may tell a range for the height, but not an exact value. Also the hint using the floor or ceil function makes not much sense as it is a mathematical problem that should be expressed using mathematicals terms (e. g. highest integer below log x) rather than using C functions of the math library.

Regards, Alex


 

 

 



0
 

Author Comment

by:edelossantos
Comment Utility
Thank you Alex.  Del
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now