Blender V2.61 - r43446

CTR_Map.h

Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN GPL LICENSE BLOCK *****
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License
00006  * as published by the Free Software Foundation; either version 2
00007  * of the License, or (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software Foundation,
00016  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00017  *
00018  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
00019  * All rights reserved.
00020  *
00021  * The Original Code is: all of this file.
00022  *
00023  * Contributor(s): none yet.
00024  *
00025  * ***** END GPL LICENSE BLOCK *****
00026  */
00027 
00033 #ifndef CTR_MAP_H
00034 #define CTR_MAP_H
00035 
00036 template <class Key, class Value>
00037 class CTR_Map {
00038 private:
00039     struct Entry {
00040         Entry (Entry *next, Key key, Value value) :
00041             m_next(next),
00042             m_key(key),
00043             m_value(value) {}
00044 
00045         Entry *m_next;
00046         Key    m_key;
00047         Value  m_value;
00048     };
00049 
00050 public:
00051     CTR_Map(int num_buckets = 100) : m_num_buckets(num_buckets) {
00052         m_buckets = new Entry *[num_buckets];
00053         for (int i = 0; i < num_buckets; ++i) {
00054             m_buckets[i] = 0;
00055         }
00056     }
00057 
00058     CTR_Map(const CTR_Map& map)
00059     {
00060         m_num_buckets = map.m_num_buckets;
00061         m_buckets = new Entry *[m_num_buckets];
00062 
00063         for (int i = 0; i < m_num_buckets; ++i) {
00064             m_buckets[i] = 0;
00065 
00066             for(Entry *entry = map.m_buckets[i]; entry; entry=entry->m_next)
00067                 insert(entry->m_key, entry->m_value);
00068         }
00069     }
00070 
00071     int size() {
00072         int count=0;
00073         for (int i=0;i<m_num_buckets;i++)
00074         {
00075             Entry* bucket = m_buckets[i];
00076             while(bucket)
00077             {
00078                 bucket = bucket->m_next;
00079                 count++;
00080             }
00081         }
00082         return count;
00083     }
00084 
00085     Value* at(int index) {
00086         int count=0;
00087         for (int i=0;i<m_num_buckets;i++)
00088         {
00089             Entry* bucket = m_buckets[i];
00090             while(bucket)
00091             {
00092                 if (count==index)
00093                 {
00094                     return &bucket->m_value;
00095                 }
00096                 bucket = bucket->m_next;
00097                 count++;
00098             }
00099         }
00100         return 0;
00101     }
00102 
00103     Key* getKey(int index) {
00104         int count=0;
00105         for (int i=0;i<m_num_buckets;i++)
00106         {
00107             Entry* bucket = m_buckets[i];
00108             while(bucket)
00109             {
00110                 if (count==index)
00111                 {
00112                     return &bucket->m_key;
00113                 }
00114                 bucket = bucket->m_next;
00115                 count++;
00116             }
00117         }
00118         return 0;
00119     }
00120 
00121     void clear() {
00122         for (int i = 0; i < m_num_buckets; ++i) {
00123             Entry *entry_ptr = m_buckets[i];
00124 
00125             while (entry_ptr != 0) {
00126                 Entry *tmp_ptr = entry_ptr->m_next;
00127                 delete entry_ptr;
00128                 entry_ptr = tmp_ptr;
00129             }
00130             m_buckets[i] = 0;
00131         }
00132     }
00133 
00134     ~CTR_Map() {
00135         clear();
00136         delete [] m_buckets;
00137     }
00138 
00139     void insert(const Key& key, const Value& value) {
00140         Entry *entry_ptr = m_buckets[key.hash() % m_num_buckets];
00141         while ((entry_ptr != 0) && !(key == entry_ptr->m_key)) {
00142             entry_ptr = entry_ptr->m_next;
00143         }
00144 
00145         if (entry_ptr != 0) {
00146             entry_ptr->m_value = value;
00147         }
00148         else {
00149             Entry **bucket = &m_buckets[key.hash() % m_num_buckets];
00150             *bucket = new Entry(*bucket, key, value);
00151         }
00152     }
00153 
00154     void remove(const Key& key) {
00155         Entry **entry_ptr = &m_buckets[key.hash() % m_num_buckets];
00156         while ((*entry_ptr != 0) && !(key == (*entry_ptr)->m_key)) {
00157             entry_ptr = &(*entry_ptr)->m_next;
00158         }
00159 
00160         if (*entry_ptr != 0) {
00161             Entry *tmp_ptr = (*entry_ptr)->m_next;
00162             delete *entry_ptr;
00163             *entry_ptr = tmp_ptr;
00164         }
00165     }
00166 
00167     Value *operator[](Key key) {
00168         Entry *bucket = m_buckets[key.hash() % m_num_buckets];
00169         while ((bucket != 0) && !(key == bucket->m_key)) {
00170             bucket = bucket->m_next;
00171         }
00172         return bucket != 0 ? &bucket->m_value : 0;
00173     }
00174 
00175 private:
00176     int     m_num_buckets;
00177     Entry **m_buckets;
00178 };
00179 
00180 #endif
00181