Daily bump.
[official-gcc.git] / gcc / ada / a-stwima.adb
blob5937c7d9ec9de2bf9be284f850567e97e855d62a
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT RUN-TIME COMPONENTS --
4 -- --
5 -- A D A . S T R I N G S . W I D E _ M A P S --
6 -- --
7 -- B o d y --
8 -- --
9 -- Copyright (C) 1992-2009, Free Software Foundation, Inc. --
10 -- --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
17 -- --
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
19 -- additional permissions described in the GCC Runtime Library Exception, --
20 -- version 3.1, as published by the Free Software Foundation. --
21 -- --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
26 -- --
27 -- GNAT was originally developed by the GNAT team at New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
29 -- --
30 ------------------------------------------------------------------------------
32 with Ada.Unchecked_Deallocation;
34 package body Ada.Strings.Wide_Maps is
36 ---------
37 -- "-" --
38 ---------
40 function "-"
41 (Left, Right : Wide_Character_Set) return Wide_Character_Set
43 LS : constant Wide_Character_Ranges_Access := Left.Set;
44 RS : constant Wide_Character_Ranges_Access := Right.Set;
46 Result : Wide_Character_Ranges (1 .. LS'Last + RS'Last);
47 -- Each range on the right can generate at least one more range in
48 -- the result, by splitting one of the left operand ranges.
50 N : Natural := 0;
51 R : Natural := 1;
52 L : Natural := 1;
54 Left_Low : Wide_Character;
55 -- Left_Low is lowest character of the L'th range not yet dealt with
57 begin
58 if LS'Last = 0 or else RS'Last = 0 then
59 return Left;
60 end if;
62 Left_Low := LS (L).Low;
63 while R <= RS'Last loop
65 -- If next right range is below current left range, skip it
67 if RS (R).High < Left_Low then
68 R := R + 1;
70 -- If next right range above current left range, copy remainder
71 -- of the left range to the result
73 elsif RS (R).Low > LS (L).High then
74 N := N + 1;
75 Result (N).Low := Left_Low;
76 Result (N).High := LS (L).High;
77 L := L + 1;
78 exit when L > LS'Last;
79 Left_Low := LS (L).Low;
81 else
82 -- Next right range overlaps bottom of left range
84 if RS (R).Low <= Left_Low then
86 -- Case of right range complete overlaps left range
88 if RS (R).High >= LS (L).High then
89 L := L + 1;
90 exit when L > LS'Last;
91 Left_Low := LS (L).Low;
93 -- Case of right range eats lower part of left range
95 else
96 Left_Low := Wide_Character'Succ (RS (R).High);
97 R := R + 1;
98 end if;
100 -- Next right range overlaps some of left range, but not bottom
102 else
103 N := N + 1;
104 Result (N).Low := Left_Low;
105 Result (N).High := Wide_Character'Pred (RS (R).Low);
107 -- Case of right range splits left range
109 if RS (R).High < LS (L).High then
110 Left_Low := Wide_Character'Succ (RS (R).High);
111 R := R + 1;
113 -- Case of right range overlaps top of left range
115 else
116 L := L + 1;
117 exit when L > LS'Last;
118 Left_Low := LS (L).Low;
119 end if;
120 end if;
121 end if;
122 end loop;
124 -- Copy remainder of left ranges to result
126 if L <= LS'Last then
127 N := N + 1;
128 Result (N).Low := Left_Low;
129 Result (N).High := LS (L).High;
131 loop
132 L := L + 1;
133 exit when L > LS'Last;
134 N := N + 1;
135 Result (N) := LS (L);
136 end loop;
137 end if;
139 return (AF.Controlled with
140 Set => new Wide_Character_Ranges'(Result (1 .. N)));
141 end "-";
143 ---------
144 -- "=" --
145 ---------
147 -- The sorted, discontiguous form is canonical, so equality can be used
149 function "=" (Left, Right : Wide_Character_Set) return Boolean is
150 begin
151 return Left.Set.all = Right.Set.all;
152 end "=";
154 -----------
155 -- "and" --
156 -----------
158 function "and"
159 (Left, Right : Wide_Character_Set) return Wide_Character_Set
161 LS : constant Wide_Character_Ranges_Access := Left.Set;
162 RS : constant Wide_Character_Ranges_Access := Right.Set;
164 Result : Wide_Character_Ranges (1 .. LS'Last + RS'Last);
165 N : Natural := 0;
166 L, R : Natural := 1;
168 begin
169 -- Loop to search for overlapping character ranges
171 while L <= LS'Last and then R <= RS'Last loop
173 if LS (L).High < RS (R).Low then
174 L := L + 1;
176 elsif RS (R).High < LS (L).Low then
177 R := R + 1;
179 -- Here we have LS (L).High >= RS (R).Low
180 -- and RS (R).High >= LS (L).Low
181 -- so we have an overlapping range
183 else
184 N := N + 1;
185 Result (N).Low := Wide_Character'Max (LS (L).Low, RS (R).Low);
186 Result (N).High :=
187 Wide_Character'Min (LS (L).High, RS (R).High);
189 if RS (R).High = LS (L).High then
190 L := L + 1;
191 R := R + 1;
192 elsif RS (R).High < LS (L).High then
193 R := R + 1;
194 else
195 L := L + 1;
196 end if;
197 end if;
198 end loop;
200 return (AF.Controlled with
201 Set => new Wide_Character_Ranges'(Result (1 .. N)));
202 end "and";
204 -----------
205 -- "not" --
206 -----------
208 function "not"
209 (Right : Wide_Character_Set) return Wide_Character_Set
211 RS : constant Wide_Character_Ranges_Access := Right.Set;
213 Result : Wide_Character_Ranges (1 .. RS'Last + 1);
214 N : Natural := 0;
216 begin
217 if RS'Last = 0 then
218 N := 1;
219 Result (1) := (Low => Wide_Character'First,
220 High => Wide_Character'Last);
222 else
223 if RS (1).Low /= Wide_Character'First then
224 N := N + 1;
225 Result (N).Low := Wide_Character'First;
226 Result (N).High := Wide_Character'Pred (RS (1).Low);
227 end if;
229 for K in 1 .. RS'Last - 1 loop
230 N := N + 1;
231 Result (N).Low := Wide_Character'Succ (RS (K).High);
232 Result (N).High := Wide_Character'Pred (RS (K + 1).Low);
233 end loop;
235 if RS (RS'Last).High /= Wide_Character'Last then
236 N := N + 1;
237 Result (N).Low := Wide_Character'Succ (RS (RS'Last).High);
238 Result (N).High := Wide_Character'Last;
239 end if;
240 end if;
242 return (AF.Controlled with
243 Set => new Wide_Character_Ranges'(Result (1 .. N)));
244 end "not";
246 ----------
247 -- "or" --
248 ----------
250 function "or"
251 (Left, Right : Wide_Character_Set) return Wide_Character_Set
253 LS : constant Wide_Character_Ranges_Access := Left.Set;
254 RS : constant Wide_Character_Ranges_Access := Right.Set;
256 Result : Wide_Character_Ranges (1 .. LS'Last + RS'Last);
257 N : Natural;
258 L, R : Natural;
260 begin
261 N := 0;
262 L := 1;
263 R := 1;
265 -- Loop through ranges in output file
267 loop
268 -- If no left ranges left, copy next right range
270 if L > LS'Last then
271 exit when R > RS'Last;
272 N := N + 1;
273 Result (N) := RS (R);
274 R := R + 1;
276 -- If no right ranges left, copy next left range
278 elsif R > RS'Last then
279 N := N + 1;
280 Result (N) := LS (L);
281 L := L + 1;
283 else
284 -- We have two ranges, choose lower one
286 N := N + 1;
288 if LS (L).Low <= RS (R).Low then
289 Result (N) := LS (L);
290 L := L + 1;
291 else
292 Result (N) := RS (R);
293 R := R + 1;
294 end if;
296 -- Loop to collapse ranges into last range
298 loop
299 -- Collapse next length range into current result range
300 -- if possible.
302 if L <= LS'Last
303 and then LS (L).Low <= Wide_Character'Succ (Result (N).High)
304 then
305 Result (N).High :=
306 Wide_Character'Max (Result (N).High, LS (L).High);
307 L := L + 1;
309 -- Collapse next right range into current result range
310 -- if possible
312 elsif R <= RS'Last
313 and then RS (R).Low <=
314 Wide_Character'Succ (Result (N).High)
315 then
316 Result (N).High :=
317 Wide_Character'Max (Result (N).High, RS (R).High);
318 R := R + 1;
320 -- If neither range collapses, then done with this range
322 else
323 exit;
324 end if;
325 end loop;
326 end if;
327 end loop;
329 return (AF.Controlled with
330 Set => new Wide_Character_Ranges'(Result (1 .. N)));
331 end "or";
333 -----------
334 -- "xor" --
335 -----------
337 function "xor"
338 (Left, Right : Wide_Character_Set) return Wide_Character_Set
340 begin
341 return (Left or Right) - (Left and Right);
342 end "xor";
344 ------------
345 -- Adjust --
346 ------------
348 procedure Adjust (Object : in out Wide_Character_Mapping) is
349 begin
350 Object.Map := new Wide_Character_Mapping_Values'(Object.Map.all);
351 end Adjust;
353 procedure Adjust (Object : in out Wide_Character_Set) is
354 begin
355 Object.Set := new Wide_Character_Ranges'(Object.Set.all);
356 end Adjust;
358 --------------
359 -- Finalize --
360 --------------
362 procedure Finalize (Object : in out Wide_Character_Mapping) is
364 procedure Free is new Ada.Unchecked_Deallocation
365 (Wide_Character_Mapping_Values,
366 Wide_Character_Mapping_Values_Access);
368 begin
369 if Object.Map /= Null_Map'Unrestricted_Access then
370 Free (Object.Map);
371 end if;
372 end Finalize;
374 procedure Finalize (Object : in out Wide_Character_Set) is
376 procedure Free is new Ada.Unchecked_Deallocation
377 (Wide_Character_Ranges,
378 Wide_Character_Ranges_Access);
380 begin
381 if Object.Set /= Null_Range'Unrestricted_Access then
382 Free (Object.Set);
383 end if;
384 end Finalize;
386 ----------------
387 -- Initialize --
388 ----------------
390 procedure Initialize (Object : in out Wide_Character_Mapping) is
391 begin
392 Object := Identity;
393 end Initialize;
395 procedure Initialize (Object : in out Wide_Character_Set) is
396 begin
397 Object := Null_Set;
398 end Initialize;
400 -----------
401 -- Is_In --
402 -----------
404 function Is_In
405 (Element : Wide_Character;
406 Set : Wide_Character_Set) return Boolean
408 L, R, M : Natural;
409 SS : constant Wide_Character_Ranges_Access := Set.Set;
411 begin
412 L := 1;
413 R := SS'Last;
415 -- Binary search loop. The invariant is that if Element is in any of
416 -- of the constituent ranges it is in one between Set (L) and Set (R).
418 loop
419 if L > R then
420 return False;
422 else
423 M := (L + R) / 2;
425 if Element > SS (M).High then
426 L := M + 1;
427 elsif Element < SS (M).Low then
428 R := M - 1;
429 else
430 return True;
431 end if;
432 end if;
433 end loop;
434 end Is_In;
436 ---------------
437 -- Is_Subset --
438 ---------------
440 function Is_Subset
441 (Elements : Wide_Character_Set;
442 Set : Wide_Character_Set) return Boolean
444 ES : constant Wide_Character_Ranges_Access := Elements.Set;
445 SS : constant Wide_Character_Ranges_Access := Set.Set;
447 S : Positive := 1;
448 E : Positive := 1;
450 begin
451 loop
452 -- If no more element ranges, done, and result is true
454 if E > ES'Last then
455 return True;
457 -- If more element ranges, but no more set ranges, result is false
459 elsif S > SS'Last then
460 return False;
462 -- Remove irrelevant set range
464 elsif SS (S).High < ES (E).Low then
465 S := S + 1;
467 -- Get rid of element range that is properly covered by set
469 elsif SS (S).Low <= ES (E).Low
470 and then ES (E).High <= SS (S).High
471 then
472 E := E + 1;
474 -- Otherwise we have a non-covered element range, result is false
476 else
477 return False;
478 end if;
479 end loop;
480 end Is_Subset;
482 ---------------
483 -- To_Domain --
484 ---------------
486 function To_Domain
487 (Map : Wide_Character_Mapping) return Wide_Character_Sequence
489 begin
490 return Map.Map.Domain;
491 end To_Domain;
493 ----------------
494 -- To_Mapping --
495 ----------------
497 function To_Mapping
498 (From, To : Wide_Character_Sequence) return Wide_Character_Mapping
500 Domain : Wide_Character_Sequence (1 .. From'Length);
501 Rangev : Wide_Character_Sequence (1 .. To'Length);
502 N : Natural := 0;
504 begin
505 if From'Length /= To'Length then
506 raise Translation_Error;
508 else
509 pragma Warnings (Off); -- apparent uninit use of Domain
511 for J in From'Range loop
512 for M in 1 .. N loop
513 if From (J) = Domain (M) then
514 raise Translation_Error;
515 elsif From (J) < Domain (M) then
516 Domain (M + 1 .. N + 1) := Domain (M .. N);
517 Rangev (M + 1 .. N + 1) := Rangev (M .. N);
518 Domain (M) := From (J);
519 Rangev (M) := To (J);
520 goto Continue;
521 end if;
522 end loop;
524 Domain (N + 1) := From (J);
525 Rangev (N + 1) := To (J);
527 <<Continue>>
528 N := N + 1;
529 end loop;
531 pragma Warnings (On);
533 return (AF.Controlled with
534 Map => new Wide_Character_Mapping_Values'(
535 Length => N,
536 Domain => Domain (1 .. N),
537 Rangev => Rangev (1 .. N)));
538 end if;
539 end To_Mapping;
541 --------------
542 -- To_Range --
543 --------------
545 function To_Range
546 (Map : Wide_Character_Mapping) return Wide_Character_Sequence
548 begin
549 return Map.Map.Rangev;
550 end To_Range;
552 ---------------
553 -- To_Ranges --
554 ---------------
556 function To_Ranges
557 (Set : Wide_Character_Set) return Wide_Character_Ranges
559 begin
560 return Set.Set.all;
561 end To_Ranges;
563 -----------------
564 -- To_Sequence --
565 -----------------
567 function To_Sequence
568 (Set : Wide_Character_Set) return Wide_Character_Sequence
570 SS : constant Wide_Character_Ranges_Access := Set.Set;
572 Result : Wide_String (Positive range 1 .. 2 ** 16);
573 N : Natural := 0;
575 begin
576 for J in SS'Range loop
577 for K in SS (J).Low .. SS (J).High loop
578 N := N + 1;
579 Result (N) := K;
580 end loop;
581 end loop;
583 return Result (1 .. N);
584 end To_Sequence;
586 ------------
587 -- To_Set --
588 ------------
590 -- Case of multiple range input
592 function To_Set
593 (Ranges : Wide_Character_Ranges) return Wide_Character_Set
595 Result : Wide_Character_Ranges (Ranges'Range);
596 N : Natural := 0;
597 J : Natural;
599 begin
600 -- The output of To_Set is required to be sorted by increasing Low
601 -- values, and discontiguous, so first we sort them as we enter them,
602 -- using a simple insertion sort.
604 pragma Warnings (Off);
605 -- Kill bogus warning on Result being uninitialized
607 for J in Ranges'Range loop
608 for K in 1 .. N loop
609 if Ranges (J).Low < Result (K).Low then
610 Result (K + 1 .. N + 1) := Result (K .. N);
611 Result (K) := Ranges (J);
612 goto Continue;
613 end if;
614 end loop;
616 Result (N + 1) := Ranges (J);
618 <<Continue>>
619 N := N + 1;
620 end loop;
622 pragma Warnings (On);
624 -- Now collapse any contiguous or overlapping ranges
626 J := 1;
627 while J < N loop
628 if Result (J).High < Result (J).Low then
629 N := N - 1;
630 Result (J .. N) := Result (J + 1 .. N + 1);
632 elsif Wide_Character'Succ (Result (J).High) >= Result (J + 1).Low then
633 Result (J).High :=
634 Wide_Character'Max (Result (J).High, Result (J + 1).High);
636 N := N - 1;
637 Result (J + 1 .. N) := Result (J + 2 .. N + 1);
639 else
640 J := J + 1;
641 end if;
642 end loop;
644 if N > 0 and then Result (N).High < Result (N).Low then
645 N := N - 1;
646 end if;
648 return (AF.Controlled with
649 Set => new Wide_Character_Ranges'(Result (1 .. N)));
650 end To_Set;
652 -- Case of single range input
654 function To_Set
655 (Span : Wide_Character_Range) return Wide_Character_Set
657 begin
658 if Span.Low > Span.High then
659 return Null_Set;
660 -- This is safe, because there is no procedure with parameter
661 -- Wide_Character_Set of mode "out" or "in out".
663 else
664 return (AF.Controlled with
665 Set => new Wide_Character_Ranges'(1 => Span));
666 end if;
667 end To_Set;
669 -- Case of wide string input
671 function To_Set
672 (Sequence : Wide_Character_Sequence) return Wide_Character_Set
674 R : Wide_Character_Ranges (1 .. Sequence'Length);
676 begin
677 for J in R'Range loop
678 R (J) := (Sequence (J), Sequence (J));
679 end loop;
681 return To_Set (R);
682 end To_Set;
684 -- Case of single wide character input
686 function To_Set
687 (Singleton : Wide_Character) return Wide_Character_Set
689 begin
690 return
691 (AF.Controlled with
692 Set => new Wide_Character_Ranges'(1 => (Singleton, Singleton)));
693 end To_Set;
695 -----------
696 -- Value --
697 -----------
699 function Value
700 (Map : Wide_Character_Mapping;
701 Element : Wide_Character) return Wide_Character
703 L, R, M : Natural;
705 MV : constant Wide_Character_Mapping_Values_Access := Map.Map;
707 begin
708 L := 1;
709 R := MV.Domain'Last;
711 -- Binary search loop
713 loop
714 -- If not found, identity
716 if L > R then
717 return Element;
719 -- Otherwise do binary divide
721 else
722 M := (L + R) / 2;
724 if Element < MV.Domain (M) then
725 R := M - 1;
727 elsif Element > MV.Domain (M) then
728 L := M + 1;
730 else -- Element = MV.Domain (M) then
731 return MV.Rangev (M);
732 end if;
733 end if;
734 end loop;
735 end Value;
737 end Ada.Strings.Wide_Maps;