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