== SoC Bullet - Bullet Upgrade to 2.76 ==
[blender.git] / extern / bullet2 / BulletCollision / Gimpact / gim_hash_table.h
1 #ifndef GIM_HASH_TABLE_H_INCLUDED
2 #define GIM_HASH_TABLE_H_INCLUDED
3 /*! \file gim_trimesh_data.h
4 \author Francisco Le\7fn N├čjera
5 */
6 /*
7 -----------------------------------------------------------------------------
8 This source file is part of GIMPACT Library.
9
10 For the latest info, see http://gimpact.sourceforge.net/
11
12 Copyright (c) 2006 Francisco Leon Najera. C.C. 80087371.
13 email: projectileman@yahoo.com
14
15  This library is free software; you can redistribute it and/or
16  modify it under the terms of EITHER:
17    (1) The GNU Lesser General Public License as published by the Free
18        Software Foundation; either version 2.1 of the License, or (at
19        your option) any later version. The text of the GNU Lesser
20        General Public License is included with this library in the
21        file GIMPACT-LICENSE-LGPL.TXT.
22    (2) The BSD-style license that is included with this library in
23        the file GIMPACT-LICENSE-BSD.TXT.
24    (3) The zlib/libpng license that is included with this library in
25        the file GIMPACT-LICENSE-ZLIB.TXT.
26
27  This library is distributed in the hope that it will be useful,
28  but WITHOUT ANY WARRANTY; without even the implied warranty of
29  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files
30  GIMPACT-LICENSE-LGPL.TXT, GIMPACT-LICENSE-ZLIB.TXT and GIMPACT-LICENSE-BSD.TXT for more details.
31
32 -----------------------------------------------------------------------------
33 */
34
35 #include "gim_radixsort.h"
36
37
38 #define GIM_INVALID_HASH 0xffffffff //!< A very very high value
39 #define GIM_DEFAULT_HASH_TABLE_SIZE 380
40 #define GIM_DEFAULT_HASH_TABLE_NODE_SIZE 4
41 #define GIM_HASH_TABLE_GROW_FACTOR 2
42
43 #define GIM_MIN_RADIX_SORT_SIZE 860 //!< calibrated on a PIII
44
45 template<typename T>
46 struct GIM_HASH_TABLE_NODE
47 {
48     GUINT m_key;
49     T m_data;
50     GIM_HASH_TABLE_NODE()
51     {
52     }
53
54     GIM_HASH_TABLE_NODE(const GIM_HASH_TABLE_NODE & value)
55     {
56         m_key = value.m_key;
57         m_data = value.m_data;
58     }
59
60     GIM_HASH_TABLE_NODE(GUINT key, const T & data)
61     {
62         m_key = key;
63         m_data = data;
64     }
65
66     bool operator <(const GIM_HASH_TABLE_NODE<T> & other) const
67         {
68                 ///inverse order, further objects are first
69                 if(m_key <  other.m_key) return true;
70                 return false;
71         }
72
73         bool operator >(const GIM_HASH_TABLE_NODE<T> & other) const
74         {
75                 ///inverse order, further objects are first
76                 if(m_key >  other.m_key) return true;
77                 return false;
78         }
79
80         bool operator ==(const GIM_HASH_TABLE_NODE<T> & other) const
81         {
82                 ///inverse order, further objects are first
83                 if(m_key ==  other.m_key) return true;
84                 return false;
85         }
86 };
87
88 ///Macro for getting the key
89 class GIM_HASH_NODE_GET_KEY
90 {
91 public:
92         template<class T>
93         inline GUINT operator()( const T& a)
94         {
95                 return a.m_key;
96         }
97 };
98
99
100
101 ///Macro for comparing the key and the element
102 class GIM_HASH_NODE_CMP_KEY_MACRO
103 {
104 public:
105         template<class T>
106         inline int operator() ( const T& a, GUINT key)
107         {
108                 return ((int)(a.m_key - key));
109         }
110 };
111
112 ///Macro for comparing Hash nodes
113 class GIM_HASH_NODE_CMP_MACRO
114 {
115 public:
116         template<class T>
117         inline int operator() ( const T& a, const T& b )
118         {
119                 return ((int)(a.m_key - b.m_key));
120         }
121 };
122
123
124
125
126
127 //! Sorting for hash table
128 /*!
129 switch automatically between quicksort and radixsort
130 */
131 template<typename T>
132 void gim_sort_hash_node_array(T * array, GUINT array_count)
133 {
134     if(array_count<GIM_MIN_RADIX_SORT_SIZE)
135     {
136         gim_heap_sort(array,array_count,GIM_HASH_NODE_CMP_MACRO());
137     }
138     else
139     {
140         memcopy_elements_func cmpfunc;
141         gim_radix_sort(array,array_count,GIM_HASH_NODE_GET_KEY(),cmpfunc);
142     }
143 }
144
145
146
147
148
149
150 // Note: assumes long is at least 32 bits.
151 #define GIM_NUM_PRIME 28
152
153 static const GUINT gim_prime_list[GIM_NUM_PRIME] =
154 {
155   53ul,         97ul,         193ul,       389ul,       769ul,
156   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
157   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
158   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
159   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
160   1610612741ul, 3221225473ul, 4294967291ul
161 };
162
163 inline GUINT gim_next_prime(GUINT number)
164 {
165     //Find nearest upper prime
166     GUINT result_ind = 0;
167     gim_binary_search(gim_prime_list,0,(GIM_NUM_PRIME-2),number,result_ind);
168
169     // inv: result_ind < 28
170     return gim_prime_list[result_ind];
171 }
172
173
174
175 //! A compact hash table implementation
176 /*!
177 A memory aligned compact hash table that coud be treated as an array.
178 It could be a simple sorted array without the overhead of the hash key bucked, or could
179 be a formely hash table with an array of keys.
180 You can use switch_to_hashtable() and switch_to_sorted_array for saving space or increase speed.
181 </br>
182
183 <ul>
184 <li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes.
185 When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable.
186 <li> If node_size != 0, then this container becomes a hash table for ever
187 </ul>
188
189 */
190 template<class T>
191 class gim_hash_table
192 {
193 protected:
194     typedef GIM_HASH_TABLE_NODE<T> _node_type;
195
196     //!The nodes
197     //array< _node_type, SuperAllocator<_node_type> > m_nodes;
198     gim_array< _node_type > m_nodes;
199     //SuperBufferedArray< _node_type > m_nodes;
200     bool m_sorted;
201
202     ///Hash table data management. The hash table has the indices to the corresponding m_nodes array
203     GUINT * m_hash_table;//!<
204     GUINT m_table_size;//!<
205     GUINT m_node_size;//!<
206     GUINT m_min_hash_table_size;
207
208
209
210     //! Returns the cell index
211     inline GUINT _find_cell(GUINT hashkey)
212     {
213         _node_type * nodesptr = m_nodes.pointer();
214         GUINT start_index = (hashkey%m_table_size)*m_node_size;
215         GUINT end_index = start_index + m_node_size;
216
217         while(start_index<end_index)
218         {
219             GUINT value = m_hash_table[start_index];
220             if(value != GIM_INVALID_HASH)
221             {
222                 if(nodesptr[value].m_key == hashkey) return start_index;
223             }
224             start_index++;
225         }
226         return GIM_INVALID_HASH;
227     }
228
229     //! Find the avaliable cell for the hashkey, and return an existing cell if it has the same hash key
230     inline GUINT _find_avaliable_cell(GUINT hashkey)
231     {
232         _node_type * nodesptr = m_nodes.pointer();
233         GUINT avaliable_index = GIM_INVALID_HASH;
234         GUINT start_index = (hashkey%m_table_size)*m_node_size;
235         GUINT end_index = start_index + m_node_size;
236
237         while(start_index<end_index)
238         {
239             GUINT value = m_hash_table[start_index];
240             if(value == GIM_INVALID_HASH)
241             {
242                 if(avaliable_index==GIM_INVALID_HASH)
243                 {
244                     avaliable_index = start_index;
245                 }
246             }
247             else if(nodesptr[value].m_key == hashkey)
248             {
249                 return start_index;
250             }
251             start_index++;
252         }
253         return avaliable_index;
254     }
255
256
257
258     //! reserves the memory for the hash table.
259     /*!
260     \pre hash table must be empty
261     \post reserves the memory for the hash table, an initializes all elements to GIM_INVALID_HASH.
262     */
263     inline void _reserve_table_memory(GUINT newtablesize)
264     {
265         if(newtablesize==0) return;
266         if(m_node_size==0) return;
267
268         //Get a Prime size
269
270         m_table_size = gim_next_prime(newtablesize);
271
272         GUINT datasize = m_table_size*m_node_size;
273         //Alloc the data buffer
274         m_hash_table =  (GUINT *)gim_alloc(datasize*sizeof(GUINT));
275     }
276
277     inline void _invalidate_keys()
278     {
279         GUINT datasize = m_table_size*m_node_size;
280         for(GUINT i=0;i<datasize;i++)
281         {
282             m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys
283         }
284     }
285
286     //! Clear all memory for the hash table
287     inline void _clear_table_memory()
288     {
289         if(m_hash_table==NULL) return;
290         gim_free(m_hash_table);
291         m_hash_table = NULL;
292         m_table_size = 0;
293     }
294
295     //! Invalidates the keys (Assigning GIM_INVALID_HASH to all) Reorders the hash keys
296     inline void _rehash()
297     {
298         _invalidate_keys();
299
300         _node_type * nodesptr = m_nodes.pointer();
301         for(GUINT i=0;i<(GUINT)m_nodes.size();i++)
302         {
303             GUINT nodekey = nodesptr[i].m_key;
304             if(nodekey != GIM_INVALID_HASH)
305             {
306                 //Search for the avaliable cell in buffer
307                 GUINT index = _find_avaliable_cell(nodekey);
308
309
310                                 if(m_hash_table[index]!=GIM_INVALID_HASH)
311                                 {//The new index is alreade used... discard this new incomming object, repeated key
312                                     btAssert(m_hash_table[index]==nodekey);
313                                         nodesptr[i].m_key = GIM_INVALID_HASH;
314                                 }
315                                 else
316                                 {
317                                         //;
318                                         //Assign the value for alloc
319                                         m_hash_table[index] = i;
320                                 }
321             }
322         }
323     }
324
325     //! Resize hash table indices
326     inline void _resize_table(GUINT newsize)
327     {
328         //Clear memory
329         _clear_table_memory();
330         //Alloc the data
331         _reserve_table_memory(newsize);
332         //Invalidate keys and rehash
333         _rehash();
334     }
335
336     //! Destroy hash table memory
337     inline void _destroy()
338     {
339         if(m_hash_table==NULL) return;
340         _clear_table_memory();
341     }
342
343     //! Finds an avaliable hash table cell, and resizes the table if there isn't space
344     inline GUINT _assign_hash_table_cell(GUINT hashkey)
345     {
346         GUINT cell_index = _find_avaliable_cell(hashkey);
347
348         if(cell_index==GIM_INVALID_HASH)
349         {
350             //rehashing
351             _resize_table(m_table_size+1);
352             GUINT cell_index = _find_avaliable_cell(hashkey);
353             btAssert(cell_index!=GIM_INVALID_HASH);
354         }
355         return cell_index;
356     }
357
358     //! erase by index in hash table
359     inline bool _erase_by_index_hash_table(GUINT index)
360     {
361         if(index >= m_nodes.size()) return false;
362         if(m_nodes[index].m_key != GIM_INVALID_HASH)
363         {
364             //Search for the avaliable cell in buffer
365             GUINT cell_index = _find_cell(m_nodes[index].m_key);
366
367             btAssert(cell_index!=GIM_INVALID_HASH);
368             btAssert(m_hash_table[cell_index]==index);
369
370             m_hash_table[cell_index] = GIM_INVALID_HASH;
371         }
372
373         return this->_erase_unsorted(index);
374     }
375
376     //! erase by key in hash table
377     inline bool _erase_hash_table(GUINT hashkey)
378     {
379         if(hashkey == GIM_INVALID_HASH) return false;
380
381         //Search for the avaliable cell in buffer
382         GUINT cell_index = _find_cell(hashkey);
383         if(cell_index ==GIM_INVALID_HASH) return false;
384
385         GUINT index = m_hash_table[cell_index];
386         m_hash_table[cell_index] = GIM_INVALID_HASH;
387
388         return this->_erase_unsorted(index);
389     }
390
391
392
393     //! insert an element in hash table
394     /*!
395     If the element exists, this won't insert the element
396     \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted
397     If so, the element has been inserted at the last position of the array.
398     */
399     inline GUINT _insert_hash_table(GUINT hashkey, const T & value)
400     {
401         if(hashkey==GIM_INVALID_HASH)
402         {
403             //Insert anyway
404             _insert_unsorted(hashkey,value);
405             return GIM_INVALID_HASH;
406         }
407
408         GUINT cell_index = _assign_hash_table_cell(hashkey);
409
410         GUINT value_key = m_hash_table[cell_index];
411
412         if(value_key!= GIM_INVALID_HASH) return value_key;// Not overrited
413
414         m_hash_table[cell_index] = m_nodes.size();
415
416         _insert_unsorted(hashkey,value);
417         return GIM_INVALID_HASH;
418     }
419
420     //! insert an element in hash table.
421     /*!
422     If the element exists, this replaces the element.
423     \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted
424     If so, the element has been inserted at the last position of the array.
425     */
426     inline GUINT _insert_hash_table_replace(GUINT hashkey, const T & value)
427     {
428         if(hashkey==GIM_INVALID_HASH)
429         {
430             //Insert anyway
431             _insert_unsorted(hashkey,value);
432             return GIM_INVALID_HASH;
433         }
434
435         GUINT cell_index = _assign_hash_table_cell(hashkey);
436
437         GUINT value_key = m_hash_table[cell_index];
438
439         if(value_key!= GIM_INVALID_HASH)
440         {//replaces the existing
441             m_nodes[value_key] = _node_type(hashkey,value);
442             return value_key;// index of the replaced element
443         }
444
445         m_hash_table[cell_index] = m_nodes.size();
446
447         _insert_unsorted(hashkey,value);
448         return GIM_INVALID_HASH;
449
450     }
451
452     
453     ///Sorted array data management. The hash table has the indices to the corresponding m_nodes array
454     inline bool _erase_sorted(GUINT index)
455     {
456         if(index>=(GUINT)m_nodes.size()) return false;
457         m_nodes.erase_sorted(index);
458                 if(m_nodes.size()<2) m_sorted = false;
459         return true;
460     }
461
462     //! faster, but unsorted
463     inline bool _erase_unsorted(GUINT index)
464     {
465         if(index>=m_nodes.size()) return false;
466
467         GUINT lastindex = m_nodes.size()-1;
468         if(index<lastindex && m_hash_table!=0)
469         {
470                         GUINT hashkey =  m_nodes[lastindex].m_key;
471                         if(hashkey!=GIM_INVALID_HASH)
472                         {
473                                 //update the new position of the last element
474                                 GUINT cell_index = _find_cell(hashkey);
475                                 btAssert(cell_index!=GIM_INVALID_HASH);
476                                 //new position of the last element which will be swaped
477                                 m_hash_table[cell_index] = index;
478                         }
479         }
480         m_nodes.erase(index);
481         m_sorted = false;
482         return true;
483     }
484
485     //! Insert in position ordered
486     /*!
487     Also checks if it is needed to transform this container to a hash table, by calling check_for_switching_to_hashtable
488     */
489     inline void _insert_in_pos(GUINT hashkey, const T & value, GUINT pos)
490     {
491         m_nodes.insert(_node_type(hashkey,value),pos);
492         this->check_for_switching_to_hashtable();
493     }
494
495     //! Insert an element in an ordered array
496     inline GUINT _insert_sorted(GUINT hashkey, const T & value)
497     {
498         if(hashkey==GIM_INVALID_HASH || size()==0)
499         {
500             m_nodes.push_back(_node_type(hashkey,value));
501             return GIM_INVALID_HASH;
502         }
503         //Insert at last position
504         //Sort element
505
506
507         GUINT result_ind=0;
508         GUINT last_index = m_nodes.size()-1;
509         _node_type * ptr = m_nodes.pointer();
510
511         bool found = gim_binary_search_ex(
512                 ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO());
513
514
515         //Insert before found index
516         if(found)
517         {
518             return result_ind;
519         }
520         else
521         {
522             _insert_in_pos(hashkey, value, result_ind);
523         }
524         return GIM_INVALID_HASH;
525     }
526
527     inline GUINT _insert_sorted_replace(GUINT hashkey, const T & value)
528     {
529         if(hashkey==GIM_INVALID_HASH || size()==0)
530         {
531             m_nodes.push_back(_node_type(hashkey,value));
532             return GIM_INVALID_HASH;
533         }
534         //Insert at last position
535         //Sort element
536         GUINT result_ind;
537         GUINT last_index = m_nodes.size()-1;
538         _node_type * ptr = m_nodes.pointer();
539
540         bool found = gim_binary_search_ex(
541                 ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO());
542
543         //Insert before found index
544         if(found)
545         {
546             m_nodes[result_ind] = _node_type(hashkey,value);
547         }
548         else
549         {
550             _insert_in_pos(hashkey, value, result_ind);
551         }
552         return result_ind;
553     }
554
555     //! Fast insertion in m_nodes array
556     inline GUINT  _insert_unsorted(GUINT hashkey, const T & value)
557     {
558         m_nodes.push_back(_node_type(hashkey,value));
559         m_sorted = false;
560         return GIM_INVALID_HASH;
561     }
562
563     
564
565 public:
566
567     /*!
568         <li> if node_size = 0, then this container becomes a simple sorted array allocator. reserve_size is used for reserve memory in m_nodes.
569         When the array size reaches the size equivalent to 'min_hash_table_size', then it becomes a hash table by calling check_for_switching_to_hashtable.
570         <li> If node_size != 0, then this container becomes a hash table for ever
571         </ul>
572     */
573     gim_hash_table(GUINT reserve_size = GIM_DEFAULT_HASH_TABLE_SIZE,
574                      GUINT node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE,
575                      GUINT min_hash_table_size = GIM_INVALID_HASH)
576     {
577         m_hash_table = NULL;
578         m_table_size = 0;
579         m_sorted = false;
580         m_node_size = node_size;
581         m_min_hash_table_size = min_hash_table_size;
582
583         if(m_node_size!=0)
584         {
585             if(reserve_size!=0)
586             {
587                 m_nodes.reserve(reserve_size);
588                 _reserve_table_memory(reserve_size);
589                 _invalidate_keys();
590             }
591             else
592             {
593                 m_nodes.reserve(GIM_DEFAULT_HASH_TABLE_SIZE);
594                 _reserve_table_memory(GIM_DEFAULT_HASH_TABLE_SIZE);
595                 _invalidate_keys();
596             }
597         }
598         else if(reserve_size!=0)
599         {
600             m_nodes.reserve(reserve_size);
601         }
602
603     }
604
605     ~gim_hash_table()
606     {
607         _destroy();
608     }
609
610     inline bool is_hash_table()
611     {
612         if(m_hash_table) return true;
613         return false;
614     }
615
616     inline bool is_sorted()
617     {
618         if(size()<2) return true;
619         return m_sorted;
620     }
621
622     bool sort()
623     {
624         if(is_sorted()) return true;
625         if(m_nodes.size()<2) return false;
626
627
628         _node_type * ptr = m_nodes.pointer();
629         GUINT siz = m_nodes.size();
630         gim_sort_hash_node_array(ptr,siz);
631         m_sorted=true;
632
633
634
635         if(m_hash_table)
636         {
637             _rehash();
638         }
639         return true;
640     }
641
642     bool switch_to_hashtable()
643     {
644         if(m_hash_table) return false;
645         if(m_node_size==0) m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
646         if(m_nodes.size()<GIM_DEFAULT_HASH_TABLE_SIZE)
647         {
648             _resize_table(GIM_DEFAULT_HASH_TABLE_SIZE);
649         }
650         else
651         {
652             _resize_table(m_nodes.size()+1);
653         }
654
655         return true;
656     }
657
658     bool switch_to_sorted_array()
659     {
660         if(m_hash_table==NULL) return true;
661         _clear_table_memory();
662         return sort();
663     }
664
665     //!If the container reaches the
666     bool check_for_switching_to_hashtable()
667     {
668         if(this->m_hash_table) return true;
669
670         if(!(m_nodes.size()< m_min_hash_table_size))
671         {
672             if(m_node_size == 0)
673             {
674                 m_node_size = GIM_DEFAULT_HASH_TABLE_NODE_SIZE;
675             }
676
677             _resize_table(m_nodes.size()+1);
678             return true;
679         }
680         return false;
681     }
682
683     inline void set_sorted(bool value)
684     {
685         m_sorted = value;
686     }
687
688     //! Retrieves the amount of keys.
689     inline GUINT size() const
690     {
691         return m_nodes.size();
692     }
693
694     //! Retrieves the hash key.
695     inline GUINT get_key(GUINT index) const
696     {
697         return m_nodes[index].m_key;
698     }
699
700     //! Retrieves the value by index
701     /*!
702     */
703     inline T * get_value_by_index(GUINT index)
704     {
705         return &m_nodes[index].m_data;
706     }
707
708     inline const T& operator[](GUINT index) const
709     {
710         return m_nodes[index].m_data;
711     }
712
713     inline T& operator[](GUINT index)
714     {
715         return m_nodes[index].m_data;
716     }
717
718     //! Finds the index of the element with the key
719     /*!
720     \return the index in the array of the existing element,or GIM_INVALID_HASH if the element has been inserted
721     If so, the element has been inserted at the last position of the array.
722     */
723     inline GUINT find(GUINT hashkey)
724     {
725         if(m_hash_table)
726         {
727             GUINT cell_index = _find_cell(hashkey);
728             if(cell_index==GIM_INVALID_HASH) return GIM_INVALID_HASH;
729             return m_hash_table[cell_index];
730         }
731                 GUINT last_index = m_nodes.size();
732         if(last_index<2)
733         {
734                         if(last_index==0) return GIM_INVALID_HASH;
735             if(m_nodes[0].m_key == hashkey) return 0;
736             return GIM_INVALID_HASH;
737         }
738         else if(m_sorted)
739         {
740             //Binary search
741             GUINT result_ind = 0;
742                         last_index--;
743             _node_type *  ptr =  m_nodes.pointer();
744
745             bool found = gim_binary_search_ex(ptr,0,last_index,result_ind,hashkey,GIM_HASH_NODE_CMP_KEY_MACRO());
746
747
748             if(found) return result_ind;
749         }
750         return GIM_INVALID_HASH;
751     }
752
753     //! Retrieves the value associated with the index
754     /*!
755     \return the found element, or null
756     */
757     inline T * get_value(GUINT hashkey)
758     {
759         GUINT index = find(hashkey);
760         if(index == GIM_INVALID_HASH) return NULL;
761         return &m_nodes[index].m_data;
762     }
763
764
765     /*!
766     */
767     inline bool erase_by_index(GUINT index)
768     {
769         if(index > m_nodes.size()) return false;
770
771         if(m_hash_table == NULL)
772         {
773             if(is_sorted())
774             {
775                 return this->_erase_sorted(index);
776             }
777             else
778             {
779                 return this->_erase_unsorted(index);
780             }
781         }
782         else
783         {
784             return this->_erase_by_index_hash_table(index);
785         }
786         return false;
787     }
788
789
790
791     inline bool erase_by_index_unsorted(GUINT index)
792     {
793         if(index > m_nodes.size()) return false;
794
795         if(m_hash_table == NULL)
796         {
797             return this->_erase_unsorted(index);
798         }
799         else
800         {
801             return this->_erase_by_index_hash_table(index);
802         }
803         return false;
804     }
805
806
807
808     /*!
809
810     */
811     inline bool erase_by_key(GUINT hashkey)
812     {
813         if(size()==0) return false;
814
815         if(m_hash_table)
816         {
817             return this->_erase_hash_table(hashkey);
818         }
819         //Binary search
820
821         if(is_sorted()==false) return false;
822
823         GUINT result_ind = find(hashkey);
824         if(result_ind!= GIM_INVALID_HASH)
825         {
826             return this->_erase_sorted(result_ind);
827         }
828         return false;
829     }
830
831     void clear()
832     {
833         m_nodes.clear();
834
835         if(m_hash_table==NULL) return;
836         GUINT datasize = m_table_size*m_node_size;
837         //Initialize the hashkeys.
838         GUINT i;
839         for(i=0;i<datasize;i++)
840         {
841             m_hash_table[i] = GIM_INVALID_HASH;// invalidate keys
842         }
843                 m_sorted = false;
844     }
845
846     //! Insert an element into the hash
847     /*!
848     \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position
849     of the existing element.
850     */
851     inline GUINT insert(GUINT hashkey, const T & element)
852     {
853         if(m_hash_table)
854         {
855             return this->_insert_hash_table(hashkey,element);
856         }
857         if(this->is_sorted())
858         {
859             return this->_insert_sorted(hashkey,element);
860         }
861         return this->_insert_unsorted(hashkey,element);
862     }
863
864     //! Insert an element into the hash, and could overrite an existing object with the same hash.
865     /*!
866     \return If GIM_INVALID_HASH, the object has been inserted succesfully. Else it returns the position
867     of the replaced element.
868     */
869     inline GUINT insert_override(GUINT hashkey, const T & element)
870     {
871         if(m_hash_table)
872         {
873             return this->_insert_hash_table_replace(hashkey,element);
874         }
875         if(this->is_sorted())
876         {
877             return this->_insert_sorted_replace(hashkey,element);
878         }
879         this->_insert_unsorted(hashkey,element);
880         return m_nodes.size();
881     }
882
883
884
885     //! Insert an element into the hash,But if this container is a sorted array, this inserts it unsorted
886     /*!
887     */
888     inline GUINT insert_unsorted(GUINT hashkey,const T & element)
889     {
890         if(m_hash_table)
891         {
892             return this->_insert_hash_table(hashkey,element);
893         }
894         return this->_insert_unsorted(hashkey,element);
895     }
896
897
898 };
899
900
901
902 #endif // GIM_CONTAINERS_H_INCLUDED