X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fparray.hh;h=bef32612f007d2dcf5de344a11540cac20d4ed11;hb=38d7d319eabc906e82fb42002678c6d42a23b6f7;hp=b4d00af4f5b0b87fc735e122d5b0b653fe00a38b;hpb=9f4d4a1ce5dc0fad4ed27c9cc1e357cae090b1b1;p=lilypond.git diff --git a/flower/include/parray.hh b/flower/include/parray.hh index b4d00af4f5..bef32612f0 100644 --- a/flower/include/parray.hh +++ b/flower/include/parray.hh @@ -3,7 +3,7 @@ source file of the Flower Library - (c) 1997--2006 Han-Wen Nienhuys + (c) 1997--2009 Han-Wen Nienhuys */ #ifndef PARRAY_HH @@ -11,335 +11,13 @@ #include "std-vector.hh" -/** - an array of pointers. +using namespace std; - TODO - should init to 0. -*/ template -class Link_array : private Array +class Link_array : public vector { - - Link_array (Array const &v) - :Array (v) - { - } - -public: - Link_array () - { - } - - T *const &back() const - { - return (T * const &) Array::back(); - } - - T *&back () - { - return (T *&) Array::back (); - } - - Array::begin; - Array::end; - Array::clear; - Array::erase; - Array::resize; - Array::size; - Array::empty; - Array::pop_back; - - - /* Flower compat */ - Array::unordered_del; - Array::reverse; - Array::tighten_maxsize; - - static int default_compare (T *const &p1, T *const &p2) - { - /* can't do p1 -p2, since T might be an incomplete type */ - if (p1 < p2) - return -1; - if (p2 < p1) - return 1; - return 0; - } - Link_array (T *const *tp, int n) - : Array ((void **)tp, n) - { - } - - Link_array (Link_array const &src) - : Array (src) - { - } - - /// access element - T *elem (int i) const - { - return elem_ref (i); - } - T *&elem_ref (int i) const - { - return (T *&) Array::elem_ref (i); - } - - /// access element - T *&operator [] (int i) - { - return (T *&) Array::elem_ref (i); - } - /// access element - T *const operator [] (int i) const - { - return (T *const) Array::elem (i); - } - T *pop () - { - T* t = (T *) Array::back (); - pop_back (); - return t; - } - void insert (iterator b, T *t) - { - Array::insert (b, t); - } - void push_back (T *t) - { - Array::push_back (t); - } - - /// return last entry - T *top (int j) const - { - return (T *) Array::top (j); - } - T *& top (int i) - { - return (T *&) Array::top (i); - } - - void substitute (T *old, T *new_p) - { - int i; - while ((i = find_index (old)) >= 0) - if (new_p) - elem_ref (i) = new_p; - else - erase (begin () + i); - } - void unordered_substitute (T *old, T *new_p) - { - int i; - while ((i = find_index (old)) >= 0) - if (new_p) - elem_ref (i) = new_p; - else - unordered_del (i); - } - void default_sort () - { - sort (default_compare); - } - - // quicksort. - void sort (int (*compare) (T *const &, T *const &), - int lower = -1, int upper = -1); - - void uniq () - { - Link_array ls; - for (vsize i = 0; i < size (); i++) - if (!i || elem (i - 1) != elem (i)) - ls.push_back (elem (i)); - *this = ls; - } - - T *& boundary (int d, int i) - { - assert (d); - if (d == 1) - return top (i); - else - return elem_ref (i); - } - T *boundary (int d, int i)const - { - assert (d); - if (d == 1) - return top (i); - else - return elem_ref (i); - } - - T ** accesses () const - { - return (T **) Array::accesses (); - } - /** - remove i-th element, and return it. - */ - T *get (vsize i) - { - T *t = elem (i); - Array::erase (Array::begin () + i); - return t; - } - Link_array - slice (int l, int u) const - { - return Array::Array (begin () + l, begin () + u); - } - void concat (Link_array const &a2) - { - Array::concat (a2); - } - int find_index (T const *t) const - { - for (vsize i = 0; i < size (); i++) - if (elem (i) == t) - return i; - return -1; - } - T *find (T const *t) const - { - int i = find_index (t); - if (i >= 0) - return elem (i); - else - return 0; - } + }; -template -Link_array -typecasts (Link_array const &a, T * /* dummy */) -{ - Link_array ret; - for (vsize i = a.size (); i--;) - ret.push_back (dynamic_cast (a[i])); // ugh? - return ret; -} - -template inline void -Link_array::sort (int (*compare) (T *const &, T *const &), int lower, int upper) -{ - if (lower < 0) - { - lower = 0; - upper = size () - 1; - } - if (lower >= upper) - return; - swap (lower, (lower + upper) / 2); - int last = lower; - for (int i = lower +1; i <= upper; i++) - if (compare (elem (i), elem (lower)) < 0) - swap (++last, i); - swap (lower, last); - sort (compare, lower, last - 1); - sort (compare, last + 1, upper); -} - -template -void -junk_pointers (Link_array &a) -{ - for (vsize i = 0; i < a.size (); i++) - delete a[i]; - a.clear (); -} - -/* - lookup with binsearch, return tokencode. -*/ -template -int -binsearch (Array const &arr, T t, int (*compare) (T const &, T const &)) -{ - int cmp; - int result; - int lo = 0; - int hi = arr.size (); - - /* binary search */ - do - { - cmp = (lo + hi) / 2; - - result = compare (t, arr[cmp]); - - if (result < 0) - hi = cmp; - else - lo = cmp; - } - while (hi - lo > 1); - - if (!compare (t, arr[lo])) - return lo; - /* not found */ - return -1; -} - -template -int -binsearch_links (Link_array const &arr, T *t, - int (*compare) (T *const &, T *const &)) -{ - int cmp; - int result; - int lo = 0; - int hi = arr.size (); - - if (hi == 0) - return -1; - - /* binary search */ - do - { - cmp = (lo + hi) / 2; - - result = (*compare) (t, arr[cmp]); - - if (result < 0) - hi = cmp; - else - lo = cmp; - } - while (hi - lo > 1); - - if (!compare (t, arr[lo])) - return lo; - /* not found */ - return -1; -} - -template -void -binary_search_bounds (Link_array const &table, - T const *key, int (*compare) (T *const &, T *const &), - int *lo, - int *hi) -{ - int cmp; - int result; - - /* binary search */ - do - { - cmp = (*lo + *hi) / 2; - - result = (*compare) ((T *) key, table[cmp]); - - if (result < 0) - *hi = cmp; - else - *lo = cmp; - } - while (*hi - *lo > 1); -} - #endif // PARRAY_HH