1 /*
2 This file is part of GNU APL, a free implementation of the
3 ISO/IEC Standard 13751, "Programming Language APL, Extended"
4
5 Copyright (C) 2008-2016 Dr. Jürgen Sauermann
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #ifndef __COLLATING_CACHE_HH_DEFINED__
22 #define __COLLATING_CACHE_HH_DEFINED__
23
24 #include <vector>
25
26 #include "Common.hh"
27 #include "PrimitiveFunction.hh"
28 #include "Token.hh"
29 #include "Shape.hh"
30
31 class Cell;
32
33 //-----------------------------------------------------------------------------
34 /** one item of a CollatingCache. Every character in A (of A⍋B or A⍒B gets
35 one CollatingCacheEntry; if the same character occurs multiple times in A,
36 then the first one (in row-major order) creates the entry and the remaining
37 copies of the character use the same CollatingCacheEntry.
38
39 Later on, f two Unicodes c1 and c2 shall be compared, then the ce_shapes
40 (which are actually indices into A) of the CollatingCacheEntry for c1 and
41 c2 are used for the comparison and the lowest dimansion wins.
42 **/
43 /// One item in a CollatingCache
44 struct CollatingCacheEntry
45 {
46 /// constructor: an invalid entry (for allocatingi
47 /// vector<CollatingCacheEntry> items)
CollatingCacheEntryCollatingCacheEntry48 CollatingCacheEntry()
49 : ce_char(Invalid_Unicode),
50 ce_shape()
51 {}
52
53 /// constructor: an entry with character \b c and shape \b shape
CollatingCacheEntryCollatingCacheEntry54 CollatingCacheEntry(Unicode uni, const Shape & shape_A)
55 : ce_char(uni),
56 ce_shape(shape_A) // shape_A means not found
57 {}
58
59 /// the character
60 const Unicode ce_char;
61
62 /// the shape
63 Shape ce_shape;
64
65 /// assignment (to allow const ce_char)
operator =CollatingCacheEntry66 void operator =(const CollatingCacheEntry & other)
67 { new (this) CollatingCacheEntry(other); }
68
69 /// compare this entry with \b other at \b axis
compare_axisCollatingCacheEntry70 int compare_axis(const CollatingCacheEntry & other, Rank axis) const
71 {
72 return ce_shape.get_shape_item(axis)
73 - other.ce_shape.get_shape_item(axis);
74 }
75
76 /// compare \b key with \b entry (for Heapsort::search())
compare_charsCollatingCacheEntry77 static int compare_chars(const Unicode & key,
78 const CollatingCacheEntry & entry)
79 { return key - entry.ce_char; }
80 };
81 //-----------------------------------------------------------------------------
82 inline ostream &
operator <<(ostream & out,const CollatingCacheEntry & entry)83 operator << (ostream & out, const CollatingCacheEntry & entry)
84 {
85 return out << "CC-entry(" << entry.ce_char << ")";
86 }
87 //-----------------------------------------------------------------------------
88 /** A collating cache which is the internal representation of the left
89 argument A of dydic A⍋B or A⍒B
90 */
91 /// A cache for speeding up dyadic ⍋ and ⍒
92 class CollatingCache : public std::vector<CollatingCacheEntry>
93 {
94 public:
95 /// constructor: cache of rank r and comparison length clen
96 CollatingCache(const Value & A, const Cell * base, ShapeItem clen);
97
98 /// return the number of dimensions of the collating sequence
get_rank() const99 Rank get_rank() const { return rank; }
100
101 /// return the number of items to compare
get_comp_len() const102 ShapeItem get_comp_len() const { return comp_len; }
103
104 /// find (the index of) the entry for \b uni
105 ShapeItem find_entry(Unicode uni) const;
106
107 /// compare cache items \b ia and \b ib ascendingly.
108 /// \b comp_arg is a CollatingCache pointer
109 static bool greater_vec(const IntCell & ia, const IntCell & ib,
110 const void * comp_arg);
111
112 /// compare cache items \b ia and \b ib descendingly.
113 /// \b comp_arg is a CollatingCache pointer
114 static bool smaller_vec(const IntCell & ia, const IntCell & ib,
115 const void * comp_arg);
116
117 protected:
118 /// the rank of the collating sequence
119 const Rank rank;
120
121
122 /// start of B.s ravel, ⎕IO adjusted
123 const Cell * base_B1;
124
125 /// the number of items to compare
126 const ShapeItem comp_len;
127 };
128 //=============================================================================
129 /** primitive functions grade up and grade down
130 */
131 /// Base class for ⍋ and ⍒
132 class Bif_F12_SORT : public NonscalarFunction
133 {
134 public:
135 /// Constructor
Bif_F12_SORT(TokenTag tag)136 Bif_F12_SORT(TokenTag tag)
137 : NonscalarFunction(tag)
138 {}
139
140 /// sort integer vector B
141 static Token sort(Value_P B, Sort_order order);
142
143 protected:
144 /// a helper structure for sorting: a char and a shape
145 struct char_shape
146 {
147 APL_Char achar; ///< a char
148 Shape ashape; ///< a shape
149 };
150
151 /// sort char vector B according to collationg sequence A
152 Token sort_collating(Value_P A, Value_P B, Sort_order order);
153
154 /// find or create the collating cache entry for \b uni
155 static ShapeItem find_collating_cache_entry(Unicode uni,
156 CollatingCache & cache);
157 };
158 //-----------------------------------------------------------------------------
159 /** System function grade up ⍋
160 */
161 /// The class implementing ⍋
162 class Bif_F12_SORT_ASC : public Bif_F12_SORT
163 {
164 public:
165 /// Constructor
Bif_F12_SORT_ASC()166 Bif_F12_SORT_ASC()
167 : Bif_F12_SORT(TOK_F12_SORT_ASC)
168 {}
169
170 /// overloaded Function::eval_B()
eval_B(Value_P B)171 virtual Token eval_B(Value_P B)
172 { Token ret = sort(B, SORT_ASCENDING);
173 if (ret.get_Class() == TC_VALUE) return ret;
174 DOMAIN_ERROR; // complex value(s)
175 }
176
177 /// overloaded Function::eval_AB()
eval_AB(Value_P A,Value_P B)178 virtual Token eval_AB(Value_P A, Value_P B)
179 { return sort_collating(A, B, SORT_ASCENDING); }
180
181 static Bif_F12_SORT_ASC * fun; ///< Built-in function
182 static Bif_F12_SORT_ASC _fun; ///< Built-in function
183 protected:
184 };
185 //-----------------------------------------------------------------------------
186 /** System function grade down ⍒
187 */
188 /// The class implementing ⍒
189 class Bif_F12_SORT_DES : public Bif_F12_SORT
190 {
191 public:
192 /// Constructor
Bif_F12_SORT_DES()193 Bif_F12_SORT_DES()
194 : Bif_F12_SORT(TOK_F12_SORT_DES)
195 {}
196
197 /// overloaded Function::eval_B()
eval_B(Value_P B)198 virtual Token eval_B(Value_P B)
199 { Token ret = sort(B, SORT_DESCENDING);
200 if (ret.get_Class() == TC_VALUE) return ret;
201 DOMAIN_ERROR; // complex value(s)
202 }
203
204 /// overloaded Function::eval_AB()
eval_AB(Value_P A,Value_P B)205 virtual Token eval_AB(Value_P A, Value_P B)
206 { return sort_collating(A, B, SORT_DESCENDING); }
207
208 static Bif_F12_SORT_DES * fun; ///< Built-in function
209 static Bif_F12_SORT_DES _fun; ///< Built-in function
210 protected:
211 };
212 //-----------------------------------------------------------------------------
213
214
215 #endif // __COLLATING_CACHE_HH_DEFINED__
216