diff options
author | charlet <charlet@138bc75d-0d04-0410-961f-82ee72b054a4> | 2006-10-31 18:13:22 +0000 |
---|---|---|
committer | charlet <charlet@138bc75d-0d04-0410-961f-82ee72b054a4> | 2006-10-31 18:13:22 +0000 |
commit | d9e74e050bd1ae08f4be72f63784a42c0973a94a (patch) | |
tree | 1a5cb845f084a8360d6f2bc2dd674427a1a51b02 /gcc/ada/a-crbtgk.ads | |
parent | ad67c992e9102a7a00351747f46956e56b6f0c3f (diff) | |
download | gcc-d9e74e050bd1ae08f4be72f63784a42c0973a94a.tar.gz |
2006-10-31 Matt Heaney <heaney@adacore.com>
* a-crbtgo.ads: Commented each subprogram
* a-crbtgo.adb: Added reference to book from which algorithms were
adapted.
* a-crbtgk.ads, a-crbtgk.adb (Generic_Insert_Post): pass flag to
indicate which child.
(Generic_Conditional_Insert): changed parameter name from "Success" to
"Inserted".
(Generic_Unconditional_Insert_With_Hint): improved algorithm
* a-coorse.adb (Replace_Element): changed parameter name in call to
conditional insert operation.
* a-convec.adb, a-coinve.adb (Insert): removed obsolete comment
* a-cohama.adb (Iterate): manipulate busy-bit here, instead of in
Generic_Iteration
* a-ciorse.adb (Replace_Element): changed parameter name in call to
conditional insert operation.
* a-cihama.adb (Iterate): manipulate busy-bit here, instead of in
Generic_Iteration.
* a-cidlli.ads, a-cidlli.adb (Splice): Position param is now mode in
instead of mode inout.
* a-chtgop.adb (Adjust): modified comments to reflect current AI-302
draft
(Generic_Read): preserve existing buckets array if possible
(Generic_Write): don't send buckets array length anymore
* a-cdlili.ads, a-cdlili.adb (Splice): Position param is now mode in
instead of mode inout.
* a-cihase.adb (Difference): iterate over smaller of Tgt and Src sets
(Iterate): manipulate busy-bit here, instead of in Generic_Iteration
* a-cohase.adb (Difference): iterate over smaller of Tgt and Src sets
(Iterate): manipulate busy-bit here, instead of in Generic_Iteration
(Replace_Element): local operation is now an instantiation
* a-chtgke.ads, a-chtgke.adb (Generic_Conditional_Insert): manually
check current length.
(Generic_Replace_Element): new operation
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@118324 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'gcc/ada/a-crbtgk.ads')
-rw-r--r-- | gcc/ada/a-crbtgk.ads | 127 |
1 files changed, 93 insertions, 34 deletions
diff --git a/gcc/ada/a-crbtgk.ads b/gcc/ada/a-crbtgk.ads index e1a3824a953..1e8c4fd9eb2 100644 --- a/gcc/ada/a-crbtgk.ads +++ b/gcc/ada/a-crbtgk.ads @@ -7,13 +7,32 @@ -- -- -- S p e c -- -- -- --- This specification is adapted from the Ada Reference Manual for use with -- --- GNAT. In accordance with the copyright of that document, you can freely -- --- copy and modify this specification, provided that if you redistribute a -- --- modified version, any changes that you have made are clearly indicated. -- +-- Copyright (C) 2004-2006, Free Software Foundation, Inc. -- -- -- +-- GNAT is free software; you can redistribute it and/or modify it under -- +-- terms of the GNU General Public License as published by the Free Soft- -- +-- ware Foundation; either version 2, or (at your option) any later ver- -- +-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- +-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- +-- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -- +-- for more details. You should have received a copy of the GNU General -- +-- Public License distributed with GNAT; see file COPYING. If not, write -- +-- to the Free Software Foundation, 51 Franklin Street, Fifth Floor, -- +-- Boston, MA 02110-1301, USA. -- +-- -- +-- As a special exception, if other files instantiate generics from this -- +-- unit, or you link this unit with other files to produce an executable, -- +-- this unit does not by itself cause the resulting executable to be -- +-- covered by the GNU General Public License. This exception does not -- +-- however invalidate any other reasons why the executable file might be -- +-- covered by the GNU Public License. -- +-- -- +-- This unit was originally developed by Matthew J Heaney. -- ------------------------------------------------------------------------------ +-- Tree_Type is used to implement ordered containers. This package declares +-- the tree operations that depend on keys. + with Ada.Containers.Red_Black_Trees.Generic_Operations; generic @@ -37,42 +56,58 @@ package Ada.Containers.Red_Black_Trees.Generic_Keys is generic with function New_Node return Node_Access; procedure Generic_Insert_Post - (Tree : in out Tree_Type; - X, Y : Node_Access; - Key : Key_Type; - Z : out Node_Access); + (Tree : in out Tree_Type; + Y : Node_Access; + Before : Boolean; + Z : out Node_Access); + -- Completes an insertion after the insertion position has been + -- determined. On output Z contains a pointer to the newly inserted + -- node, allocated using New_Node. If Tree is busy then + -- Program_Error is raised. If Y is null, then Tree must be empty. + -- Otherwise Y denotes the insertion position, and Before specifies + -- whether the new node is Y's left (True) or right (False) child. generic with procedure Insert_Post - (Tree : in out Tree_Type; - X, Y : Node_Access; - Key : Key_Type; - Z : out Node_Access); + (T : in out Tree_Type; + Y : Node_Access; + B : Boolean; + Z : out Node_Access); procedure Generic_Conditional_Insert - (Tree : in out Tree_Type; - Key : Key_Type; - Node : out Node_Access; - Success : out Boolean); + (Tree : in out Tree_Type; + Key : Key_Type; + Node : out Node_Access; + Inserted : out Boolean); + -- Inserts a new node in Tree, but only if the tree does not already + -- contain Key. Generic_Conditional_Insert first searches for a key + -- equivalent to Key in Tree. If an equivalent key is found, then on + -- output Node designates the node with that key and Inserted is + -- False; there is no allocation and Tree is not modified. Otherwise + -- Node designates a new node allocated using Insert_Post, and + -- Inserted is True. generic with procedure Insert_Post - (Tree : in out Tree_Type; - X, Y : Node_Access; - Key : Key_Type; - Z : out Node_Access); + (T : in out Tree_Type; + Y : Node_Access; + B : Boolean; + Z : out Node_Access); procedure Generic_Unconditional_Insert (Tree : in out Tree_Type; Key : Key_Type; Node : out Node_Access); + -- Inserts a new node in Tree. On output Node designates the new + -- node, which is allocated using Insert_Post. The node is inserted + -- immediately after already-existing equivalent keys. generic with procedure Insert_Post - (Tree : in out Tree_Type; - X, Y : Node_Access; - Key : Key_Type; - Z : out Node_Access); + (T : in out Tree_Type; + Y : Node_Access; + B : Boolean; + Z : out Node_Access); with procedure Unconditional_Insert_Sans_Hint (Tree : in out Tree_Type; @@ -84,53 +119,77 @@ package Ada.Containers.Red_Black_Trees.Generic_Keys is Hint : Node_Access; Key : Key_Type; Node : out Node_Access); + -- Inserts a new node in Tree near position Hint, to avoid having to + -- search from the root for the insertion position. If Hint is null + -- then Generic_Unconditional_Insert_With_Hint attempts to insert + -- the new node after Tree.Last. If Hint is non-null then if Key is + -- less than Hint, it attempts to insert the new node immediately + -- prior to Hint. Otherwise it attempts to insert the node + -- immediately following Hint. We say "attempts" above to emphasize + -- that insertions always preserve invariants with respect to key + -- order, even when there's a hint. So if Key can't be inserted + -- immediately near Hint, then the new node is inserted in the + -- normal way, by searching for the correct position starting from + -- the root. generic with procedure Insert_Post - (Tree : in out Tree_Type; - X, Y : Node_Access; - Key : Key_Type; - Z : out Node_Access); + (T : in out Tree_Type; + Y : Node_Access; + B : Boolean; + Z : out Node_Access); with procedure Conditional_Insert_Sans_Hint - (Tree : in out Tree_Type; - Key : Key_Type; - Node : out Node_Access; - Success : out Boolean); + (Tree : in out Tree_Type; + Key : Key_Type; + Node : out Node_Access; + Inserted : out Boolean); procedure Generic_Conditional_Insert_With_Hint (Tree : in out Tree_Type; - Position : Node_Access; + Position : Node_Access; -- the hint Key : Key_Type; Node : out Node_Access; - Success : out Boolean); + Inserted : out Boolean); + -- Inserts a new node in Tree if the tree does not already contain + -- Key, using Position as a hint about where to insert the new node. + -- See Generic_Unconditional_Insert_With_Hint for more details about + -- hint semantics. function Find (Tree : Tree_Type; Key : Key_Type) return Node_Access; + -- Searches Tree for the smallest node equivalent to Key function Ceiling (Tree : Tree_Type; Key : Key_Type) return Node_Access; + -- Searches Tree for the smallest node equal to or greater than Key function Floor (Tree : Tree_Type; Key : Key_Type) return Node_Access; + -- Searches Tree for the largest node less than or equal to Key function Upper_Bound (Tree : Tree_Type; Key : Key_Type) return Node_Access; + -- Searches Tree for the smallest node greater than Key generic with procedure Process (Node : Node_Access); procedure Generic_Iteration (Tree : Tree_Type; Key : Key_Type); + -- Calls Process for each node in Tree equivalent to Key, in order + -- from earliest in range to latest. generic with procedure Process (Node : Node_Access); procedure Generic_Reverse_Iteration (Tree : Tree_Type; Key : Key_Type); + -- Calls Process for each node in Tree equivalent to Key, but in + -- order from largest in range to earliest. end Ada.Containers.Red_Black_Trees.Generic_Keys; |