]> git.donarmstrong.com Git - lilypond.git/blob - flower/include/array.icc
* flower
[lilypond.git] / flower / include / array.icc
1 /*
2   (c) 1995--2005  Han-Wen Nienhuys  <hanwen@cs.uu.nl>
3
4   Distributed under GNU GPL
5 */
6
7 #if 0
8 #include "array.hh"
9 #ifdef INLINE
10 #undef INLINE
11 #endif
12
13 #define INLINE
14 #endif
15
16 /*
17   functions with loops don't inline
18 */
19
20 template<class T> INLINE void
21 arrcpy (T *dest, T const *src, int count)
22 {
23   for (int i_shadows_local = 0; i_shadows_local < count; i_shadows_local++)
24 #ifdef __powerpc__
25     {
26       /*
27         urg: wierd egcs-1.1.2-12c (stock LinuxPPC R5) bug on ppc
28         bug report filed
29         fixed in egcs-1.1.2-12f
30         ftp://dev.linuxppc.org/users/fsirl/R5/RPMS/ppc/
31       */
32       *dest = *src;
33       dest++, src++;
34     }
35 #else
36   *dest++ = *src++;
37 #endif
38 }
39
40 template<class T> INLINE void
41 Array<T>::insert (T k, int j)
42 {
43   assert (j >=0 && j<= size_);
44   set_size (size_ + 1);
45   for (int i = size_ - 1; i > j; i--)
46     array_[i] = array_[i - 1];
47   array_[j] = k;
48 }
49
50 template<class T> INLINE void
51 Array<T>::sort (int (*compare) (T const &, T const &), int lower, int upper)
52 {
53   if (lower < 0)
54     {
55       lower = 0;
56       upper = size () - 1;
57     }
58   if (lower >= upper)
59     return;
60   swap (lower, (lower + upper) / 2);
61   int last = lower;
62   for (int i= lower +1; i <= upper; i++)
63     if (compare (array_[i], array_[lower]) < 0)
64       swap (++last, i);
65   swap (lower, last);
66   sort (compare, lower, last - 1);
67   sort (compare, last + 1, upper);
68 }
69
70 template<class T> INLINE void
71 Array<T>::reverse ()
72 {
73   int h = size_ / 2;
74   for (int i =0, j = size_ - 1; i < h; i++, j--)
75     swap (i, j);
76 }
77
78 template<class T> INLINE
79 void
80 Array<T>::OK () const
81 {
82   assert (max_ >= size_ && size_ >=0);
83   if (max_) assert (array_);
84 }
85
86 template<class T> INLINE
87 T *
88 Array<T>::remove_array ()
89 {
90   T *p = array_;
91   size_ = 0;
92   max_ = 0;
93   array_ =0;
94   return p;
95 }
96
97 template<class T> INLINE
98 Array<T>
99 Array<T>::slice (int lower, int upper) const
100 {
101   assert (lower >= 0 && lower <=upper&& upper <= size_);
102   Array<T> r;
103   int s =upper - lower;
104   r.set_size (s);
105   arrcpy (r.array_, array_ + lower, s);
106   return r;
107 }
108
109 template<class T>
110 void
111 binary_search_bounds (Array<T> const &table,
112                       T const &key, int (*compare) (T const &, T const &),
113                       int *lo,
114                       int *hi)
115 {
116   int cmp;
117   int result;
118
119   /* binary search */
120   do
121     {
122       cmp = (*lo + *hi) / 2;
123
124       result = (*compare) (key, table[cmp]);
125
126       if (result < 0)
127         *hi = cmp;
128       else
129         *lo = cmp;
130     }
131   while (*hi - *lo > 1);
132 }
133
134 /*
135   lookup with binsearch, return array index.
136 */
137 template<class T>
138 int
139 binary_search (Array<T> const &table,
140                T const &key, int (*compare) (T const &, T const &),
141                int lo = 0,
142                int hi = -1)
143 {
144   if (hi < 0)
145     hi = table.size ();
146
147   binary_search_bounds (table, key, compare, &lo, &hi);
148
149   if (! (*compare) (key, table[lo]))
150     {
151       return lo;
152     }
153   else
154     return -1;              /* not found */
155 }