1 /////////////////////////////////////////////////////////////////////////////// 2 // Name: pairarr.h 3 // Purpose: Sorted Key/Value pairs of wxArrays using a binary search lookup 4 // Author: John Labenski 5 // Modified by: 6 // Created: 1/08/2004 7 // RCS-ID: $Id$ 8 // Copyright: (c) John Labenski 9 // Licence: wxWidgets licence 10 /////////////////////////////////////////////////////////////////////////////// 11 12 #ifndef __WX_PAIRARR_H__ 13 #define __WX_PAIRARR_H__ 14 15 // Note: there is no cpp file as all the code is contained in these macros. 16 17 #include "wx/dynarray.h" 18 19 // ============================================================================ 20 // Provides macros for creating your own (key, value) pair arrays using a binary 21 // search to insert/retrieve values using a key. While this doesn't have the 22 // performance of a good hash table O(n), it is smaller and with a lookup speed 23 // O(log(n)) is suitable for some applications. You can use virtually any 24 // class for keys and values that can be put into wxArrays so long as they 25 // define the standard comparison operators ==, <, >, <=, >=. 26 // 27 // Implementation note: I've chosen to use two independent arrays instead of 28 // a single array of a data struct with (key, value) members to squeeze out the 29 // slightest increase in performance. 30 // ---------------------------------------------------------------------------- 31 // DECLARE_PAIRED_DATA_ARRAYS(Tkey, TkeyArray, Tval, TvalArray, name, classexp) 32 // DEFINE_PAIRED_DATA_ARRAYS(Tkey, Tval, name) 33 // Tkey must have the operators =, ==, <, >, <=, >= 34 // They'll be sorted by using the <, >, <=, >= operators 35 // Tval must have a default constructor and be able to be passed as const Tval& val 36 // You must have created wx(Object)Arrays of Tkey with name TkeyArray 37 // and of Tval named TvalArray, for example wxArrayInt and wxArrayString 38 // 39 // Creates a class named "name" that manages the TkeyArray, TvalArray data. 40 // It keeps the pairs sorted in order of Tkey and uses a binary search 41 // to retrieve and set the values. 42 // 43 // ---------------------------------------------------------------------------- 44 // DECLARE_PAIRED_INT_DATA_ARRAYS(Tval, TvalArray, name, classexp) 45 // DEFINE_PAIRED_INT_DATA_ARRAYS(Tval, name) 46 // Tkey is an int (wxArrayInt), Tval may be anything 47 // UpdatePos(int pos, int num) is added for inserting if num > 0 and 48 // deleting if num < 0. The keys above pos are shifted. 49 // 50 // ---------------------------------------------------------------------------- 51 // name() - default constructor 52 // name(const Tval& defaultVal) - initialize the class with the default value, 53 // see Get/SetDefaultValue to change it later. 54 // name(const name& other) - full copy constructor 55 // name(Tkey key, const Tval& val) - create with the first pair 56 // int GetCount() - get the number of pairs 57 // int FindIndex(Tkey) - find this key returning position in pair array or wxNOT_FOUND 58 // size_t FindInsertIndex(Tkey) - find array position to insert key at, returns 59 // GetCount for append (check first in case count=0), the pos to insert 60 // before, or the pos with existing key (see SetValue for code) 61 // bool HasKey(Tkey) - does this key exist 62 // Tval& GetValue(Tkey) - get the value for this key or it it doesn't exist 63 // the default value, see also Get/SetDefaultValue. 64 // Tval& GetOrCreateValue(Tkey key) - get or create a GetDefaultValue() value for this key 65 // void SetValue(Tkey, Tval) - set the Tval for this Tkey, replacing if exists 66 // bool RemoveValue(Tkey) - remove pair with this Tkey, returns if it existed 67 // void Clear() - clears the pair arrays 68 // const Tval& GetItemValue(index) const - get the Tval at this array index 69 // const Tkey& GetItemKey(index) const - get the Tkey at this array index 70 // Tval& GetItemValue(index) - get the Tval at this array index 71 // Tkey& GetItemKey(index) - get the Tkey at this array index 72 // void RemoveAt(index) - remove the key and value at this array index 73 // TvalArray& GetValues() - get the TvalArray 74 // TkeyArray& GetKeys() - get the TkeyArray (don't unsort them) 75 // const Tval& GetDefaultValue() const - get the default value to return for 76 // GetValue(Tkey) when the key doesn't exist. (inits to Tval()) 77 // void SetDefaultValue(const Tval& val) - set the default value to return for 78 // GetValue(Tkey) when the key doesn't exist. If your values don't have a 79 // default constructor (eg. ints) you'll want to set this. 80 // void Copy(const name& other) - make full copy of other 81 // void Sort() - sort the pairs by the keys (only necessary if you want to 82 // quickly add unorderered pairs using GetKeys().Add(x); GetValues().Add(x);) 83 // You MUST keep them sorted for the lookup mechanism to work. 84 // name& operator=(const name& other) - make full copy of other 85 // 86 // ---------------------------------------------------------------------------- 87 // DECLARE_PAIRED_INT_DATA_ARRAYS - added functions 88 // bool UpdatePos(int pos, int numPos) - 89 // if numPos > 0 - shifts keys greater than pos by numPos 90 // if numPos < 0 - deletes keys between pos and pos-numPos, 91 // shifts keys greater than by pos-numPos by -numPos 92 // 93 // ============================================================================ 94 // Examples: 95 // 96 // 1.) For string arrays you'll write this in the header 97 // DECLARE_PAIRED_DATA_ARRAYS(wxString, wxArrayString, wxString, wxArrayString, 98 // wxPairArrayStringString, class WXDLLIMPEXP_ADV) 99 // And this code in some cpp file. 100 // DEFINE_PAIRED_DATA_ARRAYS(wxString, wxString, wxPairArrayStringString) 101 // 102 // 2.) For int pairs and wxString values, write this in your header 103 // DECLARE_PAIRED_INT_DATA_ARRAYS(wxString, wxArrayString, 104 // wxPairArrayIntSheetString, class WXDLLIMPEXP_ADV) 105 // 106 // You can even make nested pair arrays, 2D arrays (wxSheetStringSparseTable) 107 // WX_DECLARE_OBJARRAY_WITH_DECL(wxPairArrayIntSheetString, 108 // wxArrayPairArrayIntSheetString, 109 // class WXDLLIMPEXP_ADV); 110 // DECLARE_PAIRED_INT_DATA_ARRAYS(wxPairArrayIntSheetString, wxArrayPairArrayIntSheetString, 111 // wxPairArrayIntPairArraySheetStringBase, class WXDLLIMPEXP_ADV) 112 // 113 // In your source file write this to get the code for the pair array 114 // DEFINE_PAIRED_INT_DATA_ARRAYS(wxString, wxPairArrayIntSheetString) 115 // DEFINE_PAIRED_INT_DATA_ARRAYS(wxPairArrayIntSheetString, 116 // wxPairArrayIntPairArraySheetStringBase) 117 // 118 // ============================================================================ 119 120 #define DECLARE_PAIRED_DATA_ARRAYS_BASE(Tkey, TkeyArray, Tval, TvalArray, name, classexp) \ 121 \ 122 classexp name \ 123 { \ 124 public: \ 125 name() {} \ 126 name(const Tval& defaultVal) : m_defaultValue(defaultVal) {} \ 127 name(const name& other) { Copy(other); } \ 128 name(const Tkey& key, const Tval& val) { m_keys.Add(key); m_values.Add(val); } \ 129 int GetCount() const { return m_keys.GetCount(); } \ 130 int FindIndex(const Tkey& key) const; \ 131 size_t FindInsertIndex(const Tkey& pos) const; \ 132 bool HasKey(const Tkey& key) const { return FindIndex(key) != wxNOT_FOUND; } \ 133 const Tval& GetValue(const Tkey& key) const; \ 134 Tval& GetValue(const Tkey& key); \ 135 Tval& GetOrCreateValue(const Tkey& key); \ 136 void SetValue(const Tkey& key, const Tval& value); \ 137 bool RemoveValue(const Tkey& key); \ 138 void Clear() { m_keys.Clear(); m_values.Clear(); } \ 139 const Tval& GetItemValue(size_t index) const { return m_values[index]; } \ 140 const Tkey& GetItemKey(size_t index) const { return m_keys[index]; } \ 141 Tval& GetItemValue(size_t index) { return m_values[index]; } \ 142 Tkey& GetItemKey(size_t index) { return m_keys[index]; } \ 143 void RemoveAt(size_t index) { m_keys.RemoveAt(index); m_values.RemoveAt(index); } \ 144 const TvalArray& GetValues() const { return m_values; } \ 145 const TkeyArray& GetKeys() const { return m_keys; } \ 146 TvalArray& GetValues() { return m_values; } \ 147 TkeyArray& GetKeys() { return m_keys; } \ 148 const Tval& GetDefaultValue() const { return m_defaultValue; } \ 149 void SetDefaultValue(const Tval& val) { m_defaultValue = val; } \ 150 void Copy(const name& other); \ 151 void Sort() { if (GetCount() > 1) q_sort(0, GetCount()-1); } \ 152 name& operator=(const name& other) { Copy(other); return *this; } \ 153 protected : \ 154 void q_sort(int left, int right); \ 155 TkeyArray m_keys; \ 156 TvalArray m_values; \ 157 Tval m_defaultValue; 158 159 // ---------------------------------------------------------------------------- 160 // Note: The above macros is incomplete to allow you to extend the class. 161 162 #define DECLARE_PAIRED_DATA_ARRAYS(Tkey, TkeyArray, Tval, TvalArray, name, classexp) \ 163 DECLARE_PAIRED_DATA_ARRAYS_BASE(Tkey, TkeyArray, Tval, TvalArray, name, classexp) \ 164 }; 165 166 #define DECLARE_PAIRED_INT_DATA_ARRAYS_BASE(Tval, TvalArray, name, classexp) \ 167 DECLARE_PAIRED_DATA_ARRAYS_BASE(int, wxArrayInt, Tval, TvalArray, name, classexp) \ 168 public: \ 169 bool UpdatePos( int pos, int numPos ); 170 171 #define DECLARE_PAIRED_INT_DATA_ARRAYS(Tval, TvalArray, name, classexp) \ 172 DECLARE_PAIRED_INT_DATA_ARRAYS_BASE(Tval, TvalArray, name, classexp) \ 173 }; 174 175 // ============================================================================ 176 #define DEFINE_PAIRED_DATA_ARRAYS(Tkey, Tval, name) \ 177 \ 178 const Tval& name::GetValue(const Tkey& key) const \ 179 { \ 180 const int n = FindIndex(key); \ 181 if (n != wxNOT_FOUND) return m_values[n]; \ 182 return m_defaultValue; \ 183 } \ 184 Tval& name::GetValue(const Tkey& key) \ 185 { \ 186 const int n = FindIndex(key); \ 187 if (n != wxNOT_FOUND) return m_values[n]; \ 188 return m_defaultValue; \ 189 } \ 190 Tval& name::GetOrCreateValue(const Tkey& key) \ 191 { \ 192 const size_t n = FindInsertIndex(key); \ 193 if (n == m_keys.GetCount()) \ 194 { m_keys.Add(key); m_values.Add(Tval(m_defaultValue)); } \ 195 else if (key != m_keys[n]) \ 196 { m_keys.Insert(key, n); m_values.Insert(Tval(m_defaultValue), n); } \ 197 return m_values[n]; \ 198 } \ 199 void name::SetValue(const Tkey& key, const Tval& value) \ 200 { \ 201 const size_t n = FindInsertIndex(key); \ 202 if (n == m_keys.GetCount()) \ 203 { m_keys.Add(key); m_values.Add(value); } \ 204 else if (key == m_keys[n]) \ 205 m_values[n] = value; \ 206 else \ 207 { m_keys.Insert(key, n); m_values.Insert(value, n); } \ 208 } \ 209 bool name::RemoveValue(const Tkey& key) \ 210 { \ 211 const int n = FindIndex(key); \ 212 if (n != wxNOT_FOUND) { RemoveAt(n); return true; } \ 213 return false; \ 214 } \ 215 int name::FindIndex(const Tkey& key) const \ 216 { \ 217 size_t n, lo = 0, hi = m_keys.GetCount(); \ 218 while ( lo < hi ) \ 219 { \ 220 n = (lo + hi)/2; \ 221 const Tkey &tmp = m_keys[n]; \ 222 if (tmp == key) return n; \ 223 if (tmp > key) hi = n; \ 224 else lo = n + 1; \ 225 } \ 226 return wxNOT_FOUND; \ 227 } \ 228 size_t name::FindInsertIndex(const Tkey& key) const \ 229 { \ 230 size_t n, lo = 0, hi = m_keys.GetCount(); \ 231 while ( lo < hi ) \ 232 { \ 233 n = (lo + hi)/2; \ 234 const Tkey &tmp = m_keys[n]; \ 235 if (tmp == key) return n; \ 236 if (tmp > key) hi = n; \ 237 else lo = n + 1; \ 238 } \ 239 return lo; \ 240 } \ 241 void name::Copy(const name& other) \ 242 { \ 243 m_keys = other.GetKeys(); \ 244 m_values = other.GetValues(); \ 245 m_defaultValue = other.GetDefaultValue(); \ 246 } \ 247 void name::q_sort(int left, int right) \ 248 { \ 249 int l_hold = left, r_hold = right; \ 250 Tkey pivot = m_keys[left]; Tval pivotVal = m_values[left]; \ 251 while (left < right) \ 252 { \ 253 while ((m_keys[right] >= pivot) && (left < right)) right--; \ 254 if (left != right) { m_keys[left] = m_keys[right]; \ 255 m_values[left] = m_values[right]; left++; } \ 256 while ((m_keys[left] <= pivot) && (left < right)) left++; \ 257 if (left != right) { m_keys[right] = m_keys[left]; \ 258 m_values[right] = m_values[left]; right--; } \ 259 } \ 260 m_keys[left] = pivot; m_values[left] = pivotVal; \ 261 if (l_hold < left) q_sort(l_hold, left-1); \ 262 if (r_hold > left) q_sort(left+1, r_hold); \ 263 } 264 265 // ---------------------------------------------------------------------------- 266 267 #define DEFINE_PAIRED_INT_DATA_ARRAYS(Tval, name) \ 268 DEFINE_PAIRED_DATA_ARRAYS(int, Tval, name) \ 269 bool name::UpdatePos( int pos, int numPos ) \ 270 { \ 271 int n, count = m_keys.GetCount(), start_pos = FindInsertIndex(pos); \ 272 if ((numPos == 0) || (start_pos >= count)) return false; \ 273 if ( numPos > 0 ) \ 274 { \ 275 for (n=start_pos; n<count; n++) \ 276 m_keys[n] += numPos; \ 277 } \ 278 else if ( numPos < 0 ) \ 279 { \ 280 int pos_right = pos-numPos; \ 281 for (n=start_pos; n<count; n++) \ 282 { \ 283 int &k = m_keys[n]; \ 284 if (k < pos_right) { RemoveAt(n); n--; count--; } \ 285 else if (k >= pos_right) { k += numPos; } \ 286 } \ 287 } \ 288 return true; \ 289 } 290 291 #endif // __WX_PAIRARR_H__ 292