Solved

I am using C++ pointers wrong again

Posted on 2012-03-31
12
1,251 Views
Last Modified: 2012-06-21
Is there some sort of macro or something that I could use to make working with pointers more verbose using them becomes more second nature?  I have no problem getting mixed up with references in other languages.  It seems like I waste time re-learning this every time I have to touch C.


/* 
 * File:   main.cpp
 * Author: Administrator
 *
 * Created on March 23, 2012, 4:08 PM
 */
#include <cstdlib>
#include <vector>
#include <iostream>
#include <cstddef>
#include "Cell.h"
#define MAXX 15
#define MAXY 15
using namespace std;
typedef void* Grid;
/*
 * 
 */
Grid makeGrid(int maxX, int maxY)
{
    
    Cell* r;                  // points to first cell of the grid.. for all
                              // purposes this is a pointer to our grid and
                              // will be returned
    Cell* currentCell; 
    int isFirstRun = 1;
    int isLastRun = 0;
    int membershipCount = 0;   // variable to give each cell a special
                               // membership to it's own group
                               // when two cells join they both 
                               // join the group with the lowest membership
                               // integer
    
    r = new Cell(membershipCount++);  // make first cell, we will return this 
                                    // pointer as the start of the maze
    
    
    
    // a vector of vectors, once the cells are double linked to each other
    // there will be no more need for this to hold everything in place
    // and it will go away.
    
    
    // TODO FROM Experts-Exchange:
    /*You don't use vector properly and it's the problem.
        using this line of code:
        std::vector<std::vector<Cell> > grid;
        you only define a vector of vector of Cell with no space for items. 
     * You should push_back items in grid, also you can use constructor or 
     * resize method to change the size of vector from its default(0).
     
        std::vector<int> g;
        g.push_back(0);
        g.push_back(1);
        g.push_back(2);
        g.push_back(3);
     * 
     * is equal to
     * 
        std::vector<int> g(4);
        for (int i=0; i<4; i++)
        g[i] = i;
                        
     
     */
    
    
    vector<*Cell> gridX(maxX);
    vector<vector<int> >  grid(maxY,gridX);
    
    //std::vector<std::vector<Cell> > grid; //make a vector of vectors to store in
    //Cell[maxX][maxY];
    grid[0][0] = *r;                   //put first cell in first spot
                                       
    
    
    
    // populate our vector of vector grid with cell objects that live in the 
    // heap and then double link them in every direction so they stay in place
    //  after all a real maze is navigated cell by cell.
    for (int y = 0; y <= maxY; y++ )
    {   
        for (int x = isFirstRun; x <= maxX; x++)
        {
            
            currentCell = new Cell(membershipCount++);
            if (0 != y) // if we aren't the top row link the node to the north
            {           // then link that row back to us on the south
                currentCell->setNorth(grid[x][y-1]); // link row above here
                grid[x][y-1].setSouth(*currentCell);// link above row back to us               
            }
            
            if (0 != x) // if we aren't the first column link to the west cell
            {           // then link that cell back to us on the east
                currentCell->setWest(grid[x-1][y]); // link cell behind here
                grid[x][y-1].setEast(*currentCell);// link that cell back to us               
            }
            // TODO: NOW PUSH IT ON TO YOUR VECTOR
            
        }   
        isFirstRun = 0; // this isn't the first run anymore so we don't need to
                        // leave space for the first already made cell
    }
    
    return r;
}

void smashWalls(Cell firstCell)
/* this iterates through every cell of the maze and orders
   cells that are not membership zero to smash into one of 
   their neighbors but leaves membership 0 cells alone so that
   their walls do not become unusually sparse, junctions are
  usually not good in mazes unless they're put there for a deliberate 
  reason that might be hard to describe to a machine                 */
{
    //srand();  //at some point we'll want to seed this but lets keep it
                //predictable right now
    
    Cell* currentCell = firstCell;   // start at the first cell
    
    while (currentCell->getSouth())  // and move from there 
    {
        while (currentCell->getEast)  // first to the east and south row by row
        {
            while (currentCell->getMemberhship())  //leave membership 0 rooms
                                                   //alone so their walls don't
                                                   //become sparse
                currentCell.smashRandom();   // have the cell remove a wall
                
        }
    }
}


int main(int argc, char** argv) {

    
    Grid grid;  // make something to point to the maze while we build it

    grid = makeGrid(MAXX, MAXY);  // build the maze 
    smashWalls(grid);   //step through each node of the maze and randomly
                          // tear down walls except in the case when 
                          // membership is zero
    //printMaze(grid);  // print out the maze node by node
    return 0;
}

Open in new window


and Cell.h
#ifndef CELL_H
#define	CELL_H
#include <cstddef>
#include <cstdlib>
#include <iostream>
using namespace std;
class Cell
/*This class represents a single cell in a maze  *
 * They all should be double linked to each other *
 * There is an array of booleans representing walls
 * and four seperate pointers to indicate adjecency*/
{
private:
    bool walls_[4];   //this represents the presence of a wall
    int membership_;  //this is a value representing the contigious space
                      //this cell is part of.. a complete maze is 0 all over
    Cell* north_; // Pointers to adjecent cells even if they're inaccessable
    Cell* south_; // null for the edge of the maze.
    Cell* east_;
    Cell* west_;
    

public:
    Cell(int membership)
    {
        membership_ = membership;
        walls_[0] = true; // put up four walls
        walls_[1] = true; // I know this is the ugly way to do it
        walls_[2] = true; // but I can't it to work the right way and need
        walls_[3] = true; // to stop wasting time.
        north_ = NULL;    // if we've never been linked to someone 
        south_ = NULL;    // we're an island and we have edges with 
        east_ = NULL;     // no adjecency
        west_ = NULL;
    }  
    void setNorth(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *north_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif
    }
    void setSouth(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *south_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    void setEast(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *east_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    void setWest(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *west_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    
    void smashRandom()
    /*  This method picks a random wall and if it's not the edge of the maze
     *  it removes it and then reached out and tears out the wall on the
     *  other cell.  If it was already gone it tries anyhow
     *  if it does happen to be the edge of the maze it just skips
     *  inefficent but efficency is unimportant when we have grades to make.
     */
    {
        switch(rand()%3)
        {
            case 0:
                if (north_)  // make sure there is something on the other side
                {
                    walls_[0] = false;   // smash the wall
                    south_.walls_[1] = false;// make the neighbor smash the other side 
                    membership_ = north_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
            case 1:
                if (south_)  // make sure there is something on the other side
                {
                    walls_[1] = false;   // smash the wall
                    north_.walls_[0] = false;// make the neighbor smash the other side
                    membership_ = south_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
            case 2:
                if (east_)  // make sure there is something on the other side
                {
                    walls_[2] = false;     // smash the wall
                    west_.walls_[1] = false;// make the neighbor smash the other side
                    membership_ = north_->combine(membership_);// figure out who
                           //has the smaller membership id both of you adopt it      
                }
                    break;
            case 3:
                if (west_)  // make sure there is something on the other side
                {
                    walls_[3] = false;     // smash the wall
                    east_.walls_[1] = false;// make the neighbor smash the other side
                    membership_ = north_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
                          
                
        }
    }
    int combine(int membership)
    /* Combines this cell with the cell
     from the parameters and returns the
     winning membership ID the cells now
     share                              */
    {
#if DEBUG > 2
        cout << "Cell Membership is:   \t" << membership_ << endl;
        cout << "Cell Membership contender:\t" << membership << endl;
#endif

        if (membership < membership_) { membership_ = membership; }
#if DEBUG > 2
        cout << "Cell Membership is now:   \t" << membership_ << endl;
#endif
        return membership_;
    }
    int getMemberhship()
    /*This returns the membership ID of the cell
     */
    {
        return membership_;
    }
    
    Cell getNorth()
    /* Returns a pointer to the northern cell*/
    {
        return north_;
    }
    Cell getSouth()
    /* Returns a pointer to the southern cell*/
    {
        return south_;
    }
    Cell getEast()
    /* Returns a pointer to the eastern cell*/
    {
        return east_;
    }
    Cell getWest()
    /* Returns a pointer to the western cell*/
    {
        return west_;
    }
    
    
    
  
};


#endif	/* CELL_H */

Open in new window


finally the error list
g++.exe -Wall -pedantic   -c -g -MMD -MP -MF build/Debug/Cygwin_4.x-Windows/main.o.d -o build/Debug/Cygwin_4.x-Windows/main.o main.cpp
Cell.h: In member function ‘void Cell::smashRandom()’:
In file included from main.cpp:11:0:
Cell.h:97:28: error: request for member ‘walls_’ in ‘((Cell*)this)->Cell::south_’, which is of non-class type ‘Cell*’
Cell.h:106:28: error: request for member ‘walls_’ in ‘((Cell*)this)->Cell::north_’, which is of non-class type ‘Cell*’
Cell.h:115:27: error: request for member ‘walls_’ in ‘((Cell*)this)->Cell::west_’, which is of non-class type ‘Cell*’
Cell.h:124:27: error: request for member ‘walls_’ in ‘((Cell*)this)->Cell::east_’, which is of non-class type ‘Cell*’
Cell.h: In member function ‘Cell Cell::getNorth()’:
Cell.h:160:16: error: conversion from ‘Cell*’ to non-scalar type ‘Cell’ requested
Cell.h: In member function ‘Cell Cell::getSouth()’:
Cell.h:165:16: error: conversion from ‘Cell*’ to non-scalar type ‘Cell’ requested
Cell.h: In member function ‘Cell Cell::getEast()’:
Cell.h:170:16: error: conversion from ‘Cell*’ to non-scalar type ‘Cell’ requested
Cell.h: In member function ‘Cell Cell::getWest()’:
Cell.h:175:16: error: conversion from ‘Cell*’ to non-scalar type ‘Cell’ requested
main.cpp: In function ‘void* makeGrid(int, int)’:
main.cpp:68:13: error: ‘*’ cannot appear in a constant-expression
main.cpp:68:17: error: template argument 1 is invalid
main.cpp:68:17: error: template argument 2 is invalid
main.cpp:68:24: error: invalid type in declaration before ‘(’ token
main.cpp:73:19: error: cannot convert ‘Cell’ to ‘int’ in assignment
main.cpp:90:30: error: request for member ‘setSouth’ in ‘((std::vector<int>*)grid.std::vector<_Tp, _Alloc>::operator[] [with _Tp = std::vector<int>, _Alloc = std::allocator<std::vector<int> >, std::vector<_Tp, _Alloc>::reference = std::vector<int>&, std::vector::size_type = unsigned int](((unsigned int)x)))->std::vector<_Tp, _Alloc>::operator[] [with _Tp = int, _Alloc = std::allocator<int>, std::vector<_Tp, _Alloc>::reference = int&, std::vector::size_type = unsigned int](((unsigned int)(y + -0x000000001)))’, which is of non-class type ‘int’
main.cpp:96:30: error: request for member ‘setEast’ in ‘((std::vector<int>*)grid.std::vector<_Tp, _Alloc>::operator[] [with _Tp = std::vector<int>, _Alloc = std::allocator<std::vector<int> >, std::vector<_Tp, _Alloc>::reference = std::vector<int>&, std::vector::size_type = unsigned int](((unsigned int)x)))->std::vector<_Tp, _Alloc>::operator[] [with _Tp = int, _Alloc = std::allocator<int>, std::vector<_Tp, _Alloc>::reference = int&, std::vector::size_type = unsigned int](((unsigned int)(y + -0x000000001)))’, which is of non-class type ‘int’
main.cpp:27:9: warning: unused variable ‘isLastRun’
main.cpp: In function ‘void smashWalls(Cell)’:
main.cpp:119:25: error: cannot convert ‘Cell’ to ‘Cell*’ in initialization
main.cpp:121:34: error: could not convert ‘currentCell->Cell::getSouth()’ to ‘bool’
main.cpp:123:29: error: argument of type ‘Cell (Cell::)()’ does not match ‘bool’
main.cpp:128:29: error: request for member ‘smashRandom’ in ‘currentCell’, which is of non-class type ‘Cell*’
nbproject/Makefile-Debug.mk:65: recipe for target `build/Debug/Cygwin_4.x-Windows/main.o' failed
make[2]: Leaving directory `/cygdrive/c/Users/Administrator/Documents/NetBeansProjects/Maze'
main.cpp: In function ‘int main(int, char**)’:
nbproject/Makefile-Debug.mk:58: recipe for target `.build-conf' failed
make[1]: Leaving directory `/cygdrive/c/Users/Administrator/Documents/NetBeansProjects/Maze'
main.cpp:141:20: error: conversion from ‘void*’ to non-scalar type ‘Cell’ requested
nbproject/Makefile-impl.mk:39: recipe for target `.build-impl' failed
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_vector.h: In member function ‘void std::vector<_Tp, _Alloc>::_M_initialize_dispatch(_Integer, _Integer, std::__true_type) [with _Integer = int, _Tp = std::vector<int>, _Alloc = std::allocator<std::vector<int> >]’:
In file included from /usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/vector:65:0,
                 from main.cpp:8:
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_vector.h:303:4:   instantiated from ‘std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = int, _Tp = std::vector<int>, _Alloc = std::allocator<std::vector<int> >, allocator_type = std::allocator<std::vector<int> >]’
main.cpp:69:42:   instantiated from here
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_vector.h:995:4: error: no matching function for call to ‘std::vector<std::vector<int> >::_M_fill_initialize(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >::size_type, int&)’
/usr/lib/gcc/i686-pc-cygwin/4.5.3/include/c++/bits/stl_vector.h:1037:7: note: candidate is: void std::vector<_Tp, _Alloc>::_M_fill_initialize(std::vector::size_type, const value_type&) [with _Tp = std::vector<int>, _Alloc = std::allocator<std::vector<int> >, std::vector::size_type = unsigned int, value_type = std::vector<int>]
make[2]: *** [build/Debug/Cygwin_4.x-Windows/main.o] Error 1
make[1]: *** [.build-conf] Error 2
make: *** [.build-impl] Error 2

BUILD FAILED (exit value 2, total time: 2s)
 

Open in new window

0
Comment
Question by:GPicasso
  • 4
  • 3
  • 3
  • +2
12 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 37792038
If you're struggling with pointers why don't you just use references? I suspect you'll find that a lot simpler because references are more like what you're probably used to in other languages.

http://www.cprogramming.com/tutorial/references.html
http://www.parashift.com/c++-faq-lite/references.html

That all said; if you need to write C++ code often you really should get your head around pointers. They're not really that hard and with a little practice it usually starts to make sense. Is there anything specific you struggle with when trying to understand pointers?
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37792048
I've not tried building your code but looking at the errors I suspect a lot of them are because you are using a dot and not an arrow when trying to dereference a Cell pointer member.

For example

north_.walls_[0] = false;

should be

north_->walls_[0] = false;

because north_ is a Cell * (a pointer of type Cell) and walls_[] is a member of Cell.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 37792069
IMO, when using pointers, you need to understand them in both syntax and in memory references. There are some typedef constructs to hide the pointer, and also to make multi-dimensional pointers simpler to look at, but you still need to understand what is going on under the hood when things go awry.

But one standard approach to help remember what variables are a pointer is to prefix the variable with a p or p_.

re: syntax, you have:

Cell* south_;
south_.walls_[1] = false;  // wrong way to access the member via a pointer:

Revise:
south_->walls_[1] = false;


re: syntax, you have:
    Cell getNorth()    {
        return north_;
    }

Revise:
    Cell getNorth()    {
        return *north_;  // you are returning a Cell object, but north is a pointer, so need to dereference the pointer
    }
But, consider that a class can be large, and you are returning the class instance by value - could be very inefficient. Suggest that you pass by reference. Well, I guess the answer is that pointers can be very tricky, and I have not seen a solid way to simplify their usage to the degree that you are requesting.
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 125 total points
ID: 37792075
I would definately not do this...

Cell getNorth()    {
        return *north_;  // you are returning a Cell object, but north is a pointer, so need to dereference the pointer
    }

... because it is returning by value.

I would do this...

Cell const * getNorth()    {
        return north_;  // you are returning a Cell object, but north is a pointer, so need to dereference the pointer
    }

 (return a const pointer) or

Cell const & getNorth()    {
        return *north_;  // you are returning a Cell object, but north is a pointer, so need to dereference the pointer
    }

(return a const reference)

This way you have the option to take a pointer, reference or value. In the former you always return a value.
0
 
LVL 32

Expert Comment

by:phoffric
ID: 37792092
So, as you can see, there is more to pointers than just syntax. Generally, as we both have said, you should not return class instantiations; but rather return a pointer or a reference to the object. (And just be careful that the pointer or reference is not on the stack that is unwinding.)

Since evilrix got here first, I'll bow out and let him continue with you.

Good luck with pointers - not easy!
0
 
LVL 40

Expert Comment

by:evilrix
ID: 37792096
There's enough room for both of us here Paul :)
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:GPicasso
ID: 37792191
using a dot and not an arrow when trying to dereference a Cell pointer member
I'm using netbeans and it appears to change these things automatically, there could be special cases where it doesn't because it's code analysis in c++ is not as good as in java, and in java it's not even perfect.
Is there anything specific you struggle with when trying to understand pointers?
Well let me see if I understand this right
int* p makes a pointer
print(p); would return it's memory address if any
print(*p) would return the value stored at that memory address
and print(&i) would return the memory address of variable i.
(with print() being imaginary and working how we need it to for the sake of example)
I need to understand pointers for analyzing code, so I might as well bite the bullet and learn.  I didn't even know you could make reference variables until you told me, that is so useful and from now on I will always use them unless there is a compelling reason not to.

I think I get mixed up in the use of these things.  I think my intent is usually clear to a human reader I think that I just don't have a good understanding of pointer behavior.  for example if I have a vector<Cell> v;   is v[2] a pointer?  Is it a cell?  conceptually I don't really know.

Ok I paid a little closer attention to these errors and thought hard about what I was really saying.   I got most of the errors to go away but these two are persistent :
main.cpp: In function ‘void smashWalls(Cell)’:
main.cpp:121:39: error: no match for ‘operator!=’ in ‘currentCell->Cell::getSouth() != 0’
main.cpp:123:40: error: invalid use of member (did you forget the ‘&’ ?)
main.cpp: In function ‘int main(int, char**)’:

Open in new window


I have played with it a little but there is always some kind of error.
main.cpp: In function ‘int main(int, char**)’:
main.cpp:141:20: error: conversion from ‘void*’ to non-scalar type ‘Cell’ requested

Open in new window


What I really want to have happen is for the "grid" to eventually be represented as a pointer to the first cell.  Not sure how to make that work.

here is my new code
/* 
 * File:   main.cpp
 * Author: Administrator
 *
 * Created on March 23, 2012, 4:08 PM
 */
#include <cstdlib>
#include <vector>
#include <iostream>
#include <cstddef>
#include "Cell.h"
#define MAXX 15
#define MAXY 15
using namespace std;
typedef void* Grid;
/*
 * 
 */
Grid makeGrid(int maxX, int maxY)
{
    
    Cell* r;                  // points to first cell of the grid.. for all
                              // purposes this is a pointer to our grid and
                              // will be returned
    Cell* currentCell; 
    int isFirstRun = 1;
    int isLastRun = 0;
    int membershipCount = 0;   // variable to give each cell a special
                               // membership to it's own group
                               // when two cells join they both 
                               // join the group with the lowest membership
                               // integer
    
    r = new Cell(membershipCount++);  // make first cell, we will return this 
                                    // pointer as the start of the maze
    
    
    
    // a vector of vectors, once the cells are double linked to each other
    // there will be no more need for this to hold everything in place
    // and it will go away.
    
    
    // TODO FROM Experts-Exchange:
    /*You don't use vector properly and it's the problem.
        using this line of code:
        std::vector<std::vector<Cell> > grid;
        you only define a vector of vector of Cell with no space for items. 
     * You should push_back items in grid, also you can use constructor or 
     * resize method to change the size of vector from its default(0).
     
        std::vector<int> g;
        g.push_back(0);
        g.push_back(1);
        g.push_back(2);
        g.push_back(3);
     * 
     * is equal to
     * 
        std::vector<int> g(4);
        for (int i=0; i<4; i++)
        g[i] = i;
                        
     
     */
    
    
    vector<Cell> gridX(maxX);
    vector<vector<Cell> >  grid(maxY,gridX);
    
    //std::vector<std::vector<Cell> > grid; //make a vector of vectors to store in
    //Cell[maxX][maxY];
    grid[0][0] = *r;                   //put first cell in first spot
                                       
    
    
    
    // populate our vector of vector grid with cell objects that live in the 
    // heap and then double link them in every direction so they stay in place
    //  after all a real maze is navigated cell by cell.
    for (int y = 0; y <= maxY; y++ )
    {   
        for (int x = isFirstRun; x <= maxX; x++)
        {
            
            currentCell = new Cell(membershipCount++);
            if (0 != y) // if we aren't the top row link the node to the north
            {           // then link that row back to us on the south
                currentCell->setNorth(grid[x][y-1]); // link row above here
                grid[x][y-1].setSouth(*currentCell);// link above row back to us               
            }
            
            if (0 != x) // if we aren't the first column link to the west cell
            {           // then link that cell back to us on the east
                currentCell->setWest(grid[x-1][y]); // link cell behind here
                grid[x][y-1].setEast(*currentCell);// link that cell back to us               
            }
            // TODO: NOW PUSH IT ON TO YOUR VECTOR
            
        }   
        isFirstRun = 0; // this isn't the first run anymore so we don't need to
                        // leave space for the first already made cell
    }
    
    return r;
}

void smashWalls(Cell firstCell)
/* this iterates through every cell of the maze and orders
   cells that are not membership zero to smash into one of 
   their neighbors but leaves membership 0 cells alone so that
   their walls do not become unusually sparse, junctions are
  usually not good in mazes unless they're put there for a deliberate 
  reason that might be hard to describe to a machine                 */
{
    //srand();  //at some point we'll want to seed this but lets keep it
                //predictable right now
    
    Cell* currentCell = &firstCell;   // start at the first cell
    
    while (currentCell->getSouth() != NULL)  // and move from there 
    {
        while (currentCell->getEast != NULL)  // first to the east and south row by row
        {
            while (currentCell->getMemberhship() != 0)  //leave membership 0 rooms
                                                   //alone so their walls don't
                                                   //become sparse
                currentCell->smashRandom();   // have the cell remove a wall
                
        }
    }
}


int main(int argc, char** argv) {

    
    Grid grid;  // make something to point to the maze while we build it

    grid = makeGrid(MAXX, MAXY);  // build the maze 
    smashWalls(grid);   //step through each node of the maze and randomly
                          // tear down walls except in the case when 
                          // membership is zero
    //printMaze(grid);  // print out the maze node by node
    return 0;
}

Open in new window


and the class

#ifndef CELL_H
#define	CELL_H
#include <cstddef>
#include <cstdlib>
#include <iostream>
using namespace std;
class Cell
/*This class represents a single cell in a maze  *
 * They all should be double linked to each other *
 * There is an array of booleans representing walls
 * and four seperate pointers to indicate adjecency*/
{
private:
    bool walls_[4];   //this represents the presence of a wall
    int membership_;  //this is a value representing the contigious space
                      //this cell is part of.. a complete maze is 0 all over
    Cell* north_; // Pointers to adjecent cells even if they're inaccessable
    Cell* south_; // null for the edge of the maze.
    Cell* east_;
    Cell* west_;
    

public:
    Cell(){}
    Cell(int membership)
    {
        membership_ = membership;
        walls_[0] = true; // put up four walls
        walls_[1] = true; // I know this is the ugly way to do it
        walls_[2] = true; // but I can't it to work the right way and need
        walls_[3] = true; // to stop wasting time.
        north_ = NULL;    // if we've never been linked to someone 
        south_ = NULL;    // we're an island and we have edges with 
        east_ = NULL;     // no adjecency
        west_ = NULL;
    }  
    void setNorth(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *north_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif
    }
    void setSouth(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *south_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    void setEast(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *east_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    void setWest(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *west_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    
    void smashRandom()
    /*  This method picks a random wall and if it's not the edge of the maze
     *  it removes it and then reached out and tears out the wall on the
     *  other cell.  If it was already gone it tries anyhow
     *  if it does happen to be the edge of the maze it just skips
     *  inefficent but efficency is unimportant when we have grades to make.
     */
    {
        switch(rand()%3)
        {
            case 0:
                if (north_)  // make sure there is something on the other side
                {
                    walls_[0] = false;   // smash the wall
                    south_->walls_[1] = false;// make the neighbor smash the other side 
                    membership_ = north_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
            case 1:
                if (south_)  // make sure there is something on the other side
                {
                    walls_[1] = false;   // smash the wall
                    north_->walls_[0] = false;// make the neighbor smash the other side
                    membership_ = south_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
            case 2:
                if (east_)  // make sure there is something on the other side
                {
                    walls_[2] = false;     // smash the wall
                    west_->walls_[1] = false;// make the neighbor smash the other side
                    membership_ = north_->combine(membership_);// figure out who
                           //has the smaller membership id both of you adopt it      
                }
                    break;
            case 3:
                if (west_)  // make sure there is something on the other side
                {
                    walls_[3] = false;     // smash the wall
                    east_->walls_[1] = false;// make the neighbor smash the other side
                    membership_ = north_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
                          
                
        }
    }
    int combine(int membership)
    /* Combines this cell with the cell
     from the parameters and returns the
     winning membership ID the cells now
     share                              */
    {
#if DEBUG > 2
        cout << "Cell Membership is:   \t" << membership_ << endl;
        cout << "Cell Membership contender:\t" << membership << endl;
#endif

        if (membership < membership_) { membership_ = membership; }
#if DEBUG > 2
        cout << "Cell Membership is now:   \t" << membership_ << endl;
#endif
        return membership_;
    }
    int getMemberhship()
    /*This returns the membership ID of the cell
     */
    {
        return membership_;
    }
    
    Cell getNorth()
    /* Returns a pointer to the northern cell*/
    {
        return *north_;
    }
    Cell getSouth()
    /* Returns a pointer to the southern cell*/
    {
        return *south_;
    }
    Cell getEast()
    /* Returns a pointer to the eastern cell*/
    {
        return *east_;
    }
    Cell getWest()
    /* Returns a pointer to the western cell*/
    {
        return *west_;
    }
    
    
    
  
};


#endif	/* CELL_H */

Open in new window

0
 

Author Comment

by:GPicasso
ID: 37792194
ok also changed the return types on getNorth(), ... , etc to references as suggested.  I understand the performance difference here.
/* 
 * File:   Cell.h
 * Author: Administrator
 *
 * Created on March 23, 2012, 4:23 PM
 */

#ifndef CELL_H
#define	CELL_H
#include <cstddef>
#include <cstdlib>
#include <iostream>
using namespace std;
class Cell
/*This class represents a single cell in a maze  *
 * They all should be double linked to each other *
 * There is an array of booleans representing walls
 * and four seperate pointers to indicate adjecency*/
{
private:
    bool walls_[4];   //this represents the presence of a wall
    int membership_;  //this is a value representing the contigious space
                      //this cell is part of.. a complete maze is 0 all over
    Cell* north_; // Pointers to adjecent cells even if they're inaccessable
    Cell* south_; // null for the edge of the maze.
    Cell* east_;
    Cell* west_;
    

public:
    Cell(){}
    Cell(int membership)
    {
        membership_ = membership;
        walls_[0] = true; // put up four walls
        walls_[1] = true; // I know this is the ugly way to do it
        walls_[2] = true; // but I can't it to work the right way and need
        walls_[3] = true; // to stop wasting time.
        north_ = NULL;    // if we've never been linked to someone 
        south_ = NULL;    // we're an island and we have edges with 
        east_ = NULL;     // no adjecency
        west_ = NULL;
    }  
    void setNorth(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *north_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif
    }
    void setSouth(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *south_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    void setEast(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *east_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    void setWest(const Cell &cell)
    /* Points the northern direction to 
     * the cell in the parameter       */
    {
        *west_ = cell;
#if DEBUG > 2
        cout << north_ << endl;
#endif

    }
    
    void smashRandom()
    /*  This method picks a random wall and if it's not the edge of the maze
     *  it removes it and then reached out and tears out the wall on the
     *  other cell.  If it was already gone it tries anyhow
     *  if it does happen to be the edge of the maze it just skips
     *  inefficent but efficency is unimportant when we have grades to make.
     */
    {
        switch(rand()%3)
        {
            case 0:
                if (north_)  // make sure there is something on the other side
                {
                    walls_[0] = false;   // smash the wall
                    south_->walls_[1] = false;// make the neighbor smash the other side 
                    membership_ = north_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
            case 1:
                if (south_)  // make sure there is something on the other side
                {
                    walls_[1] = false;   // smash the wall
                    north_->walls_[0] = false;// make the neighbor smash the other side
                    membership_ = south_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
            case 2:
                if (east_)  // make sure there is something on the other side
                {
                    walls_[2] = false;     // smash the wall
                    west_->walls_[1] = false;// make the neighbor smash the other side
                    membership_ = north_->combine(membership_);// figure out who
                           //has the smaller membership id both of you adopt it      
                }
                    break;
            case 3:
                if (west_)  // make sure there is something on the other side
                {
                    walls_[3] = false;     // smash the wall
                    east_->walls_[1] = false;// make the neighbor smash the other side
                    membership_ = north_->combine(membership_);// figure out who
                            //has the smaller membership id both of you adopt it      
                }
                    break;
                          
                
        }
    }
    int combine(int membership)
    /* Combines this cell with the cell
     from the parameters and returns the
     winning membership ID the cells now
     share                              */
    {
#if DEBUG > 2
        cout << "Cell Membership is:   \t" << membership_ << endl;
        cout << "Cell Membership contender:\t" << membership << endl;
#endif

        if (membership < membership_) { membership_ = membership; }
#if DEBUG > 2
        cout << "Cell Membership is now:   \t" << membership_ << endl;
#endif
        return membership_;
    }
    int getMemberhship()
    /*This returns the membership ID of the cell
     */
    {
        return membership_;
    }
    
    Cell const & getNorth()
    /* Returns a pointer to the northern cell*/
    {
        return *north_;
    }
    Cell const & getSouth()
    /* Returns a pointer to the southern cell*/
    {
        return *south_;
    }
    Cell const & getEast()
    /* Returns a pointer to the eastern cell*/
    {
        return *east_;
    }
    Cell const & getWest()
    /* Returns a pointer to the western cell*/
    {
        return *west_;
    }
    
    
    
  
};


#endif	/* CELL_H */

Open in new window

0
 

Author Comment

by:GPicasso
ID: 37792199
I did think about pointers and the stack unwinding bit.  I was pretty proud of myself to build a vector grid on the stack and then populate it with pointers to Cells on the heap.. then link all the cells together and let the vectors go away after the makegrid function returns a pointer to the first cell.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 125 total points
ID: 37792346
if I have a vector<Cell> v;   is v[2] a pointer?  Is it a cell?
Conceptually, just think of a vector as a container holding an array of Cell's, and v[2] is simply the third cell in this array.

re: your != NULL getSouth error:
south_ is a pointer and you are returning a dereferenced pointer. But, south_ can be NULL, right? Checking a pointer for NULL makes good sense. But you are passing an object (by reference).  You could redesign a little, or overload the != operator if you wanted; and you may wish to read closely today's other question about returning dereferenced NULL pointers:
     http://www.experts-exchange.com/Programming/Languages/Q_27655637.html

I haven't looked closely at all your code, so I don't really understand why you want have Grid typed as void *. Maybe you can change that to get your other error to go away. smashWalls takes a Cell parameter. You could change that to a reference to a Cell and make other corresponding changes to make it fit.
0
 
LVL 4

Assisted Solution

by:historychef
historychef earned 125 total points
ID: 37793481
If I may offer some suggestions on how to "get your head around pointers": I used to teach C programming in college. When students were confused by pointers, I always told them to draw a picture of how memory was laid out. This doesn't require any great artistic ability (Heaven knows I don't have any!), but simply the ability to draw a rectangle for a word in memory, an arrow from that rectangle to another to represent a pointer, and a longer, subdivided box (like a small table) to represent a struct or an object. Try doing that with the following small example (in C; it would arguably be better in C++):

int x, y;   // draw rectangles to hold x and y
int *px = &x;    // draw a rectangle for px, then an arrow from that to the 'x' rectangle
struct Person {  // draw these out as a small table, with one row for each member
   char name[30];
   int age;
   char sex;  // a single character, 'M' or 'F'
   struct Person *spouse;  // a link to another Person object
} my_friend[10];

// Now, if you've drawn the pictures that represent these objects in memory, you can
// easily get the pointers, and the syntax, right:

strcpy(my_friend[0].name, "Fred Smith");    // Use . because it's a member accessor
my_friend[0].age = 43;
my_friend[0].sex = 'M';

strcpy(my_friend[1].name, "Wilma Smith");
my_friend[1].age = 41;
my_friend[1].sex = 'F';

my_friend[0].spouse = &my_friend[1];  // I now pronounce you man and wife ...
my_friend[1].spouse = &my_friend[0];

// Now, to find Fred's age, I can simply use
x = my_friend[0].age;

// To find the age of Fred's spouse, I'm tempted to write
y = *my_friend[0].spouse.age;  // INCORRECT!

// but this is WRONG, because the [] and . operators bind more tightly than the * operator.
// This will give an error, because you're trying to dereference something (age) that isn't 
// a pointer. If you wanted to access Fred's spouse's age with the dot operator, you'd have to
// qualify it with parentheses:
y = (*my_friend[0].spouse).age;  // Correct, but clunky

// This will work, but the syntax is REALLY clunky. Therefore, C defines the -> operator to
// handle this exact case:
y = my_friend[0].spouse -> age;  // Correct and non-clunky

Open in new window


So, here's the story in a nutshell. 'x' refers to the contents of the memory location defined with the variable name 'x'. '*x' refers to the contents of the memory location pointed to by (i.e., whose address is stored in) the memory location defined with the variable name 'x'. 'x.y' refers to the contents of the field named 'y' within the struct (or object, for C++) named 'x'. 'x -> y' refers to the contents of the field named 'y' within the struct (or object) whose address is contained in memory location 'x'. Finally, as the example above showed, 'x -> y' is exactly the same as '(*x).y' -- it's just a lot clearer and easier to read.

I hope that helps. Draw pictures!
0
 
LVL 22

Assisted Solution

by:ambience
ambience earned 125 total points
ID: 37797542
You can use a shared_ptr which is closer to what you would expect from a reference in other languages. A reference is C++ is much different from a managed reference because it does not have a say in controlling the lifetime of the object it is referencing - something that a managed reference does.

http://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#std.util.memory.shared_ptr

>> What I really want to have happen is for the "grid" to eventually be represented as a pointer to the first cell.

That does not make sense - is a Grid really a Cell? I guess the relation is HasA i.e. a maze has cells and therefore first cell.

>> typedef void* Grid;

Very dangerous, unless you really know what you are doing. Try not to downcast a typed pointer to void* because that would take away all the type-checking that compiler would be able to do for you. I guess you already know how daunting pointers can become and interchanging void* is like adding insult to injury.

I dont think there is a pressing reason to use pointers, because you can use a two dimensional array of cells and indices for finding out neighboring cells. For Idea

class Maze;
class Cell
{
     friend class Maze;
public:
   int iIndex(int i) { return _index; }

private:
   void setIndex(int i) { _index = i; }

private:
   int _index;
};

class Maze
{
public:
     Maze(int maxX, int maxY) : _maxX(maxX), _maxY(maxY) {
         _cells.resize(maxX * maxY);
         for(int i=0; i<_cells.size(); i++)
             _cells[i].setIndex(i);
   }

   Cell* firstCell() {
        return &_cells[0];
   }

   Cell* cellNorthOf(Cell* cell) {
        if(cell == nullptr) return nullptr;
        if(cell->index() - _maxX < 0) return nullptr;

        // Adding -maxX takes us one full row backwards same position columnwise
        return &_cells[cell->index() - _maxX];
   }

   Cell* cellSouthOf(Cell* cell) {
        if(cell == nullptr) return nullptr;
        if(cell->index() + _maxX >= _cells.size()) return nullptr;

        // Adding maxX takes us one full row forward same position columnwise
        return &_cells[cell->index() + _maxX];
   }


   Cell* cellWesOf(Cell* cell) {
        if(cell == nullptr) return nullptr;
        if((cell->index() % _maxX) + 1 >= _maxX) return nullptr;

        return &_cells[cell->index() - 1];
   }

   Cell* cellEastOf(Cell* cell) {
        if(cell == nullptr) return nullptr;
        if((cell->index() % _maxX) - 1 < 0) return nullptr;

        return &_cells[cell->index() - 1];
   }


private:
 std::vector<Cell> _cells;
 int _maxX, _maxY;
};


void smashWalls(Maze& maze)
/* this iterates through every cell of the maze and orders
   cells that are not membership zero to smash into one of 
   their neighbors but leaves membership 0 cells alone so that
   their walls do not become unusually sparse, junctions are
  usually not good in mazes unless they're put there for a deliberate 
  reason that might be hard to describe to a machine                 */
{
    //srand();  //at some point we'll want to seed this but lets keep it
                //predictable right now
    
    Cell* currentCell = maze.firstCell();   // start at the first cell
    
    while (maze.cellSouthOf(currentCell) != NULL)  // and move from there 
    {
        currentCell = maze.cellSouthOf(currentCell);
        while (maze.cellEastOf(currentCell) != NULL)  // first to the east and south row by row
        {
            currentCell = maze.cellEastOf(currentCell);
            while (currentCell->getMemberhship() != 0)  //leave membership 0 rooms
                                                   //alone so their walls don't
                                                   //become sparse
                currentCell->smashRandom();   // have the cell remove a wall
                
        }
    }
}

Open in new window

0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Visual c++ and text files 7 55
how to convert c++ code to Android App 3 64
Grammars for C C++ and java 1 108
Safe conversion? 4 17
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

757 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

19 Experts available now in Live!

Get 1:1 Help Now