casacore
OrderedMap.h
Go to the documentation of this file.
1 //# OrderedMap.h: Templated associatve array (map) classes with ordered keys
2 //# Copyright (C) 1993,1994,1995,1996,1999,2000,2001
3 //# Associated Universities, Inc. Washington DC, USA.
4 //#
5 //# This library is free software; you can redistribute it and/or modify it
6 //# under the terms of the GNU Library General Public License as published by
7 //# the Free Software Foundation; either version 2 of the License, or (at your
8 //# option) any later version.
9 //#
10 //# This library is distributed in the hope that it will be useful, but WITHOUT
11 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13 //# License for more details.
14 //#
15 //# You should have received a copy of the GNU Library General Public License
16 //# along with this library; if not, write to the Free Software Foundation,
17 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18 //#
19 //# Correspondence concerning AIPS++ should be addressed as follows:
20 //# Internet email: aips2-request@nrao.edu.
21 //# Postal address: AIPS++ Project Office
22 //# National Radio Astronomy Observatory
23 //# 520 Edgemont Road
24 //# Charlottesville, VA 22903-2475 USA
25 //#
26 //# $Id$
27 
28 #ifndef CASA_ORDEREDMAP_H
29 #define CASA_ORDEREDMAP_H
30 
31 #include <casacore/casa/aips.h>
32 #include <casacore/casa/Exceptions/Error.h>
33 #include <casacore/casa/Containers/Block.h>
34 #include <casacore/casa/BasicSL/String.h>
35 #include <casacore/casa/Containers/Map.h>
36 #include <casacore/casa/Containers/OrderedPair.h>
37 #include <casacore/casa/Utilities/Register.h>
38 #include <casacore/casa/Utilities/Notice.h>
39 
40 namespace casacore { //#Begin casa namespace
41 
42 template<class t, class v> class OrderedMap;
43 template<class t, class v> class OrderedMapRep;
44 template<class t, class v> class OrderedMapIterRep;
45 
46 // <category lib=aips sect="Notice">
47 // <summary>Message used for OrderedMap notification</summary>
48 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
49 // </reviewed>
50 //
51 // This is the message that flows between the OrderedMap
52 // and the OrderedMap iterators. It allows OrderedMap
53 // iterators to react to changes as they occur to the
54 // OrderedMap.
55 //
56 template<class t,class v> class OrderedMapNotice : public Notice {
57 friend class OrderedMapRep<t,v>;
58 friend class OrderedMapIterRep<t,v>;
59 private:
62 
63  //*display 1
64  //
65  // This is used to construct a list notice. The parameters are:
66  // <list>
67  // <item> the change modification position
68  // <item> the change type
69  // </list>
70  //
71  OrderedMapNotice(uInt pos, NoticeType typ) : changeType(typ), modPos(pos) {}
72 
73 public:
74  //
75  // This function returns the "Notice" type, retrieved
76  // from the "type registry".
77  //
78  uInt type() const {return Register(this);}
79 
80  //
81  // This operator can be used to compare two
82  // "OrderedMapNotice"s.
83  //
84  int operator==(const Notice &op) const {
85  if (type() != op.type()) {
86  return 0;
87  } else {
88  const OrderedMapNotice<t,v> &opD = (const OrderedMapNotice<t,v> &) op;
89  return (modPos == opD.modPos && changeType == opD.changeType);
90  }
91  }
92 };
93 
94 // <summary> Representation class for an Ordered Map</summary>
95 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
96 // </reviewed>
97 
98 template<class key, class value> class OrderedMapRep : public NoticeSource, public MapRep<key,value> {
99 friend class OrderedMap<key,value>;
100 public:
101  //
102  // Creates a map with the specified default value, "value", and the
103  // internal block size.
104  //
105  OrderedMapRep (const value&, uInt size);
106 
107  //
108  // Creates a map with the specified default value, "value".
109  //
110  OrderedMapRep (const value&);
111 
112  //
113  // These functions check to see if a mapping is defined between
114  // the specified key and some value. If one is, a pointer to
115  // the value is returned, otherwise 0 is returned.
116  //
117  //+grp
118  value *isDefined(const key&);
119  const value *isDefined(const key&) const;
120  //-grp
121 
122  //
123  // Returns the number of user defined mappings
124  //
125  uInt ndefined() const;
126 
127  //
128  // Defines a mapping (ie. create a key value mapping)
129  //
130  value &define (const key&, const value&);
131 
132  //
133  // Undefines a mapping (ie. remove a key value mapping).
134  //
135  void remove (const key&);
136 
137  //
138  // Clear the entire map (ie. remove all mappings).
139  //
140  void clear ();
141 
142  MapIterRep<key,value> *getRep(Map<key,value> *) const;
143 
144  MapRep<key,value> *Clone() const;
145 
146  //
147  // Get the number of mappings.
148  //
149  uInt nused() const { return nrused; }
150  uInt ntot() const { return nrtot; }
151 
152  //
153  // Get or set the Block allocation increment.
154  //
155  //+grp
156  uInt incr() const { return nrincr; }
157  uInt incr(uInt nri) { return (nrincr = nri); }
158  //-grp
159 
160  //
161  // Removes a map.
162  //
163  ~OrderedMapRep ();
164 
165  enum {OrderedMapRepVersion = 1};
166 
167 protected:
168  // The blocks to hold the keys and values
169  // and the total, used and increment size of these blocks.
174 
175  // The index of the last key used.
177 
178  // Binary search for the key.
179  Int findKey (const key&, Bool&) const;
180 };
181 
182 //
183 // <category lib=aips sect="Containers">
184 // <summary>Map with keys ordered</summary>
185 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
186 // </reviewed>
187 //
188 // OrderedMap<key,value> is a template class derived from Map.
189 // It is similar to ListMap, but the keys are kept in order and
190 // they have to be unique.
191 //
192 // It uses a Block to store an array of pointers to the keys and
193 // the associated values.
194 // The keys and values themselves are stored on the heap.
195 // The keys are kept in order to allow a binary search through
196 // the keys for rapid access.
197 //
198 // This is one (simple) implementation of an ordered map.
199 // It is not suitable for large arrays of keys, since the overhead
200 // of keeping the keys in order would get too big.
201 // For large arrays a red-black tree implementation would be better.
202 //
203 // Exceptions are raised when new[] is failing, when the next()
204 // getKey() or getValue() function is failing or when a duplicate key
205 // is defined.
206 //
207 // The AipsIO >> and << operators are defined in <aips/OrdMapIO.h>.
208 //
209 template<class key, class value> class OrderedMap : public Map<key,value> {
210 friend class OrderedMapIterRep<key,value>;
211 protected:
212 
213  void throwgetKey(uInt) const;
214  void throwgetValue(uInt) const;
215 
216  value &getVal(uInt inx) {
217  if (!this->Rep || inx >= nused())
218  throwgetValue(inx);
219  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->y());
220  }
221 
222  const value &getVal(uInt inx) const {
223  if (!this->Rep || inx >= nused())
224  throwgetValue(inx);
225  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->y());
226  }
227 
228  key &getKey (uInt inx) {
229  if (!this->Rep || inx >= nused())
230  throwgetKey(inx);
231  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->x());
232  }
233 
234  const key &getKey (uInt inx) const {
235  if (!this->Rep || inx >= nused())
236  throwgetKey(inx);
237  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->x());
238  }
239 
240 public:
241  //
242  // Creates a map with the specified default value, "value", and the
243  // internal block size.
244  //
245  OrderedMap (const value& dflt, uInt size) : Map<key,value>(new OrderedMapRep<key,value>(dflt,size)) { }
246 
247  //
248  // Creates a map with the specified default value, "value".
249  //
250  explicit OrderedMap (const value& dflt) : Map<key,value>(new OrderedMapRep<key,value>(dflt)) { }
251 
252  //
253  // Creates a map from another one; use copy semantics.
254  //
255  OrderedMap (const OrderedMap<key,value>& other) : Map<key,value>(other.Rep->Clone()) { }
256 
257  //
258  // Does nothing, the destruction is taken care of in the base class, i.e. the
259  // letter contains the guts.
260  //
261  ~OrderedMap();
262 
263  //
264  // Assigns this OrderedMap to another with copy semantics.
265  //
267  this->SetRep(other.Rep->Clone());
268  return *this;
269  }
270 
271  //
272  // Get the number of mappings.
273  //
274  uInt nused() const { return ((OrderedMapRep<key,value> *)(this->Rep))->nused(); }
275  uInt ntot() const { return ((OrderedMapRep<key,value> *)(this->Rep))->ntot(); }
276 
277  //
278  // Get or set the Block allocation increment.
279  //
280  //+grp
281  uInt incr() const { return ((OrderedMapRep<key,value> *)(this->Rep))->incr(); }
282  uInt incr(uInt nri) { return ((OrderedMapRep<key,value> *)(this->Rep))->incr(nri);}
283  //-grp
284 
285  enum {OrderedMapVersion = 1};
286 };
287 
288 
289 //
290 // <category lib=aips sect="Containers">
291 // <summary>OrderedMap iterator "letter"</summary>
292 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
293 // </reviewed>
294 //
295 // This is the "letter" which when paired (Const)MapIter "envelope"
296 // allows traversal of "OrderedMap"s.
297 //
298 template<class key, class value> class OrderedMapIterRep : virtual public MapIterRep<key,value>, public NoticeTarget {
299 protected:
300 
301  //*display 4
302  //
303  // Throw exceptions on behalf of inline functions.
304  //
305  //+grp
306  void thrownext() const;
307  void throwInvalidIter() const;
308  //-grp
309 
311 
313 
314 public:
315 
316  //
317  // Checks to see if the iterator is in a valid state.
318  //
319  Bool isValid() const;
320 
321  //
322  // Checks to see if the iterator is at one of the
323  // map extremes, "atEnd()" or "atStart()".
324  //
325  //+grp
326  Bool atEnd() const;
327  Bool atStart() const;
328  //-grp
329 
330  //
331  // Move the iterator to the beginning of the Map.
332  //
333  void toStart();
334 
335  //
336  // Advance the iterator to the next key.
337  //
338  //+grp
339  void operator++();
340  void operator++(int);
341  //-grp
342 
343  //
344  // Retrieve the key at the current iterator position.
345  //
346  //+grp
347  const key &getKey () const;
348  const key &getKey (uInt inx) const {
349  if (!container || !isValid())
350  throwInvalidIter();
351  return ((*container).getKey(inx));
352  }
353  //-grp
354 
355  //
356  // Retrieve the value at the given index in the internal block
357  // which stores the representation of the OrderedMap.
358  //
359  // <note> This should typically not be used.</note>
360  //
361  //+grp
362  value &getVal(uInt inx) {
363  if (!container || !isValid())
364  throwInvalidIter();
365  return ((*container).getVal(inx));
366  }
367  //-grp
368 
369  //
370  // Retrieve the value at the current iterator position.
371  //
372  //+grp
373  const value &getVal() const;
374  const value &getVal(uInt inx) const {
375  if (!container || !isValid())
376  throwInvalidIter();
377  return ((*container).getVal(inx));
378  }
379 
380  value &getVal() {return getVal(CurIndex);}
381  //-grp
382 
383 
386  return ret;
387  }
388 
389  //*display 4
390  //
391  // This function is the hook through which OrderedMap
392  // iterators are notified of changes to the OrderedMap
393  // which they observe, i.e. changes which may cause
394  // require iterator update.
395  //
396  void notify(const Notice &);
397 
398  //
399  // These constructors allow a ListMapIter to be constructed from a
400  // ListMap.
401  //
402  //+grp
404  : MapIterRep<key,value>(st),
405  NoticeTarget((NoticeSource *)((OrderedMapRep<key,value> *) st->Rep)),
406  container(st),
407  CurIndex(0)
408  {}
409 
411  : MapIterRep<key,value>(st),
412  NoticeTarget((NoticeSource *)((OrderedMapRep<key,value> *) st.Rep)),
413  container(&st),
414  CurIndex(0)
415  {}
416  //-grp
417 
418  enum {OrderedMapIterRepVersion = 1};
419 
420 };
421 
422 } //#End casa namespace
423 #ifndef CASACORE_NO_AUTO_TEMPLATES
424 #include <casacore/casa/Containers/OrderedMap.tcc>
425 #endif //# CASACORE_NO_AUTO_TEMPLATES
426 #endif
int Int
Definition: aipstype.h:47
abstract base class for notice receptors
Definition: Notice.h:153
uInt type() const
This function returns the "Notice" type, retrieved from the "type registry".
Definition: OrderedMap.h:78
Abstract base class for associative array iterators.
Definition: Map.h:51
value & getVal(uInt inx)
Definition: OrderedMap.h:216
OrderedMap(const OrderedMap< key, value > &other)
Creates a map from another one; use copy semantics.
Definition: OrderedMap.h:255
PtrHolder< T > & operator=(const PtrHolder< T > &other)
uInt incr(uInt nri)
Definition: OrderedMap.h:282
MapIterRep< key, value > * Clone()
Duplicate a map iterator.
Definition: OrderedMap.h:384
OrderedMap(const value &dflt, uInt size)
Creates a map with the specified default value, "value", and the internal block size.
Definition: OrderedMap.h:245
uInt ntot() const
Definition: OrderedMap.h:150
uInt nused() const
Get the number of mappings.
Definition: OrderedMap.h:274
OrderedMap< key, value > * container
Definition: OrderedMap.h:310
OrderedMapNotice(uInt pos, NoticeType typ)
Definition: OrderedMap.h:71
virtual uInt type() const =0
Return the identification number of the Notice type.
const value & getVal(uInt inx) const
Definition: OrderedMap.h:222
uInt lastRef
The index of the last key used.
Definition: OrderedMap.h:176
base class for notice originators
Definition: Notice.h:102
Map with keys ordered.
Definition: OrderedMap.h:42
key & getKey(uInt inx)
Definition: OrderedMap.h:228
const key & getKey(uInt inx) const
Definition: OrderedMap.h:348
OrderedMapIterRep(OrderedMap< key, value > *st)
These constructors allow a ListMapIter to be constructed from a ListMap.
Definition: OrderedMap.h:403
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:39
abstract base class for notices
Definition: Notice.h:62
Message used for OrderedMap notification.
Definition: OrderedMap.h:56
OrderedMap(const value &dflt)
Creates a map with the specified default value, "value".
Definition: OrderedMap.h:250
A drop-in replacement for Block<T*>.
Definition: Block.h:861
MapRep< key, value > * Rep
Definition: Map.h:243
uInt incr() const
Get or set the Block allocation increment.
Definition: OrderedMap.h:156
uInt incr() const
Get or set the Block allocation increment.
Definition: OrderedMap.h:281
Map representation class.
Definition: Map.h:59
const key & getKey(uInt inx) const
Definition: OrderedMap.h:234
Abstract base class for associative arrays.
Definition: Map.h:53
uInt incr(uInt nri)
Definition: OrderedMap.h:157
const value & getVal(uInt inx) const
Definition: OrderedMap.h:374
uInt ntot() const
Definition: OrderedMap.h:275
value & getVal(uInt inx)
Retrieve the value at the given index in the internal block which stores the representation of the Or...
Definition: OrderedMap.h:362
enum casacore::OrderedMapNotice::NoticeType changeType
Representation class for an Ordered Map.
Definition: OrderedMap.h:43
uInt nused() const
Get the number of mappings.
Definition: OrderedMap.h:149
value & getVal()
Return the value at the current location of the map iterator.
Definition: OrderedMap.h:380
OrderedMapIterRep(OrderedMap< key, value > &st)
Definition: OrderedMap.h:410
this file contains all the compiler specific defines
Definition: mainpage.dox:28
int operator==(const Notice &op) const
This operator can be used to compare two "OrderedMapNotice"s.
Definition: OrderedMap.h:84
LatticeExprNode value(const LatticeExprNode &expr)
This function returns the value of the expression without a mask.
OrderedMap iterator "letter".
Definition: OrderedMap.h:44
unsigned int uInt
Definition: aipstype.h:48
PtrBlock< OrderedPair< key, value > * > kvblk
The blocks to hold the keys and values and the total, used and increment size of these blocks...
Definition: OrderedMap.h:170