Finally learning C++!

alexander · August 28, 2007

no this works for everything (look at the beginning of that line)

in double quotes inditiates a search for unprintable characters and is one of those

so say you wanted to display test the c++ code would be "test"

list of unprintable characters:

n - new line

r - carriage return

t - tab

a - bell

e - escape

f - form feed

v - vertical tab

if you are writing to a windows text file, or reading for that matter, remember, that lines in those are terminated with rn while unix terminates with n

this will be important when i discuss regular expressions in later lessons ;)

ronthepon · September 13, 2007

It's been some time since I've actually had time to use the internet at my leisure. In the mean time, I've gone a bit ahead in my course. We've gone through the 'if-else', 'do-while', 'for', etc, and I've made a couple of algorithms in it. To be honest, what's come so far has been pretty easy to go through.

Thanks, alexander, for the program. About now, I pretty much am able to figure out every aspect of it. Btw, sans using the declaration "using namespace std" I can't seem to be able to use endl instead of "n", with cout. How do I manage that?

A counter using program, I had made for the fun of it:

 
//Counter file
#include <iostream>
#include <string>
int main ()
{
   std::cout << "Welcome to the password program. The password happens to be RTP.nAnd you need not exhaust all the tries. This is for your safety and sanity.n";
   
   std::string n;
   int tries = 5;
   
   std::cout << std::endl << "Enter the password: ";
   std::cin >> n;
   
   while (n != "RTP")
   {
         if ( tries > 0 )
         {
              
              std::cout << "nIncorrect. You have " << tries << " tries left.nPlease re-enter: ";
              --tries;
              std::cin >> n;
         }
         else
         {
             std::cout << "nGood bye.";
             return 0;
         }
   }
   
   
   std::cout << "Correct!nAin't no use knowing the password though...n n";
   
   system ("pause");
   
   return 0;
}

Using the if-else thing, for checking out a triangle:

 
#include <iostream>
int main ()
{
   int a, b, c;
   
   std::cout << "Enter the lengths of three sides of a triangle. Please.n";
   std::cin >> a >> b >> c;
   std::cout << "n";
   
   if (a > b+c || b > a+c || c > a+:D
   {
         std::cout << "Not a triangle.n";
   }
   else
   {
       if (a == b && b == c)
       {std::cout << "Equilateral.n";}
       else if (a == b || b == c || a == c)
       {std::cout << "Iscoceles";}
       else
       {std::cout << "The triangle is scalene, and it totally stinks.n";}
   }
   system ("pause");
   return 0;
}

My first real algorithm, for getting the roots of a quadratic equation. (Had some bugs... don't quite recall...

 
#include <iostream>
#include <cmath> //For the sqrt function
int main ()
{
   std::cout << "Welcome to the quadratic solver!nThis program assumes the quadratic function to be present as:nax^2 + bx + c = 0n";
   
   float a, b, c = 0; //Prepare to get the equation...
   
   std::cout << "nEnter integral value for a: ";
   std::cin >> a;
   
   std::cout << "nEnter integral value for b: ";
   std::cin >> b;
   
   std::cout << "nEnter integral value for c: ";
   std::cin >> c;
   
   std::cout << "The expression looks like:nt" << a << "x^2 + " << b << "x + " << c << "n";
   
   if (a == 0) //short circuit for a = 0 case. Avoids fatal runtime error.
   {
         double r = -c/b;
         std::cout << "Not a quadratic equation. The value of x is " << r << "n";
         system ("pause");
         return 0;
         
   }
   
   float sD;
   double d;
   double r_1, r_2; //Used for general vars, as they have the double charecters...
   
   bool imag = 0; //Flag for imaginary roots.
   
   sD = b*b - 4*a*c;
       
   if (sD < 0)  //Self explanatory.
   {
          std::cout << "nRoots are imaginary.n";
          sD = -sD; //To validate working of sqrt(sd)
          imag = 1; //Flag roots as imaginary.
   }
   
   d = sqrt (sD);
   
   if (imag == 0) //For real roots, calculation of roots and display
   {
           r_1 = (d - B)/(2*a);
   
           r_2 = (0-(b + d))/(2*a);
       
           std::cout << "The roots are: " << r_1 << " and " << r_2 << "n";
   }
   else //For imaginary roots...
   {
           r_1 = (d)/(2*a);
           r_2 = (-B)/(2*a);
   
           if (b != 0) //Come on, i looks cooler than 0 + i...
           {
                   std::cout << "The roots are: " << r_2 << "+" << r_1 << "i and " << r_2 << "-" << r_1 << "in";
           }
           else
           {
                   std::cout << "The roots are: " << r_1 << "i and -" << r_1 << "in";
           }
   
   }
   
   system ("pause");
   return 0;
}

And so on.

Now, I've reached control structures, and I'm currently trying to decipher my lecture notes on it. Yeah, I've got a ton of questions on that. Let me just compile them...

Buffy · September 13, 2007

Btw, sans using the declaration "using namespace std" I can't seem to be able to use endl instead of "n", with cout. How do I manage that?

The "using namespace" command--which is really a compiler directive--brings in all of the predefined constants that are in the "std" library so that you can use them, along with the functions included. "endl" is a constant that translates to the string "n", so there's really no magic about it.

On the other hand "cout" and the "<<" operator are part of the C++ language definition and will work even if you do not include the "using namespace" line (although some compilers might fail to bring in the std library at link time and you'll have errors, so you should always include it!).

for( ; ; ) hacking; :D

Buffy

Qfwfq · September 13, 2007

Ya must be talking about newfangled compilers, in ancient times cout was defined in iostream.h which had to be explicitly included.

alexander · September 13, 2007

Rod, I'll be glad to answer any questions you have, don't hesitate to post :P

ronthepon · September 27, 2007

Yeah... er... so lately I've been messing with file transfer ops, and after believing myself to be somewhat confident about them, I decide to actually write something.

So here's my aim. I'm interested in having my program read a table of numbers, say a text file written as:

And my program should be able to count the number of positive and negative numbers I supply.

So here's how my code is looking so far:

#include <iostream>
#include <fstream>
int main ()
{
   ifstream fread ("tes.txt");
   
   if (fread.is_open())
   {
       int neg = 0;
       int pos = 0;
       while (! fread.eof() )
       {
           fread.read /*how do I manage to get to have it read only three charecters??*/
           if (/*it's less than zero*/)
           {neg++)
           else
           {pos++)
       }
       std::cout << "Total negatives = " << neg << "Total positives = " << pos << 'n';
   }
   else
   {std::cout << "ntttError: File open failed."}
   
   system ("pause")
   return 0;
}

Ouch. I don't even know how to have it read just 3 digits (or four?) yet.

Any help on how I could add to the missing bits?

alexander · September 27, 2007

#include <iostream>
#include <fstream>
int main ()
{
 std::ifstream in_file; //declare the right datatype
 in_file.open("test.txt"); //open the file
 
 if (in_file.is_open()) //check if the file is open
   {
     int neg = 0; //declare the total negative integer variable
     int pos = 0; //declare the total positive integer variable
     int num = 0; //declare a temporary number variable 
     while (in_file>>num) //while we can read the line
       {
         if (num<0) //if the number is less then zero
           {neg++;} //increase neg
         else
           {pos++;} //increase pos
       }
     std::cout << "Total negatives = " << neg << "nTotal positives = " << pos << 'n';
   }
 else
   {
     std::cout << "ntttError: File open failed."; //and if we can not open the file, return an error
                                                                }
 //system("pause") //i dont need it in nix
 return 0;
}

works for me.... :)

ronthepon · October 4, 2007

Excellent, thanks!

So I see that 'in_file>>num' is not only a condition that returns 1 when successful, but also does it simultaneously insert the numbers, separated by de-limiters into 'num'. Truly cool. For de-limiters, I've managed to be able to find space and newline. What others are there? And how could I create or define my own delimiters?

I'm gonna see if I can make up something similar of charecters. Lessee how we manage in this precious hour...

alexander · October 4, 2007

yeah, if i'm not mistaken you can define your own delimiters, they can be anything really, from spaces to special characters or even letters, whatever you want, you can use getline for that :doh:

something like

while(!file.eof())
{
	getline(file,line, '~');  //get line and ignore delimiter
}

and the if (something) can be done with any statement, at that point it executes the command in (), if the command was successfully executed, then a true is passed to the if statement, if there are any errors, false is returned to if.

i actually have a macro routine that uses that principal for input validation :)

#define catch_err(x)
{
if(!(x))
{
cout << "An invalid value has been enteredn";
exit(1);
}
}

you can use this routine for validating user input type, and returning custom codes for data mistypes (your programming teacher will think you are god if you show this off)

use it like this catch_err(cin >> choice); if someone uses a string and choice is of type int, or if they dont enter anything in, they will get your nasty grhamm saying that an invalid option has been chosen (also its a way of writing more secure c++ code that needs input)

IDMclean · October 8, 2007

If nobody is particularly contrary, I would like some help with a feature of C++.

I have background in Java (much easier to read and understand than C++ IMHO) but I want to learn C++ because of it's ability to manage resources effectively.

I have a near impossible time understanding the * and **. Could I get some pointers on pointers?

Buffy · October 8, 2007

I have background in Java (much easier to read and understand than C++ IMHO)

Really, they're almost identical! Java used C++ as a starting point, but designed to be more strongly typed (more below).

but I want to learn C++ because of it's ability to manage resources effectively.

That depends on what you mean by "effectively." C++ has the advantage of still being kinda-sorta low-level like its parent C is, so to a certain extent, your C++ code can influence how the machine code gets generated, and you have the ability to directly manipulate the memory layout of objects (via pointers!).

As to whether that's a *benefit* or not, well, that depends on who you are and what you want!

The real significant difference at a high-level though between C++ and Java is that Java intentionally left out multiple-inheritance, a weakness that can be gotten around, but makes C++ a lot easier for really complex systems modeling.

Java also fixed the linking problems that are inherent in C++ implementations (mostly *just* an implementation/backward compatibility issue, but to a great extent also because pointers went away!), so if modular development is one of your primary goals, Java is going to be *much* easier to deal with.

I've never written a lot of Java, mainly because I've written C++ for so long, but for practical reasons have jumped over to C# which is almost identical to Java anyway.

I have a near impossible time understanding the * and **. Could I get some pointers on pointers?

You can use the simple translation:

"*" == "pointer to"

in order to figure out what they're doing. SO,

"int" is an integer variable
"int*" is a pointer to an integer variable, and
"int**" is a pointer to a pointer to an integer variable

Now, why do you need these? C never had a syntactic "pass by reference" mechanism, as was common even in earlier languages. Pass by reference is needed because you have a call to a function where a parameter is passed to the function, changed within it and then the developer wants to then used the changed value after the call (equivalent to having multiple return values for a function rather than just one). The way you do this in C/C++ is to pass a pointer. So:

function foo(int i) { i = i+1; return i; }
function foobyref(int *i) { *i = *i + 1; return *i; }

int myint = 1;
cout << foo (myint);
cout << myint;
cout << foobyref(&myint);
cout << myint;

Should produce:

2

1

2

Now "**" simply takes the level of indirection upward once more. This is useful primarily if you're dealing with a complex data structure that you want to restructure, for example in sorting routines, where you would have an array of pointers, and then your "swap" function would pass "pointers to pointers" to let the function "move" the two data structures in in your array by simply swapping the pointers instead of copying all the data in the structures.

I'm too lazy to give you an example, but you might want to post some attempts and I'm sure some of us will be happy to critique them! :eek:

Of course you'll also have to start learning to use "&" to get the "address" of variables or places in arrays or structures (which is not the same thing as the "&" "reference to" data type specifier, but you didn't ask about that so I won't confuse the topic further! :hihi: ).

Stop pointing, its impolite,

Buffy

IDMclean · October 8, 2007

What is getting passed by:

cout << foobyref(&myint);

The address, the contents of an address, or other?

I think I need a primer on *, **, &, and--hmm, what's that other one? &&?

What does a pointer represent/contain? Do pointers point to an address or the contents of an address?

I comprehend:
Variables, functions, classes, objects, and operators.

I fail to comprehend:
Pointers *, references &, dereferencing, and templates <T>

I'll leave my response to your points regarding Java as compared to C++ for it's own thread Here.

Buffy · October 8, 2007

What is getting passed by:
cout << foobyref(&myint);
The address, the contents of an address, or other?

"myint" is a 4-byte space in memory that has an address of say, 0x12345678. If you were to inspect the stack when this function was called, you'd see 0x12345678. The code that the compiler constructs around the call assumes that this is an address and does the appropriate operations to go get the value when a reference is made to this passed value, OR--and this is the "beauty" of C/C++--you *could* manipulate the address *itself*.

This is about as rational as quantum mechanics, so ask away...

What does a pointer represent/contain? Do pointers point to an address or the contents of an address?

A pointer is an address, nothing more or less. However a pointer is also a variable, and *it* can have an address, so you can have a "pointer to a pointer" (and on and on recursively ad infinitum).

A few definitions:

Variable: a *label* for a location in memory. It is a pointer only before the application is compiled, and cannot be "manipulated"
Pointer: a *variable* that is used to refer to address in memory: since it is a variable and not a label, you can have it point at different places in memory using various mechanisms like setting it to a memory address or operate on it (for example moving through an array by incrementing it).
Reference (see Visual Basic's "ByRef" keyword as an example): is a mechanism for passing parameters that is similar to passing a pointer in that the data in the variable that is referenced can be permanently changed, but it is "type-safe" in that the compiler hides the fact that it is a reference and does not require you to use strange "*" and "&" operators.
Address-of operator ("&"): an operator that lets you take a variable and find its address in memory. Since you are directly accessing memory, you need to be aware of what kind of memory it is (heap vs. stack) and its persistence), otherwise the memory location may not be there when you want it to be.
Dereferencing: The effect of the "*" operator that says "take this reference and tell me what the value is that is stored in that location"
Templates: These are *compile-time* constructs that can be used to specify data *types* that can have different values at run-time. They were actually completely unnecessary in C which let you blithely assign values from one data type to another with no checking whatsoever (a "low-level programming" "feature"), but C++ tightened up (although did not disallow) broad type conversions for base types, and required Templates for complex types. They are really hard to completely grok and 99.999% of programs do not need them, and even then they can be programmed around.

Incrementally pointed,

Buffy

alexander · October 9, 2007

ok, so here is some fairly complex code to show you just how oftenly you use pointers, and pointers to pointers

This is a Red-Black tree, which, if you are not familiar with the DS, its basically a binary tree that has a few rules to follow making it so the longest path from the root node to the leaf is no longer then twice the shortest path from the root to a leaf (which makes this an ideal data structure for real life applications, only thing is that you have to have comparable data in the tree...)

RedBlackTree.h:

       #ifndef RED_BLACK_TREE_H_
       #define RED_BLACK_TREE_H_

       #include "dsexceptions.h"
       #include <iostream.h>       // For NULL

       // Red-black tree class
       //
       // CONSTRUCTION: with negative infinity object also
       //               used to signal failed finds
       //
       // ******************PUBLIC OPERATIONS*********************
       // void insert( x )       --> Insert x
       // void remove( x )       --> Remove x (unimplemented)
       // Comparable find( x )   --> Return item that matches x
       // Comparable findMin( )  --> Return smallest item
       // Comparable findMax( )  --> Return largest item
       // boolean isEmpty( )     --> Return true if empty; else false
       // void makeEmpty( )      --> Remove all items
       // void printTree( )      --> Print tree in sorted order



         // Node and forward declaration because g++ does
         // not understand nested classes.
       template <class Comparable>
       class RedBlackTree;

       template <class Comparable>
       class RedBlackNode
       {
           Comparable    element;
           RedBlackNode *left;
           RedBlackNode *right;
           int           color;

           // c = 1 should be c = RedBlackTree<Comparable>::BLACK
           // But Visual 5.0 does not comprehend it.
           RedBlackNode( const Comparable & theElement = Comparable( ),
                             RedBlackNode *lt = NULL, RedBlackNode *rt = NULL,
                             int c = 1 )
             : element( theElement ), left( lt ), right( rt ), color( c ) { }
           friend class RedBlackTree<Comparable>;
       };

       template <class Comparable>
       class RedBlackTree
       {
         public:
           explicit RedBlackTree( const Comparable & negInf );
           RedBlackTree( const RedBlackTree & rhs );
           ~RedBlackTree( );

           const Comparable & findMin( ) const;
           const Comparable & findMax( ) const;
           const Comparable & find( const Comparable & x ) const;
           bool isEmpty( ) const;
           void printTree( ) const;

           void makeEmpty( );
           void insert( const Comparable & x );
           void remove( const Comparable & x );

           enum { RED, BLACK };

           const RedBlackTree & operator=( const RedBlackTree & rhs );

         private:
           RedBlackNode<Comparable> *header;   // The tree header (contains negInf)
           const Comparable ITEM_NOT_FOUND;
           RedBlackNode<Comparable> *nullNode;

               // Used in insert routine and its helpers (logically static)
           RedBlackNode<Comparable> *current;
           RedBlackNode<Comparable> *parent;
           RedBlackNode<Comparable> *grand;
           RedBlackNode<Comparable> *great;

               // Usual recursive stuff
           void reclaimMemory( RedBlackNode<Comparable> *t ) const;
           void printTree( RedBlackNode<Comparable> *t ) const;
           RedBlackNode<Comparable> * clone( RedBlackNode<Comparable> * t ) const;

               // Red-black tree manipulations
           void handleReorient( const Comparable & item );
           RedBlackNode<Comparable> * rotate( const Comparable & item,
                                       RedBlackNode<Comparable> *parent ) const;
           void rotateWithLeftChild( RedBlackNode<Comparable> * & k2 ) const;
           void rotateWithRightChild( RedBlackNode<Comparable> * & k1 ) const;
       };

       #include "RedBlackTree.cpp"
       #endif

RedBlackTree.cpp

       #include "RedBlackTree.h"

       /**
        * Construct the tree.
        * negInf is a value less than or equal to all others.
        * It is also used as ITEM_NOT_FOUND.
        */
       template <class Comparable>
       RedBlackTree<Comparable>::RedBlackTree( const Comparable & negInf )
         : ITEM_NOT_FOUND( negInf )
       {
           nullNode    = new RedBlackNode<Comparable>;
           nullNode->left = nullNode->right = nullNode;
           header      = new RedBlackNode<Comparable>( negInf );
           header->left = header->right = nullNode;
       }

       /**
        * Copy constructor.
        */
       template <class Comparable>
       RedBlackTree<Comparable>::RedBlackTree( const RedBlackTree<Comparable> & rhs )
         : ITEM_NOT_FOUND( rhs.ITEM_NOT_FOUND )
       {
           nullNode    = new RedBlackNode<Comparable>;
           nullNode->left = nullNode->right = nullNode;
           header      = new RedBlackNode<Comparable>( ITEM_NOT_FOUND );
           header->left = header->right = nullNode;
           *this = rhs;
       }

       /**
        * Destroy the tree.
        */
       template <class Comparable>
       RedBlackTree<Comparable>::~RedBlackTree( )
       {
           makeEmpty( );
           delete nullNode;
           delete header;
       }

       /**
        * Insert item x into the tree. Does nothing if x already present.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::insert( const Comparable & x )
       {
           current = parent = grand = header;
           nullNode->element = x;

           while( current->element != x )
           {
               great = grand; grand = parent; parent = current;
               current = x < current->element ?  current->left : current->right;

                   // Check if two red children; fix if so
               if( current->left->color == RED && current->right->color == RED )
                    handleReorient( x );
           }

               // Insertion fails if already present
           if( current != nullNode )
               return;
           current = new RedBlackNode<Comparable>( x, nullNode, nullNode );

               // Attach to parent
           if( x < parent->element )
               parent->left = current;
           else
               parent->right = current;
           handleReorient( x );
       }

       /**
        * Remove item x from the tree.
        * Not implemented in this version.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::remove( const Comparable & x )
       {
           cout << "Sorry, remove unimplemented; " << x <<
                " still present" << endl;
       }

       /**
        * Find the smallest item  the tree.
        * Return the smallest item or ITEM_NOT_FOUND if empty.
        */
       template <class Comparable>
       const Comparable & RedBlackTree<Comparable>::findMin( ) const
       {
           if( isEmpty( ) )
               return ITEM_NOT_FOUND;

           RedBlackNode<Comparable> *itr = header->right;

           while( itr->left != nullNode )
               itr = itr->left;

           return itr->element;
       }

       /**
        * Find the largest item in the tree.
        * Return the largest item or ITEM_NOT_FOUND if empty.
        */
       template <class Comparable>
       const Comparable & RedBlackTree<Comparable>::findMax( ) const
       {
           if( isEmpty( ) )
               return ITEM_NOT_FOUND;

           RedBlackNode<Comparable> *itr = header->right;

           while( itr->right != nullNode )
               itr = itr->right;

           return itr->element;
       }

       /**
        * Find item x in the tree.
        * Return the matching item or ITEM_NOT_FOUND if not found.
        */
       template <class Comparable>
       const Comparable & RedBlackTree<Comparable>::find( const Comparable & x ) const
       {
           nullNode->element = x;
           RedBlackNode<Comparable> *curr = header->right;

           for( ; ; )
           {
               if( x < curr->element )
                   curr = curr->left;
               else if( curr->element < x )
                   curr = curr->right;
               else if( curr != nullNode )
                   return curr->element;
               else
                   return ITEM_NOT_FOUND;
           }
       }

       /**
        * Make the tree logically empty.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::makeEmpty( )
       {
           reclaimMemory( header->right );
           header->right = nullNode;
       }

       /**
        * Test if the tree is logically empty.
        * Return true if empty, false otherwise.
        */
       template <class Comparable>
       bool RedBlackTree<Comparable>::isEmpty( ) const
       {
           return header->right == nullNode;
       }

       /**
        * Print the tree contents in sorted order.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::printTree( ) const
       {
           if( header->right == nullNode )
               cout << "Empty tree" << endl;
           else
               printTree( header->right );
       }


       /**
        * Deep copy.
        */
       template <class Comparable>
       const RedBlackTree<Comparable> &
       RedBlackTree<Comparable>::operator=( const RedBlackTree<Comparable> & rhs )
       {
           if( this != &rhs )
           {
               makeEmpty( );
               header->right = clone( rhs.header->right );
           }

           return *this;
       }

       /**
        * Internal method to print a subtree t in sorted order.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::printTree( RedBlackNode<Comparable> *t ) const
       {
           if( t != t->left )
           {
               printTree( t->left );
               cout << t->element << endl;
               printTree( t->right );
           }
       }

       /**
        * Internal method to clone subtree.
        */
       template <class Comparable>
       RedBlackNode<Comparable> *
       RedBlackTree<Comparable>::clone( RedBlackNode<Comparable> * t ) const
       {
           if( t == t->left )  // Cannot test against nullNode!!!
               return nullNode;
           else
               return new RedBlackNode<Comparable>( t->element, clone( t->left ),
                                              clone( t->right ), t->color );
       }


       /**
        * Internal routine that is called during an insertion
        *     if a node has two red children. Performs flip
        *     and rotatons.
        * item is the item being inserted.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::handleReorient( const Comparable & item )
       {
               // Do the color flip
           current->color = RED;
           current->left->color = BLACK;
           current->right->color = BLACK;

           if( parent->color == RED )   // Have to rotate
           {
               grand->color = RED;
               if( item < grand->element != item < parent->element )
                   parent = rotate( item, grand );  // Start dbl rotate
               current = rotate( item, great );
               current->color = BLACK;
           }
           header->right->color = BLACK; // Make root black
       }

       /**
        * Internal routine that performs a single or double rotation.
        * Because the result is attached to the parent, there are four cases.
        * Called by handleReorient.
        * item is the item in handleReorient.
        * parent is the parent of the root of the rotated subtree.
        * Return the root of the rotated subtree.
        */
       template <class Comparable>
       RedBlackNode<Comparable> *
       RedBlackTree<Comparable>::rotate( const Comparable & item,
                             RedBlackNode<Comparable> *theParent ) const
       {
           if( item < theParent->element )
           {
               item < theParent->left->element ?
                   rotateWithLeftChild( theParent->left )  :  // LL
                   rotateWithRightChild( theParent->left ) ;  // LR
               return theParent->left;
           }
           else
           {
               item < theParent->right->element ?
                   rotateWithLeftChild( theParent->right ) :  // RL
                   rotateWithRightChild( theParent->right );  // RR
               return theParent->right;
           }
       }

       /**
        * Rotate binary tree node with left child.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::
       rotateWithLeftChild( RedBlackNode<Comparable> * & k2 ) const
       {
           RedBlackNode<Comparable> *k1 = k2->left;
           k2->left = k1->right;
           k1->right = k2;
           k2 = k1;
       }

       /**
        * Rotate binary tree node with right child.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::
       rotateWithRightChild( RedBlackNode<Comparable> * & k1 ) const
       {
           RedBlackNode<Comparable> *k2 = k1->right;
           k1->right = k2->left;
           k2->left = k1;
           k1 = k2;
       }


       /**
        * Internal method to reclaim internal nodes
        * in subtree t.
        */
       template <class Comparable>
       void RedBlackTree<Comparable>::reclaimMemory( RedBlackNode<Comparable> *t ) const
       {
           if( t != t->left )
           {
               reclaimMemory( t->left );
               reclaimMemory( t->right );
               delete t;
           }
       }

and if you want to test it:


TestRedBlack
[code]
       #include <iostream.h>
       #include "RedBlackTree.h"

           // Test program
       int main( )
       {
           const int NEG_INF = -9999;
           const int ITEM_NOT_FOUND = NEG_INF;
           RedBlackTree<int> t( ITEM_NOT_FOUND );
           int NUMS = 40000;
           const int GAP  =   37;
           int i;

           cout << "Checking... (no more output means success)" << endl;

           for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
               t.insert( i );

           if( NUMS < 40 )
               t.printTree( );
           if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )
               cout << "FindMin or FindMax error!" << endl;

           for( i = 1; i < NUMS; i++ )
               if( t.find( i ) != i )
                   cout << "Find error1!" << endl;
           if( t.find( 0 ) != ITEM_NOT_FOUND )
               cout << "ITEM_NOT_FOUND failed!" << endl;


           RedBlackTree<int> t2( ITEM_NOT_FOUND );
           t2 = t;

           for( i = 1; i < NUMS; i++ )
               if( t2.find( i ) != i )
                   cout << "Find error1!" << endl;
           if( t2.find( 0 ) != ITEM_NOT_FOUND )
               cout << "ITEM_NOT_FOUND failed!" << endl;

           return 0;
   }

No i did not write the code if you are wondering... and yes my point being that you very very rarely use pointers to pointers in most applications and even fairly complex DSes

alexander · October 19, 2007

ok, so finally some code that will compile in g++.

Working on a project for OS class, to model scheduling algorithms, and while i havent gotten to the part of the actual modeling of the algorithms, i have gotten quite far in setting up the data structure for Jobs. its pretty neat code, nothing super complex, figured you guys will probably appreciate it to the extent coders appreciate code to (and buffy is going to critique it, but i am ready for it)

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

class Job
{
     private:
     		  int job_id; //job id
             int time_to_exec; //time it takes for the job to execute
             bool inuse;  //is this job being ran?
             int time_in; //when does the job come in?
             int wait_time; //wait time of the job
     public:
            Job(); //constructor
            Job(int, int, int); //overloaded constructor with assignment
            void inc_wait_time(); //method to increase waiting time
            void change_state(); //method to change the state from active to inactive job
            bool state(); //returns current state (0 being not executing)
            void set_time_to_exec(int); //set time to execute (just in case we need to edit)
            void set_time_in(int); //set time the job enters (once again in case we need it)
            void set_job_id(int); //edit the job ID
            bool operator<(Job); //overloaded < operator for easiness of comparison
            bool operator>(Job); //overloaded > operator
            bool operator==(Job); //overloaded == operator
            Job& operator=(const Job); //this is the fun one, the = operator overload
            int show_time_in() {return time_in;} //method to display time in
            int show_time_to_exec() {return time_to_exec;} //method to display time to execute
            int show_job_id() {return job_id;} //method to display the job ID
};

Job::Job() //constructor that initializes everything to zero
{
		job_id=0;
           time_to_exec=0;
           inuse = false;
           time_in = 0;
           wait_time = 0;
};

Job::Job(int id, int tte, int ti) //constructor, init the two values we want from the input menu
{
            if (tte >= 0)
            {
               time_to_exec = tte; //time to execute should be positive
            }
            else
            {
                time_to_exec = 0; //or 0
            }  
            if (ti >= 0)
            {
                time_in = ti; //time the job enters should be positive
            }
            else
            {
                time_in=0; //or zero
            }
            if (id >= 0)
            {
            	 job_id=id; //job id should not be less then zero
            }
            else
            {
            	 job_id=0; //or zero
            }
            inuse=false; //when we are setting up the program is not being used
            wait_time=0; //and since the simulation hasnt started, our wait time = 0
};

bool Job::operator<(Job :lightning
{
            if(time_to_exec < b.show_time_to_exec())
            {
                return true;
            }
            else
            {
                return false;
            }
};

bool Job::operator>(Job :naughty:
{
            if(time_to_exec > b.show_time_to_exec())
            {
                return true;
            }
            else
            {
                return false;
            }
};

bool Job::operator==(Job :hihi:
{
            if(time_to_exec == b.show_time_to_exec())
            {
                return true;
            }
            else
            {
                return false;
            }
};

Job& Job::operator=(Job :doh:
{
		if (this != &:) 
		{
			job_id = b.show_job_id();
       		time_to_exec = b.show_time_to_exec();
           	inuse = b.state();
           	time_in = b.show_time_in();
           	wait_time = b.wait_time;
		}
		return *this;
};

void Job::change_state()//method to change the state from active to inactive job
{            
            inuse^=1; //xor of our current use state and one
};

void Job::inc_wait_time() //method to increase waiting time
{
    wait_time++;
};

bool Job::state() //returns current state (0 being not executing)
{
    return inuse;
};

void Job::set_time_to_exec(int tte) //set time to execute (just in case we need to edit)
{
    if(tte >= 0)
    {
           time_to_exec=tte;
    }
    else
    {
           time_to_exec=0;
    }
};

void Job::set_time_in(int ti) //set time the job enters (once again in case we need it)
{
    if(ti >= 0)
    {
          time_in=ti;
    }
    else
    {
          time_in=0;
    }
}; 

void Job::set_job_id(int id)
{
    if(id >= 0)
    {
          job_id=id;
    }
    else
    {
          job_id=0;
    }
};

/* Sorts first n elements of array a[] in non-decreasing order. */
template<typename T> void merge_sort(T a[], int n)
{
int i, j, k;
T tmp;

/* For small arrays, insertion sort is much faster */
if (n < 64) {
	for (i = 1; i < n; i++) {
		tmp = a[i];
		for (j = i-1; j >= 0 && tmp < a[j]; j--) a[j+1] = a[j];
		a[j+1] = tmp;
	}
	return;
}

int f = n / 2;		/* f = number of elements in first half */

       /* Recursively sort both halves */
merge_sort(a, f);
merge_sort(a+f, n-f);

       /* Merge */
T *s = new T[n];	/* temporary array to keep the sorted sequence */

for (i = 0, j = f, k = 0; i < f && j < n;)
	s[k++] = (a[i] < a[j]) ? a[i++] : a[j++];

while (i < f) s[k++] = a[i++];
while (j < n) s[k++] = a[j++];

for (i = 0; i < n; i++) a[i] = s[i];
delete[] s;
}

/* Example of usage: */
int main()
{
const int MAX_JOBS = 5;

Job jobs[MAX_JOBS];

//setup for testsing purposes
jobs[0].set_job_id(1);
jobs[0].set_time_to_exec(10);
jobs[0].set_time_in(1);
jobs[1].set_job_id(2);
jobs[1].set_time_to_exec(50);
jobs[1].set_time_in(4);
jobs[2].set_job_id(50);
jobs[2].set_time_to_exec(20);
jobs[2].set_time_in(3);
jobs[3].set_job_id(4);
jobs[3].set_time_to_exec(15);
jobs[3].set_time_in(5);
jobs[4].set_job_id(3);
jobs[4].set_time_to_exec(60);
jobs[4].set_time_in(2);

cout << "before the sort:n";
for (int i = 0; i < MAX_JOBS; i++) printf("%dn", jobs[i].show_time_to_exec());

//merge sort test
cout << "after the sort:n";
merge_sort(jobs, MAX_JOBS);
for (int i = 0; i < MAX_JOBS; i++) printf("%dn", jobs[i].show_time_to_exec());

}

alexander · October 19, 2007

biggest thing of notice is the templated merge sort function, thank you google :lightning

oh dont mind the namespace std, its there for testing while i develop, it will be more speciffic in the final program (which i will post here)

ronthepon · November 8, 2007

It's been ages since I've actually been on the net at my leisure, but BTW, I'd just like to announce that I've just managed like the institute highest score in the C++ course for now. Thanks for that Alex.

Meanwhile I divert my energy from my studies to 3D modelling.

But I'm supposed to be figuring classes in the meantime. So what I figure till now that the file handling operations I was struggling with earlier was more of the normal way in which classes are used. I figure that fstream has got to be a class that includes ofstream and ifstream, and the functions like 'open()' and 'is_open()' are no more than included functions.

Lovely. Now I actually begin to figure what this language is all about.

Sign In

Finally learning C++!

Recommended Posts

alexander

Top Posters In This Topic

Popular Days

Top Posters In This Topic

Popular Days

Popular Posts

sanctus

alexander

alexander

ronthepon

Buffy

Qfwfq

alexander

ronthepon

alexander

ronthepon

alexander

IDMclean

Buffy

IDMclean

Buffy

alexander

alexander

alexander

ronthepon

Join the conversation

sanctus

alexander

alexander

Browse

Activity