1/* Keyword list.
2
3 Copyright (C) 2002 Free Software Foundation, Inc.
4 Written by Bruno Haible <bruno@clisp.org>.
5
6 This file is part of GNU GPERF.
7
8 This program 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 3 of the License, or
11 (at your option) any later version.
12
13 This program 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.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20
21/* Specification. */
22#include "keyword-list.h"
23
24#include <stddef.h>
25
26/* -------------------------- Keyword_List class --------------------------- */
27
28/* Constructor. */
29Keyword_List::Keyword_List (Keyword *car)
30 : _cdr (NULL), _car (car)
31{
32}
33
34/* ------------------------- KeywordExt_List class ------------------------- */
35
36/* Constructor. */
37KeywordExt_List::KeywordExt_List (KeywordExt *car)
38 : Keyword_List (car)
39{
40}
41
42/* ------------------------ Keyword_List functions ------------------------- */
43
44/* Copies a linear list, sharing the list elements. */
45Keyword_List *
46copy_list (Keyword_List *list)
47{
48 Keyword_List *result;
49 Keyword_List **lastp = &result;
50 while (list != NULL)
51 {
52 Keyword_List *new_cons = new Keyword_List (list->first());
53 *lastp = new_cons;
54 lastp = &new_cons->rest();
55 list = list->rest();
56 }
57 *lastp = NULL;
58 return result;
59}
60
61/* Copies a linear list, sharing the list elements. */
62KeywordExt_List *
63copy_list (KeywordExt_List *list)
64{
65 return static_cast<KeywordExt_List *> (copy_list (static_cast<Keyword_List *> (list)));
66}
67
68/* Deletes a linear list, keeping the list elements in memory. */
69void
70delete_list (Keyword_List *list)
71{
72 while (list != NULL)
73 {
74 Keyword_List *rest = list->rest();
75 delete list;
76 list = rest;
77 }
78}
79
80/* Type of a comparison function. */
81typedef bool (*Keyword_Comparison) (Keyword *keyword1, Keyword *keyword2);
82
83/* Merges two sorted lists together to form one sorted list. */
84static Keyword_List *
85merge (Keyword_List *list1, Keyword_List *list2, Keyword_Comparison less)
86{
87 Keyword_List *result;
88 Keyword_List **resultp = &result;
89 for (;;)
90 {
91 if (!list1)
92 {
93 *resultp = list2;
94 break;
95 }
96 if (!list2)
97 {
98 *resultp = list1;
99 break;
100 }
101 if (less (list2->first(), list1->first()))
102 {
103 *resultp = list2;
104 resultp = &list2->rest();
105 /* We would have a stable sorting if the next line would read:
106 list2 = *resultp; */
107 list2 = list1; list1 = *resultp;
108 }
109 else
110 {
111 *resultp = list1;
112 resultp = &list1->rest();
113 list1 = *resultp;
114 }
115 }
116 return result;
117}
118
119/* Sorts a linear list, given a comparison function.
120 Note: This uses a variant of mergesort that is *not* a stable sorting
121 algorithm. */
122Keyword_List *
123mergesort_list (Keyword_List *list, Keyword_Comparison less)
124{
125 if (list == NULL || list->rest() == NULL)
126 /* List of length 0 or 1. Nothing to do. */
127 return list;
128 else
129 {
130 /* Determine a list node in the middle. */
131 Keyword_List *middle = list;
132 for (Keyword_List *temp = list->rest();;)
133 {
134 temp = temp->rest();
135 if (temp == NULL)
136 break;
137 temp = temp->rest();
138 middle = middle->rest();
139 if (temp == NULL)
140 break;
141 }
142
143 /* Cut the list into two halves.
144 If the list has n elements, the left half has ceiling(n/2) elements
145 and the right half has floor(n/2) elements. */
146 Keyword_List *right_half = middle->rest();
147 middle->rest() = NULL;
148
149 /* Sort the two halves, then merge them. */
150 return merge (mergesort_list (list, less),
151 mergesort_list (right_half, less),
152 less);
153 }
154}
155
156KeywordExt_List *
157mergesort_list (KeywordExt_List *list,
158 bool (*less) (KeywordExt *keyword1, KeywordExt *keyword2))
159{
160 return
161 static_cast<KeywordExt_List *>
162 (mergesort_list (static_cast<Keyword_List *> (list),
163 reinterpret_cast<Keyword_Comparison> (less)));
164}
165
166
167#ifndef __OPTIMIZE__
168
169#define INLINE /* not inline */
170#include "keyword-list.icc"
171#undef INLINE
172
173#endif /* not defined __OPTIMIZE__ */
174