OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [ada/] [a-ciormu.ads] - Blame information for rev 826

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 281 jeremybenn
------------------------------------------------------------------------------
2
--                                                                          --
3
--                         GNAT LIBRARY COMPONENTS                          --
4
--                                                                          --
5
--               ADA.CONTAINERS.INDEFINITE_ORDERED_MULTISETS                --
6
--                                                                          --
7
--                                 S p e c                                  --
8
--                                                                          --
9
--          Copyright (C) 2004-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
-- This unit was originally developed by Matthew J Heaney.                  --
28
------------------------------------------------------------------------------
29
 
30
--  The indefinite ordered multiset container is similar to the indefinite
31
--  ordered set, but with the difference that multiple equivalent elements are
32
--  allowed. It also provides additional operations, to iterate over items that
33
--  are equivalent.
34
 
35
private with Ada.Containers.Red_Black_Trees;
36
private with Ada.Finalization;
37
private with Ada.Streams;
38
 
39
generic
40
   type Element_Type (<>) is private;
41
 
42
   with function "<" (Left, Right : Element_Type) return Boolean is <>;
43
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
44
 
45
package Ada.Containers.Indefinite_Ordered_Multisets is
46
   pragma Preelaborate;
47
   pragma Remote_Types;
48
 
49
   function Equivalent_Elements (Left, Right : Element_Type) return Boolean;
50
   --  Returns False if Left is less than Right, or Right is less than Left;
51
   --  otherwise, it returns True.
52
 
53
   type Set is tagged private;
54
   pragma Preelaborable_Initialization (Set);
55
 
56
   type Cursor is private;
57
   pragma Preelaborable_Initialization (Cursor);
58
 
59
   Empty_Set : constant Set;
60
   --  The default value for set objects declared without an explicit
61
   --  initialization expression.
62
 
63
   No_Element : constant Cursor;
64
   --  The default value for cursor objects declared without an explicit
65
   --  initialization expression.
66
 
67
   function "=" (Left, Right : Set) return Boolean;
68
   --  If Left denotes the same set object as Right, then equality returns
69
   --  True. If the length of Left is different from the length of Right, then
70
   --  it returns False. Otherwise, set equality iterates over Left and Right,
71
   --  comparing the element of Left to the element of Right using the equality
72
   --  operator for elements. If the elements compare False, then the iteration
73
   --  terminates and set equality returns False. Otherwise, if all elements
74
   --  compare True, then set equality returns True.
75
 
76
   function Equivalent_Sets (Left, Right : Set) return Boolean;
77
   --  Similar to set equality, but with the difference that elements are
78
   --  compared for equivalence instead of equality.
79
 
80
   function To_Set (New_Item : Element_Type) return Set;
81
   --  Constructs a set object with New_Item as its single element
82
 
83
   function Length (Container : Set) return Count_Type;
84
   --  Returns the total number of elements in Container
85
 
86
   function Is_Empty (Container : Set) return Boolean;
87
   --  Returns True if Container.Length is 0
88
 
89
   procedure Clear (Container : in out Set);
90
   --  Deletes all elements from Container
91
 
92
   function Element (Position : Cursor) return Element_Type;
93
   --  If Position equals No_Element, then Constraint_Error is raised.
94
   --  Otherwise, function Element returns the element designed by Position.
95
 
96
   procedure Replace_Element
97
     (Container : in out Set;
98
      Position  : Cursor;
99
      New_Item  : Element_Type);
100
   --  If Position equals No_Element, then Constraint_Error is raised. If
101
   --  Position is associated with a set different from Container, then
102
   --  Program_Error is raised. If New_Item is equivalent to the element
103
   --  designated by Position, then if Container is locked (element tampering
104
   --  has been attempted), Program_Error is raised; otherwise, the element
105
   --  designated by Position is assigned the value of New_Item. If New_Item is
106
   --  not equivalent to the element designated by Position, then if the
107
   --  container is busy (cursor tampering has been attempted), Program_Error
108
   --  is raised; otherwise, the element designed by Position is assigned the
109
   --  value of New_Item, and the node is moved to its new position (in
110
   --  canonical insertion order).
111
 
112
   procedure Query_Element
113
     (Position : Cursor;
114
      Process  : not null access procedure (Element : Element_Type));
115
   --  If Position equals No_Element, then Constraint_Error is
116
   --  raised. Otherwise, it calls Process with the element designated by
117
   --  Position as the parameter. This call locks the container, so attempts to
118
   --  change the value of the element while Process is executing (to "tamper
119
   --  with elements") will raise Program_Error.
120
 
121
   procedure Move (Target : in out Set; Source : in out Set);
122
   --  If Target denotes the same object as Source, the operation does
123
   --  nothing. If either Target or Source is busy (cursor tampering is
124
   --  attempted), then it raises Program_Error. Otherwise, Target is cleared,
125
   --  and the nodes from Source are moved (not copied) to Target (so Source
126
   --  becomes empty).
127
 
128
   procedure Insert
129
     (Container : in out Set;
130
      New_Item  : Element_Type;
131
      Position  : out Cursor);
132
   --  Insert adds New_Item to Container, and returns cursor Position
133
   --  designating the newly inserted node. The node is inserted after any
134
   --  existing elements less than or equivalent to New_Item (and before any
135
   --  elements greater than New_Item). Note that the issue of where the new
136
   --  node is inserted relative to equivalent elements does not arise for
137
   --  unique-key containers, since in that case the insertion would simply
138
   --  fail. For a multiple-key container (the case here), insertion always
139
   --  succeeds, and is defined such that the new item is positioned after any
140
   --  equivalent elements already in the container.
141
 
142
   procedure Insert (Container : in out Set; New_Item : Element_Type);
143
   --  Inserts New_Item in Container, but does not return a cursor designating
144
   --  the newly-inserted node.
145
 
146
--  TODO: include Replace too???
147
--
148
--     procedure Replace
149
--       (Container : in out Set;
150
--        New_Item  : Element_Type);
151
 
152
   procedure Exclude (Container : in out Set; Item : Element_Type);
153
   --  Deletes from Container all of the elements equivalent to Item
154
 
155
   procedure Delete (Container : in out Set; Item : Element_Type);
156
   --  Deletes from Container all of the elements equivalent to Item. If there
157
   --  are no elements equivalent to Item, then it raises Constraint_Error.
158
 
159
   procedure Delete (Container : in out Set; Position : in out Cursor);
160
   --  If Position equals No_Element, then Constraint_Error is raised. If
161
   --  Position is associated with a set different from Container, then
162
   --  Program_Error is raised. Otherwise, the node designated by Position is
163
   --  removed from Container, and Position is set to No_Element.
164
 
165
   procedure Delete_First (Container : in out Set);
166
   --  Removes the first node from Container
167
 
168
   procedure Delete_Last (Container : in out Set);
169
   --  Removes the last node from Container
170
 
171
   procedure Union (Target : in out Set; Source : Set);
172
   --  If Target is busy (cursor tampering is attempted), then Program_Error is
173
   --  raised. Otherwise, it inserts each element of Source into Target.
174
   --  Elements are inserted in the canonical order for multisets, such that
175
   --  the elements from Source are inserted after equivalent elements already
176
   --  in Target.
177
 
178
   function Union (Left, Right : Set) return Set;
179
   --  Returns a set comprising the all elements from Left and all of the
180
   --  elements from Right. The elements from Right follow the equivalent
181
   --  elements from Left.
182
 
183
   function "or" (Left, Right : Set) return Set renames Union;
184
 
185
   procedure Intersection (Target : in out Set; Source : Set);
186
   --  If Target denotes the same object as Source, the operation does
187
   --  nothing. If Target is busy (cursor tampering is attempted),
188
   --  Program_Error is raised. Otherwise, the elements in Target having no
189
   --  equivalent element in Source are deleted from Target.
190
 
191
   function Intersection (Left, Right : Set) return Set;
192
   --  If Left denotes the same object as Right, then the function returns a
193
   --  copy of Left. Otherwise, it returns a set comprising the equivalent
194
   --  elements from both Left and Right. Items are inserted in the result set
195
   --  in canonical order, such that the elements from Left precede the
196
   --  equivalent elements from Right.
197
 
198
   function "and" (Left, Right : Set) return Set renames Intersection;
199
 
200
   procedure Difference (Target : in out Set; Source : Set);
201
   --  If Target is busy (cursor tampering is attempted), then Program_Error is
202
   --  raised. Otherwise, the elements in Target that are equivalent to
203
   --  elements in Source are deleted from Target.
204
 
205
   function Difference (Left, Right : Set) return Set;
206
   --  Returns a set comprising the elements from Left that have no equivalent
207
   --  element in Right.
208
 
209
   function "-" (Left, Right : Set) return Set renames Difference;
210
 
211
   procedure Symmetric_Difference (Target : in out Set; Source : Set);
212
   --  If Target is busy, then Program_Error is raised. Otherwise, the elements
213
   --  in Target equivalent to elements in Source are deleted from Target, and
214
   --  the elements in Source not equivalent to elements in Target are inserted
215
   --  into Target.
216
 
217
   function Symmetric_Difference (Left, Right : Set) return Set;
218
   --  Returns a set comprising the union of the elements from Target having no
219
   --  equivalent in Source, and the elements of Source having no equivalent in
220
   --  Target.
221
 
222
   function "xor" (Left, Right : Set) return Set renames Symmetric_Difference;
223
 
224
   function Overlap (Left, Right : Set) return Boolean;
225
   --  Returns True if Left contains an element equivalent to an element of
226
   --  Right.
227
 
228
   function Is_Subset (Subset : Set; Of_Set : Set) return Boolean;
229
   --  Returns True if every element in Subset has an equivalent element in
230
   --  Of_Set.
231
 
232
   function First (Container : Set) return Cursor;
233
   --  If Container is empty, the function returns No_Element. Otherwise, it
234
   --  returns a cursor designating the smallest element.
235
 
236
   function First_Element (Container : Set) return Element_Type;
237
   --  Equivalent to Element (First (Container))
238
 
239
   function Last (Container : Set) return Cursor;
240
   --  If Container is empty, the function returns No_Element. Otherwise, it
241
   --  returns a cursor designating the largest element.
242
 
243
   function Last_Element (Container : Set) return Element_Type;
244
   --  Equivalent to Element (Last (Container))
245
 
246
   function Next (Position : Cursor) return Cursor;
247
   --  If Position equals No_Element or Last (Container), the function returns
248
   --  No_Element. Otherwise, it returns a cursor designating the node that
249
   --  immediately follows (as per the insertion order) the node designated by
250
   --  Position.
251
 
252
   procedure Next (Position : in out Cursor);
253
   --  Equivalent to Position := Next (Position)
254
 
255
   function Previous (Position : Cursor) return Cursor;
256
   --  If Position equals No_Element or First (Container), the function returns
257
   --  No_Element. Otherwise, it returns a cursor designating the node that
258
   --  immediately precedes (as per the insertion order) the node designated by
259
   --  Position.
260
 
261
   procedure Previous (Position : in out Cursor);
262
   --  Equivalent to Position := Previous (Position)
263
 
264
   function Find (Container : Set; Item : Element_Type) return Cursor;
265
   --  Returns a cursor designating the first element in Container equivalent
266
   --  to Item. If there is no equivalent element, it returns No_Element.
267
 
268
   function Floor (Container : Set; Item : Element_Type) return Cursor;
269
   --  If Container is empty, the function returns No_Element. If Item is
270
   --  equivalent to elements in Container, it returns a cursor designating the
271
   --  first equivalent element. Otherwise, it returns a cursor designating the
272
   --  largest element less than Item, or No_Element if all elements are
273
   --  greater than Item.
274
 
275
   function Ceiling (Container : Set; Item : Element_Type) return Cursor;
276
   --  If Container is empty, the function returns No_Element. If Item is
277
   --  equivalent to elements of Container, it returns a cursor designating the
278
   --  last equivalent element. Otherwise, it returns a cursor designating the
279
   --  smallest element greater than Item, or No_Element if all elements are
280
   --  less than Item.
281
 
282
   function Contains (Container : Set; Item : Element_Type) return Boolean;
283
   --  Equivalent to Container.Find (Item) /= No_Element
284
 
285
   function Has_Element (Position : Cursor) return Boolean;
286
   --  Equivalent to Position /= No_Element
287
 
288
   function "<" (Left, Right : Cursor) return Boolean;
289
   --  Equivalent to Element (Left) < Element (Right)
290
 
291
   function ">" (Left, Right : Cursor) return Boolean;
292
   --  Equivalent to Element (Right) < Element (Left)
293
 
294
   function "<" (Left : Cursor; Right : Element_Type) return Boolean;
295
   --  Equivalent to Element (Left) < Right
296
 
297
   function ">" (Left : Cursor; Right : Element_Type) return Boolean;
298
   --  Equivalent to Right < Element (Left)
299
 
300
   function "<" (Left : Element_Type; Right : Cursor) return Boolean;
301
   --  Equivalent to Left < Element (Right)
302
 
303
   function ">" (Left : Element_Type; Right : Cursor) return Boolean;
304
   --  Equivalent to Element (Right) < Left
305
 
306
   procedure Iterate
307
     (Container : Set;
308
      Process   : not null access procedure (Position : Cursor));
309
   --  Calls Process with a cursor designating each element of Container, in
310
   --  order from Container.First to Container.Last.
311
 
312
   procedure Reverse_Iterate
313
     (Container : Set;
314
      Process   : not null access procedure (Position : Cursor));
315
   --  Calls Process with a cursor designating each element of Container, in
316
   --  order from Container.Last to Container.First.
317
 
318
   procedure Iterate
319
     (Container : Set;
320
      Item      : Element_Type;
321
      Process   : not null access procedure (Position : Cursor));
322
   --  Call Process with a cursor designating each element equivalent to Item,
323
   --  in order from Container.Floor (Item) to Container.Ceiling (Item).
324
 
325
   procedure Reverse_Iterate
326
     (Container : Set;
327
      Item      : Element_Type;
328
      Process   : not null access procedure (Position : Cursor));
329
   --  Call Process with a cursor designating each element equivalent to Item,
330
   --  in order from Container.Ceiling (Item) to Container.Floor (Item).
331
 
332
   generic
333
      type Key_Type (<>) is private;
334
 
335
      with function Key (Element : Element_Type) return Key_Type;
336
 
337
      with function "<" (Left, Right : Key_Type) return Boolean is <>;
338
 
339
   package Generic_Keys is
340
 
341
      function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
342
      --  Returns False if Left is less than Right, or Right is less than Left;
343
      --  otherwise, it returns True.
344
 
345
      function Key (Position : Cursor) return Key_Type;
346
      --  Equivalent to Key (Element (Position))
347
 
348
      function Element (Container : Set; Key : Key_Type) return Element_Type;
349
      --  Equivalent to Element (Find (Container, Key))
350
 
351
      procedure Exclude (Container : in out Set; Key : Key_Type);
352
      --  Deletes from Container any elements whose key is equivalent to Key
353
 
354
      procedure Delete (Container : in out Set; Key : Key_Type);
355
      --  Deletes from Container any elements whose key is equivalent to
356
      --  Key. If there are no such elements, then it raises Constraint_Error.
357
 
358
      function Find (Container : Set; Key : Key_Type) return Cursor;
359
      --  Returns a cursor designating the first element in Container whose key
360
      --  is equivalent to Key. If there is no equivalent element, it returns
361
      --  No_Element.
362
 
363
      function Floor (Container : Set; Key : Key_Type) return Cursor;
364
      --  If Container is empty, the function returns No_Element. If Item is
365
      --  equivalent to the keys of elements in Container, it returns a cursor
366
      --  designating the first such element. Otherwise, it returns a cursor
367
      --  designating the largest element whose key is less than Item, or
368
      --  No_Element if all keys are greater than Item.
369
 
370
      function Ceiling (Container : Set; Key : Key_Type) return Cursor;
371
      --  If Container is empty, the function returns No_Element. If Item is
372
      --  equivalent to the keys of elements of Container, it returns a cursor
373
      --  designating the last such element. Otherwise, it returns a cursor
374
      --  designating the smallest element whose key is greater than Item, or
375
      --  No_Element if all keys are less than Item.
376
 
377
      function Contains (Container : Set; Key : Key_Type) return Boolean;
378
      --  Equivalent to Find (Container, Key) /= No_Element
379
 
380
      procedure Update_Element  -- Update_Element_Preserving_Key ???
381
        (Container : in out Set;
382
         Position  : Cursor;
383
         Process   : not null access
384
                       procedure (Element : in out Element_Type));
385
      --  If Position equals No_Element, then Constraint_Error is raised. If
386
      --  Position is associated with a set object different from Container,
387
      --  then Program_Error is raised. Otherwise, it makes a copy of the key
388
      --  of the element designated by Position, and then calls Process with
389
      --  the element as the parameter. Update_Element then compares the key
390
      --  value obtained before calling Process to the key value obtained from
391
      --  the element after calling Process. If the keys are equivalent then
392
      --  the operation terminates. If Container is busy (cursor tampering has
393
      --  been attempted), then Program_Error is raised. Otherwise, the node
394
      --  is moved to its new position (in canonical order).
395
 
396
      procedure Iterate
397
        (Container : Set;
398
         Key       : Key_Type;
399
         Process   : not null access procedure (Position : Cursor));
400
      --  Call Process with a cursor designating each element equivalent to
401
      --  Key, in order from Floor (Container, Key) to
402
      --  Ceiling (Container, Key).
403
 
404
      procedure Reverse_Iterate
405
        (Container : Set;
406
         Key       : Key_Type;
407
         Process   : not null access procedure (Position : Cursor));
408
      --  Call Process with a cursor designating each element equivalent to
409
      --  Key, in order from Ceiling (Container, Key) to
410
      --  Floor (Container, Key).
411
 
412
   end Generic_Keys;
413
 
414
private
415
 
416
   pragma Inline (Next);
417
   pragma Inline (Previous);
418
 
419
   type Node_Type;
420
   type Node_Access is access Node_Type;
421
 
422
   type Element_Access is access Element_Type;
423
 
424
   type Node_Type is limited record
425
      Parent  : Node_Access;
426
      Left    : Node_Access;
427
      Right   : Node_Access;
428
      Color   : Red_Black_Trees.Color_Type := Red_Black_Trees.Red;
429
      Element : Element_Access;
430
   end record;
431
 
432
   package Tree_Types is new Red_Black_Trees.Generic_Tree_Types
433
     (Node_Type,
434
      Node_Access);
435
 
436
   type Set is new Ada.Finalization.Controlled with record
437
      Tree : Tree_Types.Tree_Type;
438
   end record;
439
 
440
   overriding
441
   procedure Adjust (Container : in out Set);
442
 
443
   overriding
444
   procedure Finalize (Container : in out Set) renames Clear;
445
 
446
   use Red_Black_Trees;
447
   use Tree_Types;
448
   use Ada.Finalization;
449
   use Ada.Streams;
450
 
451
   type Set_Access is access all Set;
452
   for Set_Access'Storage_Size use 0;
453
 
454
   type Cursor is record
455
      Container : Set_Access;
456
      Node      : Node_Access;
457
   end record;
458
 
459
   procedure Write
460
     (Stream : not null access Root_Stream_Type'Class;
461
      Item   : Cursor);
462
 
463
   for Cursor'Write use Write;
464
 
465
   procedure Read
466
     (Stream : not null access Root_Stream_Type'Class;
467
      Item   : out Cursor);
468
 
469
   for Cursor'Read use Read;
470
 
471
   No_Element : constant Cursor := Cursor'(null, null);
472
 
473
   procedure Write
474
     (Stream    : not null access Root_Stream_Type'Class;
475
      Container : Set);
476
 
477
   for Set'Write use Write;
478
 
479
   procedure Read
480
     (Stream    : not null access Root_Stream_Type'Class;
481
      Container : out Set);
482
 
483
   for Set'Read use Read;
484
 
485
   Empty_Set : constant Set :=
486
                 (Controlled with Tree => (First  => null,
487
                                           Last   => null,
488
                                           Root   => null,
489
                                           Length => 0,
490
                                           Busy   => 0,
491
                                           Lock   => 0));
492
 
493
end Ada.Containers.Indefinite_Ordered_Multisets;

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.