Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

wvvector.h

Go to the documentation of this file.
00001 /* -*- Mode: C++ -*-
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Provides an auto-resizing array data structure.
00006  */
00007 #ifndef __WVVECTOR_H
00008 #define __WVVECTOR_H
00009 
00010 #include "wvlink.h"
00011 #include <string.h>
00012 
00013 /**
00014  * The untyped vector base type.
00015  * @see WvVector
00016  */
00017 class WvVectorBase
00018 {
00019 protected:
00020     static const int MINALLOC = 4;
00021         /*!< the minimum number of slots to allocate */
00022 
00023     void **xseq; /*!< the controlled sequence */
00024     int xcount; /*!< the number of elements in the sequence */
00025     int xslots; /*!< the capacity of the array */
00026     bool auto_free; /*!< whether to auto-delete the elements when removed */
00027 
00028     /** Creates an empty vector. */
00029     WvVectorBase(bool _auto_free);
00030 
00031     /** Computes the number of slots needed to grow to at least minslots. */
00032     int growcapacity(int minslots);
00033     
00034     /** Computes the number of slots needed to shrink down to maxslots. */
00035     int shrinkcapacity(int maxslots);
00036     
00037     /** A shorthand for memmove() with size adjustment. */
00038     void moveelems(void *dst, void *src, int nelems)
00039         { memmove(dst, src, nelems * sizeof(void *)); }
00040 
00041     /** Removes the element at the specified slot. */
00042     void remove(int slot);
00043     
00044     /** Inserts an element at the specified slot. */
00045     void insert(int slot, void *elem);
00046 
00047     /** Appends an element onto the tail of the vector. */
00048     void append(void *elem);
00049     
00050 public:
00051     /** Returns the number of elements actually stored in the vector. */
00052     int count() const
00053         { return xcount; }
00054 
00055     /** Returns true if the vector is empty. */
00056     bool isempty() const
00057         { return xcount == 0; }
00058 
00059     /** The number of elements that could be stored without resizing. */
00060     int capacity() const
00061         { return xslots; }
00062     
00063     /**
00064      * Adjusts the capacity of the vector.
00065      *
00066      * If the new capacity is greater than the old one, extends the array
00067      * size without actually filling in any elements.
00068      */
00069     void setcapacity(int newslots);
00070 
00071     /** Compacts the vector to minimize its footprint. */
00072     void compact()
00073         { setcapacity(count()); }
00074 };
00075 
00076 
00077 /**
00078  * A dynamic array data structure with constant time lookup,
00079  * linear time insertion / removal, and expected logarithmic time
00080  * append.
00081  */
00082 template<class T>
00083 class WvVector : public WvVectorBase
00084 {
00085 public:
00086     /** Creates an empty vector. */
00087     WvVector(bool _auto_free) : WvVectorBase(_auto_free)
00088         { }
00089 
00090     /** Destroys the vector and all of its contents. */
00091     ~WvVector()
00092         { zap(); }
00093 
00094     /** Dereferences a particular slot of the vector. */
00095     T *operator[] (int slot)
00096         { return ptr()[slot]; }
00097 
00098     /** Removes all elements from the vector. */
00099     void zap()
00100     { 
00101         // guard against potential side-effects
00102         T **oldarray = ptr();
00103         int oldcount = xcount;
00104         xcount = 0;
00105         xslots = 0;
00106         xseq = NULL;
00107         if (auto_free)
00108         {
00109             while (oldcount > 0)
00110                 delete oldarray[--oldcount];
00111         }
00112         delete[] oldarray;
00113     }
00114 
00115     void remove(int slot, bool never_delete = false)
00116     {
00117         T *obj = (*this)[slot];
00118         WvVectorBase::remove(slot);
00119         if (auto_free && !never_delete)
00120             delete obj;
00121     }
00122     
00123     /** Removes the last element */
00124     void remove_last()
00125         { if (xcount) { remove(xcount-1); } }
00126         
00127     T *last()
00128         { return xcount ? (*this)[xcount-1] : NULL; }
00129     
00130     void insert(int slot, T *elem)
00131         { WvVectorBase::insert(slot, elem); }
00132 
00133     void append(T *elem)
00134         { WvVectorBase::append(elem); }
00135     
00136     // FIXME: I'd rather not give public access to this, since it's dangerous!
00137     T **ptr() 
00138         { return reinterpret_cast<T **>(xseq); }
00139     
00140     
00141     /** A simple iterator that walks through all elements in the list. */
00142     class Iter
00143     {
00144         WvVector<T> *list;
00145         int count;
00146         
00147     protected:
00148         /** _list is allowed to be NULL, and this will still work. */
00149         Iter(WvVector<T> *_list) : list(_list)
00150             { count = -1; }
00151 
00152     public:
00153         Iter(WvVector<T> &_list) : list(&_list)
00154             { count = -1; }
00155         
00156         void rewind()
00157             { count = -1; }
00158         bool next()
00159             { count++; return cur(); }
00160         bool cur()
00161             { return list && count >= 0 && count < list->count(); }
00162         
00163         T *ptr() const
00164             { return (*list)[count]; }
00165         
00166         WvIterStuff(T);
00167     };
00168 };
00169 
00170 #endif // __WVVECTOR_H

Generated on Wed Dec 15 15:08:11 2004 for WvStreams by  doxygen 1.3.9.1