summaryrefslogtreecommitdiff
path: root/gcc/ada/a-crbtgk.ads
diff options
context:
space:
mode:
authorcharlet <charlet@138bc75d-0d04-0410-961f-82ee72b054a4>2006-10-31 18:13:22 +0000
committercharlet <charlet@138bc75d-0d04-0410-961f-82ee72b054a4>2006-10-31 18:13:22 +0000
commitd9e74e050bd1ae08f4be72f63784a42c0973a94a (patch)
tree1a5cb845f084a8360d6f2bc2dd674427a1a51b02 /gcc/ada/a-crbtgk.ads
parentad67c992e9102a7a00351747f46956e56b6f0c3f (diff)
downloadgcc-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.ads127
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;