home *** CD-ROM | disk | FTP | other *** search
Text File | 1988-05-03 | 1007.0 KB | 29,927 lines |
- ::::::::::::::
- block_u.bdy
- ::::::::::::::
- --VMS file: %nosc.work.tools.halstead.source*(block_u.bdy)
- --UTS file: /nosccomp/byron/_vms//nosc/work/tools/halstead/COMP/block_u.bdy
- -- $Source: /nosc/work/tools/halstead/RCS/block_u.bdy,v $
- -- $Revision: 1.2 $ -- $Date: 86/02/04 22:05:46 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.2 $");
-
- with ML_Source_Position_Pkg;
- package body Block_Utilities is
-
- package MLSP renames ML_Source_Position_Pkg;
- --------------------------------------------------------------------------
- -- LOCAL SUBPROGRAMS
- --------------------------------------------------------------------------
-
- function Is_Source_Position_Null (
- Position :in MLSP.Source_Position
- ) return boolean;
-
- --| OVERVIEW
- --| This procedure returns true if the source position passed in
- --| is null. This means that column and line of the
- --| Position.first_location is 0.
-
- --------------------------------------------------------------------------
-
- function In_Declare_Block ( --| This function determines whether
- --| we are in a block with declarations.
- --| If we are it returns true otherwise
- --| false.
- block :in BLOCK_STUB.Locator
- ) return boolean is
-
- use SeqOfITEM;
- I :Generator;
-
- begin
- --| OVERVIEW
- --| This function is used to determined if in fact the block
- --| passed in is a block with explicit declarations which
- --| means the token declare appears in the source program.
- --| This is determined by walking down the list of declarations
- --| until something which is not an implicit label is encountered.
- --| Implicit labels are inserted in the as_item_s list
- --| of the enclosing block. Thus if the only elements of the
- --| as_item_s of the block are implicit_labels then the token
- --| declare does not appear in the source program.
-
- StartForward (as_item_s (block), I);
- while not Finished(I) loop
- case Kind (Cell (I)) is
- when implicit_label_declKind =>
- Forward (I);
- when others =>
- EndIterate (I);
- return true;
- end case;
- end loop;
- EndIterate (I);
- return false;
- end In_declare_block;
-
- --------------------------------------------------------------------------
-
- function Is_Block_Labeled ( --| This function returns true
- --| if the block passed in has a label
- --| and returns false otherwise.
- block :in block_stmNode.Locator
- ) return boolean is
- begin
- return not Is_Source_Position_Null (
- lx_srcpos (as_block_label (block))
- );
- end;
-
- --------------------------------------------------------------------------
-
- function Is_Source_Position_Null (
- Position :in MLSP.Source_Position
- ) return boolean is
- begin
- return MLSP."=" (Position.first_location,0);
- end;
-
- end Block_Utilities;
- ::::::::::::::
- block_u.spc
- ::::::::::::::
- --VMS file: %nosc.work.tools.halstead.source*(block_u.spc)
- --UTS file: /nosccomp/byron/_vms//nosc/work/tools/halstead/COMP/block_u.spc
- -- $Source: /nosc/work/tools/halstead/RCS/block_u.spc,v $
- -- $Revision: 1.2 $ -- $Date: 86/02/04 22:05:09 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.2 $");
-
-
- with ST_DIANA; use ST_DIANA;
- package Block_Utilities is
- --------------------------------------------------------------------------
-
- function In_Declare_Block ( --| This function determines whether
- --| we are in a block with declarations.
- --| If we are it returns true otherwise
- --| false.
- block :in BLOCK_STUB.Locator
- ) return boolean;
-
-
- function Is_Block_Labeled ( --| This function returns true
- --| if the block passed in has a label
- --| and returns false otherwise.
- block :in block_stmNode.Locator
- ) return boolean;
- end Block_Utilities;
- ::::::::::::::
- comlin.bdy
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/comlin.bdy,v $
- -- $Revision: 1.18 $ -- $Date: 85/03/25 21:03:22 $ -- $Author: buddy $
- with Text_IO; use Text_IO;
- with Int_IO; use Int_IO;
- package body CommandLine is
- TokenSeparator :constant character := '%';
-
- --------------------------------------------------------------------------
- procedure ScanForChar (
- S :in String;
- C :in character;
- Start :in positive;
- Place : out natural
- ) is
- Temp :positive := Start;
- Found :boolean := false;
- begin
-
- Place := 0;
- while (Temp <= S'Last) and (not Found) loop
- if S(Temp) = C then
- Place := Temp;
- Found := true;
- end if;
- Temp := Temp + 1;
- end loop;
- end;
-
- --------------------------------------------------------------------------
-
- function GetNumberOfUnits(
- S :in String
- ) return natural is
-
- count :natural := 0;
- begin
- for i in S'Range loop
- if S(i) = TokenSeparator then
- count := count + 1;
- end if;
- end loop;
- return count;
- end;
-
- --------------------------------------------------------------------------
-
- function GetToken (
- S :in String;
- Start :in positive
- ) return String is
- EndOfToken :natural;
- begin
-
- ScanForChar (S, TokenSeparator, Start, EndOfToken);
- if EndOfToken = 0 then
- raise TokenNotFound;
- else
- return S(Start..EndOfToken - 1);
- end if;
- end;
-
- --------------------------------------------------------------------------
-
- procedure Advance (
- S :in String;
- Start :in out positive
- ) is
- begin
- Start := Start + GetToken (S, Start)'Length + 1;
- end;
-
- --------------------------------------------------------------------------
-
- function GetSpec (
- S :in String;
- Start :in positive
- ) return boolean is
- begin
-
- if boolean'Value (GetToken (S, Start)) in false..true then
- return boolean'Value (GetToken (S, Start));
- end if;
- exception
- when CONSTRAINT_ERROR =>
- raise ExpectingBoolean;
- end;
-
- --------------------------------------------------------------------------
-
- function IsSubUnit (
- S :in String;
- Start :in positive
- ) return boolean is
- PeriodPosition :natural;
- begin
- ScanForChar (S, '.', Start, PeriodPosition);
- if (S'First < PeriodPosition) and (PeriodPosition < S'Last) then
- return true;
- else
- return false;
- end if;
- end;
-
- --------------------------------------------------------------------------
-
- function GetParent (
- S :in String;
- Start :in positive
- ) return String is
- PeriodPosition :natural;
- begin
- ScanForChar (S, '.', Start, PeriodPosition);
- if PeriodPosition = 0 then
- raise InvalidSubUnit;
- else
- Return S(Start..PeriodPosition - 1);
- end if;
- end;
-
- --------------------------------------------------------------------------
-
- function GetSubUnit (
- S :in String;
- Start :in positive
- ) return String is
- PeriodPosition :natural;
- EndToken :natural;
- begin
- ScanForChar (S, '.', Start, PeriodPosition);
- ScanForChar (S, TokenSeparator, PeriodPosition, EndToken);
- if EndToken = 0 then
- raise InvalidSubUnit;
- else
- return S(PeriodPosition + 1..EndToken - 1);
- end if;
- end;
-
- --------------------------------------------------------------------------
-
- end CommandLine;
- ::::::::::::::
- comlin.spc
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/comlin.spc,v $
- -- $Revision: 1.5 $ -- $Date: 85/03/24 16:17:23 $ -- $Author: buddy $
-
- package CommandLine is
- TokenNotFound :exception;
- ExpectingBoolean :exception;
- InvalidSubUnit :exception;
-
- function GetNumberOfUnits(
- S :in String
- ) return natural;
-
- --------------------------------------------------------------------------
-
- procedure Advance (
- S :in String;
- Start :in out positive
- );
-
- --------------------------------------------------------------------------
-
- function GetToken (
- S :in String;
- Start :in positive
- ) return String;
-
- --------------------------------------------------------------------------
-
- function IsSubUnit (
- S :in String;
- Start :in positive
- ) return boolean;
-
- --------------------------------------------------------------------------
-
- function GetParent (
- S :in String;
- Start :in positive
- ) return String;
-
- --------------------------------------------------------------------------
-
- function GetSpec (
- S :in String;
- Start :in positive
- ) return boolean;
-
- --------------------------------------------------------------------------
-
- function GetSubUnit (
- S :in String;
- Start :in positive
- ) return String;
-
- --------------------------------------------------------------------------
-
- end CommandLine;
- ::::::::::::::
- count.bdy
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/count5.bdy,v $
- -- $Revision: 1.1 $ -- $Date: 85/12/31 14:51:21 $ -- $Author: maria $
-
- --pragma revision ("$Revision: 1.1 $");
-
- -- $Source: /nosc/work/tools/halstead/RCS/count5.bdy,v $
- -- $Revision: 1.1 $ -- $Date: 85/12/31 14:51:21 $ -- $Author: maria $
-
- --pragma revision ("$Revision: 1.1 $");
-
- -- $Source: /nosc/work/tools/halstead/RCS/count5.bdy,v $
- -- $Revision: 1.1 $ -- $Date: 85/12/31 14:51:21 $ -- $Author: maria $
-
- --pragma revision ("$Revision: 1.1 $");
-
- -- $Source: /nosc/work/tools/halstead/RCS/count5.bdy,v $
- -- $Revision: 1.1 $ -- $Date: 85/12/31 14:51:21 $ -- $Author: maria $
-
- --pragma revision ("$Revision: 1.1 $");
-
- with Text_IO; use Text_IO;
- with Int_IO; use Int_IO;
- package body count is
- TokenClassification: array (D.TokenItem) of D.Class := (
- D.abortz => D.operator,
- D.acceptz => D.operator,
- D.accessz => D.operator,
- D.allz => D.operator,
- D.and_thenz => D.operator,
- D.arrayz => D.operator,
- D.atz => D.neither,
- D.beginz => D.neither,
- D.bodyz => D.neither,
- D.body_packagez => D.neither,
- D.body_taskz => D.neither,
- D.casez => D.neither,
- D.case_stmz => D.neither,
- D.case_variantz => D.neither,
- D.constantz => D.operator,
- D.declarez => D.operator,
- D.delayz => D.operator,
- D.deltaz => D.operator,
- D.digitsz => D.operator,
- D.doz => D.neither,
- D.elsez => D.operator,
- D.else_ifz => D.operator,
- D.else_orz => D.operator,
- D.else_selectz => D.operator,
- D.elsifz => D.operator,
- D.endz => D.neither,
- D.end_acceptz => D.neither,
- D.end_beginz => D.neither,
- D.end_case_stmz => D.operator,
- D.end_case_variantz => D.operator,
- D.end_ifz => D.operator,
- D.end_loopz => D.operator,
- D.end_package_bdyz => D.operator,
- D.end_package_spcz => D.operator,
- D.end_recordz => D.operator,
- D.end_record_repz => D.operator,
- D.end_selectz => D.operator,
- D.end_task_spcz => D.operator,
- D.entryz => D.operator,
- D.exceptionz => D.operator,
- D.exitz => D.operator,
- D.forz => D.neither,
- D.for_loopz => D.neither,
- D.for_repz => D.neither,
- D.functionz => D.operator,
- D.genericz => D.operator,
- D.gotoz => D.operator,
- D.ifz => D.neither,
- D.inz => D.operator,
- D.in_loopz => D.operator,
- D.in_membershipz => D.operator,
- D.in_out_parameterz => D.neither,
- D.in_parameterz => D.neither,
- D.isz => D.neither,
- D.is_case_stmz => D.neither,
- D.is_case_variantz => D.neither,
- D.is_functionz => D.neither,
- D.is_genericz => D.neither,
- D.is_package_bdyz => D.neither,
- D.is_package_spcz => D.neither,
- D.is_procedurez => D.neither,
- D.is_separatez => D.operator,
- D.is_subtypez => D.neither,
- D.is_typez => D.neither,
- D.is_task_bdyz => D.neither,
- D.is_task_spcz => D.neither,
- D.limitedz => D.operator,
- D.loopz => D.neither,
- D.modz => D.operator,
- D.newz => D.neither,
- D.new_allocatorz => D.operator,
- D.new_derived_typez => D.operator,
- D.new_generic_instz => D.operator,
- D.not_in_membershipz => D.operator,
- D.nullz => D.neither,
- D.null_valuez => D.operand,
- D.null_stmz => D.operator,
- D.null_fieldz => D.operator,
- D.ofz => D.operator,
- D.orz => D.operator,
- D.or_elsez => D.operator,
- D.or_selectz => D.operator,
- D.othersz => D.neither,
- D.others_aggregatez => D.operator,
- D.others_casez => D.operator,
- D.others_exceptionz => D.operator,
- D.others_variantz => D.operator,
- D.outz => D.neither,
- D.packagez => D.neither,
- D.package_bdyz => D.neither,
- D.package_spcz => D.neither,
- D.pragmaz => D.operator,
- D.privatez => D.neither,
- D.private_sectionz => D.operator,
- D.private_typez => D.operator,
- D.procedurez => D.neither,
- D.raisez => D.operator,
- D.rangez => D.operator,
- D.recordz => D.neither,
- D.record_typez => D.neither,
- D.record_repz => D.neither,
- D.renamesz => D.operator,
- D.returnz => D.operator,
- D.reversez => D.operator,
- D.selectz => D.neither,
- D.separatez => D.neither,
- D.subtypez => D.operator,
- D.taskz => D.neither,
- D.task_bdyz => D.neither,
- D.task_spcz => D.neither,
- D.terminatez => D.operator,
- D.thenz => D.neither,
- D.then_andz => D.operator,
- D.typez => D.operator,
- D.usez => D.neither,
- D.use_contextz => D.operator,
- D.use_repz => D.operator,
- D.whenz => D.neither,
- D.when_case_stmz => D.neither,
- D.when_exitz => D.neither,
- D.when_exceptionz => D.neither,
- D.when_selectz => D.neither,
- D.when_case_variantz => D.neither,
- D.whilez => D.operator,
- D.withz => D.neither,
- D.with_contextz => D.operator,
- D.with_genericz => D.operator,
- ------------- punctuation --------------
- D.arrowz => D.operator,
- D.barz => D.operator,
- D.boxz => D.neither,
- D.box_rangez => D.operator,
- D.box_default_subpz => D.operator,
- D.character_literalz => D.operand,
- D.closed_anglesz => D.neither,
- D.closed_parenthesisz => D.neither,
- D.colon_equalsz => D.operator,
- D.colonz => D.operator,
- D.commaz => D.operator,
- D.dotz => D.operator,
- D.dot_dot_rangez => D.operator,
- D.double_quotez => D.operand,
- D.numeric_literalz => D.operand,
- D.open_anglesz => D.operator,
- D.open_parenthesisz => D.operator,
- D.semicolonz => D.neither,
- D.single_quotez => D.neither,
- D.tickz => D.operator,
- D.declare_blockz => D.neither
- );
- --| This is a map from token types to symbol classification.
- --| It indicates which class (D.operator, operand, neither)
- --| a token is in.
-
- --------------------------------------------------------------------------
-
- function RemoveLastChar ( --| This removes the last character from
- --| the string S. This is used to get
- --| rid of the z's in the TokenItems.
- S :in String
- ) return String is
-
- begin
- return S(S'first..S'last - 1);
- end;
-
- --------------------------------------------------------------------------
-
- procedure HalsteadCount (
- TokenInfo :in D.TokenCountType;
- VerboseOn :in boolean;
- Nn: in out CT.NnInfoType
- ) is
- begin
- for t in D.TokenItem loop
- if TokenInfo(t) > 0 then
- Nn(TokenClassification(t)).Vocabulary :=
- Nn(TokenClassification(t)).Vocabulary + 1;
- Nn(TokenClassification(t)).Usage :=
- Nn(TokenClassification(t)).Usage + TokenInfo(t);
-
- if VerboseOn then
- Put (Standard_Output, "number of ");
- Put (Standard_Output,
- RemoveLastChar (D.TokenItem ' image (t)));
- Put (Standard_Output, " tokens is ");
- Put (Standard_Output, TokenInfo(t));
- New_Line (Standard_Output);
- end if;
-
- end if;
- end loop;
- end HalsteadCount;
- end count;
- ::::::::::::::
- count.spc
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/count.spc,v $
- -- $Revision: 1.3 $ -- $Date: 85/06/13 13:29:12 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.3 $");
-
- with Definitions;
- with Count_Types;
- package Count is
-
- package D renames Definitions;
- package CT renames Count_Types;
-
- --------------------------------------------------------------------------
-
- procedure HalsteadCount ( --| This procedure determines which tokens
- --| are operators and operands and counts
- --| them.
- TokenInfo :in D.TokenCountType;
- VerboseOn :in boolean;
- Nn: in out CT.NnInfoType
- );
-
- --------------------------------------------------------------------------
- end Count;
- ::::::::::::::
- countype.bdy
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/countype.bdy,v $
- -- $Revision: 1.1 $ -- $Date: 85/07/04 11:38:21 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.1 $");
-
- -- $Source: /nosc/work/tools/halstead/RCS/countype.bdy,v $
- -- $Revision: 1.1 $ -- $Date: 85/07/04 11:38:21 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.1 $");
-
- with Definitions;
- package body Count_Types is
-
- --------------------------------------------------------------------------
-
- function AddCounts ( --| This function Adds two records and
- --| returns their sum.
- L :in NnInfoType;
- R :in NnInfoType
- ) return NnInfoType is
- Sum :NnInfoType;
- begin
- for c in Definitions.Class loop
- Sum(c).Vocabulary := L(c).Vocabulary + R(c).Vocabulary;
- Sum(c).Usage := L(c).Usage + R(c).Usage;
- end loop;
- return Sum;
- end;
- --------------------------------------------------------------------------
-
- procedure ZeroCount (--| Sets the counts of all the classes of NnInfo
- --| to 0.
- NnInfo :in out NnInfoType
- ) is
- begin
- for c in Definitions.Class loop
- NnInfo(c).Vocabulary := 0;
- NnInfo(c).Usage := 0;
- end loop;
- end;
-
- ------------------------------------------------------------------------- -
- end Count_Types;
- ::::::::::::::
- countype.spc
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/countype.spc,v $
- -- $Revision: 1.1 $ -- $Date: 85/07/04 11:36:37 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.1 $");
-
- -- $Source: /nosc/work/tools/halstead/RCS/countype.spc,v $
- -- $Revision: 1.1 $ -- $Date: 85/07/04 11:36:37 $ -- $Author: buddy $
-
- --pragma revision ("$Revision: 1.1 $");
-
- with Definitions;
- package Count_Types is
- --| OVERVIEW
- --| This package defines types that are being used in the counting
- --| of tokens. It also provides an operation AddCounts which
- --| a function which returns the sum of two NnInfoType records.
- --| This is needed because it is necessary to separate the token
- --| counts which result from DEF_ID_Analysis and Literal_Analysis
- --| and the token counts which result from keyword other syntactic
- --| constructs.
-
- type NnRecordType is
- record
- Vocabulary: natural := 0;
- Usage: natural := 0;
- end record;
- --| This package is used to define the NnInfoType used by all
- --| the different counting strategies.
-
- type NnInfoType is array (Definitions.Class) of NnRecordType;
- --| NnInfoType keeps track of the vocabulary and usage for each
- --| class (i.e. operator, operand, and neither).
- --|
- --| Vocabulary keeps track of the number of unique symbols in
- --| the source program. For example:
- --|
- --| Nn :NnInfoType;
- --|
- --| Then Nn(operator).Vocabulary corresponds to n1 the unique
- --| number of operators in Halstead's notation and
- --| Nn(operand).Vocabulary corresponds to n2 the unique number of
- --| operands. Thus
- --|
- --| Nn(operator).Vocabulary + Nn(operand).Vocabulary =n
- --|
- --| which is the vocabulary for the source program.
- --|
- --| Usage keeps track of the total usage of each class of
- --| operator, operand, and neither. Nn(operator).Usage
- --| Nn(operand).Usage correspond to N1 and N2 in Halstead
- --| notation and their sum corresponds to N which is the length of
-
- --------------------------------------------------------------------------
-
- function AddCounts ( --| This function Adds two records and
- --| returns their sum.
- L :in NnInfoType;
- R :in NnInfoType
- ) return NnInfoType ;
- --------------------------------------------------------------------------
-
- procedure ZeroCount (--| Sets the counts of NnInfo to 0.
- NnInfo :in out NnInfoType
- );
-
- ------------------------------------------------------------------------- -
- end Count_Types;
- ::::::::::::::
- defs.bdy
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/defs.bdy,v $
- -- $Revision: 5.1 $ -- $Date: 85/04/04 08:30:38 $ -- $Author: buddy $
-
- with VmmTextPkg;
- with unchecked_deallocation;
- package body Definitions is
-
- function "<" ( --| This function compares the text of two literals
- --| to see if X is lexigraphically less than Y.
- X :in Source_Text.Locator;
- Y :in Source_Text.Locator
- ) return boolean is
-
- begin
- return
- VmmTextPkg.Value (Source_Text.Value (X))
- <
- VmmTextPkg.Value (Source_Text.Value (Y));
- end;
-
- package body Literal_Set is
-
- ------------------------------------------------------------------------------
- -- Nested Private Definitions
- -------------------------------------------------------------------------------
-
-
- package body TreePkg is
- ---------------------------------------------------------------------------
- -- Nested Private Definitions
- ---------------------------------------------------------------------------
-
-
-
- package body NodeOrder is
-
- procedure Free is new unchecked_deallocation (Cell, List);
-
- --------------------------------------------------------------------------
-
- function Last (L: in List) return List is
-
- Place_In_L: List;
- Temp_Place_In_L: List;
-
- --| Link down the list L and return the pointer to the last element
- --| of L. If L is null raise the EmptyList exception.
-
- begin
- if L = null then
- raise EmptyList;
- else
-
- --| Link down L saving the pointer to the previous element in
- --| Temp_Place_In_L. After the last iteration Temp_Place_In_L
- --| points to the last element in the list.
-
- Place_In_L := L;
- while Place_In_L /= null loop
- Temp_Place_In_L := Place_In_L;
- Place_In_L := Place_In_L.Next;
- end loop;
- return Temp_Place_In_L;
- end if;
- end Last;
-
-
- --------------------------------------------------------------------------
-
- procedure Attach (List1: in out List;
- List2: in List ) is
- EndOfList1: List;
-
- --| Attach List2 to List1.
- --| If List1 is null return List2
- --| If List1 equals List2 then raise CircularList
- --| Otherwise get the pointer to the last element of List1 and change
- --| its Next field to be List2.
-
- begin
- if List1 = null then
- List1 := List2;
- return;
- elsif List1 = List2 then
- raise CircularList;
- else
- EndOfList1 := Last (List1);
- EndOfList1.Next := List2;
- end if;
- end Attach;
-
- --------------------------------------------------------------------------
-
- procedure Attach (L: in out List;
- Element: in Tree ) is
-
- NewEnd: List;
-
- --| Create a list containing Element and attach it to the end of L
-
- begin
- NewEnd := new Cell'(Info => Element, Next => null);
- Attach (L, NewEnd);
- end;
-
- --------------------------------------------------------------------------
-
- function Attach (Element1: in Tree;
- Element2: in Tree ) return List is
- NewList: List;
-
- --| Create a new list containing the information in Element1 and
- --| attach Element2 to that list.
-
- begin
- NewList := new Cell'(Info => Element1, Next => null);
- Attach (NewList, Element2);
- return NewList;
- end;
-
- --------------------------------------------------------------------------
-
- procedure Attach (Element: in Tree;
- L: in out List ) is
-
- --| Create a new cell whose information is Element and whose Next
- --| field is the list L. This prepends Element to the List L.
-
- begin
- L := new Cell'(Info => Element, Next => L);
- end;
-
- --------------------------------------------------------------------------
-
- function Attach ( List1: in List;
- List2: in List ) return List is
-
- Last_Of_List1: List;
-
- begin
- if List1 = null then
- return List2;
- elsif List1 = List2 then
- raise CircularList;
- else
- Last_Of_List1 := Last (List1);
- Last_Of_List1.Next := List2;
- return List1;
- end if;
- end Attach;
-
- -------------------------------------------------------------------------
-
- function Attach( L: in List;
- Element: in Tree ) return List is
-
- NewEnd: List;
- Last_Of_L: List;
-
- --| Create a list called NewEnd and attach it to the end of L.
- --| If L is null return NewEnd
- --| Otherwise get the last element in L and make its Next field
- --| NewEnd.
-
- begin
- NewEnd := new Cell'(Info => Element, Next => null);
- if L = null then
- return NewEnd;
- else
- Last_Of_L := Last (L);
- Last_Of_L.Next := NewEnd;
- return L;
- end if;
- end Attach;
-
- --------------------------------------------------------------------------
-
- function Attach (Element: in Tree;
- L: in List ) return List is
-
- begin
- return (new Cell'(Info => Element, Next => L));
- end Attach;
-
- --------------------------------------------------------------------------
-
- function Copy (L: in List) return List is
-
- --| If L is null return null
- --| Otherwise recursively copy the list by first copying the information
- --| at the head of the list and then making the Next field point to
- --| a copy of the tail of the list.
-
- begin
- if L = null then
- return null;
- else
- return new Cell'(Info => L.Info, Next => Copy (L.Next));
- end if;
- end Copy;
-
-
- --------------------------------------------------------------------------
-
- function Create return List is
-
- --| Return the empty list.
-
- begin
- return null;
- end Create;
-
- --------------------------------------------------------------------------
-
- procedure DeleteHead (L: in out List) is
-
- TempList: List;
-
- --| Remove the element of the head of the list and return it to the heap.
- --| If L is null EmptyList.
- --| Otherwise save the Next field of the first element, remove the first
- --| element and then assign to L the Next field of the first element.
-
- begin
- if L = null then
- raise EmptyList;
- else
- TempList := L.Next;
- Free (L);
- L := TempList;
- end if;
- end DeleteHead;
-
- --------------------------------------------------------------------------
-
- procedure DeleteItem (L: in out List;
- Element: in Tree ) is
-
- Temp_L :List;
-
- --| Remove the first element in the list with the value Element.
- --| If the first element of the list is equal to element then
- --| remove it. Otherwise, recurse on the tail of the list.
-
- begin
- if L.Info = Element then
- DeleteHead(L);
- else
- DeleteItem(L.Next, Element);
- end if;
- exception
- when constraint_error =>
- raise ItemNotPresent;
- end DeleteItem;
-
- --------------------------------------------------------------------------
-
- procedure DeleteItems (L: in out List;
- Element: in Tree ) is
-
- Place_In_L :List; --| Current place in L.
- Last_Place_In_L :List; --| Last place in L.
- Temp_Place_In_L :List; --| Holds a place in L to be removed.
- Found :boolean := false; --| Indicates if an element with
- --| the correct value was found.
-
- --| Walk over the list removing all elements with the value Element.
-
- begin
- Place_In_L := L;
- Last_Place_In_L := null;
- while (Place_In_L /= null) loop
-
- --| Found an element equal to Element
-
- if Place_In_L.Info = Element then
- Found := true;
-
- --| If Last_Place_In_L is null then we are at first element
- --| in L.
-
- if Last_Place_In_L = null then
- Temp_Place_In_L := Place_In_L;
- L := Place_In_L.Next;
- else
- Temp_Place_In_L := Place_In_L;
-
- --| Relink the list Last's Next gets Place's Next
-
- Last_Place_In_L.Next := Place_In_L.Next;
- end if;
-
- --| Move Place_In_L to the next position in the list.
- --| Free the element.
- --| Do not update the last element in the list it remains the
- --| same.
-
- Place_In_L := Place_In_L.Next;
- Free (Temp_Place_In_L);
- else
- --| Update the last place in L and the place in L.
-
- Last_Place_In_L := Place_In_L;
- Place_In_L := Place_In_L.Next;
- end if;
- end loop;
-
- --| If we have not found an element raise an exception.
-
- if not Found then
- raise ItemNotPresent;
- end if;
-
- end DeleteItems;
-
- --------------------------------------------------------------------------
-
- procedure Destroy (L: in out List) is
-
- Place_In_L: List;
- HoldPlace: List;
-
- --| Walk down the list removing all the elements and set the list to
- --| the empty list.
-
- begin
- Place_In_L := L;
- while Place_In_L /= null loop
- HoldPlace := Place_In_L;
- Place_In_L := Place_In_L.Next;
- Free (HoldPlace);
- end loop;
- L := null;
- end Destroy;
-
- --------------------------------------------------------------------------
-
- function FirstValue (L: in List) return Tree is
-
- --| Return the first value in the list.
-
- begin
- if L = null then
- raise EmptyList;
- else
- return (L.Info);
- end if;
- end FirstValue;
-
- --------------------------------------------------------------------------
-
- procedure Forword (I: in out ListIter) is
-
- --| Return the pointer to the next member of the list.
- Temp_L :List;
- begin
- Temp_L := List (I);
- I := ListIter (Temp_L.Next);
- end Forword;
-
- --------------------------------------------------------------------------
-
- function IsInList (L: in List;
- Element: in Tree ) return boolean is
-
- Place_In_L: List;
-
- --| Check if Element is in L. If it is return true otherwise return false.
-
- begin
- Place_In_L := L;
- while Place_In_L /= null loop
- if Place_In_L.Info = Element then
- return true;
- end if;
- Place_In_L := Place_In_L.Next;
- end loop;
- return false;
- end IsInList;
-
- --------------------------------------------------------------------------
-
- function IsEmpty (L: in List) return boolean is
-
- --| Is the list L empty.
-
- begin
- return (L = null);
- end IsEmpty;
-
- --------------------------------------------------------------------------
-
- function LastValue (L: in List) return Tree is
-
- LastElement: List;
-
- --| Return the value of the last element of the list. Get the pointer
- --| to the last element of L and then return its information.
-
- begin
- LastElement := Last (L);
- return LastElement.Info;
- end LastValue;
-
- --------------------------------------------------------------------------
-
- function Length (L: in List) return integer is
-
- --| Recursively compute the length of L. The length of a list is
- --| 0 if it is null or 1 + the length of the tail.
-
- begin
- if L = null then
- return (0);
- else
- return (1 + Length (Tail (L)));
- end if;
- end Length;
-
- --------------------------------------------------------------------------
-
- function MakeListIter (L: in List) return ListIter is
-
- --| Start an iteration operation on the list L. Do a type conversion
- --| from List to ListIter.
-
- begin
- return ListIter (L);
- end MakeListIter;
-
- --------------------------------------------------------------------------
-
- function More (L: in ListIter) return boolean is
-
- --| This is a test to see whether an iteration is complete.
-
- begin
- return L /= null;
- end;
-
- --------------------------------------------------------------------------
-
- procedure Next (Place: in out ListIter;
- Info: out Tree ) is
- PlaceInList: List;
-
- --| This procedure gets the information at the current place in the List
- --| and moves the ListIter to the next postion in the list.
- --| If we are at the end of a list then exception NoMore is raised.
-
- begin
- if Place = null then
- raise NoMore;
- else
- PlaceInList := List(Place);
- Info := PlaceInList.Info;
- Place := ListIter(PlaceInList.Next);
- end if;
- end Next;
-
- --------------------------------------------------------------------------
-
- procedure ReplaceHead (L: in out List;
- Info: in Tree ) is
-
- --| This procedure replaces the information at the head of a list
- --| with the given information. If the list is empty the exception
- --| EmptyList is raised.
-
- begin
- if L = null then
- raise EmptyList;
- else
- L.Info := Info;
- end if;
- end ReplaceHead;
-
- --------------------------------------------------------------------------
-
- procedure ReplaceTail (L: in out List;
- NewTail: in List ) is
- Temp_L: List;
-
- --| This destroys the tail of a list and replaces the tail with
- --| NewTail. If L is empty EmptyList is raised.
-
- begin
- Destroy(L.Next);
- L.Next := NewTail;
- exception
- when constraint_error =>
- raise EmptyList;
- end ReplaceTail;
-
- --------------------------------------------------------------------------
-
- function Tail (L: in List) return List is
-
- --| This returns the list which is the tail of L. If L is null Empty
- --| List is raised.
-
- begin
- if L = null then
- raise EmptyList;
- else
- return L.Next;
- end if;
- end Tail;
-
- --------------------------------------------------------------------------
- function Equal (List1: in List;
- List2: in List ) return boolean is
-
- PlaceInList1: List;
- PlaceInList2: List;
- Contents1: Tree;
- Contents2: Tree;
-
- --| This function tests to see if two lists are equal. Two lists
- --| are equal if for all the elements of List1 the corresponding
- --| element of List2 has the same value. Thus if the 1st elements
- --| are equal and the second elements are equal and so up to n.
- --| Thus a necessary condition for two lists to be equal is that
- --| they have the same number of elements.
-
-
- --| This function walks over the two list and checks that the
- --| corresponding elements are equal. As soon as we reach
- --| the end of a list (PlaceInList = null) we fall out of the loop.
- --| If both PlaceInList1 and PlaceInList2 are null after exiting the loop
- --| then the lists are equal. If they both are not null the lists aren't
- --| equal. Note that equality on elements is based on a user supplied
- --| function Equal which is used to test for item equality.
-
- begin
- PlaceInList1 := List1;
- PlaceInList2 := List2;
- while (PlaceInList1 /= null) and (PlaceInList2 /= null) loop
- if PlaceInList1.Info /= PlaceInList2.Info then
- return false;
- end if;
- PlaceInList1 := PlaceInList1.Next;
- PlaceInList2 := PlaceInList2.Next;
- end loop;
- return ((PlaceInList1 = null) and (PlaceInList2 = null) );
- end Equal;
- end NodeOrder;
-
- --------------------------------------------------------------------------
-
- ----------------------------------------------------------------------------
- -- Local Subprograms
- ----------------------------------------------------------------------------
-
- procedure Free is new unchecked_deallocation (Node, Tree);
-
- function equal (X, Y: in Member) return boolean is
-
- begin
-
- return (not (X < Y)) and (not (Y < X));
- end;
-
- ------------------------------------------------------------------------------
-
- function Generate (T :in Tree ) return Nodeorder.List is
- L : Nodeorder.List;
-
- --| This routine generates a list of pointers to nodes in the tree t.
- --| The list is ordered with respect to the order of the nodes in the tree.
-
- --| generate does a depth first search of the tree.
- --| 1. It first visits the leftchild of t and generates the list for that.
- --| 2. It then appends the root node of t to the list generated for the left
- --| child.
- --| 3. It then appends the list generated for the rightchild to the list
- --| generated for the leftchild and the root.
- --|
-
- begin
- L := NodeOrder.Create;
- if T /= null then
- L := Generate (T.Leftchild);
- Nodeorder.Attach (L, T);
- Nodeorder.Attach (L, Generate (T.Rightchild));
- end if;
- return L;
- End Generate;
-
- ------------------------------------------------------------------------------
-
-
-
- ------------------------------------------------------------------------------
- -- Visible Subprograms
- ------------------------------------------------------------------------------
-
-
-
-
-
- ------------------------------------------------------------------------------
-
- function Create return Tree is
-
- begin
- return null;
- end;
-
- -----------------------------------------------------------------------------
-
- procedure Deposit (
- I :in Member;
- S :in Tree ) is
-
- begin
- S.Info := I;
- end;
-
- ------------------------------------------------------------------------------
-
- procedure DestroyTree ( T :in out Tree) is
-
- --| This procedure recursively destroys the tree T.
- --| 1. It destroy the leftchild of T
- --| 2. It then destroys the rightchild of T.
- --| 3. It then destroy the root T and set T to be null.
-
- begin
- if T /= null then
- DestroyTree (T.leftchild);
- DestroyTree (T.rightchild);
- Free (T);
- end if;
- end DestroyTree;
-
- ------------------------------------------------------------------------------
-
- procedure InsertNode (
- N :in out Member; --| Node being inserted.
- T :in out Tree; --| Tree node is being inserted
- --| into.
- Root : out Tree; --| Root of the subtree which node N
- --| heads. This is the position of
- --| node N in T;
- Exists : out boolean --| If this node already exists in
- --| the tree then Exists is true. If
- --| If this is the first insertion
- --| Exists is false.
-
- ) is
- --| This inserts the node N in T.
- --| 1. If T is null then a new node is allocated and assigned to T
- --| 2. If T is not null then T is searched for the proper place to insert n.
- --| This is first done by checking whether N < rightchild
- --| 3. If this is not true then we check to see if leftchild < N
- --| 4. If this is not true then N is in the tree.
-
- begin
- if T = null then
- T := new Node ' (Info => N, leftchild => null, rightchild => null);
- Root := T;
- Exists := false;
- N := T.Info;
- elsif N < T.Info then
- InsertNode (N, T.leftchild, Root, Exists);
- elsif T.Info < N then
- InsertNode (N, T.rightchild, Root, Exists);
- else
- Root := T;
- Exists := true;
- N := T.Info;
-
- end if;
- end InsertNode;
-
- ------------------------------------------------------------------------------
-
- function MakeTreeIter (T :in Tree ) return TreeIter is
-
- I :TreeIter;
- --| This sets up the iterator for a tree T.
- --| The NodeList keeps track of the order of the nodes of T. The NodeList
- --| is computed by first invoking Generate of the leftchild then append
- --| the root node to NodeList and then append the result of Generate
- --| to NodeList. Since the tree is ordered such that
- --|
- --| leftchild < root root < rightchild
- --|
- --| NodeOrder returns the nodes in ascending order.
- --|
- --| Thus NodeList keeps the list alive for the duration of the iteration
- --| operation. The variable State is the a pointer into the NodeList
- --| which is the current place of the iteration.
-
- begin
- I.NodeList := NodeOrder.Create;
- if T /= null then
- I.NodeList := Generate (T.leftchild);
- NodeOrder.Attach (I.NodeList, T);
- NodeOrder.Attach (I.NodeList, Generate (T.rightChild));
- end if;
- I.State := NodeOrder.MakeListIter (I.NodeList);
- return I;
- end;
-
- ------------------------------------------------------------------------------
-
- function More (I :in TreeIter) return boolean is
-
- begin
- return NodeOrder.More (I.State);
- end;
-
- ------------------------------------------------------------------------------
-
- procedure Next (
- I :in out TreeIter;
- Info : out Member ) is
- T: Tree;
-
- --| Next returns the information at the current position in the iterator
- --| and increments the iterator. This is accomplished by using the iterater
- --| associated with the NodeOrder list. This returns a pointer into the Tree
- --| and then the information found at this node in T is returned.
-
-
- begin
- NodeOrder.Next (I.State, T);
- Info := T.Info;
- end;
-
- -------------------------------------------------------------------------------
-
- end TreePkg;
-
-
- -------------------------------------------------------------------------------
- -- Local Subprograms
- -------------------------------------------------------------------------------
-
- -------------------------------------------------------------------------------
-
- function "<" ( --| Implements "<" for the type member.
- X :in Member;
- Y :in Member
- ) return boolean is
-
- begin
- return X.Info < Y.Info;
- end;
-
- -------------------------------------------------------------------------------
-
-
- -------------------------------------------------------------------------------
- -- Visible Subprograms
- -------------------------------------------------------------------------------
-
-
- -------------------------------------------------------------------------------
-
- function Cardinality (
- S :in Set --| The set whose size is being computed.
- ) return natural is
-
- T :TreePkg.TreeIter;
- M :Member;
- count :natural := 0;
- begin
- T := TreePkg.MakeTreeIter (S.SetRep);
- while TreePkg.More (T) loop
- TreePkg.Next (T, M);
- count := count + 1;
- end loop;
- return count;
- end Cardinality;
-
- -------------------------------------------------------------------------------
-
- function Create
-
- return Set is
- S :Set;
- begin
- S.SetRep := TreePkg.Create;
- return S;
- end Create;
-
- ------------------------------------------------------------------------------
-
- procedure Destroy (
- S :in out Set
- ) is
-
- begin
- TreePkg.DestroyTree (S.SetRep);
- end Destroy;
-
- -----------------------------------------------------------------------------
-
- function GetCount (
- I :in SetIter
- ) return natural is
-
- begin
- return I.Count;
- end;
-
- -----------------------------------------------------------------------------
- procedure Insert(
- M :in Source_Text.Locator;
- S :in out Set
- ) is
- Subtree :TreePkg.Tree;
- Exists :boolean;
- MemberToEnter :Member := ( Info => M, count => 1);
- begin
- --| If NewMember doesn't exist in SetRep it is added. If it does exist
- --| Exists comes back true and then M's count is updated. Since the
- --| first argument of TreePkg.Insert is in out, after Insert
- --| MemberToEnter has the value stored in the tree. Thus if we
- --| need to update the count we can simple bump the count in MemberToEnter.
-
- TreePkg.InsertNode (MemberToEnter, S.SetRep, SubTree, Exists);
- if Exists then
- MemberToEnter.Count := MemberToEnter.Count + 1;
- TreePkg.Deposit (MemberToEnter, SubTree);
- end if;
- end Insert;
-
- ------------------------------------------------------------------------------
-
- function MakeSetIter (
- S :in Set
- ) return SetIter is
-
- I :SetIter;
- begin
- I.Place := TreePkg.MakeTreeIter (S.SetRep);
- I.Count := 0;
- return I;
- end;
-
- ------------------------------------------------------------------------------
-
- function More (
- I :in SetIter
- ) return boolean is
-
- begin
- return TreePkg.More (I.Place);
- end;
-
- ------------------------------------------------------------------------------
-
- procedure Next (
- I :in out SetIter;
- M : out Source_Text.Locator
- ) is
- TempMember :Member;
- begin
- TreePkg.Next (I.Place, TempMember);
- M := TempMember.Info;
- I.Count := TempMember.Count;
- end;
-
- ------------------------------------------------------------------------------
-
- end Literal_Set;
-
-
-
-
-
-
- package body DEF_ID_Set is
-
- ------------------------------------------------------------------------------
- -- Nested Private Definitions
- -------------------------------------------------------------------------------
-
-
- package body TreePkg is
- ---------------------------------------------------------------------------
- -- Nested Private Definitions
- ---------------------------------------------------------------------------
-
-
-
- package body NodeOrder is
-
- procedure Free is new unchecked_deallocation (Cell, List);
-
- --------------------------------------------------------------------------
-
- function Last (L: in List) return List is
-
- Place_In_L: List;
- Temp_Place_In_L: List;
-
- --| Link down the list L and return the pointer to the last element
- --| of L. If L is null raise the EmptyList exception.
-
- begin
- if L = null then
- raise EmptyList;
- else
-
- --| Link down L saving the pointer to the previous element in
- --| Temp_Place_In_L. After the last iteration Temp_Place_In_L
- --| points to the last element in the list.
-
- Place_In_L := L;
- while Place_In_L /= null loop
- Temp_Place_In_L := Place_In_L;
- Place_In_L := Place_In_L.Next;
- end loop;
- return Temp_Place_In_L;
- end if;
- end Last;
-
-
- --------------------------------------------------------------------------
-
- procedure Attach (List1: in out List;
- List2: in List ) is
- EndOfList1: List;
-
- --| Attach List2 to List1.
- --| If List1 is null return List2
- --| If List1 equals List2 then raise CircularList
- --| Otherwise get the pointer to the last element of List1 and change
- --| its Next field to be List2.
-
- begin
- if List1 = null then
- List1 := List2;
- return;
- elsif List1 = List2 then
- raise CircularList;
- else
- EndOfList1 := Last (List1);
- EndOfList1.Next := List2;
- end if;
- end Attach;
-
- --------------------------------------------------------------------------
-
- procedure Attach (L: in out List;
- Element: in Tree ) is
-
- NewEnd: List;
-
- --| Create a list containing Element and attach it to the end of L
-
- begin
- NewEnd := new Cell'(Info => Element, Next => null);
- Attach (L, NewEnd);
- end;
-
- --------------------------------------------------------------------------
-
- function Attach (Element1: in Tree;
- Element2: in Tree ) return List is
- NewList: List;
-
- --| Create a new list containing the information in Element1 and
- --| attach Element2 to that list.
-
- begin
- NewList := new Cell'(Info => Element1, Next => null);
- Attach (NewList, Element2);
- return NewList;
- end;
-
- --------------------------------------------------------------------------
-
- procedure Attach (Element: in Tree;
- L: in out List ) is
-
- --| Create a new cell whose information is Element and whose Next
- --| field is the list L. This prepends Element to the List L.
-
- begin
- L := new Cell'(Info => Element, Next => L);
- end;
-
- --------------------------------------------------------------------------
-
- function Attach ( List1: in List;
- List2: in List ) return List is
-
- Last_Of_List1: List;
-
- begin
- if List1 = null then
- return List2;
- elsif List1 = List2 then
- raise CircularList;
- else
- Last_Of_List1 := Last (List1);
- Last_Of_List1.Next := List2;
- return List1;
- end if;
- end Attach;
-
- -------------------------------------------------------------------------
-
- function Attach( L: in List;
- Element: in Tree ) return List is
-
- NewEnd: List;
- Last_Of_L: List;
-
- --| Create a list called NewEnd and attach it to the end of L.
- --| If L is null return NewEnd
- --| Otherwise get the last element in L and make its Next field
- --| NewEnd.
-
- begin
- NewEnd := new Cell'(Info => Element, Next => null);
- if L = null then
- return NewEnd;
- else
- Last_Of_L := Last (L);
- Last_Of_L.Next := NewEnd;
- return L;
- end if;
- end Attach;
-
- --------------------------------------------------------------------------
-
- function Attach (Element: in Tree;
- L: in List ) return List is
-
- begin
- return (new Cell'(Info => Element, Next => L));
- end Attach;
-
- --------------------------------------------------------------------------
-
- function Copy (L: in List) return List is
-
- --| If L is null return null
- --| Otherwise recursively copy the list by first copying the information
- --| at the head of the list and then making the Next field point to
- --| a copy of the tail of the list.
-
- begin
- if L = null then
- return null;
- else
- return new Cell'(Info => L.Info, Next => Copy (L.Next));
- end if;
- end Copy;
-
-
- --------------------------------------------------------------------------
-
- function Create return List is
-
- --| Return the empty list.
-
- begin
- return null;
- end Create;
-
- --------------------------------------------------------------------------
-
- procedure DeleteHead (L: in out List) is
-
- TempList: List;
-
- --| Remove the element of the head of the list and return it to the heap.
- --| If L is null EmptyList.
- --| Otherwise save the Next field of the first element, remove the first
- --| element and then assign to L the Next field of the first element.
-
- begin
- if L = null then
- raise EmptyList;
- else
- TempList := L.Next;
- Free (L);
- L := TempList;
- end if;
- end DeleteHead;
-
- --------------------------------------------------------------------------
-
- procedure DeleteItem (L: in out List;
- Element: in Tree ) is
-
- Temp_L :List;
-
- --| Remove the first element in the list with the value Element.
- --| If the first element of the list is equal to element then
- --| remove it. Otherwise, recurse on the tail of the list.
-
- begin
- if L.Info = Element then
- DeleteHead(L);
- else
- DeleteItem(L.Next, Element);
- end if;
- exception
- when constraint_error =>
- raise ItemNotPresent;
- end DeleteItem;
-
- --------------------------------------------------------------------------
-
- procedure DeleteItems (L: in out List;
- Element: in Tree ) is
-
- Place_In_L :List; --| Current place in L.
- Last_Place_In_L :List; --| Last place in L.
- Temp_Place_In_L :List; --| Holds a place in L to be removed.
- Found :boolean := false; --| Indicates if an element with
- --| the correct value was found.
-
- --| Walk over the list removing all elements with the value Element.
-
- begin
- Place_In_L := L;
- Last_Place_In_L := null;
- while (Place_In_L /= null) loop
-
- --| Found an element equal to Element
-
- if Place_In_L.Info = Element then
- Found := true;
-
- --| If Last_Place_In_L is null then we are at first element
- --| in L.
-
- if Last_Place_In_L = null then
- Temp_Place_In_L := Place_In_L;
- L := Place_In_L.Next;
- else
- Temp_Place_In_L := Place_In_L;
-
- --| Relink the list Last's Next gets Place's Next
-
- Last_Place_In_L.Next := Place_In_L.Next;
- end if;
-
- --| Move Place_In_L to the next position in the list.
- --| Free the element.
- --| Do not update the last element in the list it remains the
- --| same.
-
- Place_In_L := Place_In_L.Next;
- Free (Temp_Place_In_L);
- else
- --| Update the last place in L and the place in L.
-
- Last_Place_In_L := Place_In_L;
- Place_In_L := Place_In_L.Next;
- end if;
- end loop;
-
- --| If we have not found an element raise an exception.
-
- if not Found then
- raise ItemNotPresent;
- end if;
-
- end DeleteItems;
-
- --------------------------------------------------------------------------
-
- procedure Destroy (L: in out List) is
-
- Place_In_L: List;
- HoldPlace: List;
-
- --| Walk down the list removing all the elements and set the list to
- --| the empty list.
-
- begin
- Place_In_L := L;
- while Place_In_L /= null loop
- HoldPlace := Place_In_L;
- Place_In_L := Place_In_L.Next;
- Free (HoldPlace);
- end loop;
- L := null;
- end Destroy;
-
- --------------------------------------------------------------------------
-
- function FirstValue (L: in List) return Tree is
-
- --| Return the first value in the list.
-
- begin
- if L = null then
- raise EmptyList;
- else
- return (L.Info);
- end if;
- end FirstValue;
-
- --------------------------------------------------------------------------
-
- procedure Forword (I: in out ListIter) is
-
- --| Return the pointer to the next member of the list.
- Temp_L :List;
- begin
- Temp_L := List (I);
- I := ListIter (Temp_L.Next);
- end Forword;
-
- --------------------------------------------------------------------------
-
- function IsInList (L: in List;
- Element: in Tree ) return boolean is
-
- Place_In_L: List;
-
- --| Check if Element is in L. If it is return true otherwise return false.
-
- begin
- Place_In_L := L;
- while Place_In_L /= null loop
- if Place_In_L.Info = Element then
- return true;
- end if;
- Place_In_L := Place_In_L.Next;
- end loop;
- return false;
- end IsInList;
-
- --------------------------------------------------------------------------
-
- function IsEmpty (L: in List) return boolean is
-
- --| Is the list L empty.
-
- begin
- return (L = null);
- end IsEmpty;
-
- --------------------------------------------------------------------------
-
- function LastValue (L: in List) return Tree is
-
- LastElement: List;
-
- --| Return the value of the last element of the list. Get the pointer
- --| to the last element of L and then return its information.
-
- begin
- LastElement := Last (L);
- return LastElement.Info;
- end LastValue;
-
- --------------------------------------------------------------------------
-
- function Length (L: in List) return integer is
-
- --| Recursively compute the length of L. The length of a list is
- --| 0 if it is null or 1 + the length of the tail.
-
- begin
- if L = null then
- return (0);
- else
- return (1 + Length (Tail (L)));
- end if;
- end Length;
-
- --------------------------------------------------------------------------
-
- function MakeListIter (L: in List) return ListIter is
-
- --| Start an iteration operation on the list L. Do a type conversion
- --| from List to ListIter.
-
- begin
- return ListIter (L);
- end MakeListIter;
-
- --------------------------------------------------------------------------
-
- function More (L: in ListIter) return boolean is
-
- --| This is a test to see whether an iteration is complete.
-
- begin
- return L /= null;
- end;
-
- --------------------------------------------------------------------------
-
- procedure Next (Place: in out ListIter;
- Info: out Tree ) is
- PlaceInList: List;
-
- --| This procedure gets the information at the current place in the List
- --| and moves the ListIter to the next postion in the list.
- --| If we are at the end of a list then exception NoMore is raised.
-
- begin
- if Place = null then
- raise NoMore;
- else
- PlaceInList := List(Place);
- Info := PlaceInList.Info;
- Place := ListIter(PlaceInList.Next);
- end if;
- end Next;
-
- --------------------------------------------------------------------------
-
- procedure ReplaceHead (L: in out List;
- Info: in Tree ) is
-
- --| This procedure replaces the information at the head of a list
- --| with the given information. If the list is empty the exception
- --| EmptyList is raised.
-
- begin
- if L = null then
- raise EmptyList;
- else
- L.Info := Info;
- end if;
- end ReplaceHead;
-
- --------------------------------------------------------------------------
-
- procedure ReplaceTail (L: in out List;
- NewTail: in List ) is
- Temp_L: List;
-
- --| This destroys the tail of a list and replaces the tail with
- --| NewTail. If L is empty EmptyList is raised.
-
- begin
- Destroy(L.Next);
- L.Next := NewTail;
- exception
- when constraint_error =>
- raise EmptyList;
- end ReplaceTail;
-
- --------------------------------------------------------------------------
-
- function Tail (L: in List) return List is
-
- --| This returns the list which is the tail of L. If L is null Empty
- --| List is raised.
-
- begin
- if L = null then
- raise EmptyList;
- else
- return L.Next;
- end if;
- end Tail;
-
- --------------------------------------------------------------------------
- function Equal (List1: in List;
- List2: in List ) return boolean is
-
- PlaceInList1: List;
- PlaceInList2: List;
- Contents1: Tree;
- Contents2: Tree;
-
- --| This function tests to see if two lists are equal. Two lists
- --| are equal if for all the elements of List1 the corresponding
- --| element of List2 has the same value. Thus if the 1st elements
- --| are equal and the second elements are equal and so up to n.
- --| Thus a necessary condition for two lists to be equal is that
- --| they have the same number of elements.
-
-
- --| This function walks over the two list and checks that the
- --| corresponding elements are equal. As soon as we reach
- --| the end of a list (PlaceInList = null) we fall out of the loop.
- --| If both PlaceInList1 and PlaceInList2 are null after exiting the loop
- --| then the lists are equal. If they both are not null the lists aren't
- --| equal. Note that equality on elements is based on a user supplied
- --| function Equal which is used to test for item equality.
-
- begin
- PlaceInList1 := List1;
- PlaceInList2 := List2;
- while (PlaceInList1 /= null) and (PlaceInList2 /= null) loop
- if PlaceInList1.Info /= PlaceInList2.Info then
- return false;
- end if;
- PlaceInList1 := PlaceInList1.Next;
- PlaceInList2 := PlaceInList2.Next;
- end loop;
- return ((PlaceInList1 = null) and (PlaceInList2 = null) );
- end Equal;
- end NodeOrder;
-
- --------------------------------------------------------------------------
-
- ----------------------------------------------------------------------------
- -- Local Subprograms
- ----------------------------------------------------------------------------
-
- procedure Free is new unchecked_deallocation (Node, Tree);
-
- function equal (X, Y: in Member) return boolean is
-
- begin
-
- return (not (X < Y)) and (not (Y < X));
- end;
-
- ------------------------------------------------------------------------------
-
- function Generate (T :in Tree ) return Nodeorder.List is
- L : Nodeorder.List;
-
- --| This routine generates a list of pointers to nodes in the tree t.
- --| The list is ordered with respect to the order of the nodes in the tree.
-
- --| generate does a depth first search of the tree.
- --| 1. It first visits the leftchild of t and generates the list for that.
- --| 2. It then appends the root node of t to the list generated for the left
- --| child.
- --| 3. It then appends the list generated for the rightchild to the list
- --| generated for the leftchild and the root.
- --|
-
- begin
- L := NodeOrder.Create;
- if T /= null then
- L := Generate (T.Leftchild);
- Nodeorder.Attach (L, T);
- Nodeorder.Attach (L, Generate (T.Rightchild));
- end if;
- return L;
- end Generate;
-
- ------------------------------------------------------------------------------
-
-
-
- ------------------------------------------------------------------------------
- -- Visible Subprograms
- ------------------------------------------------------------------------------
-
-
-
-
-
- ------------------------------------------------------------------------------
-
- function Create return Tree is
-
- begin
- return null;
- end;
-
- -----------------------------------------------------------------------------
-
- procedure Deposit (
- I :in Member;
- S :in Tree ) is
-
- begin
- S.Info := I;
- end;
-
- ------------------------------------------------------------------------------
-
- procedure DestroyTree ( T :in out Tree) is
-
- --| This procedure recursively destroys the tree T.
- --| 1. It destroy the leftchild of T
- --| 2. It then destroys the rightchild of T.
- --| 3. It then destroy the root T and set T to be null.
-
- begin
- if T /= null then
- DestroyTree (T.leftchild);
- DestroyTree (T.rightchild);
- Free (T);
- end if;
- end DestroyTree;
-
- ------------------------------------------------------------------------------
-
- procedure InsertNode (
- N :in out Member; --| Node being inserted.
- T :in out Tree; --| Tree node is being inserted
- --| into.
- Root : out Tree; --| Root of the subtree which node N
- --| heads. This is the position of
- --| node N in T;
- Exists : out boolean --| If this node already exists in
- --| the tree then Exists is true. If
- --| If this is the first insertion
- --| Exists is false.
-
- ) is
- --| This inserts the node N in T.
- --| 1. If T is null then a new node is allocated and assigned to T
- --| 2. If T is not null then T is searched for the proper place to insert n.
- --| This is first done by checking whether N < rightchild
- --| 3. If this is not true then we check to see if leftchild < N
- --| 4. If this is not true then N is in the tree.
-
- begin
- if T = null then
- T := new Node ' (Info => N, leftchild => null, rightchild => null);
- Root := T;
- Exists := false;
- N := T.Info;
- elsif N < T.Info then
- InsertNode (N, T.leftchild, Root, Exists);
- elsif T.Info < N then
- InsertNode (N, T.rightchild, Root, Exists);
- else
- Root := T;
- Exists := true;
- N := T.Info;
-
- end if;
- end InsertNode;
-
- ------------------------------------------------------------------------------
-
- function MakeTreeIter (T :in Tree ) return TreeIter is
-
- I :TreeIter;
- --| This sets up the iterator for a tree T.
- --| The NodeList keeps track of the order of the nodes of T. The NodeList
- --| is computed by first invoking Generate of the leftchild then append
- --| the root node to NodeList and then append the result of Generate
- --| to NodeList. Since the tree is ordered such that
- --|
- --| leftchild < root root < rightchild
- --|
- --| NodeOrder returns the nodes in ascending order.
- --|
- --| Thus NodeList keeps the list alive for the duration of the iteration
- --| operation. The variable State is the a pointer into the NodeList
- --| which is the current place of the iteration.
-
- begin
- I.NodeList := NodeOrder.Create;
- if T /= null then
- I.NodeList := Generate (T.leftchild);
- NodeOrder.Attach (I.NodeList, T);
- NodeOrder.Attach (I.NodeList, Generate (T.rightChild));
- end if;
- I.State := NodeOrder.MakeListIter (I.NodeList);
- return I;
- end;
-
- ------------------------------------------------------------------------------
-
- function More (I :in TreeIter) return boolean is
-
- begin
- return NodeOrder.More (I.State);
- end;
-
- ------------------------------------------------------------------------------
-
- procedure Next (
- I :in out TreeIter;
- Info : out Member ) is
- T: Tree;
-
- --| Next returns the information at the current position in the iterator
- --| and increments the iterator. This is accomplished by using the iterater
- --| associated with the NodeOrder list. This returns a pointer into the Tree
- --| and then the information found at this node in T is returned.
-
-
- begin
- NodeOrder.Next (I.State, T);
- Info := T.Info;
- end;
-
- -------------------------------------------------------------------------------
-
- end TreePkg;
-
-
- -------------------------------------------------------------------------------
- -- Local Subprograms
- -------------------------------------------------------------------------------
-
- -------------------------------------------------------------------------------
-
- function "<" ( --| Implements "<" for the type member.
- X :in Member;
- Y :in Member
- ) return boolean is
-
- begin
- return X.Info < Y.Info;
- end;
-
- -------------------------------------------------------------------------------
-
-
- -------------------------------------------------------------------------------
- -- Visible Subprograms
- -------------------------------------------------------------------------------
-
-
- -------------------------------------------------------------------------------
-
- function Cardinality (
- S :in Set --| The set whose size is being computed.
- ) return natural is
-
- T :TreePkg.TreeIter;
- M :Member;
- count :natural := 0;
- begin
- T := TreePkg.MakeTreeIter (S.SetRep);
- while TreePkg.More (T) loop
- TreePkg.Next (T, M);
- count := count + 1;
- end loop;
- return count;
- end Cardinality;
-
- -------------------------------------------------------------------------------
-
- function Create
-
- return Set is
- S :Set;
- begin
- S.SetRep := TreePkg.Create;
- return S;
- end Create;
-
- ------------------------------------------------------------------------------
-
- procedure Destroy (
- S :in out Set
- ) is
-
- begin
- TreePkg.DestroyTree (S.SetRep);
- end Destroy;
-
- -----------------------------------------------------------------------------
-
- function GetCount (
- I :in SetIter
- ) return natural is
-
- begin
- return I.Count;
- end;
-
- -----------------------------------------------------------------------------
- procedure Insert(
- M :in DEF_ID.Locator;
- S :in out Set
- ) is
- Subtree :TreePkg.Tree;
- Exists :boolean;
- MemberToEnter :Member := ( Info => M, count => 1);
- begin
- --| If NewMember doesn't exist in SetRep it is added. If it does exist
- --| Exists comes back true and then M's count is updated. Since the
- --| first argument of TreePkg.Insert is in out, after Insert
- --| MemberToEnter has the value stored in the tree. Thus if we
- --| need to update the count we can simple bump the count in MemberToEnter.
-
- TreePkg.InsertNode (MemberToEnter, S.SetRep, SubTree, Exists);
- if Exists then
- MemberToEnter.Count := MemberToEnter.Count + 1;
- TreePkg.Deposit (MemberToEnter, SubTree);
- end if;
- end Insert;
-
- ------------------------------------------------------------------------------
-
- function MakeSetIter (
- S :in Set
- ) return SetIter is
-
- I :SetIter;
- begin
- I.Place := TreePkg.MakeTreeIter (S.SetRep);
- I.Count := 0;
- return I;
- end;
-
- ------------------------------------------------------------------------------
-
- function More (
- I :in SetIter
- ) return boolean is
-
- begin
- return TreePkg.More (I.Place);
- end;
-
- ------------------------------------------------------------------------------
-
- procedure Next (
- I :in out SetIter;
- M : out DEF_ID.Locator
- ) is
- TempMember :Member;
- begin
- TreePkg.Next (I.Place, TempMember);
- M := TempMember.Info;
- I.Count := TempMember.Count;
- end;
-
- ------------------------------------------------------------------------------
-
- end DEF_ID_Set;
-
-
-
-
-
- package body BlockInfoStack is
-
-
- use Lists;
-
-
-
- function create
- return stack is
- begin
- return new stack_rec'(size => 0, elts => create);
- end create;
-
- procedure push(s: in out stack;
- e: BlockInfoType) is
- begin
- s.size := s.size + 1;
- s.elts := attach(e, s.elts);
- exception
- when constraint_error =>
- raise uninitialized_stack;
- end push;
-
- procedure pop(s: in out stack) is
- begin
- DeleteHead(s.elts);
- s.size := s.size - 1;
- exception
- when EmptyList =>
- raise empty_stack;
- when constraint_error =>
- raise uninitialized_stack;
- end pop;
-
- procedure pop(s: in out stack;
- e: out BlockInfoType) is
- begin
- e := FirstValue(s.elts);
- DeleteHead(s.elts);
- s.size := s.size - 1;
- exception
- when EmptyList =>
- raise empty_stack;
- when constraint_error =>
- raise uninitialized_stack;
- end pop;
-
- function copy(s: stack)
- return stack is
- begin
- if s = null then raise uninitialized_stack; end if;
-
- return new stack_rec'(size => s.size,
- elts => copy(s.elts));
- end;
-
-
-
- function top(s: stack)
- return BlockInfoType is
- begin
- return FirstValue(s.elts);
- exception
- when EmptyList =>
- raise empty_stack;
- when constraint_error =>
- raise uninitialized_stack;
- end top;
-
- function size(s: stack)
- return natural is
- begin
- return s.size;
- exception
- when constraint_error =>
- raise uninitialized_stack;
- end size;
-
- function is_empty(s: stack)
- return boolean is
- begin
- return s.size = 0;
- exception
- when constraint_error =>
- raise uninitialized_stack;
- end is_empty;
-
-
-
- procedure destroy(s: in out stack) is
- procedure free_stack is
- new unchecked_deallocation(stack_rec, stack);
- begin
- destroy(s.elts);
- free_stack(s);
- exception
- when constraint_error => -- stack is null
- return;
- end destroy;
-
- package body Lists is
-
- procedure Free is new unchecked_deallocation (Cell, List);
-
-
- function Last (L: in List) return List is
-
- Place_In_L: List;
- Temp_Place_In_L: List;
-
-
- begin
- if L = null then
- raise EmptyList;
- else
-
- --| Link down L saving the pointer to the previous element in
- --| Temp_Place_In_L. After the last iteration Temp_Place_In_L
- --| points to the last element in the list.
-
- Place_In_L := L;
- while Place_In_L /= null loop
- Temp_Place_In_L := Place_In_L;
- Place_In_L := Place_In_L.Next;
- end loop;
- return Temp_Place_In_L;
- end if;
- end Last;
-
-
-
- procedure Attach (List1: in out List;
- List2: in List ) is
- EndOfList1: List;
-
- --| Attach List2 to List1.
- --| If List1 is null return List2
- --| If List1 equals List2 then raise CircularList
- --| Otherwise get the pointer to the last element of List1 and change
- --| its Next field to be List2.
-
- begin
- if List1 = null then
- List1 := List2;
- return;
- elsif List1 = List2 then
- raise CircularList;
- else
- EndOfList1 := Last (List1);
- EndOfList1.Next := List2;
- end if;
- end Attach;
-
-
- procedure Attach (L: in out List;
- Element: in BlockInfoType ) is
-
- NewEnd: List;
-
-
- begin
- NewEnd := new Cell'(Info => Element, Next => null);
- Attach (L, NewEnd);
- end;
-
-
- function Attach (Element1: in BlockInfoType;
- Element2: in BlockInfoType ) return List is
- NewList: List;
-
-
- begin
- NewList := new Cell'(Info => Element1, Next => null);
- Attach (NewList, Element2);
- return NewList;
- end;
-
-
- procedure Attach (Element: in BlockInfoType;
- L: in out List ) is
-
-
- begin
- L := new Cell'(Info => Element, Next => L);
- end;
-
-
- function Attach ( List1: in List;
- List2: in List ) return List is
-
- Last_Of_List1: List;
-
- begin
- if List1 = null then
- return List2;
- elsif List1 = List2 then
- raise CircularList;
- else
- Last_Of_List1 := Last (List1);
- Last_Of_List1.Next := List2;
- return List1;
- end if;
- end Attach;
-
-
- function Attach( L: in List;
- Element: in BlockInfoType ) return List is
-
- NewEnd: List;
- Last_Of_L: List;
-
-
- begin
- NewEnd := new Cell'(Info => Element, Next => null);
- if L = null then
- return NewEnd;
- else
- Last_Of_L := Last (L);
- Last_Of_L.Next := NewEnd;
- return L;
- end if;
- end Attach;
-
-
- function Attach (Element: in BlockInfoType;
- L: in List ) return List is
-
- begin
- return (new Cell'(Info => Element, Next => L));
- end Attach;
-
-
- function Copy (L: in List) return List is
-
-
- begin
- if L = null then
- return null;
- else
- return new Cell'(Info => L.Info, Next => Copy (L.Next));
- end if;
- end Copy;
-
-
-
-
-
- function Create return List is
-
- --| Return the empty list.
-
- begin
- return null;
- end Create;
-
- procedure DeleteHead (L: in out List) is
-
- TempList: List;
-
-
- begin
- if L = null then
- raise EmptyList;
- else
- TempList := L.Next;
- Free (L);
- L := TempList;
- end if;
- end DeleteHead;
-
-
- procedure DeleteItem (L: in out List;
- Element: in BlockInfoType ) is
-
- Temp_L :List;
-
-
- begin
- if L.Info = Element then
- DeleteHead(L);
- else
- DeleteItem(L.Next, Element);
- end if;
- exception
- when constraint_error =>
- raise ItemNotPresent;
- end DeleteItem;
-
-
- procedure DeleteItems (L: in out List;
- Element: in BlockInfoType ) is
-
- Place_In_L :List; --| Current place in L.
- Last_Place_In_L :List; --| Last place in L.
- Temp_Place_In_L :List; --| Holds a place in L to be removed.
- Found :boolean := false; --| Indicates if an element with
- --| the correct value was found.
-
-
- begin
- Place_In_L := L;
- Last_Place_In_L := null;
- while (Place_In_L /= null) loop
-
- --| Found an element equal to Element
-
- if Place_In_L.Info = Element then
- Found := true;
-
- --| If Last_Place_In_L is null then we are at first element
- --| in L.
-
- if Last_Place_In_L = null then
- Temp_Place_In_L := Place_In_L;
- L := Place_In_L.Next;
- else
- Temp_Place_In_L := Place_In_L;
-
- --| Relink the list Last's Next gets Place's Next
-
- Last_Place_In_L.Next := Place_In_L.Next;
- end if;
-
- --| Move Place_In_L to the next position in the list.
- --| Free the element.
- --| Do not update the last element in the list it remains the
- --| same.
-
- Place_In_L := Place_In_L.Next;
- Free (Temp_Place_In_L);
- else
- --| Update the last place in L and the place in L.
-
- Last_Place_In_L := Place_In_L;
- Place_In_L := Place_In_L.Next;
- end if;
- end loop;
-
-
- if not Found then
- raise ItemNotPresent;
- end if;
-
- end DeleteItems;
-
-
- procedure Destroy (L: in out List) is
-
- Place_In_L: List;
- HoldPlace: List;
-
-
- begin
- Place_In_L := L;
- while Place_In_L /= null loop
- HoldPlace := Place_In_L;
- Place_In_L := Place_In_L.Next;
- Free (HoldPlace);
- end loop;
- L := null;
- end Destroy;
-
-
- function FirstValue (L: in List) return BlockInfoType is
-
-
- begin
- if L = null then
- raise EmptyList;
- else
- return (L.Info);
- end if;
- end FirstValue;
-
-
- procedure Forword (I: in out ListIter) is
-
- PlaceInList :List;
- begin
- PlaceInList := List (I);
- I := ListIter (PlaceInList.Next);
- end Forword;
-
-
- function IsInList (L: in List;
- Element: in BlockInfoType ) return boolean is
-
- Place_In_L: List;
-
-
- begin
- Place_In_L := L;
- while Place_In_L /= null loop
- if Place_In_L.Info = Element then
- return true;
- end if;
- Place_In_L := Place_In_L.Next;
- end loop;
- return false;
- end IsInList;
-
-
- function IsEmpty (L: in List) return boolean is
-
- --| Is the list L empty.
-
- begin
- return (L = null);
- end IsEmpty;
-
-
- function LastValue (L: in List) return BlockInfoType is
-
- LastElement: List;
-
-
- begin
- LastElement := Last (L);
- return LastElement.Info;
- end LastValue;
-
-
- function Length (L: in List) return integer is
-
-
- begin
- if L = null then
- return (0);
- else
- return (1 + Length (Tail (L)));
- end if;
- end Length;
-
-
- function MakeListIter (L: in List) return ListIter is
-
-
- begin
- return ListIter (L);
- end MakeListIter;
-
-
- function More (L: in ListIter) return boolean is
-
-
- begin
- return L /= null;
- end;
-
-
- procedure Next (Place: in out ListIter;
- Info: out BlockInfoType ) is
- PlaceInList: List;
-
-
- begin
- if Place = null then
- raise NoMore;
- else
- PlaceInList := List(Place);
- Info := PlaceInList.Info;
- Place := ListIter(PlaceInList.Next);
- end if;
- end Next;
-
-
- procedure ReplaceHead (L: in out List;
- Info: in BlockInfoType ) is
-
-
- begin
- if L = null then
- raise EmptyList;
- else
- L.Info := Info;
- end if;
- end ReplaceHead;
-
-
- procedure ReplaceTail (L: in out List;
- NewTail: in List ) is
- Temp_L: List;
-
-
- begin
- Destroy(L.Next);
- L.Next := NewTail;
- exception
- when constraint_error =>
- raise EmptyList;
- end ReplaceTail;
-
-
- function Tail (L: in List) return List is
-
- --| This returns the list which is the tail of L. If L is null Empty
- --| List is raised.
-
- begin
- if L = null then
- raise EmptyList;
- else
- return L.Next;
- end if;
- end Tail;
-
- function Equal (List1: in List;
- List2: in List ) return boolean is
-
- PlaceInList1: List;
- PlaceInList2: LIst;
- Contents1: BlockInfoType;
- Contents2: BlockInfoType;
-
- --| This function tests to see if two lists are equal. Two lists
- --| are equal if for all the elements of List1 the corresponding
- --| element of List2 has the same value. Thus if the 1st elements
- --| are equal and the second elements are equal and so up to n.
- --| Thus a necessary condition for two lists to be equal is that
- --| they have the same number of elements.
-
- --| This function walks over the two list and checks that the
- --| corresponding elements are equal. As soon as we reach
- --| the end of a list (PlaceInList = null) we fall out of the loop.
- --| If both PlaceInList1 and PlaceInList2 are null after exiting the loop
- --| then the lists are equal. If they both are not null the lists aren't
- --| equal. Note that equality on elements is based on a user supplied
- --| function Equal which is used to test for item equality.
-
- begin
- PlaceInList1 := List1;
- PlaceInList2 := List2;
- while (PlaceInList1 /= null) and (PlaceInList2 /= null) loop
- if not "=" (PlaceInList1.Info, PlaceInList2.Info) then
- return false;
- end if;
- PlaceInList1 := PlaceInList1.Next;
- PlaceInList2 := PlaceInList2.Next;
- end loop;
- return ((PlaceInList1 = null) and (PlaceInList2 = null) );
- end Equal;
- end Lists;
-
-
-
-
-
- end BlockInfoStack;
- end Definitions;
- ::::::::::::::
- defs.spc
- ::::::::::::::
- -- $Source: /nosc/work/tools/halstead/RCS/defs.spc,v $
- -- $Revision: 5.7 $ -- $Date: 85/09/04 09:24:19 $ -- $Author: buddy $
- with ST_Diana; use ST_Diana;
- with ML_Source_Position_Pkg;
- package Definitions is
-
- --| OVERVIEW
- --| This package defines all the data used by the Halstead program. This
- --| package also defines all the operations on the data types defined.
- --| The following is a list of all the abstract data types which
- --| this package defines.
- --|
- --|
- --| 1. DEF_ID_Set.Set from the package DEF_ID_Set
- --| 2. Literal_Set.Set from the package Literal_Set
- --| 3. BlockInfoStack.Stack from the package BlockInfoStack
- --|
- --| The types defined here are all used to create the BlockInfoType.
- --| BlockInfoType keeps all the information pertaining to current block
- --| being processed. The type is composed of four components types which
- --| are:
- --| 1. TokenCountType
- --| 2. BlockIdType
- --| 3. Literal_Set.Set
- --| 4. DEF_ID_Set.Set
- --|
- --| TokenCountType keeps track of the number of times each token appears
- --| in the source program.
- --|
- --| BlockIdType maintains the name of the current block being
- --| processed, whether the block is a body or a spec, and
- --| the type of block whether its a procedure, package...
- --|
- --| Literal_Set This keeps a counted set of all the literals
- --| appearing in a given block. These literals will be
- --| counted as operands.
- --|
- --| DEF_ID_Set.Set This keeps a list of all the identifiers encounted
- --| in a block. At the end of the block all the
- --| identifiers are categorized into operands and
- --| operators.
-
-
- --| EFFECTS
- --| Associated with the three abstract data types DEF_ID_Set.Set
- --| Literal_Set.Set and BlockInfo.Stack are a complete set of
- --| operations.
- --|
- --| The operations associated with the sets DEF_ID_Set.Set and
- --| Literal_Set.Set are counted sets. This means that a member in the
- --| set has a count associated with it. Each time an insert is done
- --| on a member the count for the member is incremented.
- --|
- --| The operations associated with BlockInfoStack are the normal
- --| stack operations Push, Pop and some others. These operations are
- --| used to stack the information associated with a block.
-
- --| TUNING
- --| One way to tune this package is to cut out a lot of the functions
- --| which are not used. For example the users of this package do not
- --| use FirstValue and some of the other operations of the list package.
-
-
- type TokenItem is (
- abortz,
- acceptz,
- accessz,
- allz,
- and_thenz,
- arrayz,
- atz,
- beginz,
- bodyz,
- body_packagez,
- body_taskz,
- casez,
- case_stmz,
- case_variantz,
- constantz,
- declarez,
- delayz,
- deltaz,
- digitsz,
- doz,
- elsez,
- else_ifz,
- else_orz,
- else_selectz,
- elsifz,
- endz,
- end_acceptz,
- end_beginz,
- end_case_stmz,
- end_case_variantz,
- end_ifz,
- end_loopz,
- end_package_bdyz,
- end_package_spcz,
- end_recordz,
- end_record_repz,
- end_selectz,
- end_task_spcz,
- entryz,
- exceptionz,
- exitz,
- forz,
- for_loopz,
- for_repz,
- functionz,
- genericz,
- gotoz,
- ifz,
- inz,
- in_loopz,
- in_membershipz,
- in_out_parameterz,
- in_parameterz,
- isz,
- is_case_stmz,
- is_case_variantz,
- is_functionz,
- is_genericz,
- is_package_bdyz,
- is_package_spcz,
- is_procedurez,
- is_separatez,
- is_subtypez,
- is_typez,
- is_task_bdyz,
- is_task_spcz,
- limitedz,
- loopz,
- modz,
- newz,
- new_allocatorz,
- new_derived_typez,
- new_generic_instz,
- not_in_membershipz,
- nullz,
- null_valuez,
- null_stmz,
- null_fieldz,
- ofz,
- orz,
- or_elsez,
- or_selectz,
- othersz,
- others_aggregatez,
- others_casez,
- others_exceptionz,
- others_variantz,
- outz,
- packagez,
- package_bdyz,
- package_spcz,
- pragmaz,
- privatez,
- private_sectionz,
- private_typez,
- procedurez,
- raisez,
- rangez,
- recordz,
- record_typez,
- record_repz,
- renamesz,
- returnz,
- reversez,
- selectz,
- separatez,
- subtypez,
- taskz,
- task_bdyz,
- task_spcz,
- terminatez,
- thenz,
- then_andz,
- typez,
- usez,
- use_contextz,
- use_repz,
- whenz,
- when_case_stmz,
- when_exitz,
- when_exceptionz,
- when_selectz,
- when_case_variantz,
- whilez,
- withz,
- with_contextz,
- with_genericz,
- ------------- punctuation --------------
- arrowz,
- barz,
- boxz,
- box_rangez,
- box_default_subpz,
- character_literalz,
- closed_anglesz,
- closed_parenthesisz,
- colon_equalsz,
- colonz,
- commaz,
- dotz,
- dot_dot_rangez,
- double_quotez,
- numeric_literalz,
- open_anglesz,
- open_parenthesisz,
- semicolonz,
- single_quotez,
- tickz,
- declare_blockz
- );
- --| These are all the tokens which could possibly be counted by
- --| Halstead.
-
- type Class is (operator, operand, neither);
- --| These are the different ways to classify symbols in the source
- --| program.
-
- type TokenCountType is array(TokenItem) of natural;
- --| This type is used to count the occurrences of each token
- --| in the source program.
-
- type TokenClassificationType is array(TokenItem) of Class;
- --| This type is used to defined whether tokens are operators
- --| or operands or neither.
-
- type BlockKind is ( procedure_block,
- function_block,
- package_body_block,
- package_spec_block,
- task_body_block,
- task_spec_block,
- declare_block );
- --| This keeps track of the type of block being processed currently.
-
-
- BlockNameLength: constant := 16;
- --| Maximum length of a block name.
-
- SpcBdyIdLength: constant := 13;
- --| Maximum lenght of a string which indicates whether a block
- --| is a spec, body, or declare block.
-
- subtype SpcBdyIdType is string(1..SpcBdyIdLength);
-
- AnonId :constant SpcBdyIdType := " ";
- BdyId :constant SpcBdyIdType := "BODY ";
- DecId :constant SpcBdyIdType := "DECLARE BLOCK";
- SpcId :constant SpcBdyIdType := "SPECIFICATION";
- --| These are used to initialize the SpcOrBdyId field of
- --| BlockIdType.
-
- type StringPtr is access String;
- --| This is used to keep track of the fully qualified name of the
- --| block being processed. Each time a new scope is entered
- --| the name of that scope is concatenated with the current
- --| fully qualified name.
-
- type BlockIdType is
- record
- KindOfBlock :BlockKind;
- SpcBdyId :SpcBdyIdType;
- BlockName :StringPtr;
- LineLocation :ML_Source_Position_Pkg.Source_Line;
- end record;
- --| This type keeps track of the name of a block. For instance
- --| if we are processing the body of procedure P then the name
- --| of the block is P. The KindOfBlock is "PROCEDURE" and
- --| SpcOrBdyId = "(B)".
-
-
-
-
-
-
- --| The following code represents a generic instantiation of the
- --| OrderedSet package. It replaces:
- --|
- --| package DEF_ID_Set is new OrderedSet
- --| (ItemType => DEF_ID.Locator,
- --| "<" => ST_Diana.DEF_ID."<");
-
-
- --------------------------------------------------------------------------
- -- GENERIC INSTANTIATION
- --------------------------------------------------------------------------
-
- function "<" ( X, Y: DEF_ID.Locator) return boolean
- renames ST_Diana.DEF_ID."<";
-
- package DEF_ID_Set is
-
- --| Overview
- --| This abstractions is a counted ordered set. This means that
- --| associated with each member of the set is a count of the number of
- --| times it appears in the set. The order part means that there is
- --| an ordering associated with the members. This allows fast insertion.
- --| It also makes it easy to iterate over the set in order.
-
-
-
- -- Types
- -- -----
-
- type Set is private; --| This is the type exported to represent
- --| the ordered set.
-
- type SetIter is private; --| This is the type exported whose
- --| purpose is to walk over a set.
-
-
- -- Operations
- -- ----------
-
- --| Cardinality Returns cardinality of the set.
- --| Create Creates the empty set.
- --| CountMember Returns the number of times the member appears in
- --| the set.
- --| Destroy Destroys a set and returns the space it occupies.
- --| Insert Insert a member into the set.
- --| MakeSetIter Return a SetIter which will begin an iteration.
- --| More Are there more elements to iterate over in the
- --| set.
- --| Next Return the next element in the iteration and
- --| bump the iterator.
-
-
- ------------------------------------------------------------------------------
-
- function Cardinality ( --| Return the number of members in the set.
- S :in Set --| The set whose members are being counted.
- ) return natural;
-
- ------------------------------------------------------------------------------
-
-
- function Create --| Return the empty set.
- return Set;
-
- ------------------------------------------------------------------------------
-
- procedure Destroy ( --| Destroy a set and return its space.
- S :in out Set --| Set being destroyed.
-
- );
-
- ------------------------------------------------------------------------------
-
- function GetCount ( --| This returns the count associated with
- --| member which corresponds to the current
- --| iterator I.
- I :in SetIter
- ) return natural;
-
- -----------------------------------------------------------------------------
-
- procedure Insert ( --| Insert a member M into set S.
- M :in DEF_ID.Locator; --| Member being inserted.
- S :in out Set --| Set being inserted into.
- );
-
- ------------------------------------------------------------------------------
-
- function MakeSetIter ( --| Prepares a user for an iteration operation by
- --| by returning a SetIter.
- S :in Set --| Set being iterate over.
- ) return SetIter;
-
- ------------------------------------------------------------------------------
-
- function More ( --| Returns true if there are more elements in the
- --| set to iterate over.
- I :in SetIter --| The iterator.
-
- ) return boolean;
-
- ------------------------------------------------------------------------------
-
- procedure Next ( --| Returns the current member in the iteration
- --| an increments the iterator.
- I :in out SetIter; --| The iterator.
- M : out DEF_ID.Locator --| The current member being returned.
- );
-
- -----------------------------------------------------------------------------
-
- private
-
- type Member is
- record
- Info :DEF_ID.Locator;
- Count :natural;
- end record;
-
- function "<" (
- X:in Member;
- Y:in Member
- ) return boolean;
-
- -- generic instantiation
- --package TreePkg is new BinaryTrees ( DEF_ID.Locator => Member, "<" => "<" );
-
-
- package TreePkg is
-
-
- --| Overview
- --| This package creates an ordered binary tree. This will allow for
- --| quick insertion, and search.
- --|
- --| The tree is organized such that
- --|
- --| leftchild < root root < rightchild
- --|
- --| This means that by doing a left to right search of the tree will can
- --| produce the nodes of the tree in ascending order.
-
-
-
-
-
- -- Types
- -- -----
-
- type Tree is private; --| This is the type exported to represent the
- --| tree.
-
-
- type TreeIter is private; --| This is the type which is used to iterate
- --| over the set.
-
- --| Exceptions
- --| ----------
-
- --| Operations
- --| ----------
- --|
- --| Create Creates a tree.
- --| Deposit Replaces the given node's information with
- --| the given information.
- --| DestroyTree Destroys the given tree and returns the spaces.
- --| InsertNode This inserts a node n into a tree t.
- --| MakeTreeIter This returns an iterator to the user in order to start
- --| an iteration.
- --| More This returns true if there are more elements to iterate
- --| over in the tree.
- --| Next This returns the information associated with the current
- --| iterator and advances the iterator.
-
-
- ---------------------------------------------------------------------------
-
- function Create --| This function creates the tree.
-
- return Tree;
-
- --| Effects
- --| This creates a tree containing no information and no children. An
- --| emptytree.
-
- -------------------------------------------------------------------------------
-
- procedure Deposit ( --| This deposits the information I in the
- --| root of the Tree S.
- I :in Member; --| The information being deposited.
- S :in Tree --| The tree where the information is being
- --| stored.
- );
-
- --| Modifies
- --| This changes the information stored at the root of the tree S.
-
- -------------------------------------------------------------------------------
-
-
- procedure DestroyTree ( --| Destroys a tree.
- T :in out Tree --| Tree being destroyed.
- );
-
- --| Effects
- --| Destroys a tree and returns the space which it is occupying.
-
- --------------------------------------------------------------------------
-
- Procedure Insertnode( --| This Procedure Inserts A Node Into The
- --| Specified Tree.
- N :In Out Member; --| The Information To Be Contained In The
- --| Node Being Inserted.
-
- T :In Out Tree; --| Tree Being Inserted Into.
- Root : Out Tree; --| Root of the subtree which Node N heads.
- --| This is the position of the node N in T.
- Exists : out boolean --| If this node already exists in the tree
- --| Exists is true. If this is the first
- --| insertion Exists is false.
- );
-
- --| Effects
- --| This adds the node N to the tree T inserting in the proper postion.
-
- --| Modifies
- --| This modifies the tree T by add the node N to it.
-
- ------------------------------------------------------------------------------
-
- function MakeTreeIter ( --| Sets a variable to a position in the
- --| tree
- --| where the iteration is to begin. In this
- --| case the position is a pointer to the
- --| the deepest leftmost leaf in the tree.
- T:in Tree --| Tree being iterated over
- ) return TreeIter;
-
-
- --| Effects
-
-
- -----------------------------------------------------------------------------
-
- function More ( --| Returns true if there are more elements
- --| in the tree to iterate over.
- I :in TreeIter
- ) return boolean;
-
-
- -----------------------------------------------------------------------------
-
- procedure Next ( --| This is the iterator operation. Given
- --| an Iter in the Tree it returns the
- --| item Iter points to and updates the
- --| iter. If Iter is at the end of the Tree,
- --| yielditer returns false otherwise it
- --| returns true.
- I :in out TreeIter; --| The iter which marks the position in the
- --| Tree.
-
- Info : out Member --| Information being returned from a node.
- );
-
-
- ---------------------------------------------------------------------------
-
- private
-
- type Node;
- type Tree is access Node;
-
- type Node is
- record
- Info :Member;
- LeftChild :Tree;
- RightChild :Tree;
- end record;
-
- --- The following is a generic instantiation of NodeOrder
- --- package NodeOrder is new Lists (Tree);
-
-
- package NodeOrder is
-
- --| This package provides singly linked lists with elements of type
- --| Tree, where Tree is specified by a generic parameter.
-
- --| Overview
- --| When this package is instantiated, it provides a linked list type for
- --| lists of objects of type Tree, which can be any desired type. A
- --| complete set of operations for manipulation, and releasing
- --| those lists is also provided. For instance, to make lists of strings,
- --| all that is necessary is:
- --|
- --| type StringType is string(1..10);
- --|
- --| package Str_List is new Lists(StringType); use Str_List;
- --|
- --| L:List;
- --| S:StringType;
- --|
- --| Then to add a string S, to the list L, all that is necessary is
- --|
- --| L := Create;
- --| Attach(S,L);
- --|
- --|
- --| This package provides basic list operations.
- --|
- --| Attach append an object to an object, an object to a list,
- --| or a list to an object, or a list to a list.
- --| Copy copy a list using := on elements
- --| CopyDeep copy a list by copying the elements using a copy
- --| operation provided by the user
- --| Create Creates an empty list
- --| DeleteHead removes the head of a list
- --| DeleteItem delete the first occurrence of an element from a list
- --| DeleteItems delete all occurrences of an element from a list
- --| Destroy remove a list
- --| Equal are two lists equal
- --| FirstValue get the information from the first element of a list
- --| IsInList determines whether a given element is in a given list
- --| IsEmpty returns true if the list is empty
- --| LastValue return the last value of a list
- --| Length Returns the length of a list
- --| MakeListIter prepares for an iteration over a list
- --| More are there any more items in the list
- --| Next get the next item in a list
- --| ReplaceHead replace the information at the head of the list
- --| ReplaceTail replace the tail of a list with a new list
- --| Tail get the tail of a list
- --|
-
- --| N/A: Effects, Requires, Modifies, and Raises.
-
- --| Notes
- --| Programmer Buddy Altus
-
- --| Types
- --| -----
-
- type List is private;
- type ListIter is private;
-
-
- --| Exceptions
- --| ----------
-
- CircularList :exception; --| Raised if an attemp is made to
- --| create a circular list. This
- --| results when a list is attempted
- --| to be attached to itself.
-
- EmptyList :exception; --| Raised if an attemp is made to
- --| manipulate an empty list.
-
- ItemNotPresent :exception; --| Raised if an attempt is made to
- --| remove an element from a list in
- --| which it does not exist.
-
- NoMore :exception; --| Raised if an attemp is made to
- --| get the next element from a list
- --| after iteration is complete.
-
-
-
- --| Operations
- --| ----------
-
- ----------------------------------------------------------------------------
-
- procedure Attach( --| appends List2 to List1
- List1: in out List; --| The list being appended to.
- List2: in List --| The list being appended.
- );
-
- --| Raises
- --| CircularList
-
- --| Effects
- --| Appends List1 to List2. This makes the next field of the last element
- --| of List1 refer to List2. This can possibly change the value of List1
- --| if List1 is an empty list. This causes sharing of lists. Thus if
- --| user Destroys List1 then List2 will be a dangling reference.
- --| This procedure raises CircularList if List1 equals List2. If it is
- --| necessary to Attach a list to itself first make a copy of the list and
- --| attach the copy.
-
- --| Modifies
- --| Changes the next field of the last element in List1 to be List2.
-
- -------------------------------------------------------------------------------
-
- function Attach( --| Creates a new list containing the two
- --| Elements.
- Element1: in Tree; --| This will be first element in list.
- Element2: in Tree --| This will be second element in list.
- ) return List;
-
- --| Effects
- --| This creates a list containing the two elements in the order
- --| specified.
-
- -------------------------------------------------------------------------------
- procedure Attach( --| List L is appended with Element.
- L: in out List; --| List being appended to.
- Element: in Tree --| This will be last element in l ist.
- );
-
- --| Effects
- --| Appends Element onto the end of the list L. If L is empty then this
- --| may change the value of L.
- --|
- --| Modifies
- --| This appends List L with Element by changing the next field in List.
-
- --------------------------------------------------------------------------------
- procedure Attach( --| Makes Element first item in list L.
- Element: in Tree; --| This will be the first element in list.
- L: in out List --| The List which Element is being
- --| prepended to.
- );
-
- --| Effects
- --| This prepends list L with Element.
- --|
- --| Modifies
- --| This modifies the list L.
-
- --------------------------------------------------------------------------
-
- function Attach ( --| attaches two lists
- List1: in List; --| first list
- List2: in List --| second list
- ) return List;
-
- --| Raises
- --| CircularList
-
- --| Effects
- --| This returns a list which is List1 attached to List2. If it is desired
- --| to make List1 be the new attached list the following ada code should be
- --| used.
- --|
- --| List1 := Attach (List1, List2);
- --| This procedure raises CircularList if List1 equals List2. If it is
- --| necessary to Attach a list to itself first make a copy of the list and
- --| attach the copy.
-
- -------------------------------------------------------------------------
-
- function Attach ( --| prepends an element onto a list
- Element: in Tree; --| element being prepended to list
- L: in List --| List which element is being added
- --| to
- ) return List;
-
- --| Effects
- --| Returns a new list which is headed by Element and followed by L.
-
- ------------------------------------------------------------------------
-
- function Attach ( --| Adds an element to the end of a list
- L: in List; --| The list which element is being added to.
- Element: in Tree --| The element being added to the end of
- --| the list.
- ) return List;
-
- --| Effects
- --| Returns a new list which is L followed by Element.
-
- --------------------------------------------------------------------------
-
-
- function Copy( --| returns a copy of list1
- L: in List --| list being copied
- ) return List;
-
- --| Effects
- --| Returns a copy of L.
-
- --------------------------------------------------------------------------
-
-
- function Create --| Returns an empty List
-
- return List;
-
- ------------------------------------------------------------------------------
-
- procedure DeleteHead( --| Remove the head element from a list.
- L: in out List --| The list whose head is being removed.
- );
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| This will return the space occupied by the first element in the list
- --| to the heap. If sharing exists between lists this procedure
- --| could leave a dangling reference. If L is empty EmptyList will be
- --| raised.
-
- ------------------------------------------------------------------------------
-
- procedure DeleteItem( --| remove the first occurrence of Element
- --| from L
- L: in out List; --| list element is being removed from
- Element: in Tree --| element being removed
- );
-
- --| Raises
- --| ItemNotPresent
-
- --| Effects
- --| Removes the first element of the list equal to Element. If there is
- --| not an element equal to Element than ItemNotPresent is raised.
-
- --| Modifies
- --| This operation is destructive, it returns the storage occupied by
- --| the elements being deleted.
-
- ------------------------------------------------------------------------------
-
- procedure DeleteItems( --| remove all occurrences of Element
- --| from L.
- L: in out List; --| The List element is being removed from
- Element: in Tree --| element being removed
- );
-
- --| Raises
- --| ItemNotPresent
- --|
- --| Effects
- --| This procedure walks down the list L and removes all elements of the
- --| list equal to Element. If there are not any elements equal to Element
- --| then raise ItemNotPresent.
-
- --| Modifies
- --| This operation is destructive the storage occupied by the items
- --| removed is returned.
-
- ------------------------------------------------------------------------------
-
- procedure Destroy( --| removes the list
- L: in out List --| the list being removed
- );
-
- --| Effects
- --| This returns to the heap all the storage that a list occupies. Keep in
- --| mind if there exists sharing between lists then this operation can leave
- --| dangling references.
-
- ------------------------------------------------------------------------------
-
- function FirstValue( --| returns the contents of the first record of the
- --| list
- L: in List --| the list whose first element is being
- --| returned
-
- ) return Tree;
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| This returns the Item in the first position in the list. If the list
- --| is empty EmptyList is raised.
-
- -------------------------------------------------------------------------------
-
- function IsEmpty( --| Checks if a list is empty.
- L: in List --| List being checked.
- ) return boolean;
-
- --------------------------------------------------------------------------
-
- function IsInList( --| Checks if element is an element of
- --| list.
- L: in List; --| list being scanned for element
- Element: in Tree --| element being searched for
- ) return boolean;
-
- --| Effects
- --| Walks down the list L looking for an element whose value is Element.
-
- ------------------------------------------------------------------------------
-
- function LastValue( --| Returns the contents of the last record of
- --| the list.
- L: in List --| The list whose first element is being
- --| returned.
- ) return Tree;
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| Returns the last element in a list. If the list is empty EmptyList is
- --| raised.
-
-
- ------------------------------------------------------------------------------
-
- function Length( --| count the number of elements on a list
- L: in List --| list whose length is being computed
- ) return integer;
-
- ------------------------------------------------------------------------------
-
- function MakeListIter( --| Sets a variable to point to the head
- --| of the list. This will be used to
- --| prepare for iteration over a list.
- L: in List --| The list being iterated over.
- ) return ListIter;
-
-
- --| This prepares a user for iteration operation over a list. The iterater is
- --| an operation which returns successive elements of the list on successive
- --| calls to the iterator. There needs to be a mechanism which marks the
- --| position in the list, so on successive calls to the Next operation the
- --| next item in the list can be returned. This is the function of the
- --| MakeListIter and the type ListIter. MakeIter just sets the Iter to the
- --| the beginning of the list. On subsequent calls to NextList the Iter
- --| is updated with each call.
-
- -----------------------------------------------------------------------------
-
- function More( --| Returns true if there are more elements in
- --| the and false if there aren't any more
- --| the in the list.
- L: in ListIter --| List being checked for elements.
- ) return boolean;
-
- ------------------------------------------------------------------------------
-
- procedure Next( --| This is the iterator operation. Given
- --| a ListIter in the list it returns the
- --| current item and updates the ListIter.
- --| If ListIter is at the end of the list,
- --| More returns false otherwise it
- --| returns true.
- Place: in out ListIter; --| The Iter which marks the position in
- --| the list.
- Info: out Tree --| The element being returned.
-
- );
-
- --| The iterators subprograms MakeListIter, More, and NextList should be used
- --| in the following way:
- --|
- --| L: List;
- --| Place: ListIter;
- --| Info: SomeType;
- --|
- --|
- --| Place := MakeListIter(L);
- --|
- --| while ( More(Place) ) loop
- --| NextList(Place, Info);
- --| process each element of list L;
- --| end loop;
-
-
- ----------------------------------------------------------------------------
-
- procedure ReplaceHead( --| Replace the Item at the head of the list
- --| with the parameter Item.
- L: in out List; --| The list being modified.
- Info: in Tree --| The information being entered.
- );
- --| Raises
- --| EmptyList
-
- --| Effects
- --| Replaces the information in the first element in the list. Raises
- --| EmptyList if the list is empty.
-
- ------------------------------------------------------------------------------
-
- procedure ReplaceTail( --| Replace the Tail of a list
- --| with a new list.
- L: in out List; --| List whose Tail is replaced.
- NewTail: in List --| The list which will become the
- --| tail of Oldlist.
- );
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| Replaces the tail of a list with a new list. If the list whose tail
- --| is being replaced is null EmptyList is raised.
-
- -------------------------------------------------------------------------------
-
- function Tail( --| returns the tail of a list L
- L: in List --| the list whose tail is being returned
- ) return List;
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| Returns a list which is the tail of the list L. Raises EmptyList if
- --| L is empty. If L only has one element then Tail returns the Empty
- --| list.
-
- ------------------------------------------------------------------------------
-
- function Equal( --| compares list1 and list2 for equality
- List1: in List; --| first list
- List2: in List --| second list
- ) return boolean;
-
- --| Effects
- --| Returns true if for all elements of List1 the corresponding element
- --| of List2 has the same value. This function uses the Equal operation
- --| provided by the user. If one is not provided then = is used.
-
- ------------------------------------------------------------------------------
- private
- type Cell;
-
- type List is access Cell; --| pointer added by this package
- --| in order to make a list
-
-
- type Cell is --| Cell for the lists being created
- record
- Info: Tree;
- Next: List;
- end record;
-
-
- type ListIter is new List; --| This prevents Lists being assigned to
- --| iterators and vice versa
-
- end NodeOrder;
-
- type TreeIter is
- record
- NodeList :NodeOrder.List;
- State :NodeOrder.ListIter;
- end record;
-
-
- end TreePkg;
- type Set is
- record
- SetRep :TreePkg.Tree;
- end record;
-
- type SetIter is
- record
- Place :TreePkg.TreeIter;
- Count :natural;
- end record;
-
- end DEF_ID_Set;
-
-
- function "<" ( --| This is used to order the Source_Text.Locs
- X :in Source_Text.Locator;
- Y :in Source_Text.Locator
- ) return boolean;
-
- -- generic
- -- type Source_Text.Locator is private;
- -- with function "<" ( X ,Y: in Source_Text.Locator) return boolean;
-
- package Literal_Set is
-
- --| Overview
- --| This abstractions is a counted ordered set. This means that
- --| associated with each member of the set is a count of the number of
- --| times it appears in the set. The order part means that there is
- --| an ordering associated with the members. This allows fast insertion.
- --| It also makes it easy to iterate over the set in order.
-
-
-
- -- Types
- -- -----
-
- type Set is private; --| This is the type exported to represent
- --| the ordered set.
-
- type SetIter is private; --| This is the type exported whose
- --| purpose is to walk over a set.
-
-
- -- Operations
- -- ----------
-
- --| Cardinality Returns cardinality of the set.
- --| Create Creates the empty set.
- --| CountMember Returns the number of times the member appears in
- --| the set.
- --| Destroy Destroys a set and returns the space it occupies.
- --| Insert Insert a member into the set.
- --| MakeSetIter Return a SetIter which will begin an iteration.
- --| More Are there more elements to iterate over in the
- --| set.
- --| Next Return the next element in the iteration and
- --| bump the iterator.
-
-
- ------------------------------------------------------------------------------
-
- function Cardinality ( --| Return the number of members in the set.
- S :in Set --| The set whose members are being counted.
- ) return natural;
-
- ------------------------------------------------------------------------------
-
-
- function Create --| Return the empty set.
- return Set;
-
- ------------------------------------------------------------------------------
-
- procedure Destroy ( --| Destroy a set and return its space.
- S :in out Set --| Set being destroyed.
-
- );
-
- ------------------------------------------------------------------------------
-
- function GetCount ( --| This returns the count associated with
- --| member which corresponds to the current
- --| iterator I.
- I :in SetIter
- ) return natural;
-
- -----------------------------------------------------------------------------
-
- procedure Insert ( --| Insert a member M into set S.
- M :in Source_Text.Locator; --| Member being inserted.
- S :in out Set --| Set being inserted into.
- );
-
- ------------------------------------------------------------------------------
-
- function MakeSetIter ( --| Prepares a user for an iteration operation by
- --| by returning a SetIter.
- S :in Set --| Set being iterate over.
- ) return SetIter;
-
- ------------------------------------------------------------------------------
-
- function More ( --| Returns true if there are more elements in the
- --| set to iterate over.
- I :in SetIter --| The iterator.
-
- ) return boolean;
-
- ------------------------------------------------------------------------------
-
- procedure Next ( --| Returns the current member in the iteration
- --| an increments the iterator.
- I :in out SetIter; --| The iterator.
- M : out Source_Text.Locator --| The current member being returned.
- );
-
- -----------------------------------------------------------------------------
-
- private
-
- type Member is
- record
- Info :Source_Text.Locator;
- Count :natural;
- end record;
-
- function "<" (
- X:in Member;
- Y:in Member
- ) return boolean;
-
- -- generic instantiation
- --package TreePkg is new BinaryTrees ( Source_Text.Locator => Member, "<" => "<" );
-
-
- package TreePkg is
-
-
- --| Overview
- --| This package creates an ordered binary tree. This will allow for
- --| quick insertion, and search.
- --|
- --| The tree is organized such that
- --|
- --| leftchild < root root < rightchild
- --|
- --| This means that by doing a left to right search of the tree will can
- --| produce the nodes of the tree in ascending order.
-
-
-
-
-
- -- Types
- -- -----
-
- type Tree is private; --| This is the type exported to represent the
- --| tree.
-
-
- type TreeIter is private; --| This is the type which is used to iterate
- --| over the set.
-
- --| Exceptions
- --| ----------
-
- --| Operations
- --| ----------
- --|
- --| Create Creates a tree.
- --| Deposit Replaces the given node's information with
- --| the given information.
- --| DestroyTree Destroys the given tree and returns the spaces.
- --| InsertNode This inserts a node n into a tree t.
- --| MakeTreeIter This returns an iterator to the user in order to start
- --| an iteration.
- --| More This returns true if there are more elements to iterate
- --| over in the tree.
- --| Next This returns the information associated with the current
- --| iterator and advances the iterator.
-
-
- ---------------------------------------------------------------------------
-
- function Create --| This function creates the tree.
-
- return Tree;
-
- --| Effects
- --| This creates a tree containing no information and no children. An
- --| emptytree.
-
- -------------------------------------------------------------------------------
-
- procedure Deposit ( --| This deposits the information I in the
- --| root of the Tree S.
- I :in Member; --| The information being deposited.
- S :in Tree --| The tree where the information is being
- --| stored.
- );
-
- --| Modifies
- --| This changes the information stored at the root of the tree S.
-
- -------------------------------------------------------------------------------
-
-
- procedure DestroyTree ( --| Destroys a tree.
- T :in out Tree --| Tree being destroyed.
- );
-
- --| Effects
- --| Destroys a tree and returns the space which it is occupying.
-
- --------------------------------------------------------------------------
-
- Procedure Insertnode( --| This Procedure Inserts A Node Into The
- --| Specified Tree.
- N :In Out Member; --| The Information To Be Contained In The
- --| Node Being Inserted.
-
- T :In Out Tree; --| Tree Being Inserted Into.
- Root : Out Tree; --| Root of the subtree which Node N heads.
- --| This is the position of the node N in T.
- Exists : out boolean --| If this node already exists in the tree
- --| Exists is true. If this is the first
- --| insertion Exists is false.
- );
-
- --| Effects
- --| This adds the node N to the tree T inserting in the proper postion.
-
- --| Modifies
- --| This modifies the tree T by add the node N to it.
-
- ------------------------------------------------------------------------------
-
- function MakeTreeIter ( --| Sets a variable to a position in the
- --| tree
- --| where the iteration is to begin. In this
- --| case the position is a pointer to the
- --| the deepest leftmost leaf in the tree.
- T:in Tree --| Tree being iterated over
- ) return TreeIter;
-
-
- --| Effects
-
-
- -----------------------------------------------------------------------------
-
- function More ( --| Returns true if there are more elements
- --| in the tree to iterate over.
- I :in TreeIter
- ) return boolean;
-
-
- -----------------------------------------------------------------------------
-
- procedure Next ( --| This is the iterator operation. Given
- --| an Iter in the Tree it returns the
- --| item Iter points to and updates the
- --| iter. If Iter is at the end of the Tree,
- --| yielditer returns false otherwise it
- --| returns true.
- I :in out TreeIter; --| The iter which marks the position in the
- --| Tree.
-
- Info : out Member --| Information being returned from a node.
- );
-
-
- ---------------------------------------------------------------------------
-
- private
-
- type Node;
- type Tree is access Node;
-
- type Node is
- record
- Info :Member;
- LeftChild :Tree;
- RightChild :Tree;
- end record;
-
- --- The following is a generic instantiation of NodeOrder
- --- package NodeOrder is new Lists (Tree);
-
-
- package NodeOrder is
-
- --| This package provides singly linked lists with elements of type
- --| Tree, where Tree is specified by a generic parameter.
-
- --| Overview
- --| When this package is instantiated, it provides a linked list type for
- --| lists of objects of type Tree, which can be any desired type. A
- --| complete set of operations for manipulation, and releasing
- --| those lists is also provided. For instance, to make lists of strings,
- --| all that is necessary is:
- --|
- --| type StringType is string(1..10);
- --|
- --| package Str_List is new Lists(StringType); use Str_List;
- --|
- --| L:List;
- --| S:StringType;
- --|
- --| Then to add a string S, to the list L, all that is necessary is
- --|
- --| L := Create;
- --| Attach(S,L);
- --|
- --|
- --| This package provides basic list operations.
- --|
- --| Attach append an object to an object, an object to a list,
- --| or a list to an object, or a list to a list.
- --| Copy copy a list using := on elements
- --| CopyDeep copy a list by copying the elements using a copy
- --| operation provided by the user
- --| Create Creates an empty list
- --| DeleteHead removes the head of a list
- --| DeleteItem delete the first occurrence of an element from a list
- --| DeleteItems delete all occurrences of an element from a list
- --| Destroy remove a list
- --| Equal are two lists equal
- --| FirstValue get the information from the first element of a list
- --| IsInList determines whether a given element is in a given list
- --| IsEmpty returns true if the list is empty
- --| LastValue return the last value of a list
- --| Length Returns the length of a list
- --| MakeListIter prepares for an iteration over a list
- --| More are there any more items in the list
- --| Next get the next item in a list
- --| ReplaceHead replace the information at the head of the list
- --| ReplaceTail replace the tail of a list with a new list
- --| Tail get the tail of a list
- --|
-
- --| N/A: Effects, Requires, Modifies, and Raises.
-
- --| Notes
- --| Programmer Buddy Altus
-
- --| Types
- --| -----
-
- type List is private;
- type ListIter is private;
-
-
- --| Exceptions
- --| ----------
-
- CircularList :exception; --| Raised if an attemp is made to
- --| create a circular list. This
- --| results when a list is attempted
- --| to be attached to itself.
-
- EmptyList :exception; --| Raised if an attemp is made to
- --| manipulate an empty list.
-
- ItemNotPresent :exception; --| Raised if an attempt is made to
- --| remove an element from a list in
- --| which it does not exist.
-
- NoMore :exception; --| Raised if an attemp is made to
- --| get the next element from a list
- --| after iteration is complete.
-
-
-
- --| Operations
- --| ----------
-
- ----------------------------------------------------------------------------
-
- procedure Attach( --| appends List2 to List1
- List1: in out List; --| The list being appended to.
- List2: in List --| The list being appended.
- );
-
- --| Raises
- --| CircularList
-
- --| Effects
- --| Appends List1 to List2. This makes the next field of the last element
- --| of List1 refer to List2. This can possibly change the value of List1
- --| if List1 is an empty list. This causes sharing of lists. Thus if
- --| user Destroys List1 then List2 will be a dangling reference.
- --| This procedure raises CircularList if List1 equals List2. If it is
- --| necessary to Attach a list to itself first make a copy of the list and
- --| attach the copy.
-
- --| Modifies
- --| Changes the next field of the last element in List1 to be List2.
-
- -------------------------------------------------------------------------------
-
- function Attach( --| Creates a new list containing the two
- --| Elements.
- Element1: in Tree; --| This will be first element in list.
- Element2: in Tree --| This will be second element in list.
- ) return List;
-
- --| Effects
- --| This creates a list containing the two elements in the order
- --| specified.
-
- -------------------------------------------------------------------------------
- procedure Attach( --| List L is appended with Element.
- L: in out List; --| List being appended to.
- Element: in Tree --| This will be last element in l ist.
- );
-
- --| Effects
- --| Appends Element onto the end of the list L. If L is empty then this
- --| may change the value of L.
- --|
- --| Modifies
- --| This appends List L with Element by changing the next field in List.
-
- --------------------------------------------------------------------------------
- procedure Attach( --| Makes Element first item in list L.
- Element: in Tree; --| This will be the first element in list.
- L: in out List --| The List which Element is being
- --| prepended to.
- );
-
- --| Effects
- --| This prepends list L with Element.
- --|
- --| Modifies
- --| This modifies the list L.
-
- --------------------------------------------------------------------------
-
- function Attach ( --| attaches two lists
- List1: in List; --| first list
- List2: in List --| second list
- ) return List;
-
- --| Raises
- --| CircularList
-
- --| Effects
- --| This returns a list which is List1 attached to List2. If it is desired
- --| to make List1 be the new attached list the following ada code should be
- --| used.
- --|
- --| List1 := Attach (List1, List2);
- --| This procedure raises CircularList if List1 equals List2. If it is
- --| necessary to Attach a list to itself first make a copy of the list and
- --| attach the copy.
-
- -------------------------------------------------------------------------
-
- function Attach ( --| prepends an element onto a list
- Element: in Tree; --| element being prepended to list
- L: in List --| List which element is being added
- --| to
- ) return List;
-
- --| Effects
- --| Returns a new list which is headed by Element and followed by L.
-
- ------------------------------------------------------------------------
-
- function Attach ( --| Adds an element to the end of a list
- L: in List; --| The list which element is being added to.
- Element: in Tree --| The element being added to the end of
- --| the list.
- ) return List;
-
- --| Effects
- --| Returns a new list which is L followed by Element.
-
- --------------------------------------------------------------------------
-
-
- function Copy( --| returns a copy of list1
- L: in List --| list being copied
- ) return List;
-
- --| Effects
- --| Returns a copy of L.
-
- --------------------------------------------------------------------------
-
-
- function Create --| Returns an empty List
-
- return List;
-
- ------------------------------------------------------------------------------
-
- procedure DeleteHead( --| Remove the head element from a list.
- L: in out List --| The list whose head is being removed.
- );
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| This will return the space occupied by the first element in the list
- --| to the heap. If sharing exists between lists this procedure
- --| could leave a dangling reference. If L is empty EmptyList will be
- --| raised.
-
- ------------------------------------------------------------------------------
-
- procedure DeleteItem( --| remove the first occurrence of Element
- --| from L
- L: in out List; --| list element is being removed from
- Element: in Tree --| element being removed
- );
-
- --| Raises
- --| ItemNotPresent
-
- --| Effects
- --| Removes the first element of the list equal to Element. If there is
- --| not an element equal to Element than ItemNotPresent is raised.
-
- --| Modifies
- --| This operation is destructive, it returns the storage occupied by
- --| the elements being deleted.
-
- ------------------------------------------------------------------------------
-
- procedure DeleteItems( --| remove all occurrences of Element
- --| from L.
- L: in out List; --| The List element is being removed from
- Element: in Tree --| element being removed
- );
-
- --| Raises
- --| ItemNotPresent
- --|
- --| Effects
- --| This procedure walks down the list L and removes all elements of the
- --| list equal to Element. If there are not any elements equal to Element
- --| then raise ItemNotPresent.
-
- --| Modifies
- --| This operation is destructive the storage occupied by the items
- --| removed is returned.
-
- ------------------------------------------------------------------------------
-
- procedure Destroy( --| removes the list
- L: in out List --| the list being removed
- );
-
- --| Effects
- --| This returns to the heap all the storage that a list occupies. Keep in
- --| mind if there exists sharing between lists then this operation can leave
- --| dangling references.
-
- ------------------------------------------------------------------------------
-
- function FirstValue( --| returns the contents of the first record of the
- --| list
- L: in List --| the list whose first element is being
- --| returned
-
- ) return Tree;
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| This returns the Item in the first position in the list. If the list
- --| is empty EmptyList is raised.
-
- -------------------------------------------------------------------------------
-
- function IsEmpty( --| Checks if a list is empty.
- L: in List --| List being checked.
- ) return boolean;
-
- --------------------------------------------------------------------------
-
- function IsInList( --| Checks if element is an element of
- --| list.
- L: in List; --| list being scanned for element
- Element: in Tree --| element being searched for
- ) return boolean;
-
- --| Effects
- --| Walks down the list L looking for an element whose value is Element.
-
- ------------------------------------------------------------------------------
-
- function LastValue( --| Returns the contents of the last record of
- --| the list.
- L: in List --| The list whose first element is being
- --| returned.
- ) return Tree;
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| Returns the last element in a list. If the list is empty EmptyList is
- --| raised.
-
-
- ------------------------------------------------------------------------------
-
- function Length( --| count the number of elements on a list
- L: in List --| list whose length is being computed
- ) return integer;
-
- ------------------------------------------------------------------------------
-
- function MakeListIter( --| Sets a variable to point to the head
- --| of the list. This will be used to
- --| prepare for iteration over a list.
- L: in List --| The list being iterated over.
- ) return ListIter;
-
-
- --| This prepares a user for iteration operation over a list. The iterater is
- --| an operation which returns successive elements of the list on successive
- --| calls to the iterator. There needs to be a mechanism which marks the
- --| position in the list, so on successive calls to the Next operation the
- --| next item in the list can be returned. This is the function of the
- --| MakeListIter and the type ListIter. MakeIter just sets the Iter to the
- --| the beginning of the list. On subsequent calls to NextList the Iter
- --| is updated with each call.
-
- -----------------------------------------------------------------------------
-
- function More( --| Returns true if there are more elements in
- --| the and false if there aren't any more
- --| the in the list.
- L: in ListIter --| List being checked for elements.
- ) return boolean;
-
- ------------------------------------------------------------------------------
-
- procedure Next( --| This is the iterator operation. Given
- --| a ListIter in the list it returns the
- --| current item and updates the ListIter.
- --| If ListIter is at the end of the list,
- --| More returns false otherwise it
- --| returns true.
- Place: in out ListIter; --| The Iter which marks the position in
- --| the list.
- Info: out Tree --| The element being returned.
-
- );
-
- --| The iterators subprograms MakeListIter, More, and NextList should be used
- --| in the following way:
- --|
- --| L: List;
- --| Place: ListIter;
- --| Info: SomeType;
- --|
- --|
- --| Place := MakeListIter(L);
- --|
- --| while ( More(Place) ) loop
- --| NextList(Place, Info);
- --| process each element of list L;
- --| end loop;
-
-
- ----------------------------------------------------------------------------
-
- procedure ReplaceHead( --| Replace the Item at the head of the list
- --| with the parameter Item.
- L: in out List; --| The list being modified.
- Info: in Tree --| The information being entered.
- );
- --| Raises
- --| EmptyList
-
- --| Effects
- --| Replaces the information in the first element in the list. Raises
- --| EmptyList if the list is empty.
-
- ------------------------------------------------------------------------------
-
- procedure ReplaceTail( --| Replace the Tail of a list
- --| with a new list.
- L: in out List; --| List whose Tail is replaced.
- NewTail: in List --| The list which will become the
- --| tail of Oldlist.
- );
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| Replaces the tail of a list with a new list. If the list whose tail
- --| is being replaced is null EmptyList is raised.
-
- -------------------------------------------------------------------------------
-
- function Tail( --| returns the tail of a list L
- L: in List --| the list whose tail is being returned
- ) return List;
-
- --| Raises
- --| EmptyList
- --|
- --| Effects
- --| Returns a list which is the tail of the list L. Raises EmptyList if
- --| L is empty. If L only has one element then Tail returns the Empty
- --| list.
-
- ------------------------------------------------------------------------------
-
- function Equal( --| compares list1 and list2 for equality
- List1: in List; --| first list
- List2: in List --| second list
- ) return boolean;
-
- --| Effects
- --| Returns true if for all elements of List1 the corresponding element
- --| of List2 has the same value. This function uses the Equal operation
- --| provided by the user. If one is not provided then = is used.
-
- ------------------------------------------------------------------------------
- private
- type Cell;
-
- type List is access Cell; --| pointer added by this package
- --| in order to make a list
-
-
- type Cell is --| Cell for the lists being created
- record
- Info: Tree;
- Next: List;
- end record;
-
-
- type ListIter is new List; --| This prevents Lists being assigned to
- --| iterators and vice versa
-
- end NodeOrder;
-
- type TreeIter is
- record
- NodeList :NodeOrder.List;
- State :NodeOrder.ListIter;
- end record;
-
-
- end TreePkg;
- type Set is
- record
- SetRep :TreePkg.Tree;
- end record;
-
- type SetIter is
- record
- Place :TreePkg.TreeIter;
- Count :natural;
- end record;
-
- end Literal_Set;
-
-
-
-
- -- package Literal_Set is new OrderedSets
- -- (ItemType => Source_Text.Locator, "<" => "<" );
- -- generic
- -- type ItemType is private;
- -- with function "<" ( X ,Y: in ItemType) return boolean;
-
- type BlockInfoType is
- record
- TokenCount :TokenCountType;
- BlockId :BlockIdType;
- SetOfLiterals :Literal_Set.Set;
- SetOfDEF_IDs :DEF_ID_Set.Set;
- end record;
- --| This is the information which pertains to a particular block
- --| of the source program. This information is pushed on
- --| a stack when an new block is encountered. The
- --| information is a count of the tokens encountered so far
- --| and the DEF_ID's which have been found as well as the
- --| identifying information for the block. The ListOfLiterals
- --| is a list of all literals encounter
-
- --? package BlockInfoStack is new Stacks(BlockInfoType);
- --? use StackBlockInfo;
-
-
- package BlockInfoStack is
-
-
-
-
- type stack is private; --| The stack abstract data type.
-
-
- uninitialized_stack: exception;
- --| The initialization operations are create and copy.
-
- empty_stack: exception;
-
-
-
- function create
- return stack;
-
-
- procedure push(s: in out stack;
- e: BlockInfoType);
-
-
- procedure pop(s: in out stack);
-
-
- procedure pop(s: in out stack;
- e: out BlockInfoType);
-
-
- function copy(s: stack)
- return stack;
-
-
-
-
- function top(s: stack)
- return BlockInfoType;
-
-
- function size(s: stack)
- return natural;
-
-
- function is_empty(s: stack)
- return boolean;
-
-
-
-
- procedure destroy(s: in out stack);
-
-
-
- private
- package Lists is
-
-
-
-
-
-
- type List is private;
- type ListIter is private;
-
-
-
- CircularList :exception; --| Raised if an attemp is made to
- --| create a circular list. This
- --| results when a list is attempted
- --| to be attached to itself.
-
- EmptyList :exception; --| Raised if an attemp is made to
- --| manipulate an empty list.
-
- ItemNotPresent :exception; --| Raised if an attempt is made to
- --| remove an element from a list in
- --| which it does not exist.
-
- NoMore :exception; --| Raised if an attemp is made to
- --| get the next element from a list
- --| after iteration is complete.
-
-
-
-
-
- procedure Attach( --| appends List2 to List1
- List1: in out List; --| The list being appended to.
- List2: in List --| The list being appended.
- );
-
-
-
-
-
- function Attach( --| Creates a new list containing the two
- --| Elements.
- Element1: in BlockInfoType; --| This will be first element in list.
- Element2: in BlockInfoType --| This will be second element in list.
- ) return List;
-
-
- procedure Attach( --| List L is appended with Element.
- L: in out List; --| List being appended to.
- Element: in BlockInfoType --| This will be last element in l ist.
- );
-
-
- procedure Attach( --| Makes Element first item in list L.
- Element: in BlockInfoType; --| This will be the first element in list.
- L: in out List --| The List which Element is being
- --| prepended to.
- );
-
-
-
- function Attach ( --| attaches two lists
- List1: in List; --| first list
- List2: in List --| second list
- ) return List;
-
-
-
-
- function Attach ( --| prepends an element onto a list
- Element: in BlockInfoType; --| element being prepended to list
- L: in List --| List which element is being added
- --| to
- ) return List;
-
-
-
- function Attach ( --| Adds an element to the end of a list
- L: in List; --| The list which element is being added to.
- Element: in BlockInfoType --| The element being added to the end of
- --| the list.
- ) return List;
-
-
-
-
- function Copy( --| returns a copy of list1
- L: in List --| list being copied
- ) return List;
-
-
-
-
-
- function Create --| Returns an empty List
-
- return List;
-
-
- procedure DeleteHead( --| Remove the head element from a list.
- L: in out List --| The list whose head is being removed.
- );
-
-
-
- procedure DeleteItem( --| remove the first occurrence of Element
- --| from L
- L: in out List; --| list element is being removed from
- Element: in BlockInfoType --| element being removed
- );
-
-
-
-
-
- procedure DeleteItems( --| remove all occurrences of Element
- --| from L.
- L: in out List; --| The List element is being removed from
- Element: in BlockInfoType --| element being removed
- );
-
-
-
-
- procedure Destroy( --| removes the list
- L: in out List --| the list being removed
- );
-
-
-
- function FirstValue( --| returns the contents of the first record of the
- --| list
- L: in List --| the list whose first element is being
- --| returned
-
- ) return BlockInfoType;
-
-
-
- function IsEmpty( --| Checks if a list is empty.
- L: in List --| List being checked.
- ) return boolean;
-
-
- function IsInList( --| Checks if element is an element of
- --| list.
- L: in List; --| list being scanned for element
- Element: in BlockInfoType --| element being searched for
- ) return boolean;
-
-
-
- function LastValue( --| Returns the contents of the last record of
- --| the list.
- L: in List --| The list whose first element is being
- --| returned.
- ) return BlockInfoType;
-
-
-
-
- function Length( --| count the number of elements on a list
- L: in List --| list whose length is being computed
- ) return integer;
-
-
- function MakeListIter( --| Sets a variable to point to the head
- --| of the list. This will be used to
- --| prepare for iteration over a list.
- L: in List --| The list being iterated over.
- ) return ListIter;
-
-
-
-
- function More( --| Returns true if there are more elements in
- --| the and false if there aren't any more
- --| the in the list.
- L: in ListIter --| List being checked for elements.
- ) return boolean;
-
-
- procedure Next( --| This is the iterator operation. Given
- --| a ListIter in the list it returns the
- --| current item and updates the ListIter.
- --| If ListIter is at the end of the list,
- --| More returns false otherwise it
- --| returns true.
- Place: in out ListIter; --| The Iter which marks the position in
- --| the list.
- Info: out BlockInfoType --| The element being returned.
-
- );
-
-
-
-
- procedure ReplaceHead( --| Replace the Item at the head of the list
- --| with the parameter Item.
- L: in out List; --| The list being modified.
- Info: in BlockInfoType --| The information being entered.
- );
-
-
-
- procedure ReplaceTail( --| Replace the Tail of a list
- --| with a new list.
- L: in out List; --| List whose Tail is replaced.
- NewTail: in List --| The list which will become the
- --| tail of Oldlist.
- );
-
-
- function Tail( --| returns the tail of a list L
- L: in List --| the list whose tail is being returned
- ) return List;
-
-
-
- function Equal( --| compares list1 and list2 for equality
- List1: in List; --| first list
- List2: in List --| second list
- ) return boolean;
-
-
- private
- type Cell;
-
- type List is access Cell; --| pointer added by this package
- --| in order to make a list
-
-
- type Cell is --| Cell for the lists being created
- record
- Info: BlockInfoType;
- Next: List;
- end record;
-
-
- type ListIter is new List; --| This prevents Lists being assigned to
- --| iterators and vice versa
-
- end Lists;
-
- subtype elem_list is lists.list;
-
- type stack_rec is
- record
- size: natural := 0;
- elts: elem_list;
- end record;
-
- type stack is access stack_rec;
-
-
- end BlockInfoStack;
-
-
- end Definitions;
- ::::::::::::::
- halstead.ada
- ::::::::::::::
-
- -------SPEC---------------------------------------------------------------
- function Halstead return INTEGER;
-
- -------BODY---------------------------------------------------------------
-
- with STRING_LISTS;
- with COMMANDLINE;
- with STANDARD_INTERFACE;
- with STRING_PKG;
- with TEXT_IO; use TEXT_IO;
- with HOST_LIB;
- with ST_DIANA;
- with PROGRAMLIBRARY;
- with COMP_UNIT_CLASS_PKG;
- with DEFINITIONS;
- with HALSTEAD_DATA_BASE;
- --xx with FILE_MANAGER;
-
- function Halstead return INTEGER is
-
- package CL renames COMMANDLINE;
- package SI renames STANDARD_INTERFACE;
- package SL renames STRING_LISTS;
- package SP renames STRING_PKG;
- package D renames DEFINITIONS;
- package PL renames PROGRAMLIBRARY;
- package HDB renames HALSTEAD_DATA_BASE;
- --xx package FM renames FILE_MANAGER;
-
- package STRINGTYPE is new SI.STRING_ARGUMENT("string");
- package UNIT_LIST_PKG is new SI.STRING_LIST_ARGUMENT(
- STRING_TYPE_NAME => "string_type",
- STRING_TYPE_LIST => "string_list");
-
- dd_name : string(1..200);
- dd_Last : natural;
- dd_changed : boolean;
- pl_name : string(1..200);
- pl_last : natural;
-
- HALSTEAD : SI.PROCESS_HANDLE;
- library_Name : SP.string_type;
- OUTPUT_FILE: FILE_TYPE;
- output_File_Name : sp.string_type;
- unit_list : SL.LIST;
- ITER : SL.LISTITER;
- unit_Name : sp.string_type;
- ToTerminal : boolean;
- verbose : boolean;
- Unit_SD : PL.Subdomain_Type;
- COMP_UNIT_Locator: ST_DIANA.COMP_UNIT_CLASS.Locator;
- UnitPosition : natural := 1;
-
- begin -- driver
-
- HOST_LIB.SET_ERROR;
-
- SI.set_tool_identifier ("1.0");
- STANDARD_INTERFACE.DEFINE_PROCESS(PROC => Halstead,
- NAME => "Halstead",
- HELP => "Computes Halstead formulas for Ada compilation units.");
-
- UNIT_LIST_PKG.DEFINE_ARGUMENT(PROC => HALSTEAD,
- NAME => "Units",
- DEFAULT => SL.CREATE,
- HELP => "Names of the compilation units");
-
- Stringtype.DEFINE_ARGUMENT(PROC => halstead,
- NAME => "Output",
- DEFAULT => "",
- HELP => "Name of the report file (defaults to standard output)");
-
- STRINGTYPE.DEFINE_ARGUMENT(PROC => HALSTEAD,
- NAME => "library", DEFAULT => "[.BYRONLIB]",
- Help => "Name of an Ada program library (NYI)");
-
- SI.DEFINE_PROCESS_HELP(PROC => halstead,
- HELP => "Computes Halstead formulas for Ada compilation units");
-
- STANDARD_INTERFACE.PARSE_LINE(halstead);
-
- unit_list := unit_LIST_pkg.GET_ARGUMENT(PROC => halstead, NAME => "units");
- library_Name := stringtype.get_argument(proc => halstead, name => "library");
- output_File_Name :=
- STRINGTYPE.GET_ARGUMENT(PROC => halstead, NAME => "output");
- verbose := FALSE;
-
-
- if sp.equal(output_File_Name, "") then
-
- -- No file name given: output is to the terminal
- Set_Output(STANDARD_OUTPUT);
- ToTerminal := true;
-
- else
- -- Create the specified output file
- create(File => Output_File,
- Mode => Out_File,
- Name => sp.value(output_File_Name),
- Form => ""
- );
- Set_Output(Output_File);
- ToTerminal := false;
-
- end if;
-
- -- Connect to the program library directory:
- --xx FM.Show_and_Set_Default(dd_name,dd_last,dd_changed,SP.Value(library_Name));
- --xx if not dd_changed then
- --xx Put_Line("?? Cannot connect to program library.");
- --xx return HOST_LIB.RETURN_CODE(HOST_LIB.ERROR);
- --xx end if;
-
- -- Open the catalog. This is the program library which contains
- -- the library units which the user is performing the Halstead
- -- Complexity Measures on.
-
- PL.Open_catalog;
- ST_DIANA.NEWDOMAIN (PL.Get_Primary_Context, PL.Get_Secondary_Context);
-
- -- Get each library unit which the user is performing the metric on.
- -- For each unit get its COMP_UNIT_CLASS.Locator which is the handle
- -- to the beginning of the DIANA for the unit. Pass the Locator
- -- to the bonsai tree walk routine which computes the metrics.
-
- ITER := SL.MAKELISTITER(UNIT_LIST);
- while SL.MORE(ITER) loop
- SL.next(iter, unit_Name);
-
- -- Check to see if the unit specified is a SubUnit.
-
- if cl.IsSubUnit(SP.Value(unit_Name), unitposition) then
- begin
- Unit_SD := PL.Open_Subdomain(
- ST_Diana.TheDomain,
- PL.DIANA_Form,
- PL.SubUnit_Ident (
- CL.GetParent (sp.value(unit_Name), UnitPosition) ,
- CL.GetSubUnit (sp.value(unit_Name), UnitPosition),
- IsStub => false
- ));
- exception
- when PL.Object_Not_Up_To_Date =>
- Put(Standard_Output, "%% WARNING: ");
- Put(Standard_Output, "Subunit " & SP.Value(unit_Name));
- Put_Line(Standard_Output, " not found");
- end;
- -- Pass the necessary data to the Utilities package.
- HDB.InitializeData(
- LibraryUnit => SP.Value(unit_Name),
- IsUnitSpec => false,
- VerboseFlag => Verbose,
- ToTerminalFlag => ToTerminal,
- OuterMostBlockFlag => false
- );
-
- -- If writing to an output file then generate a
- -- report header. If writing to the terminal a header is
- -- generated in the utilities package.
-
- if not ToTerminal then
- HDB.ReportHeader (SP.Value(unit_Name), Spec => false);
- end if;
-
- -- Get the actual locator for the library unit.
-
- COMP_UNIT_Locator := ST_Diana.Comp_UnitNode.GetRoot (Unit_SD);
-
- -- Now that we have the locator scan the diana which
- -- the locator points to.
-
- COMP_UNIT_CLASS_Pkg.Scan_Comp_Unit_Class(COMP_UNIT_Locator);
- else
- -- For any library unit which is not a subunit this
- -- loop scans both the specification (implicit as well
- -- as explicit) and the body of the unit.
-
- for IsSpec in reverse false..true loop
- -- Open the Subdomain.
- begin
- Unit_SD := PL.Open_Subdomain(
- ST_Diana.TheDomain,
- PL.DIANA_Form,
- PL.Library_Unit_Ident (
- SP.Value(unit_Name),
- IsSpec
- ));
-
- -- Pass the data to the utilities package.
- HDB.InitializeData(
- LibraryUnit => SP.Value(unit_Name),
- IsUnitSpec => IsSpec,
- VerboseFlag => Verbose,
- ToTerminalFlag => ToTerminal,
- OuterMostBlockFlag => false
- );
-
- if not ToTerminal then
- HDB.ReportHeader (SP.Value(unit_Name), IsSpec);
- end if;
-
- -- Get the locator to the library unit.
- COMP_UNIT_Locator := ST_Diana.Comp_UnitNode.GetRoot (Unit_SD);
-
- -- Perform the scan on the diana which the locator points to.
- COMP_UNIT_CLASS_Pkg.Scan_Comp_Unit_Class(COMP_UNIT_Locator);
-
- -- Catch the exception when attempting to open either
- -- implicit spec or body.
- exception
- when PL.Object_Not_Up_To_Date =>
- Put_Line(Standard_Output, "%% WARNING: ");
- if IsSpec then
- Put(Standard_Output, "The spec of ");
- else
- Put(Standard_Output, "The body of ");
- end if;
- Put(Standard_Output, "Unit " & SP.Value(unit_Name));
- Put_Line(Standard_Output, " does not exist");
- end;
- end loop;
- end if;
- end loop;
-
- --xx FM.Show_and_Set_Default(pl_name, pl_last, dd_changed, dd_name(1..dd_last));
- return HOST_LIB.RETURN_CODE(HOST_LIB.SUCCESS);
-
- exception
-
- when STANDARD_INTERFACE.PROCESS_HELP =>
- return HOST_LIB.RETURN_CODE(HOST_LIB.INFORMATION);
-
- when STANDARD_INTERFACE.ABORT_PROCESS =>
- return HOST_LIB.RETURN_CODE(HOST_LIB.ERROR);
-
- -- when others =>
- -- TEXT_IO.PUT_LINE("internal error");
- -- return HOST_LIB.RETURN_CODE(HOST_LIB.ERROR);
-
- end Halstead;
- ::::::::::::::
- halstead.obj
- ::::::::::::::