X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fparray.hh;h=9ef9ddb2173b18f36dd6be1857ae91f615708c22;hb=47db9a3883d726ca53e2133a3b2298f78dd6a32e;hp=c39ec2500bed1ce66591f55c6be51de86343ed24;hpb=528e7b6840aa4bd8e23f69c3f6842b124cee26ae;p=lilypond.git diff --git a/flower/include/parray.hh b/flower/include/parray.hh index c39ec2500b..9ef9ddb217 100644 --- a/flower/include/parray.hh +++ b/flower/include/parray.hh @@ -1,300 +1,34 @@ /* - parray.hh -- declare Pointer_array + This file is part of LilyPond, the GNU music typesetter. - source file of the Flower Library + Copyright (C) 1997--2015 Han-Wen Nienhuys - (c) 1997--2000 Han-Wen Nienhuys -*/ + LilyPond is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + LilyPond is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + You should have received a copy of the GNU General Public License + along with LilyPond. If not, see . +*/ #ifndef PARRAY_HH #define PARRAY_HH -#include "array.hh" +#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 { - 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 (Array v) - :Array (v) - { - } -public: - Link_array () - {} - - 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 () - { - return (T*) Array::pop (); - } - void insert (T *t, int i) - { - Array::insert (t, i); - } - void push (T* t) - { - Array::push (t); - } - /// return last entry - T* top (int j=0) const - { - return (T*) Array::top (j); - } - T *& top (int i=0) - { - return (T*&) Array::top (i); - } - void substitute (T *old, T*new_l) - { - int i; - while ((i = find_i (old)) >=0) - if (new_l) - elem_ref (i) =new_l; - else - del (i); - } - void unordered_substitute (T* old, T * new_l) - { - int i; - while ((i = find_i (old)) >=0) - if (new_l) - elem_ref (i) =new_l; - 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 l_arr; - for (int i=0; i < size (); i++) - if (!i || elem (i-1) != elem (i)) - l_arr.push (elem (i)); - *this = l_arr; - } - Array::del; - Array::unordered_del; - Array::size; - Array::clear; - Array::set_size; - Array::empty; - Array::reverse; - Array::tighten_maxsize; - - 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 ** access_array () const - { - return (T**) Array::access_array (); - } - T * get (int i) - { - return (T*) Array::get (i); - } - Link_array - slice (int l,int u) - { - return Array::slice (l,u); - } - void concat (Link_array const &a2) - { - Array::concat (a2); - } - int find_i (T const * t) const { - for (int i=0; i < size (); i++) - if (elem (i) == t) - return i; - return -1; - } - T *find_l (T const *t) const - { - int i = find_i (t); - if (i >= 0) - return elem (i); - else - return 0; - } - }; -template -Link_array -typecast_array (Link_array const &a, T * /* dummy */ ) -{ - Link_array ret; - for (int i=a.size (); i-- ; ) - ret.push (dynamic_cast (a[i])); // ugh? - return ret; -} - - - -template inline void -Link_array::sort (int (*compare) (T *const&,T *const&), - int lower = -1, int upper = -1) -{ - 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_pointer_array (Link_array &a) -{ - for (int i=0; i < a.size (); i++) - { - delete a[i]; - } - a.clear (); -} - - - -/* - lookup with binsearch, return tokencode. -*/ -template -int -binsearch_array (Array const &arr, T t, int (*compare) (T const&,T const&)) -{ - int lo; - int hi; - int cmp; - int result; - lo = 0; - hi = maxkey; - - /* 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; - else - return -1; /* not found */ -} - - -template -int -binsearch_link_array (Link_array const &arr, T *t, - int (*compare) (T *const&,T *const&), - int lo = 0, int hi = -1 ) -{ - int cmp; - int result; - if (hi< 0) - 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; - else - return -1; /* not found */ -} - - #endif // PARRAY_HH