Main Page | Namespace List | Compound List | File List | Compound Members | File Members

kvector.cpp

Go to the documentation of this file.
00001 // kvector.cpp : Simple implementation of STL vector
00002 
00003 #include "stdafx.h"
00004 #include <iostream>
00005 #include <ctype.h>
00006 #include <algorithm>
00007 using namespace std;
00008 
00009 //! \file kvector.cpp
00010 //
00011 /*! \mainpage kvector documentation page
00012  * This provides a way to study the kvector code
00013  * by following the links in several ways.
00014  * Let me know if it is useful.
00015  */
00016 
00017 const int DEFSIZE=5; //!< default vector size
00018 
00019 const int INCR=5; //!< how much to increase the array size by 
00020 
00021 //! The kvector class
00022 /*! We are making a vector class. A vector is like an array but the
00023     length can vary. We will use templates so  that it can work
00024     with an array of any type and make it longer as needed.
00025     This is similar to the way the Vector class from the STL works,
00026     but much simpler.
00027     I have also added some other methods and operators to better support
00028     the Vector data type.
00029 */ 
00030 template <class MYTYPE>
00031 class kvector {
00032         public:
00033                 kvector(void); //!< default constructor
00034                 kvector(int);  //!< set initial vector size to size
00035                 ~kvector(void) { if(vptr != NULL) delete [] vptr;}
00036 
00037                 void add(MYTYPE x); // add data value x to next open slot
00038                 void show(void); // print the current contents of the vector
00039                 int get_length(void) { return length;}
00040 
00041                  //! access
00042                  /*! the access function can be used on either side of the =
00043                     since it returns a reference to the array member being accessed.
00044                 */ 
00045                 MYTYPE & access(int index) 
00046                 {
00047                         if((index >= 0) && (index < length))
00048                                 return vptr[index];
00049                         else
00050                                 throw "Bad index";
00051                 }
00052 
00053                 //! overloaded array access operator
00054                 /*! makes our vector look like an array since we can access the elements
00055                    using the [] operator. It also checks that we are not trying to access
00056                    something we shouldn't.
00057                    Note that it is very similar to the access() method 
00058                 */ 
00059                 MYTYPE & operator[](int index) 
00060                 {
00061                         if((index >= 0) && (index < length))
00062                                 return vptr[index];
00063                         else
00064                                 throw "Bad index";
00065                 }
00066 
00067                 //! overloaded output operator
00068                 /*! prints the contents in a line. Assumes the base type (MYTYPE)
00069                    has a << operator defined.
00070                 */ 
00071                 friend ostream & operator<<(ostream & os, kvector<MYTYPE> & k)
00072                 {
00073                         for(int i=0; i < k.get_length(); i++) 
00074                                         os << k[i] << " ";
00075                         os << endl;
00076                         return os;
00077                 }
00078                 
00079                 //! internal public iterator class
00080                 /*! now we define the internal iterator class. This allows us 
00081                    to create pointer like objects that will work on our Vector
00082                    without the user having to know that there is an array inside.
00083                  I added the begin() and end() methods to the kvector class to support this.
00084                  The essential feature of an iterator class is that it overload the pointer operators
00085                  like * and movement operators like ++ and --.
00086                 */ 
00087                 class iterator {
00088                 public:
00089                         iterator() {ptr = 0;}
00090                         iterator(MYTYPE * m) {ptr = m;}
00091                         iterator(iterator & i) {ptr = i.get_ptr();}  //!< copy constructor
00092                         MYTYPE * get_ptr() { return ptr;}
00093 
00094                         // since the pointer hidden inside the iterator is an regular
00095                         // array pointer, then iterator++ turns into pointer++.
00096                         // If this had been a list object, then the iterator++ would have
00097                         // turned into the pointer = pointer->next kind of structure.
00098                         // We also need one for prefix increment for copy() to work.
00099                         void operator++(int) { ptr++; }   //!< pointer post-increment
00100                         void operator++() { ++ptr; }   //!< pointer pre-increment
00101 
00102                         // probably the bitwise copy of the default assignment operator
00103                         // would have worked, but I wanted to be sure.
00104                         void operator=(iterator p) { ptr = p.get_ptr(); }  //!< assignment operator
00105 
00106                         // again, since the iterator hides a regular array pointer, the
00107                         // dereference operator becomes the pointer dereference
00108                         MYTYPE & operator*(void) { return *ptr;}  //!< dereference pointer
00109 
00110                         // comparison operators since the default might work but we want to be sure.
00111                         bool operator==(iterator i) { return (this->ptr == i.get_ptr());}
00112                         bool operator!=(iterator k) { return (this->ptr != k.get_ptr());}
00113                 private:
00114                         MYTYPE * ptr;  //!< the actual pointer to the internal array in the vector
00115         };
00116 
00117                 //! returns initial iterator for the kvector
00118                 /*! this creates a new iterator object and initializes it to
00119                    the beginning of the underlying array (vptr).
00120                    It then returns the iterator.
00121                    Note that x is a pointer because new returns a pointer,
00122                    but we have to return the actual iterator object because that is
00123                    what is expected of begin().
00124                 */
00125                 iterator begin() {
00126                                 iterator  *x = new iterator(vptr);
00127                                 return *x;
00128                 }
00129 
00130                 //! returns end iterator for the kvector
00131                 /*! This also creates a new iterator and points it
00132                    at the memory just after the end of the array.
00133                   it does this by getting the address of the last cell in the array
00134                   &vptr[length-1] is the address of the last element in the array
00135                   Then we add 1 to get the address of the next place after the end
00136                   of the array.
00137                 */
00138                 iterator end() { 
00139                                 iterator  *x = new iterator( (MYTYPE *)(&vptr[length-1]) + 1);
00140                                 return *x;
00141                 }
00142 
00143         protected:
00144                 MYTYPE * vptr;  //!< pointer to current vector array
00145                 int count;   //!< current number of used slots in vector
00146                 int length;  //!< current number of slots in vector
00147 }; 
00148 
00149 //! create the initial vector of length DEFSIZE
00150 template <class MYTYPE>
00151 kvector<MYTYPE>::kvector()
00152 {
00153         length = DEFSIZE;
00154         count = 0;
00155         if( (vptr = new MYTYPE[length]) == NULL) {
00156                 cerr << "No memory for vector of length " << length << endl;
00157         }
00158 } // constructor
00159 
00160 //! create the initial vector of length size
00161 template <class MYTYPE>
00162 kvector<MYTYPE>::kvector(int size)
00163 {
00164         length = size;
00165         count = 0;
00166         if( (vptr = new MYTYPE[length]) == NULL) {
00167                 cerr << "No memory for vector of length " << length << endl;
00168         }
00169 } // 1 arg constructor
00170 
00171 //! print the current data elements in the vector
00172 template <class MYTYPE>
00173 void
00174 kvector<MYTYPE>::show(void)
00175 {
00176         cout << "vector = (";
00177         for(int i = 0; i < count; i++) {
00178                 cout << vptr[i];
00179                 if(i+1 != count) cout << ","; // don't print trailing comma
00180         }
00181         cout << ")" << endl;
00182 } // show
00183 
00184 /*! adds the integer x to the next slot in the vector
00185    if the vector is full, it allocates a new array, copies the values,
00186    and adjusts the pointers
00187 */
00188 template <class MYTYPE>
00189 void
00190 kvector<MYTYPE>::add(MYTYPE x)
00191 {
00192         /*! count is the number of used slots
00193             length is the number of slots
00194                 if the count and length are equal, then the array
00195                 is full and we need to allocate a new bigger array.
00196                 We make the array bigger in chunks to avoid having to run this code
00197                 too often.
00198                 after the new array is created, we copy the old array elements 
00199                 to the new array.
00200                 Changing the internal kvector array pointer (vptr) to
00201                 point to the new array completes the work.
00202                 We can delete the old array now.
00203                 length is changed to the new array size.
00204                 Whether or not the array was extended, we add the
00205                 parameter x to the array.
00206         */
00207         if( count == length) {  // make new array
00208                 cout << "making new array" << endl;
00209                 MYTYPE * tptr = new MYTYPE[length + INCR];
00210                 if(tptr == NULL) { // this is fatal
00211                         cerr << "No memory for new array" << endl;
00212                         throw ("no memory");
00213                 }
00214                 // copy the old array elements to the new array.
00215                 for(int i=0; i < count; i++) tptr[i] = vptr[i];
00216 //              delete vptr;  // we don't need this anymore
00217                 vptr = tptr;  // make the new array the current array
00218                 length += INCR;
00219         }
00220         vptr[count++] = x;
00221 } // add
00222 
00223 //! run test code on integers
00224 void
00225 vector_int()
00226 {
00227         kvector<int> v;
00228 
00229         try {
00230                 // fill up the vector
00231                 cout << "putting in initial data" << endl;
00232                 for(int i=0; i < v.get_length(); i++) v.add(i);
00233                 v.show();
00234                 cout << "now adding 5 more" << endl;
00235                 for(int j=0; j < 5; j++) v.add(j);
00236                 v.show();
00237 
00238                 cout << "print using the overloaded [] operator" << endl;
00239                 for(int k=0; k < v.get_length(); k++) cout << v[k] << " ";
00240                 cout << endl;
00241 
00242                 /* since the [] operator returns a reference, we can treat it like a variable
00243                    and use it on the left side of an asignment
00244            */
00245                 cout << " changing element 0 to 99 using []" << endl;
00246                 v[0] = 99;
00247                 cout << v;
00248 
00249                 // try the access method on either side of the =
00250                 cout << "element 1 is " << v.access(1) << endl;
00251                 cout << " changing element 1 to 42 using access()" << endl;
00252                 v.access(1) = 42;
00253                 cout << v;
00254                 cout << "testing the array boundary exception" << endl;
00255                 v[100] = 87;
00256         }
00257         catch(char * str ) {
00258                         cerr << str << endl;
00259         }
00260         catch(...) {
00261                         cerr << "Some unknown exception caught" << endl;
00262         }
00263 
00264         /*
00265            now test out the iterator class
00266            since the iterator class is inside the kvector class,
00267            we have to use the scope resolution operator (::) to use it.
00268            We will also test the iterator by using the copy algorithm
00269            from the STL.
00270    */
00271         kvector<int>::iterator ptr;
00272         try {
00273                         cout << "printing the vector using iterator" << endl;
00274                         ptr = v.begin();
00275                         while(ptr != v.end()) {
00276                                 cout << *ptr << " ";
00277                                 ptr++;
00278                         }
00279                         cout << endl;
00280                         cout << "printing the vector using copy()" << endl;
00281                         copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
00282                         cout << endl;
00283         }
00284         catch(char * str ) {
00285                         cerr << str << endl;
00286         }
00287         catch(...) {
00288                         cerr << "Some unknown exception caught" << endl;
00289         }
00290 
00291 } // vector_int
00292 
00293 //! run test code on floats
00294 void
00295 vector_float()
00296 {
00297         kvector<double> v;
00298 
00299         try {
00300                 // fill up the vector
00301                 cout << "putting in initial data" << endl;
00302                 for(int i=0; i < v.get_length(); i++) v.add(i/3.0);
00303                 v.show();
00304                 cout << "now adding 5 more" << endl;
00305                 for(int j=0; j < 5; j++) v.add(j/3.0);
00306                 v.show();
00307 
00308                 cout << "print using the overloaded [] operator" << endl;
00309                 for(int k=0; k < v.get_length(); k++) cout << v[k] << " ";
00310                 cout << endl;
00311 
00312                 /*
00313                    since the [] operator returns a reference, we can treat it like a variable
00314                    and use it on the left side of an asignment
00315            */
00316                 cout << " changing element 0 to 99.4 using []" << endl;
00317                 v[0] = 99.4;
00318                 cout << v;
00319 
00320                 // try the access method on either side of the =
00321                 cout << "element 1 is " << v.access(1) << endl;
00322                 cout << " changing element 1 to 42.4 using access()" << endl;
00323                 v.access(1) = 42.4;
00324                 cout << v;
00325                 cout << "testing the array boundary exception" << endl;
00326                 v[100] = 87.4;
00327         }
00328         catch(char * str ) {
00329                         cerr << str << endl;
00330         }
00331         catch(...) {
00332                         cerr << "Some unknown exception caught" << endl;
00333         }
00334 
00335         /*
00336            now test out the iterator class
00337            since the iterator class is inside the kvector class,
00338            we have to use the scope resolution operator (::) to use it.
00339            We will also test the iterator by using the copy algorithm
00340            from the STL.
00341    */
00342         kvector<double>::iterator ptr;
00343         try {
00344                         cout << "printing the vector using iterator" << endl;
00345                         ptr = v.begin();
00346                         while(ptr != v.end()) {
00347                                 cout << *ptr << " ";
00348                                 ptr++;
00349                         }
00350                         cout << endl;
00351                         cout << "printing the vector using copy()" << endl;
00352                         copy(v.begin(),v.end(),ostream_iterator<double>(cout," "));
00353                         cout << endl;
00354         }
00355         catch(char * str ) {
00356                         cerr << str << endl;
00357         }
00358         catch(...) {
00359                         cerr << "Some unknown exception caught" << endl;
00360         }
00361 
00362 } // vector_float
00363 
00364 
00365 int main(int argc, char* argv[])
00366 {
00367         char ch;
00368         cout << "Enter i for integer test or f for float test" << endl;
00369         cin >> ch;
00370         cin.ignore();
00371         if(tolower(ch) == 'i')
00372                 vector_int();
00373         else
00374                 vector_float();
00375         return 0;
00376 }

Generated on Wed Sep 24 15:58:41 2003 for kvector by doxygen 1.3.3