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