VectorCo.h

Go to the documentation of this file.

//

#include <AfxTempl.h>

class HashNode 
{
public:
   HashNode *m_next;
   int       m_id;
   LONG      m_key;
};

class VectorCollection 
{
private:
   CArray<HashNode *, HashNode *> m_hasharray;

   int GetHashKey(LONG key);
   int GetHashKey(const Vector &vector);
public:
   CArray<Vector, Vector &> m_array;

   VectorCollection() {
      m_array.SetGranularity(1000);
      m_hasharray.SetSize(1999);
   }   
   
   virtual ~VectorCollection();
   
   int GetSize() const { return m_array.GetSize(); }
   void SetSize( int newsize, int growby = -1 ) { m_array.SetSize(newsize, growby); } 
   int Add(Vector &vector, LONG key=-1);
   int LookUp(const Vector &vector, LONG key=-1);
   int LookUpHashKey(Vector &vector);
   void Empty();

   void Shrink() {
      m_array.FreeExtra();
   }

   Vector *GetArray() { return m_array.GetArray(); }
   Vector  GetAt(int index) const { return m_array.GetAt(index); }
   Vector &ElementAt(int index) { return m_array.ElementAt(index); }
   Vector  operator [] ( int index ) const { return m_array.GetAt(index); }
   Vector &operator [](int index) { return m_array.ElementAt(index); }

};

inline void VectorCollection::Empty()
{
   int i, count = m_hasharray.GetSize();
   for (i=0; i < count; i++) {
      HashNode *nodehead = m_hasharray[i];
      if (nodehead) {
         HashNode *next;
         for (HashNode *node = nodehead; node; node=next) {
            next = node->m_next;
            delete node;
         }
         m_hasharray[i] = NULL;
      }
   }
   m_array.SetSize(0);
}

inline VectorCollection::~VectorCollection()
{
   Empty();
}

inline int VectorCollection::GetHashKey(LONG key)
{
   return ((int)(void*)(LONG)key) >> 4;
}

inline int VectorCollection::GetHashKey(const Vector &vector)
{
   double x = (int)(vector.x * 1000.0f + SIGN(vector.x) * .5f)/1000.0*12.3;
   double y = (int)(vector.y * 1000.0f + SIGN(vector.y) * .5f)/1000.0*23.4;
   double z = (int)(vector.z * 1000.0f + SIGN(vector.z) * .5f)/1000.0*34.5;
   return (int) (pow(x*x + y*y + z*z, 0.5 ) * 9.87);  
}

inline int VectorCollection::LookUp(const Vector &vector, LONG key)
{
   int hashkey;
   if (key == -1)
      hashkey = GetHashKey(vector);
   else
      hashkey = GetHashKey(key);

   int index = hashkey%m_hasharray.GetSize();   
   HashNode *nodehead = m_hasharray.GetAt(index);
   for (HashNode *node = nodehead; node; node=node->m_next) {
      if (key != -1 && node->m_key != -1) {
         if (node->m_key == key)
            return node->m_id;
         continue;
      }
      const Vector &match = m_array.GetAt(node->m_id);
      Vector diff = match-vector;
      if (fabs(diff.x) < 1.e-3 &&
       fabs(diff.y) < 1.e-3 &&
       fabs(diff.z) < 1.e-3)
         return node->m_id;
   }
   return -1;
}

inline int VectorCollection::LookUpHashKey(Vector &vector)
{
   int i, count = m_hasharray.GetSize();
   for (i = 0; i < count; i++) {
      HashNode *nodehead = m_hasharray.GetAt(i);
      if (nodehead) {
         for (HashNode *node = nodehead; node; node=node->m_next) {
            const Vector &match = m_array.GetAt(node->m_id);
            Vector diff = match-vector;
            if (fabs(diff.x) < 1.e-3 &&
               fabs(diff.y) < 1.e-3 &&
               fabs(diff.z) < 1.e-3)
               return node->m_key;
         }
      }
   }
   return -1;
}

inline int VectorCollection::Add(Vector &vector, LONG key)
{
   int hashkey;
   if (key == -1)
      hashkey = GetHashKey(vector);
   else
      hashkey = GetHashKey(key);

   int index = hashkey%m_hasharray.GetSize();   
   HashNode *nodehead = m_hasharray.GetAt(index);
   for (HashNode *node = nodehead; node; node=node->m_next) {
      if (key != -1 && node->m_key != -1) {
         if (node->m_key == key)
            return node->m_id;
         continue;
      }
      const Vector &match = m_array.GetAt(node->m_id);
      Vector diff = match-vector;
      if (fabs(diff.x) < 1.e-3 &&
       fabs(diff.y) < 1.e-3 &&
       fabs(diff.z) < 1.e-3)
         return node->m_id;
   }
// doesn't exist yet
   int newid = m_array.Add(vector);
   HashNode *newnode = new HashNode;
   newnode->m_id = newid;
   newnode->m_key = key;
   newnode->m_next = nodehead;
   m_hasharray.SetAt(index, newnode);
   return newid;
}

---