3 Copyright (C) 2002 Free Software Foundation, Inc.
4 Written by Bruno Haible <bruno@clisp.org>.
6 This file is part of GNU GPERF.
8 GNU GPERF is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU GPERF is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; see the file COPYING.
20 If not, write to the Free Software Foundation, Inc.,
21 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
24 #include "keyword-list.h"
28 /* -------------------------- Keyword_List class --------------------------- */
31 Keyword_List::Keyword_List (Keyword
*car
)
32 : _cdr (NULL
), _car (car
)
36 /* ------------------------- KeywordExt_List class ------------------------- */
39 KeywordExt_List::KeywordExt_List (KeywordExt
*car
)
44 /* ------------------------ Keyword_List functions ------------------------- */
46 /* Copies a linear list, sharing the list elements. */
48 copy_list (Keyword_List
*list
)
51 Keyword_List
**lastp
= &result
;
54 Keyword_List
*new_cons
= new Keyword_List (list
->first());
56 lastp
= &new_cons
->rest();
63 /* Copies a linear list, sharing the list elements. */
65 copy_list (KeywordExt_List
*list
)
67 return static_cast<KeywordExt_List
*> (copy_list (static_cast<Keyword_List
*> (list
)));
70 /* Deletes a linear list, keeping the list elements in memory. */
72 delete_list (Keyword_List
*list
)
76 Keyword_List
*rest
= list
->rest();
82 /* Type of a comparison function. */
83 typedef bool (*Keyword_Comparison
) (Keyword
*keyword1
, Keyword
*keyword2
);
85 /* Merges two sorted lists together to form one sorted list. */
87 merge (Keyword_List
*list1
, Keyword_List
*list2
, Keyword_Comparison less
)
90 Keyword_List
**resultp
= &result
;
103 if (less (list2
->first(), list1
->first()))
106 resultp
= &list2
->rest();
107 /* We would have a stable sorting if the next line would read:
109 list2
= list1
; list1
= *resultp
;
114 resultp
= &list1
->rest();
121 /* Sorts a linear list, given a comparison function.
122 Note: This uses a variant of mergesort that is *not* a stable sorting
125 mergesort_list (Keyword_List
*list
, Keyword_Comparison less
)
127 if (list
== NULL
|| list
->rest() == NULL
)
128 /* List of length 0 or 1. Nothing to do. */
132 /* Determine a list node in the middle. */
133 Keyword_List
*middle
= list
;
134 for (Keyword_List
*temp
= list
->rest();;)
140 middle
= middle
->rest();
145 /* Cut the list into two halves.
146 If the list has n elements, the left half has ceiling(n/2) elements
147 and the right half has floor(n/2) elements. */
148 Keyword_List
*right_half
= middle
->rest();
149 middle
->rest() = NULL
;
151 /* Sort the two halves, then merge them. */
152 return merge (mergesort_list (list
, less
),
153 mergesort_list (right_half
, less
),
159 mergesort_list (KeywordExt_List
*list
,
160 bool (*less
) (KeywordExt
*keyword1
, KeywordExt
*keyword2
))
163 static_cast<KeywordExt_List
*>
164 (mergesort_list (static_cast<Keyword_List
*> (list
),
165 reinterpret_cast<Keyword_Comparison
> (less
)));
171 #define INLINE /* not inline */
172 #include "keyword-list.icc"
175 #endif /* not defined __OPTIMIZE__ */