Broken for loop in c++

This is a discussion on Broken for loop in c++ within the C++ Programming forums, part of the General Programming Boards category; edit: got the code formatted a little better. Tabs are replaced by single spaces, but at least its halfway readable ...

  1. #1
    Registered User
    Join Date
    Oct 2013
    Posts
    7

    Broken for loop in c++

    edit: got the code formatted a little better. Tabs are replaced by single spaces, but at least its halfway readable now

    This'll be a long post, so I'll start with just the gist of the problem, and fill in more and more detail throughout the post.

    And just to get this out of the way, I'm a self learner and a beginner, not a professional or a student, so there may/will be things I am expected to know but don't, about style and such, or certain terms for things I'm not familiar with.
    So basically, I'm having problems with a simple for loop that looks like this:
    Code:
    for (int z = index; z >= 0; z--) {
           //do this
           //do that
       }

    with the variable "index" being an int that takes as its value the size of a vector I am using, minus 1.
    The idea is to count down from whatever index is and select each element in the vector and do stuff with it.
    Instead, this for loop will take some weird number as its index variable, as if Id assigned z to a random number. It then increments the index variable instead of decrementing it, as if I had z++ instead of z--. There is no other statement anywhere in this program that uses any variable called "z" for anything, much less an assignment statement for it other than the "int z = index" in the header of the for loop itself.
    I have tested it a lot. It doesn't matter what I do, I cannot get this for loop to work properly. Here is the entire for loop.
    And I don't know what's wrong with this forum or with my post, but its putting extra code tags behind the word "for" and I cant get it to quit doing it, and then its getting the tabs and spacing of the code all jacked up to where its hard to see how things fit together.

    Code:
     for (int z = index; z >= 0; z--) {
      cout << "requests.size() - 1 == " << requests.size() - 1 << ", but z == " << z << endl;
      cout << "requests.size() == " << requests.size() << ", selecting requests[" << z << "]. . ." << endl;
      if (requests.size() == 0) break;
      int currentRequest = requests[z];
      //cout << "currentRequest == " << currentRequest << endl;
      requests.remove(z);
      //cout << "for (int j = remaining.size() - 1; j >= 0; j--). . ." << endl;
      for (int j = remaining.size() - 1; j >= 0; j--) {
       cout << "remaining[" << j << "]. . ." << endl;
       if (remaining[j] >= currentRequest) {
        //cout << "remaining[j] >= currentRequest" << endl;
        if (requests.size() <= 0) {
         //cout << "requests.size() <= 0" << endl;
         pipes.add(remaining.size());
        } else {
         remaining[j] -= currentRequest;
         cut(requests, remaining, pipes);
         remaining[j] += currentRequest;
        }
       }
      }
      int newPipe = PIPE_LENGTH - currentRequest;
      remaining.add(newPipe);
      cut(requests, remaining, pipes);
      remaining.remove(remaining.size() - 1);
     }

    So I don't expect anyone to read through that garbled mess, it is easier to read in my compiler :/
    Anyway, its part of a function that calls itself to do cool stuff. I'm supposed to be learning about recursive backtracking, and I've already done 9 exercises in this chapter, and hundreds more before I got to this chapter of the book (Chapter 9 of "Programming Abstractions in C++" by Eric Roberts). In all of that time, I have never had an issue with for loops. Everything else in my crappy programs can fall apart, but if nothing else, at least the language and the compiler always work, and I can spend hours debugging and it always comes back to something I did wrong, never the language or compiler, so this problem is shaking me up a little bit.
    Now, at this point I wanted to copy-paste a little bit of the output from the console, but I cant seem to copy-paste it. But its showing that "index" is given the value -1, and the very next statement is the for loop. The for loop begins, and shows values of z starting with 2, then 3, then 4, on up to 7, which isn't anywhere near what its supposed to be. It isn't even going in the right direction, its supposed to be decrementing by 1, not incrementing!
    As for that, Ive tried changing the "z--" to "z -= 1" and then "z = z - 1" and it wont work(and if it HAD work, I wouldn't feel any better, because as Ive said, up to now I have never had a problem with a for loop)
    I have tried assigning the variable z to index before the for loop, as follows:
    Code:
     int z = index;
     for(; z >= 0; z--) {
         //stuff
     }
    of course that didn't work.
    I can even have
    Code:
     int z = index;
     cout << "z before for loop: " << z << endl;
     for(; z >= 0; z--) {
         cout << "z: " << z << endl;
         //other stuff
     }
    and it will show z to be the proper value as assigned before the for loop, but then in the for loop itself, its showing some weird number like 2 to start with, then incrementing instead of decrementing, and then terminating at another weird number like 6 or 7!
    Next I'll post the entire program. I wouldn't think anyone would want or need to read through all of it, but here it is, just so I can know I haven't withheld any information.

    edit: the broken for loop begins on line 69

    Code:
    #include <iostream>
    
    #include "console.h"
    #include "vector.h"
    #include "simpio.h"
    #include "foreach.h"
    
    using namespace std;
    
    //global variables
    //constants
    int PIPE_LENGTH = 10;
    
    //prototypes
    int cutStock(Vector<int> &requests);
    void cut(Vector<int> &requests, Vector<int> remaining, Vector<int> &pipes);
    
    //main
    int main() {
     for (int i = -5; i < 0; i++) {
      cout << "i: " << i << endl;
     }
     int x = 0;
     int stockLength = PIPE_LENGTH;
     Vector<int> requests;
     while (true) {
      while (true) {
       x = getInteger("x: ");
       if (x <= 0) break;
       requests.add(x);
      }
      if (requests.size() <= 0) break;
      cout << cutStock(requests) << " stock pipes needed." << endl;
      requests.clear();
     }
     return 0;
    }
    
    //functions
    int cutStock(Vector<int> &requests) {
     int result = -1;
     Vector<int> remaining;
     Vector<int> pipes;
     cut(requests, remaining, pipes);
     //cout << "pipes.size() == " << pipes.size() << endl;
     for (int i = 0; i < pipes.size(); i++) {
      //cout << "pipes[" << i << "] == " << pipes[i] << endl;
      if (pipes[i] < result || result == -1) {
       result = pipes[i];
      }
      //cout << pipes[i] << endl;
     }
     return result;
    }
    
    void cut(Vector<int> &requests, Vector<int> remaining, Vector<int> &pipes) {
     if (requests.size() <= 0) pipes.add(remaining.size());
     int index = requests.size() - 1;
     cout << "for (int i = requests.size() - 1; i >= 0; i--). . ." << endl;
     cout << "requests.size() - 1 == " << requests.size() - 1 << endl;
     cout << "index ........ing == " << index << endl;
     for (int i = index; i >= 0; i--) {
      cout << "i ........ing == " << i << endl;
     }
     int i = index;
     cout << "*****************" << endl;
     cout << "i == " << i << endl;
     cout << "*****************" << endl;
     for (int z = index; z >= 0; z--, cout << "zinfor: " << z << endl) {
      cout << "requests.size() - 1 == " << requests.size() - 1 << ", but z == " << z << endl;
      cout << "requests.size() == " << requests.size() << ", selecting requests[" << z << "]. . ." << endl;
      if (requests.size() == 0) break;
      int currentRequest = requests[z];
      //cout << "currentRequest == " << currentRequest << endl;
      requests.remove(z);
      //cout << "for (int j = remaining.size() - 1; j >= 0; j--). . ." << endl;
      for (int j = remaining.size() - 1; j >= 0; j--) {
       cout << "remaining[" << j << "]. . ." << endl;
       if (remaining[j] >= currentRequest) {
        //cout << "remaining[j] >= currentRequest" << endl;
        if (requests.size() <= 0) {
         //cout << "requests.size() <= 0" << endl;
         pipes.add(remaining.size());
        } else {
         remaining[j] -= currentRequest;
         cut(requests, remaining, pipes);
         remaining[j] += currentRequest;
        }
       }
      }
      int newPipe = PIPE_LENGTH - currentRequest;
      remaining.add(newPipe);
      cut(requests, remaining, pipes);
      remaining.remove(remaining.size() - 1);
     }
    }
    "simpio.h", "vector.h", and "console.h" are part of the Stanford C++ libraries that go with the book I'm using, and that students taking CS courses at Stanford use. I've been using them throughout the book so far, and done loads of exercises using them, and while I have had some issues here and there, never anything like this. I'm 99.999% sure they do not reprogram the frickin for loop somehow.
    The "vector.h" is just a simplified version of the vector in the c++ standard library, but its not exactly the same thing. Its supposedly simplified in such a way that the student will be able to implement it later in the book, though I haven't gotten that far just yet. In any case, I haven't had any trouble with it, and its been involved in plenty of for loops doing all kinds of odd stuff. So I don't think that its the problem either.
    My compiler is Microsoft Visual Studio 2008 Express.
    The exercise is to create a program that takes as input from the user several numbers (int) greater than 0 and less than or equal to 10. The program should output the minimum number of stock pipes of length 10 you must have to be able to get a pipe of each length input by the user. Say you gave it 3, 3, and 3, it would give you 1 stock pipe because its length is 10, and you can cut 3 lengths of 3 from it and have 1 left over. For two 6s, you would need two stock pipes, etc. I don't want to know how to do this, the idea is for me to figure that part out, I just want my for loop to work.
    Any help would be appreciated. Im gonna move on from this particular problem anyway. Im a completionist but f's sake, just this one thing is holding me back, Im a full week at least behind where I would be if I hadn't got hung up on this lol
    Or actually no. Im gonna just axe the for loop and turn it into a while loop with a break, but I hope to god that doesn't work, because that would mean I cant even use for loops anymore, Im hoping its just a silly thing I messed up like it always has been, I like knowing that every problem is fixable, keeps me from just skipping to the next problem whenever I have a hard time debugging something.
    Anyway, if anyone actually read this far, thanks. The post is probably too long. Ive never done this before, so I don't really know exactly how much information to give.. so I gave.. like... all of it.
    Last edited by Stark_Barksalt; 10-15-2013 at 12:42 AM. Reason: crappy looking code

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    Please edit your post, and re-paste your code using the "paste as text" option.

    Your code has been mangled by embedded BB font/colour codes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,758
    For code formatting, I would expect something like this:
    Code:
    #include <iostream>
    #include "console.h"
    #include "vector.h"
    #include "simpio.h"
    #include "foreach.h"
    
    using namespace std;
    
    //global variables
    //constants
    int PIPE_LENGTH = 10;
    
    //prototypes
    int cutStock(Vector<int> &requests);
    void cut(Vector<int> &requests, Vector<int> remaining, Vector<int> &pipes);
    
    //main
    int main() {
        int x = 0;
        int stockLength = PIPE_LENGTH;
        Vector<int> requests;
        while (true) {
            while (true) {
                x = getInteger("x: ");
                if (x <= 0)
                    break;
                requests.add(x);
            }
            if (requests.size() <= 0)
                break;
            cout << cutStock(requests) << " stock pipes needed." << endl;
            requests.clear();
        }
        return 0;
    }
    
    //functions
    int cutStock(Vector<int> &requests) {
        int result = -1;
        Vector<int> remaining;
        Vector<int> pipes;
        cut(requests, remaining, pipes);
        //cout << "pipes.size() == " << pipes.size() << endl;
    
        for (int i = 0; i < pipes.size(); i++) {
            //cout << "pipes[" << i << "] == " << pipes[i] << endl;
    
            if (pipes[i] < result || result == -1) {
                result = pipes[i];
            }
            //cout << pipes[i] << endl;
        }
        return result;
    }
    
    void cut(Vector<int> &requests, Vector<int> remaining, Vector<int> &pipes) {
        if (requests.size() <= 0)
            pipes.add(remaining.size());
        int index = requests.size() - 1;
        cout << "for (int i = requests.size() - 1; i >= 0; i--). . ." << endl;
        cout << "requests.size() - 1 == " << requests.size() - 1 << endl;
        cout << "index ........ing == " << index << endl;
        for (int i = index; i >= 0; i--) {
            cout << "i ........ing == " << i << endl;
        }
        int i = index;
        cout << "*****************" << endl;
        cout << "index == " << index << endl;
        cout << "*****************" << endl;
        int z = index;
        cout << "*****************" << endl;
        cout << "z == " << z << endl;
        cout << "*****************" << endl;
        z--;
        cout << "*****************" << endl;
        cout << "z-- == " << z << endl;
        cout << "*****************" << endl;
        z++;
        cout << "*****************" << endl;
        cout << "z++ == " << z << endl;
        cout << "*****************" << endl;
        for (int z = index; z > -1; z--) {
            //couts to see in the output what my variable are, because I suck at using the debugger
            cout << "requests.size() - 1 == " << requests.size() - 1
                 << ", but z == " << z << endl;
            cout << "requests.size() == " << requests.size()
                 << ", selecting requests[" << z << "]. . ." << endl;
            /*A break, which wouldnt be here if the for loop werent broken.
            Without the break statement, will select elements outside the
            range of the vector.*/
    
            if (requests.size() == 0)
                break;
            int currentRequest = requests[z];
            //Just checking the value of the variable with a cout again...
            cout << "currentRequest == " << currentRequest << endl;
            //Then removing this element of the vector
            requests.remove(z);
            /* This nested for loop seems to work fine, but
            its impossible for me to know for sure, since its
            nested within a broken piece of ........ for loop*/
    
            for (int j = remaining.size() - 1; j >= 0; j--) {
                if (remaining[j] >= currentRequest) {
                    if (requests.size() <= 0) {
                        pipes.add(remaining.size());
                    }
                    else {
                        remaining[j] -= currentRequest;
                        /*cut(requests, remaining, pipes) is a
                        recursive call, calls the function containing all of
                        this stuff, including the broken for loop*/
                        cut(requests, remaining, pipes);
                        remaining[j] += currentRequest;
                    }
                }
            }
            //Other stuff that probably works
    
            int newPipe = PIPE_LENGTH - currentRequest;
            remaining.add(newPipe);
            /*cut(requests, remaining, pipes) calls the function
            containing this entire mess recursively*/
            cut(requests, remaining, pipes);
            remaining.remove(remaining.size() - 1);
        }
    }
    Next, you're using a Vector type for which the class definition was not shown. What is the return type of the size member function? It looks like you think that it could return a negative number, but it might have an unsigned integer type as the return type.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Oct 2013
    Posts
    7
    ^yes that's what the code looks like in my compiler. Sorry it got jacked up in translation.

    By "size member" if you mean what "requests.size()" would return, it returns an int, not an unsigned int.

    Vector<ValueType>

  5. #5
    Registered User
    Join Date
    Oct 2013
    Posts
    7
    the header for the Vector type

    Code:
    /*
     * File: vector.h
     * --------------
     * This file exports the <code>Vector</code> class, which provides an
     * efficient, safe, convenient replacement for the array type in C++.
     */
    
    #ifndef _vector_h
    #define _vector_h
    
    #include <iterator>
    #include <iostream>
    #include <sstream>
    #include <string>
    #include "foreach.h"
    #include "strlib.h"
    
    /*
     * Class: Vector<ValueType>
     * ------------------------
     * This class stores an ordered list of values similar to an array.
     * It supports traditional array selection using square brackets, but
     * also supports inserting and deleting elements.  It is similar in
     * function to the STL <code>vector</code> type, but is simpler both
     * to use and to implement.
     */
    
    template <typename ValueType>
    class Vector {
    
    public:
    
    /*
     * Constructor: Vector
     * Usage: Vector<ValueType> vec;
     *        Vector<ValueType> vec(n, value);
     * ---------------------------------------
     * Initializes a new vector.  The default constructor creates an
     * empty vector.  The second form creates an array with <code>n</code>
     * elements, each of which is initialized to <code>value</code>;
     * if <code>value</code> is missing, the elements are initialized
     * to the default value for the type.
     */
    
       Vector();
       explicit Vector(int n, ValueType value = ValueType());
    
    /*
     * Destructor: ~Vector
     * -------------------
     * Frees any heap storage allocated by this vector.
     */
    
       virtual ~Vector();
    
    /*
     * Method: size
     * Usage: int nElems = vec.size();
     * -------------------------------
     * Returns the number of elements in this vector.
     */
    
       int size() const;
    
    /*
     * Method: isEmpty
     * Usage: if (vec.isEmpty()) ...
     * -----------------------------
     * Returns <code>true</code> if this vector contains no elements.
     */
    
       bool isEmpty() const;
    
    /*
     * Method: clear
     * Usage: vec.clear();
     * -------------------
     * Removes all elements from this vector.
     */
    
       void clear();
    
    /*
     * Method: get
     * Usage: ValueType val = vec.get(index);
     * --------------------------------------
     * Returns the element at the specified index in this vector.  This
     * method signals an error if the index is not in the array range.
     */
    
       const ValueType & get(int index) const;
    
    /*
     * Method: set
     * Usage: vec.set(index, value);
     * -----------------------------
     * Replaces the element at the specified index in this vector with
     * a new value.  The previous value at that index is overwritten.
     * This method signals an error if the index is not in the array range.
     */
    
       void set(int index, const ValueType & value);
    
    /*
     * Method: insert
     * Usage: vec.insert(0, value);
     * ----------------------------
     * Inserts the element into this vector before the specified index.
     * All subsequent elements are shifted one position to the right.  This
     * method signals an error if the index is outside the range from 0
     * up to and including the length of the vector.
     */
    
       void insert(int index, ValueType value);
    
    /*
     * Method: remove
     * Usage: vec.remove(index);
     * -------------------------
     * Removes the element at the specified index from this vector.
     * All subsequent elements are shifted one position to the left.  This
     * method signals an error if the index is outside the array range.
     */
    
       void remove(int index);
    
    /*
     * Method: add
     * Usage: vec.add(value);
     * ----------------------
     * Adds a new value to the end of this vector.  To ensure compatibility
     * with the <code>vector</code> class in the Standard Template Library,
     * this method is also called <code>push_back</code>.
     */
    
       void add(ValueType value);
       void push_back(ValueType value);
    
    /*
     * Operator: []
     * Usage: vec[index]
     * -----------------
     * Overloads <code>[]</code> to select elements from this vector.
     * This extension enables the use of traditional array notation to
     * get or set individual elements.  This method signals an error if
     * the index is outside the array range.  The file supports two
     * versions of this operator, one for <code>const</code> vectors and
     * one for mutable vectors.
     */
    
       ValueType & operator[](int index);
       const ValueType & operator[](int index) const;
    
    /*
     * Operator: +
     * Usage: v1 + v2
     * --------------
     * Concatenates two vectors.
     */
    
       Vector operator+(const Vector & v2) const;
    
    /*
     * Operator: +=
     * Usage: v1 += v2;
     *        v1 += value;
     * -------------------
     * Adds all of the elements from <code>v2</code> (or the single
     * specified value) to <code>v1</code>.  As a convenience, the
     * <code>Vector</code> package also overloads the comma operator so
     * that it is possible to initialize a vector like this:
     *
     *<pre>
     *    Vector&lt;int&gt; digits;
     *    digits += 0, 1, 2, 3, 4, 5, 6, 7, 8, 9;
     *</pre>
     */
    
       Vector & operator+=(const Vector & v2);
       Vector & operator+=(const ValueType & value);
    
    /*
     * Method: toString
     * Usage: string str = vec.toString();
     * -----------------------------------
     * Converts the vector to a printable string representation.
     */
    
       std::string toString();
    
    /*
     * Method: mapAll
     * Usage: vec.mapAll(fn);
     * ----------------------
     * Calls the specified function on each element of the vector in
     * ascending index order.
     */
    
       void mapAll(void (*fn)(ValueType)) const;
       void mapAll(void (*fn)(const ValueType &)) const;
    
       template <typename FunctorType>
       void mapAll(FunctorType fn) const;
    
    /*
     * Additional Vector operations
     * ----------------------------
     * In addition to the methods listed in this interface, the Vector
     * class supports the following operations:
     *
     *   - Stream I/O using the << and >> operators
     *   - Deep copying for the copy constructor and assignment operator
     *   - Iteration using the range-based for statement or STL iterators
     *
     * The iteration forms process the Vector in index order.
     */
    
    /* Private section */
    
    /**********************************************************************/
    /* Note: Everything below this point in the file is logically part    */
    /* of the implementation and should not be of interest to clients.    */
    /**********************************************************************/
    
    private:
    
    /*
     * Implementation notes: Vector data structure
     * -------------------------------------------
     * The elements of the Vector are stored in a dynamic array of
     * the specified element type.  If the space in the array is ever
     * exhausted, the implementation doubles the array capacity.
     */
    
    /* Instance variables */
    
       ValueType *elements;        /* A dynamic array of the elements   */
       int capacity;               /* The allocated size of the array   */
       int count;                  /* The number of elements in use     */
    
    /* Private methods */
    
       void expandCapacity();
       void deepCopy(const Vector & src);
    
    /*
     * Hidden features
     * ---------------
     * The remainder of this file consists of the code required to
     * support deep copying and iteration.  Including these methods
     * in the public interface would make that interface more
     * difficult to understand for the average client.
     */
    
    public:
    
    /*
     * Deep copying support
     * --------------------
     * This copy constructor and operator= are defined to make a deep copy,
     * making it possible to pass or return vectors by value and assign
     * from one vector to another.
     */
    
       Vector(const Vector & src);
       Vector & operator=(const Vector & src);
    
    /*
     * Operator: ,
     * -----------
     * Adds an element to the vector passed as the left-hand operatand.
     * This form makes it easier to initialize vectors in old versions of C++.
     */
    
       Vector & operator,(const ValueType & value);
    
    /*
     * Iterator support
     * ----------------
     * The classes in the StanfordCPPLib collection implement input
     * iterators so that they work symmetrically with respect to the
     * corresponding STL classes.
     */
    
       class iterator :
          public std::iterator<std::random_access_iterator_tag, ValueType> {
    
       private:
          const Vector *vp;
          int index;
    
       public:
    
          iterator() {
             this->vp = NULL;
          }
    
          iterator(const iterator & it) {
             this->vp = it.vp;
             this->index = it.index;
          }
    
          iterator(const Vector *vp, int index) {
             this->vp = vp;
             this->index = index;
          }
    
          iterator & operator++() {
             index++;
             return *this;
          }
    
          iterator operator++(int) {
             iterator copy(*this);
             operator++();
             return copy;
          }
    
          iterator & operator--() {
             index--;
             return *this;
          }
    
          iterator operator--(int) {
             iterator copy(*this);
             operator--();
             return copy;
          }
    
          bool operator==(const iterator & rhs) {
             return vp == rhs.vp && index == rhs.index;
          }
    
          bool operator!=(const iterator & rhs) {
             return !(*this == rhs);
          }
    
          bool operator<(const iterator & rhs) {
             extern void error(std::string msg);
             if (vp != rhs.vp) error("Iterators are in different vectors");
             return index < rhs.index;
          }
    
          bool operator<=(const iterator & rhs) {
             extern void error(std::string msg);
             if (vp != rhs.vp) error("Iterators are in different vectors");
             return index <= rhs.index;
          }
    
          bool operator>(const iterator & rhs) {
             extern void error(std::string msg);
             if (vp != rhs.vp) error("Iterators are in different vectors");
             return index > rhs.index;
          }
    
          bool operator>=(const iterator & rhs) {
             extern void error(std::string msg);
             if (vp != rhs.vp) error("Iterators are in different vectors");
             return index >= rhs.index;
          }
    
          iterator operator+(const int & rhs) {
             return iterator(vp, index + rhs);
          }
    
          iterator operator+=(const int & rhs) {
             index += rhs;
             return *this;
          }
    
          iterator operator-(const int & rhs) {
             return iterator(vp, index - rhs);
          }
    
          iterator operator-=(const int & rhs) {
             index -= rhs;
             return *this;
          }
    
          int operator-(const iterator & rhs) {
             extern void error(std::string msg);
             if (vp != rhs.vp) error("Iterators are in different vectors");
             return index - rhs.index;
          }
    
          ValueType & operator*() {
             return vp->elements[index];
          }
    
          ValueType *operator->() {
             return &vp->elements[index];
          }
    
          ValueType & operator[](int k) {
             return vp->elements[index + k];
          }
    
       };
    
       iterator begin() const {
          return iterator(this, 0);
       }
    
       iterator end() const {
          return iterator(this, count);
       }
    
    };
    
    /* Implementation section */
    
    extern void error(std::string msg);
    
    /*
     * Implementation notes: Vector constructor and destructor
     * -------------------------------------------------------
     * The constructor allocates storage for the dynamic array
     * and initializes the other fields of the object.  The
     * destructor frees the memory used for the array.
     */
    
    template <typename ValueType>
    Vector<ValueType>::Vector() {
       count = capacity = 0;
       elements = NULL;
    }
    
    template <typename ValueType>
    Vector<ValueType>::Vector(int n, ValueType value) {
       count = capacity = n;
       elements = (n == 0) ? NULL : new ValueType[n];
       for (int i = 0; i < n; i++) {
          elements[i] = value;
       }
    }
    
    template <typename ValueType>
    Vector<ValueType>::~Vector() {
       if (elements != NULL) delete[] elements;
    }
    
    /*
     * Implementation notes: Vector methods
     * ------------------------------------
     * The basic Vector methods are straightforward and should require
     * no detailed documentation.
     */
    
    template <typename ValueType>
    int Vector<ValueType>::size() const {
       return count;
    }
    
    template <typename ValueType>
    bool Vector<ValueType>::isEmpty() const {
       return count == 0;
    }
    
    template <typename ValueType>
    void Vector<ValueType>::clear() {
       if (elements != NULL) delete[] elements;
       count = capacity = 0;
       elements = NULL;
    }
    
    template <typename ValueType>
    const ValueType & Vector<ValueType>::get(int index) const {
       if (index < 0 || index >= count) error("get: index out of range");
       return elements[index];
    }
    
    template <typename ValueType>
    void Vector<ValueType>::set(int index, const ValueType & value) {
       if (index < 0 || index >= count) error("set: index out of range");
       elements[index] = value;
    }
    
    /*
     * Implementation notes: insert, remove, add
     * -----------------------------------------
     * These methods must shift the existing elements in the array to
     * make room for a new element or to close up the space left by a
     * deleted one.
     */
    
    template <typename ValueType>
    void Vector<ValueType>::insert(int index, ValueType value) {
       if (count == capacity) expandCapacity();
       if (index < 0 || index > count) {
          error("insert: index out of range");
       }
       for (int i = count; i > index; i--) {
          elements[i] = elements[i - 1];
       }
       elements[index] = value;
       count++;
    }
    
    template <typename ValueType>
    void Vector<ValueType>::remove(int index) {
       if (index < 0 || index >= count) error("remove: index out of range");
       for (int i = index; i < count - 1; i++) {
          elements[i] = elements[i + 1];
       }
       count--;
    }
    
    template <typename ValueType>
    void Vector<ValueType>::add(ValueType value) {
       insert(count, value);
    }
    
    template <typename ValueType>
    void Vector<ValueType>::push_back(ValueType value) {
       insert(count, value);
    }
    
    /*
     * Implementation notes: Vector selection
     * --------------------------------------
     * The following code implements traditional array selection using
     * square brackets for the index.
     */
    
    template <typename ValueType>
    ValueType & Vector<ValueType>::operator[](int index) {
       if (index < 0 || index >= count) error("Selection index out of range");
       return elements[index];
    }
    template <typename ValueType>
    const ValueType & Vector<ValueType>::operator[](int index) const {
       if (index < 0 || index >= count) error("Selection index out of range");
       return elements[index];
    }
    
    template <typename ValueType>
    Vector<ValueType> Vector<ValueType>::operator+(const Vector & v2) const {
       Vector<ValueType> vec = *this;
       foreach (ValueType value in v2) {
          vec.add(value);
       }
       return vec;
    }
    
    template <typename ValueType>
    Vector<ValueType> & Vector<ValueType>::operator+=(const Vector & v2) {
       foreach (ValueType value in v2) {
          *this += value;
       }
       return *this;
    }
    
    template <typename ValueType>
    Vector<ValueType> & Vector<ValueType>::operator+=(const ValueType & value) {
       this->add(value);
       return *this;
    }
    
    template <typename ValueType>
    std::string Vector<ValueType>::toString() {
       ostringstream os;
       os << *this;
       return os.str();
    }
    
    /*
     * Implementation notes: copy constructor and assignment operator
     * --------------------------------------------------------------
     * The constructor and assignment operators follow a standard paradigm,
     * as described in the associated textbook.
     */
    
    template <typename ValueType>
    Vector<ValueType>::Vector(const Vector & src) {
       deepCopy(src);
    }
    
    template <typename ValueType>
    Vector<ValueType> & Vector<ValueType>::operator=(const Vector & src) {
       if (this != &src) {
          if (elements != NULL) delete[] elements;
          deepCopy(src);
       }
       return *this;
    }
    
    template <typename ValueType>
    void Vector<ValueType>::deepCopy(const Vector & src) {
       count = capacity = src.count;
       elements = (capacity == 0) ? NULL : new ValueType[capacity];
       for (int i = 0; i < count; i++) {
          elements[i] = src.elements[i];
       }
    }
    
    /*
     * Implementation notes: The , operator
     * ------------------------------------
     * The comma operator works adding the right operand to the vector and
     * then returning the vector by reference so that it is set for the next
     * value in the chain.
     */
    
    template <typename ValueType>
    Vector<ValueType> & Vector<ValueType>::operator,(const ValueType & value) {
       this->add(value);
       return *this;
    }
    
    /*
     * Implementation notes: mapAll
     * ----------------------------
     * The various versions of the mapAll function apply the function or
     * function object to each element in ascending index order.
     */
    
    template <typename ValueType>
    void Vector<ValueType>::mapAll(void (*fn)(ValueType)) const {
       for (int i = 0; i < count; i++) {
          fn(elements[i]);
       }
    }
    
    template <typename ValueType>
    void Vector<ValueType>::mapAll(void (*fn)(const ValueType &)) const {
       for (int i = 0; i < count; i++) {
          fn(elements[i]);
       }
    }
    
    template <typename ValueType>
    template <typename FunctorType>
    void Vector<ValueType>::mapAll(FunctorType fn) const {
       for (int i = 0; i < count; i++) {
          fn(elements[i]);
       }
    }
    
    /*
     * Implementation notes: expandCapacity
     * ------------------------------------
     * This function doubles the array capacity, copies the old elements
     * into the new array, and then frees the old one.
     */
    
    template <typename ValueType>
    void Vector<ValueType>::expandCapacity() {
       capacity = max(1, capacity * 2);
       ValueType *array = new ValueType[capacity];
       for (int i = 0; i < count; i++) {
          array[i] = elements[i];
       }
       if (elements != NULL) delete[] elements;
       elements = array;
    }
    
    /*
     * Implementation notes: << and >>
     * -------------------------------
     * The insertion and extraction operators use the template facilities in
     * strlib.h to read and write generic values in a way that treats strings
     * specially.
     */
    
    template <typename ValueType>
    std::ostream & operator<<(std::ostream & os, const Vector<ValueType> & vec) {
       os << "{";
       int len = vec.size();
       for (int i = 0; i < len; i++) {
          if (i > 0) os << ", ";
          writeGenericValue(os, vec[i], true);
       }
       return os << "}";
    }
    
    template <typename ValueType>
    std::istream & operator>>(std::istream & is, Vector<ValueType> & vec) {
       char ch;
       is >> ch;
       if (ch != '{') error("operator >>: Missing {");
       vec.clear();
       is >> ch;
       if (ch != '}') {
          is.unget();
          while (true) {
             ValueType value;
             readGenericValue(is, value);
             vec += value;
             is >> ch;
             if (ch == '}') break;
             if (ch != ',') {
                error(std::string("operator >>: Unexpected character ") + ch);
             }
          }
       }
       return is;
    }
    
    #endif

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Did I read you correctly to say that index=-1? If so, your for loop isn't (hopefully!) running, not even once, and you are (hopefully!) looking at debugging printouts from somewhere else, or maybe just the regular output of your program. Are you definitely getting the "zinfor" printout? What about if you cut out the bits we can't replicate, and just try something like
    Code:
    #include <iostream>
    
    int main() {
    
        int index = -1;
        std::cout << index << std::endl;
        for (int z = index; z >= 0; z--, std::cout << "zinfor: " << z << std::endl)
            std::cout << "Inside for loop: z=" << z << std::endl;
        std::cout << "for loop finished";
        return 0;
    }
    Does that work?

  7. #7
    Registered User
    Join Date
    Oct 2013
    Posts
    7
    Quote Originally Posted by tabstop View Post
    Did I read you correctly to say that index=-1? If so, your for loop isn't (hopefully!) running, not even once, and you are (hopefully!) looking at debugging printouts from somewhere else, or maybe just the regular output of your program. Are you definitely getting the "zinfor" printout? What about if you cut out the bits we can't replicate, and just try something like
    Code:
     #include <iostream>
     int main() {
         int index = -1;
         std::cout << index << std::endl;
         for (int z = index; z >= 0; z--, std::cout << "zinfor: " << z << std::endl)
             std::cout << "Inside for loop: z=" << z << std::endl;
         std::cout << "for loop finished";
         return 0;
     }
    Does that work?
    Yes, that code will work. I tried several similar tests, on line 62 of the program in the original post there is a for loop with no purpose other than to try it out to see what's up, and it actually works fine.

    Its only when the for loop include instructions that manipulate elements of a vector that the for loop breaks.

    I do have a working version of the program now, though I haven't figured out WHY this version works and the original does not.

    But after reading a little bit about how you're supposed to ask these questions, especially when it comes to displaying code, I think I might have posted annoying, lazy looking code that's too painful to try to follow.

    My reasoning for not cleaning things up was basically that I was only having problems with that specific for loop, and so I didn't need to go through the trouble of making the rest of the program understandable. Which is kind of rude I guess.

    Anyway, I re-wrote the program to make its purpose self-evident and easy to follow, with lots of comments and whatnot.

    Well, when I ran it this way, it just worked. Just like that. No broken for loop, and as far as I can tell, the entire program does what its supposed to do, and the assignment is complete.

    I still don't understand why the for loop in the original crappy version of the program wont work. The function is called many different times based on input from the user, and the variable "index" takes on different values, but its only when that value is -1 that it starts to act ridiculous. I don't even have a clue why.

    Anyway, I'm gonna go ahead and post my cleaned up version of the solution. It seems to work, though I haven't tested it extensively. The for loop, at least, MUST work or it would be selecting elements outside the range of one of the vectors.

    So I have something that works, even though I have no idea why it originally wouldn't work. Id still like to know why my for loop was broken, and I still have the original crappy version of the program to play around with, but it will be a while before I come back to it I think.
    Last edited by Stark_Barksalt; 10-17-2013 at 03:48 AM.

  8. #8
    Registered User
    Join Date
    Oct 2013
    Posts
    7
    First, here's the problem, paraphrased.

    The problem, as it appears in the book, is copyrighted stuff. To me it doesn't seem like a big deal to post this practice problem from the book, but I don't want any trouble, so if its inappropriate to post it, let me know and I'll delete it or ask a mod to delete it or whatever I need to do.

    Paraphrased from Programming Abstractions in C++ by Eric Roberts, Chapter 9:

    Suppose you have a list of varying lengths of pipe needed for a job, but the distributor sells stock pipe in only one fixed size, that you can cut in any way needed.

    Write a recursive function that takes as an argument a vector of the lengths needed and returns the minimum number of stock pipes required to service all requests in the vector.

    For example, if the vector contains [ 4, 3, 4, 1, 7, 8 ] and the stock pipe length is 10, you can purchase 3 stock pipes and divide them as follows:

    Pipe 1: 4, 4, 1
    Pipe 2: 3, 7
    Pipe 3: 8

  9. #9
    Registered User
    Join Date
    Oct 2013
    Posts
    7
    And here's my solution, all pretty and overly-commented and hopefully not trashy looking like my original post.

    Code:
    #include <iostream>
    
    #include "console.h"
    #include "vector.h"
    #include "simpio.h"
    
    using namespace std;
    
    //constants
    const int STOCK_PIPE_LENGTH = 10;
    
    //prototypes
    int cutStock(Vector<int> &requests);
    void recursiveCut(Vector<int> &requests, Vector<int> remainingPipes, Vector<int> &answers);
    
    /*
     * The main function creates a Vector<int> called requests that represents the list of
     * pipe lengths needed.  The getInteger() function is used to get this list from the user.
     * The user repreatedly enters lengths, prompted by the message "Enter pipe length: ".
     * To signal the end of input, the user enters any value equal to or less than 0, or greater
     * than the length of the constant STOCK_PIPE_LENGTH.  The program cannot accomodate lengths
     * greater than STOCK_PIPE_LENGTH.
     *
     * int main() then outputs to the console the minimum number of pipes of length STOCK_PIPE_LENGTH
     * needed to accomodate the list of lengths provided by the user, represented by the
     * Vector<int> requests. For example, assuming STOCK_PIPE_LENGTH is equal to 10, and the user has
     * given the values 2 and 8, the program should output the answer 1, as one stock pipe of length
     * 10 can be cut into lengths 2 and 8. If the user entered 6, 6, and 6, the program should
     * output the answer 3.  If the user entered 3, 3, 3, and 3, the answer would be 2.
     *
     * This is all assuming the function cutStock(Vector<int> &requests) will successfully return
     * the correct answer.
     */
    
    int main() {
     int x = 0;
     Vector<int> requests;
     while (true) {
      while (true) {
       x = getInteger("Enter pipe length: ");
       if (x <= 0) break;
       requests.add(x);
      }
      if (requests.size() <= 0) break;
      cout << cutStock(requests) << " stock pipes needed." << endl;
      requests.clear();
     }
     return 0;
    }
    
    /*
     * Function: int cutStock(Vector<int> &requests)
     * ---------------------------------------------
     * This function should return the smallest number of stock pipes of length STOCK_PIPE_LENGTH
     * needed to accomodate a list of lengths requested by the user.  This list is represented by
     * the Vector<int> requests, passed by reference as a parameter when the function is called.
     *
     * The function begins by creating two new Vector<int> objects, Vector<int> remainingPipes
     * and Vector<int> answers.
     *
     * Vector<int> remainingPipes will be used to represent all of the pipes from which a request
     * can be cut.  A pipe used in this way will have its length reduced by the ammount of the 
     * request it is being used to fill.  A pipe in remainingPipes will not be used unless its
     * length is greater than or equal to the length of the request.  Thus, an element of
     * remainingPipes can never be a negative number.  If a pipe is reduced to length 0, it is
     * still kept, as it is part of the answer.
     *
     * Vector<int> answers will be used to store a list of the number of pipes used in any 
     * possible strategy of cutting from and adding to the pipes in remainingPipes.  Assuming
     * the function recursiveCut() works as intended, the answer to the problem is simply
     * the lowest number in answers.  While a Set<int> object would be more appropriate in
     * this role, I have chosen to use a Vector<int> object so that readers of this code will
     * not need to be bothered to consider yet another type from an unfamiliar library.
     *
     * cutStock(Vector<int> &requests) therefore has three steps in its operation.
     *
     * 1. create the two new Vector<int> objects.
     *
     * 2. call the recursive function recursiveCut(), passing as parameters the Vector<int> requests
     * object, as well as the empty Vector<int> objects remainingPipes and answers.  requests and 
     * answers are passed by reference, while remainingPipes is not.
     *
     * 3. find the lowest element of the Vector<int> answers, and return it.
     */
    
    int cutStock(Vector<int> &requests) {
     int result = -1;
     Vector<int> remainingPipes;
     Vector<int> answers;
     recursiveCut(requests, remainingPipes, answers);
     for (int i = 0; i < answers.size(); i++) {
      if (answers[i] < result || result == -1) {
       result = answers[i];
      }
     }
     return result;
    }
    
    /*
     * Function: recursiveCut(Vector<int> &requests, Vector<int> remainingPipes, Vector<int> &answers)
     * ------------------------
     * This function is where the work is done in this program.  It takes as its paramenters
     * three Vector<int> objects.
     *
     * Vector<int> requests represents the list if lengths input by the user.
     * Vector<int> remainingPipes represents the list of pipes to be added to or cut from.
     * Vector<int> answers represents a list of the number of pipes used in any combination 
     *  of cutting and adding to remainingPipes.
     *
     * This is a recursive function.  The simple case occurs when the size of Vector<int> requests
     * is equal to 0.
     *
     * The function starts with a for loop that will, at each iteration, remove a single element 
     * from requests and store its value in a variable:
     *
     * int currentRequest
     *
     * This value is processed and then plugged back into the Vector<int> object at the same place
     * from which it was removed.  This is done for each element in the Vector<int> requests object.
     *
     * In a single iteration of this for loop, the idea is this:
     * Start by getting the value, storing it in currentRequest, and removing it from the vector.
     *
     * From here, there are two possibilities.  
     *
     * One possibility is that the ideal answer involves cutting this
     * length from a pipe already contained in the Vector<int> remainingPipes, which represents
     * the list of pipes already in use, and their current lengths.  To this end, the nested for
     * loop using int j as its index variable will cycle through each element of remainingPipes.
     * If the current element of remainingPipes is greater than or equal to the length of
     * the currentRequest (if (remainingPipes[j] >= currentRequest)) then the length of 
     * currentRequest is subtracted from that element of remainingPipes, and the function
     * recursiveCut calls itself recursively, in this new configuration.  In this new call, 
     * requests now has one less element than it did on the original call, remainingPipes contains
     * an element from which has been subtracted the length of the request that no longer exists
     * in requests, and everything is just generally awesome and everyone is having a great time.
     *
     * After this recursive call, the length of currentRequest is added back to the element of
     * remainingPipes from which it was subtracted, and the for loop moves on to the next element
     * of remainingPipes.  Note that if remainingPipes has 0 elements, this for loop is effectively
     * skipped entirely.
     * 
     * After this for loop completes, it is time to check for the other possibility, which is:
     * The ideal answer involves cutting the length of currentRequest from a brand new pipe instead 
     * of a pipe already contained in remainingPipes.  All new pipes will be of length STOCK_PIPE_LENGTH,
     * so to make this happen we just create a new pipe of length STOCK_PIPE_LENGTH - currentRequest.
     *
     * int newPipe = STOCK_PIPE_LENGTH - currentRequest
     *
     * This element is then added to the Vector<int> remainingPipes, and the function calls itself
     * recursively in this new configuration.  In this new call, Vector<int> requests has one less
     * element than it did in the original call, and remainingPipes has one new element added it,
     * of length STOCK_PIPE_LENGTH minus the length of the element that was removed from requests 
     * in the previous call.
     * After this recursive call is complete, the new element that was added to remainingPipes
     * is then removed. (remaining.remove(remaining.size() - 1))
     *
     * The simple case occurs when requests has no more elements (if (requests.size() <= 0))
     * In this case, the idea is to simply take the number of elements in remainingPipes (including,
     * of course, elements whose length is 0, as this is simply another pipe that has been used and
     * must have been purchased), and add this number as a new element to the Vector<int> answers.
     * 
     * In this way, every possible way of cutting from and adding new pipes to remainingPipes to 
     * cover all elements of requests will have been searched, and the Vector<int> answers will
     * contain as its elements the number of pipes of length STOCK_PIPE_LENGTH that were needed
     * in each configuration.  Thus, after the first call of recursiveCut() as called by the 
     * function cutStock() has completed, the program only needs to take the lowest number contained
     * in the Vector<int> answers and return this number as the solution to the problem, the least
     * number of pipes of length STOCK_PIPE_LENGTH needed to fill the set of requests represented
     * by the Vector<int> requests.
     */
    
    void recursiveCut(Vector<int> &requests, Vector<int> remainingPipes, Vector<int> &answers) {
     if (requests.size() <= 0) {
      answers.add(remainingPipes.size());
      return;
     }
     for (int z = requests.size() - 1; z >= 0; z--) {
      int currentRequest = requests[z];
      requests.remove(z);
      for (int j = remainingPipes.size() - 1; j >= 0; j--) {
       if (remainingPipes[j] >= currentRequest) {
        if (requests.size() <= 0) {
         answers.add(remainingPipes.size());
        } else {
         remainingPipes[j] -= currentRequest;
         recursiveCut(requests, remainingPipes, answers);
         remainingPipes[j] += currentRequest;
        }
       }
      }
      int newPipe = STOCK_PIPE_LENGTH - currentRequest;
      remainingPipes.add(newPipe);
      recursiveCut(requests, remainingPipes, answers);
      remainingPipes.remove(remainingPipes.size() - 1);
      requests.insert(z, currentRequest);
     }
    }

  10. #10
    Registered User
    Join Date
    Oct 2013
    Posts
    7
    Now as far as I can tell, that program seems to work.

    The broken for loop (which doesn't seem to be broken in this version) begins on line 178.

    The identical for loop in the original program works fine until the variable "index" is -1, at which point the for loop, instead of skipping itself entirely (as its supposed to do when index is -1) decides to first assign z to 2 (weird) and then increment instead of decrementing (really weird) and then terminate at either 6 or 7 (where could it be getting this random number from???)

    In the new version, there is no variable "index", and the for loop simply assigned its index "z" to be the size of the Vector<int> requests - 1, which is what "index" is assigned to in the original version. However, making this change in the original version still doesn't fix the broken for loop.

    Im convinced I will never figure out why its been doing this. If someone else can see what I missed Id be more than happy to hear about it. Im just completely in the dark about what went wrong.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Rep Broken?
    By B0bDole in forum A Brief History of Cprogramming.com
    Replies: 27
    Last Post: 02-04-2005, 06:00 AM
  2. Broken While Loop
    By GamingMarvel in forum C++ Programming
    Replies: 6
    Last Post: 01-10-2005, 11:46 AM
  3. broken search can u fix? plz :)
    By */*/*/*/ in forum C++ Programming
    Replies: 2
    Last Post: 06-07-2003, 04:43 PM
  4. broken logic
    By ggs in forum C Programming
    Replies: 4
    Last Post: 03-17-2002, 03:11 PM

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