1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef variable_sized_pointer_array_h
26 #define variable_sized_pointer_array_h
28 ///////////////////////////////////////////////////////////////////////////
29 // Class VarPtrArray<T> provides an abstraction for
30 // an dense mapping from integers to type T.
31 // The array will grow in size when necessary.
32 // Both positive and negative indices are allowed.
33 // The indices should be centered around 0.
34 ///////////////////////////////////////////////////////////////////////////
38 #include <AD/generic/generic.h> // Generic definitions
42 T
** array
; // array of elements; displaced by offset
43 int low
, high
; // upper and lower bound on array
44 int growthRate
; // minimal number of elements for expansion
50 //////////////////////////////////////////////////////////////////
51 // Constructor and destructors
52 //////////////////////////////////////////////////////////////////
53 VarPtrArray(int lowerBound
= 0,
54 int upperBound
= 9, int growthFactor
= 32);
55 VarPtrArray(const VarPtrArray
& A
) : array(0), low(0) { *this = A
; }
56 VarPtrArray(size_t size
, T
* const []);
58 { // memset(array + low, 0, sizeof(T*) * (high - low + 1));
62 ////////////////////////////////////////////////////////////////////
64 ////////////////////////////////////////////////////////////////////
65 VarPtrArray
& operator = (const VarPtrArray
&);
67 ////////////////////////////////////////////////////////////////////
69 ////////////////////////////////////////////////////////////////////
70 inline operator const T
** () const { return array
; }
71 inline operator T
** () { return array
; }
73 ////////////////////////////////////////////////////////////////////
75 ////////////////////////////////////////////////////////////////////
76 inline int hi() const { return high
; }
77 inline int lo() const { return low
; }
78 inline int size() const { return high
- low
+ 1; }
79 inline int capacity() const { return size(); }
80 inline Bool
hasKey(int i
) const { return i
>= low
&& i
<= high
; }
81 inline const T
* operator [] (int i
) const { return array
[i
]; }
82 inline T
*& operator [] (int i
)
83 { if (! hasKey(i
)) grow(i
); return array
[i
]; }
85 ////////////////////////////////////////////////////////////////////
87 ////////////////////////////////////////////////////////////////////
88 inline Ix
first() const { return low
> high
? 0 : (Ix
)&array
[lo()]; }
89 inline Ix
last() const { return low
> high
? 0 : (Ix
)&array
[hi()]; }
90 inline Ix
next(Ix i
) const { return i
>= (Ix
)(array
+ hi()) ? 0 : (((T
**)i
)+1); }
91 inline Ix
prev(Ix i
) const { return i
<= (Ix
)(array
+ lo()) ? 0 : (((T
**)i
)-1); }
92 inline const T
* operator() (Ix i
) const { return *(T
**)i
; }
93 inline T
* operator() (Ix i
) { return *(T
**)i
; }
96 ////////////////////////////////////////////////////////////////////
97 // Implementation comes here
98 ////////////////////////////////////////////////////////////////////
100 VarPtrArray
<T
>::VarPtrArray(int lowerBound
, int upperBound
, int growthFactor
)
101 { size_t size
= upperBound
- lowerBound
+ 1;
102 high
= upperBound
; low
= lowerBound
;
103 array
= (T
**)calloc(size
, sizeof(T
*)) - low
;
104 growthRate
= growthFactor
;
108 VarPtrArray
<T
>::VarPtrArray(size_t size
, T
* const A
[])
109 { array
= (T
**)malloc(size
* sizeof(T
*));
110 low
= 0; high
= size
- 1;
112 memcpy(array
, A
, size
* sizeof(T
*));
116 VarPtrArray
<T
>& VarPtrArray
<T
>::operator = (const VarPtrArray
<T
>& A
)
118 // memset(array + low, 0, sizeof(T*) * (high - low + 1));
120 high
= A
.high
; low
= A
.low
;
121 array
= (T
**)malloc((high
- low
+ 1) * sizeof(T
*)) - A
.low
;
122 memcpy(array
, A
.array
, sizeof(T
*) * (high
- low
+ 1));
128 void VarPtrArray
<T
>::grow(int i
)
129 { int newHigh
, newLow
;
130 int growth
= growthRate
<= 0 ? (size() * 3 / 2 + 32) : growthRate
;
132 if (i
< high
+ growth
) newHigh
= high
+ growth
;
136 if (i
> low
- growth
) newLow
= low
- growth
;
139 register T
** newArray
=
140 (T
**) calloc(newHigh
- newLow
+ 1,sizeof(T
*)) - newLow
;
141 memcpy(newArray
, array
, sizeof(T
*) * (high
- low
+ 1));
142 // memset(array + low, 0, sizeof(T*) * (high - low + 1));
145 low
= newLow
; high
= newHigh
;