| //##################################################################### |
| // Copyright 2002-2004, Robert Bridson, Ronald Fedkiw, Geoffrey Irving, Neil Molino, Joseph Teran. |
| // This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt. |
| //##################################################################### |
| // Class HASHTABLE_2D |
| //##################################################################### |
| // |
| // The data stored in the table should be lightweight, e.g. integers or pointers, since it could be copied a fair bit. |
| // |
| //##################################################################### |
| #ifndef __HASHTABLE_2D__ |
| #define __HASHTABLE_2D__ |
| |
| #include "../Math_Tools/hash_function.h" |
| #include "../Arrays/ARRAY.h" |
| #include "../Arrays/ARRAYS.h" |
| #include "../Matrices_And_Vectors/VECTOR_2D.h" |
| namespace PhysBAM |
| { |
| |
| template<class T> |
| class HASHTABLE_2D |
| { |
| public: |
| ARRAY<int>* table_of_lists; // points to the first element in each list |
| ARRAY<int>* links; // links together each element in a list |
| ARRAYS<int>* indices; // (i,j) |
| ARRAY<T>* data; |
| int free_list; // points to the first allocated free space available |
| int number_of_entries; |
| |
| HASHTABLE_2D (const int estimated_max_number_of_entries = 1000) |
| { |
| Initialize_New_Table (estimated_max_number_of_entries); |
| } |
| |
| ~HASHTABLE_2D() |
| { |
| delete table_of_lists; |
| delete indices; |
| delete links; |
| delete data; |
| } |
| |
| void Initialize_New_Table (const int estimated_max_number_of_entries_input) |
| { |
| int estimated_max_number_of_entries = max (5, estimated_max_number_of_entries_input); |
| int number_of_lists = 1; |
| |
| while (number_of_lists < max (32, estimated_max_number_of_entries / 5)) number_of_lists *= 2; |
| |
| table_of_lists = new ARRAY<int> (number_of_lists); |
| indices = new ARRAYS<int> (2, estimated_max_number_of_entries); |
| links = new ARRAY<int> (estimated_max_number_of_entries); |
| |
| for (int i = 1; i <= links->m - 1; i++) (*links) (i) = i + 1; // originally the free space is linked together and (*links)(links->m)=0 |
| |
| data = new ARRAY<T> (estimated_max_number_of_entries); |
| free_list = 1; |
| number_of_entries = 0; |
| } |
| |
| void Resize_Table (const int estimated_max_number_of_entries_input = 0) |
| { |
| int estimated_max_number_of_entries = estimated_max_number_of_entries_input; |
| |
| if (!estimated_max_number_of_entries) estimated_max_number_of_entries = 3 * number_of_entries / 2; |
| |
| ARRAY<int> *old_table_of_lists = table_of_lists, *old_links = links; |
| ARRAYS<int> *old_indices = indices; |
| ARRAY<T> *old_data = data; |
| Initialize_New_Table (estimated_max_number_of_entries); |
| |
| for (int h = 1; h <= old_table_of_lists->m; h++) for (int p = (*old_table_of_lists) (h); p != 0; p = (*old_links) (p)) Insert_Entry ( (*old_indices) (1, p), (*old_indices) (2, p), (*old_data) (p)); |
| |
| delete old_table_of_lists; |
| delete old_indices; |
| delete old_links; |
| delete old_data; |
| } |
| |
| int Hash (const int i, const int j) const |
| { |
| int h = triple_int_hash (32138912, i, j) % table_of_lists->m; |
| |
| if (h <= 0) h += table_of_lists->m; |
| |
| return h; |
| } |
| |
| void Insert_Entry (const int i, const int j, const T& value) // may insert a duplicate entry for i,j |
| { |
| if (free_list == 0) Resize_Table(); // if no free spots, have to grow |
| |
| int new_entry = free_list; |
| free_list = (*links) (free_list); // put data into the first free spot |
| number_of_entries++; |
| (*indices) (1, new_entry) = i; |
| (*indices) (2, new_entry) = j; |
| (*data) (new_entry) = value; |
| int h = Hash (i, j); |
| (*links) (new_entry) = (*table_of_lists) (h); |
| (*table_of_lists) (h) = new_entry; |
| } // insert new entry at the beginning of the list |
| |
| void Insert_Entry (const VECTOR_2D<int>& v, const T& value) |
| { |
| Insert_Entry (v.x, v.y, value); |
| } |
| |
| bool Entry_Exists (const int i, const int j) const |
| { |
| for (int p = (*table_of_lists) (Hash (i, j)); p != 0; p = (*links) (p)) if ( (*indices) (1, p) == i && (*indices) (2, p) == j) return true; |
| |
| return false; |
| } |
| |
| bool Get_Entry (const int i, const int j, T& value) const |
| { |
| for (int p = (*table_of_lists) (Hash (i, j)); p != 0; p = (*links) (p)) if ( (*indices) (1, p) == i && (*indices) (2, p) == j) |
| { |
| value = (*data) (p); |
| return true; |
| } |
| |
| return false; |
| } |
| |
| bool Get_Entry (const VECTOR_2D<int>& v, T& value) const |
| { |
| return Get_Entry (v.x, v.y, value); |
| } |
| |
| bool Change_Entry (const int i, const int j, const T& value) // if (i,j) already exists, sets its value |
| { |
| for (int p = (*table_of_lists) (Hash (i, j)); p != 0; p = (*links) (p)) if ( (*indices) (1, p) == i && (*indices) (2, p) == j) |
| { |
| (*data) (p) = value; |
| return true; |
| } |
| |
| return false; |
| } |
| |
| void Delete_Entry (const int i, const int j) |
| { |
| for (int *p = & (*table_of_lists) (Hash (i, j)); (*p) != 0; p = & (*links) (*p)) if ( (*indices) (1, *p) == i && (*indices) (2, *p) == j) |
| { |
| int doomed_entry = *p; |
| *p = (*links) (doomed_entry); // delete it from the list |
| (*links) (doomed_entry) = free_list; |
| free_list = doomed_entry; // prepend to the beginning of the free space list |
| number_of_entries--; |
| return; |
| } |
| } |
| |
| void Delete_All_Entries() // doesn't update indices or data |
| { |
| ARRAY<int>::copy (0, *table_of_lists); |
| (*links) (links->m) = 0; |
| |
| for (int i = 1; i <= links->m - 1; i++) (*links) (i) = i + 1; |
| |
| free_list = 1; |
| number_of_entries = 0; |
| } |
| |
| void Print_All_Keys() |
| { |
| for (int h = 1; h <= table_of_lists->m; h++) for (int p = (*table_of_lists) (h); p != 0; p = (*links) (p)) std::cout << (*indices) (1, p) << "," << (*indices) (2, p) << "," << std::endl; |
| } |
| |
| void Apply_Function_To_All_Entries (void (*function) (int, int, T&)) |
| { |
| for (int h = 1; h <= table_of_lists->m; h++) for (int p = (*table_of_lists) (h); p != 0; p = (*links) (p)) function ( (*indices) (1, p), (*indices) (2, p), (*data) (p)); |
| } |
| |
| void Delete_Pointers_Stored_In_Table() // of course, only valid if pointers are stored in table |
| { |
| for (int h = 1; h <= table_of_lists->m; h++) for (int p = (*table_of_lists) (h); p != 0; p = (*links) (p)) |
| { |
| delete (*data) (p); |
| (*data) (p) = 0; |
| } |
| } |
| |
| void Reset_List_Arrays_Stored_In_Table() // of course, only works if pointers to LIST_ARRAY are stored in table |
| { |
| for (int h = 1; h <= table_of_lists->m; h++) for (int p = (*table_of_lists) (h); p != 0; p = (*links) (p)) (*data) (p)->Reset_Current_Size_To_Zero(); |
| } |
| |
| //##################################################################### |
| }; |
| } |
| #endif |