Well I got slightly sidetracked with the 3.1.1 release. But I cleaned up the first of my new data structures for htlib. It's a pseudo-Vector class. It implements a dynamic array of, well, pointers to Objects. So it's not a true Vector since it doesn't store the Objects directly. However, it shares most of the List methods (not surprisingly) and will nicely support the soon-to-come Heap class. For those who have forgotten their data structures lessons, the +/- of a Vector: + Direct access to components, as in an array + Saves space over Lists because there are no next (prev) references + Can be expanded easily like a String - Expansion can require copying over the whole Vector (thus you keep some slack) - Requires memory in one contiguous piece Let me know if there are glaring bugs or missing methods or whatnot. I haven't tried it out much, but I'm hoping this can be a model for new classes. Specifically, take a look at the comments at the beginning. Does this work? Cheers, -Geoff
// // HtVector.h // // A Vector class which holds objects of type Object. // (A vector is an array that can expand as necessary) // This class is very similar in interface to the List class // // Part of the ht://Dig package <http://www.htdig.org/> // Copyright (c) 1999 The ht://Dig Group // For copyright details, see the file COPYING in your distribution // or the GNU Public License version 2 or later // <http://www.gnu.org/copyleft/gpl.html> // // $Id:$ // // #ifndef _HtVector_h_ #define _HtVector_h_ #include "Object.h" class HtVector : public Object { public: // // Constructor/Destructor // HtVector(); HtVector(int capacity); ~HtVector(); // // Add() will append an Object to the end of the vector // void Add(Object *); // // Insert() will insert an object at the given position. If the // position is larger than the number of objects in the vector, the // object is appended; no new objects are created between the end // of the vector and the given position. // void Insert(Object *, int position); // // Find the given object in the vector and remove it from the vector. // The object will NOT be deleted. If the object is not found, // NOTOK will be returned, else OK. // int Remove(Object *); // // Remove the object at the given position // (in some sense, the inverse of Insert) // int RemoveFrom(int position); // // Destroy() will delete all the objects in the vector. This is // equivalent to calling the destructor // void Destroy(); // // Vector traversel (a bit redundant since you can use []) // void Start_Get() {current_index = -1;} Object *Get_Next(); Object *Get_First(); Object *Next(Object *current); Object *Previous(Object *current); Object *Last() {return data[element_count];} // // Direct access to vector items. To assign new objects, use // Insert() or Add() // Object *operator[] (int n) {return data[n];} Object *Nth(int n) {return data[n];} // // Access to the number of elements // int Count() const {return element_count;} bool IsEmpty() {return element_count==0;} // // Get the index number of an object. If the object is not found, // returns -1 // int Index(Object *); // // Deep copy member function // HtVector *Copy(); // // Vector Assignment // HtVector &operator= (HtVector *vector) {return *this = *vector;} HtVector &operator= (HtVector &vector); protected: // // The actual internal data array // Object **data; // // For traversal it is nice to know where we are... // int current_index; // // It's nice to keep track of how many things we contain... // as well as how many slots we've declared // int element_count; int allocated; // // Protected function to ensure capacity // void Allocate(int ensureCapacity); }; #endif
// // HtVector.cc // // A Vector class which holds objects of type Object. // (A vector is an array that can expand as necessary) // This class is very similar in interface to the List class // // Part of the ht://Dig package <http://www.htdig.org/> // Copyright (c) 1999 The ht://Dig Group // For copyright details, see the file COPYING in your distribution // or the GNU Public License version 2 or later // <http://www.gnu.org/copyleft/gpl.html> // // #if RELEASE static char RCSid[] = "$Id:$"; #endif #include "HtVector.h" //**************************************************************** ***** // void HtVector::HtVector() // Default constructor // HtVector::HtVector() { HtVector(4); // After all, why would anyone want an empty vector? } //****************************************************************** *** // void HtVector::HtVector(int capacity) // Constructor with known capacity // (has the side effect of not allocating double memory) // HtVector::HtVector(int capacity) { data = new Object *[capacity]; element_count = 0; allocated = capacity; current_index = -1; } //********************************************************************* // void HtVector::~HtVector() // Destructor // HtVector::~HtVector() { Destroy(); } //*************************************************************** ****** // void HtVector::Destroy() // Deletes all objects from the vector // void HtVector::Destroy() { for (current_index = 0; current_index < element_count; current_index++) delete data[current_index]; delete [] data; allocated = 0; element_count = 0; current_index = -1; } //********************************************************************* // void HtVector::Add(Object *object) // Add an object to the list. // void HtVector::Add(Object *object) { Allocate(element_count+1); data[element_count] = object; element_count += 1; } //********************************************************************* / / void HtVector::Insert(Object *object, int position) // Add an object into the list. // void HtVector::Insert(Object *object, int position) { if (position > element_count) { Add(object); return; } Allocate(element_count + 1); for (int i = element_count; i > position; i--) data[i] = data[i-1]; data[position] = object; element_count += 1; } //********************************************************************* / / int HtVector::Remove(Object *object) // Remove an object from the list. // int HtVector::Remove(Object *object) { int position = Index(object); if (position == -1) return NOTOK; for (int i = position; i < element_count; i++) data[i] = data[i+1]; element_count -= 1; return OK; } //********************************************************************* // int HtVector::RemoveFrom(int position) // Remove an object from the list. // int HtVector::RemoveFrom(int position) { if (position < 0 || position > element_count) return NOTOK; for (int i = position; i < element_count; i++) data[i] = data[i+1]; element_count -= 1; return OK; } //********************************************************************* // Object *HtVector::Get_Next() // Return the next object in the list. // Object *HtVector::Get_Next() { current_index++; if (current_index > element_count) return 0; return data[current_index]; } //***************************************************** **************** // Object *HtVector::Get_First() // Return the first object in the list. // Object *HtVector::Get_First() { if (!IsEmpty()) { current_index = 0; return data[0]; } else return 0; } //********************************************************************* / / int HtVector::Index(Object *obj) // Return the index of an object in the list. // int HtVector::Index(Object *obj) { int index = 0; while (index <= element_count && data[index] != obj) { index++; } if (index >= element_count) return -1; else return index; } //********************************************************************* // Object *HtVector::Next(Object *prev) // Return the next obj ect in the list. Using this, the list will // appear as a circular list. // Object *HtVector::Next(Object *prev) { current_index = Index(prev); if (current_index == -1) return 0; current_index++; // We should probably do this with remainders if (current_index > element_count) current_index = 0; return data[current_index]; } //***************************************************** **************** // Object *HtVector::Previous(Object *next) // Return the previous object in the vector. Using this, the vector will // appear as a circular list. // Object *HtVector::Previous(Object *next) { current_index = Index(next); if (current_index == -1) return 0; current_index--; // We should probably do this with remainders if (current_index > element_count) current_index = 0; return data[current_index]; } //***************************************************** **************** // HtVector *HtVector::Copy() // Return a deep copy of the vector. // HtVector *HtVector::Copy() { HtVector *vector = new HtVector(allocated); Start_Get(); Object *obj; while ((obj = Get_Next())) { vector->Add(obj->Copy()); } return vector; } //****************************************************************** *** // HtVector &HtVector::operator=(HtVector &vector) // Return a deep copy of the list. // HtVector &HtVector::operator=(HtVector &vector) { Destroy(); vector.Start_Get(); Object *obj; while ((obj = vector.Get_Next())) { Add(obj->Copy()); } return *this; } //******************************************************************* ** // int Allocate(int capacity) // Ensure there is at least capacity space in the vector // void HtVector::Allocate(int capacity) { if (capacity > allocated) // Darn, we actually have to do work :-) { Object **old_data = data; // Ensure we have more than the capacity and we aren't // always rebuilding the vector (which leads to quadratic behavior) while (allocated < capacity) allocated *= 2; data = new Object *[allocated]; for (int i = 0; i < element_count; i++) data[i] = old_data[i]; delete [] old_data; } }
