|
DataMuseum.dkPresents historical artifacts from the history of: Rational R1000/400 |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about Rational R1000/400 Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - download
Length: 82009 (0x14059) Types: TextFile Notes: R1k Text-file segment
└─⟦8527c1e9b⟧ Bits:30000544 8mm tape, Rational 1000, Arrival backup of disks in PAM's R1000 └─ ⟦5a81ac88f⟧ »Space Info Vol 1« └─⟦797a3cc76⟧ └─⟦this⟧
generic type ItemType is private; --| This is the data being manipulated. with function Equal ( X,Y: in ItemType) return boolean is "="; --| This allows the user to define --| equality on ItemType. For instance --| if ItemType is an abstract type --| then equality is defined in terms of --| the abstract type. If this function --| is not provided equality defaults to --| =. package Lists is --| This package provides singly linked lists with elements of type --| ItemType, where ItemType is specified by a generic parameter. --| Overview --| When this package is instantiated, it provides a linked list type for --| lists of objects of type ItemType, 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 --| DestroyDeep destroy a list as well as the elements in that list --| Equal are two lists equal --| FirstValue get the information from the first element of a list --| Forward advances an iterator --| 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 --| MakeList this takes a single element and returns 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 --| CellValue this takes an iterator and returns the value of the element --| whose position the iterator holds --| --| 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 ItemType; --| This will be first element in list. Element2: in ItemType --| 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 ItemType --| 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 ItemType; --| 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 ItemType; --| 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 ItemType --| 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. -------------------------------------------------------------------------- generic with function Copy(I: in ItemType) return ItemType; function CopyDeep( --| returns a copy of list using a user supplied --| copy function. This is helpful if the type --| of a list is an abstract data type. L: in List --| List being copied. ) return List; --| Effects --| This produces a new list whose elements have been duplicated using --| the Copy function provided by the user. ------------------------------------------------------------------------------ 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 ItemType --| element being removed ); --| 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. ---------------------------------------------------------------------------- function DeleteItem( --| remove the first occurrence of Element --| from L L: in List; --| list element is being removed from Element: in ItemType --| element being removed ) return List; --| EFFECTS --| This returns the List L with the first occurrence of Element removed. ------------------------------------------------------------------------------ function DeleteItems ( --| remove all occurrences of Element --| from L. L: in List; --| The List element is being removed from Element: in ItemType --| element being removed ) return List; --| EFFECTS --| This function returns a copy of the list L which has all elements which --| have value Element removed. ------------------------------------------------------------------------------- procedure DeleteItems ( --| remove all occurrences of Element --| from L. L: in out List; --| The List element is being removed from Element: in ItemType --| element being removed ); --| EFFECTS --| This procedure removes all occurrences of Element from the List L. This --| is a destructive procedure. ------------------------------------------------------------------------------ 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. ------------------------------------------------------------------------------ generic with procedure Dispose (I :in out ItemType); procedure DestroyDeep ( --| Destroy a list as well as all objects which --| comprise an element of the list. L :in out List ); --| OVERVIEW --| This procedure is used to destroy a list and all the objects contained --| in an element of the list. For example if L is a list of lists --| then destroy L does not destroy the lists which are elements of L. --| DestroyDeep will now destroy L and all the objects in the elements of L. --| The produce Dispose is a procedure which will destroy the objects which --| comprise an element of a list. For example if package L was a list --| of lists then Dispose for L would be the Destroy of list type package L was --| instantiated with. --| REQUIRES --| This procedure requires no sharing between elements of lists. --| For example if L_int is a list of integers and L_of_L_int is a list --| of lists of integers and two elements of L_of_L_int have the same value --| then doing a DestroyDeep will cause an access violation to be raised. --| The best way to avoid this is not to have sharing between list elements --| or use copy functions when adding to the list of lists. ------------------------------------------------------------------------------ function FirstValue( --| returns the contents of the first record of the --| list L: in List --| the list whose first element is being --| returned ) return ItemType; --| Raises --| EmptyList --| --| Effects --| This returns the Item in the first position in the list. If the list --| is empty EmptyList is raised. ------------------------------------------------------------------------------- procedure Forward ( --| Advances the iterator. I :in out ListIter --| The iterator. ); --| OVERVIEW --| This procedure can be used in conjunction with Cell to iterate over a list. --| This is in addition to Next. Instead of writing --| --| I :ListIter; --| L :List; --| V :List_Element_Type; --| --| I := MakeListIter(L); --| while More(I) loop --| Next (I, V); --| Print (V); --| end loop; --| --| One can write --| I := MakeListIter(L); --| while More (I) loop --| Print (Cell (I)); --| Forward (I); --| end loop; ------------------------------------------------------------------------------- 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 ItemType --| 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 ItemType; --| 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 MakeList ( --| This takes in an element and returns a List. E :in ItemType ) return List; ------------------------------------------------------------------------------ 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 Next 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 ItemType --| The element being returned. ); --| The iterators subprograms MakeListIter, More, and Next should be used --| in the following way: --| --| L: List; --| Place: ListIter; --| Info: SomeType; --| --| --| Place := MakeListIter(L); --| --| while ( More(Place) ) loop --| Next(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 ItemType --| 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 CellValue ( --| Return the value of the element where the iterator is --| positioned. I :in ListIter ) return ItemType; --| OVERVIEW --| This returns the value of the element at the position of the iterator. --| This is used in conjunction with Forward. -------------------------------------------------------------------------- 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: ItemType; Next: List; end record; type ListIter is new List; --| This prevents Lists being assigned to --| iterators and vice versa end Lists; \f with unchecked_deallocation; 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; --| 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 ItemType ) 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 ItemType; Element2: in ItemType ) 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 ItemType; 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 ItemType ) 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 ItemType; 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 CopyDeep (L: in List) return List is --| If L is null then return null. --| Otherwise copy the first element of the list into the head of the --| new list and copy the tail of the list recursively using CopyDeep. begin if L = null then return null; else return new Cell'( Info => Copy (L.Info), Next => CopyDeep(L.Next)); end if; end CopyDeep; -------------------------------------------------------------------------- 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; -------------------------------------------------------------------------- function DeleteItem( --| remove the first occurrence of Element --| from L L: in List; --| list element is being removed from Element: in ItemType --| element being removed ) return List is I :List; Result :List; Found :boolean := false; begin --| ALGORITHM --| Attach all elements of L to Result except the first element in L --| whose value is Element. If the current element pointed to by I --| is not equal to element or the element being skipped was found --| then attach the current element to Result. I := L; while (I /= null) loop if (not Equal (I.Info, Element)) or (Found) then Attach (Result, I.Info); else Found := true; end if; I := I.Next; end loop; return Result; end DeleteItem; ------------------------------------------------------------------------------ function DeleteItems ( --| remove all occurrences of Element --| from L. L: in List; --| The List element is being removed from Element: in ItemType --| element being removed ) return List is I :List; Result :List; begin --| ALGORITHM --| Walk over the list L and if the current element does not equal --| Element then attach it to the list to be returned. I := L; while I /= null loop if not Equal (I.Info, Element) then Attach (Result, I.Info); end if; I := I.Next; end loop; return Result; end DeleteItems; ------------------------------------------------------------------------------- procedure DeleteItem (L: in out List; Element: in ItemType ) 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 Equal(L.Info, Element) then DeleteHead(L); else DeleteItem(L.Next, Element); end if; end DeleteItem; -------------------------------------------------------------------------- procedure DeleteItems (L: in out List; Element: in ItemType ) 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. --| 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 Equal(Place_In_L.Info, Element) then --| 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. 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; -------------------------------------------------------------------------- procedure DestroyDeep (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; Dispose (HoldPlace.Info); Free (HoldPlace); end loop; L := null; end DestroyDeep; -------------------------------------------------------------------------- function FirstValue (L: in List) return ItemType is --| Return the first value in the list. begin if L = null then raise EmptyList; else return (L.Info); end if; end FirstValue; -------------------------------------------------------------------------- procedure Forward (I: in out ListIter) is --| Return the pointer to the next member of the list. begin if I = null then raise NoMore; else I := ListIter (I.Next); end if; end Forward; -------------------------------------------------------------------------- function IsInList (L: in List; Element: in ItemType ) 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 Equal(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 ItemType 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 MakeList ( E :in ItemType ) return List is begin return new Cell ' (Info => E, Next => null); end; -------------------------------------------------------------------------- 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 ItemType ) 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 ItemType ) 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 --| EmptyList is raised. begin if L = null then raise EmptyList; else return L.Next; end if; end Tail; -------------------------------------------------------------------------- function CellValue ( I :in ListIter ) return ItemType is L :List; begin -- Convert I to a List type and then return the value it points to. L := List(I); return L.Info; end CellValue; -------------------------------------------------------------------------- function Equal (List1: in List; List2: in List ) return boolean is PlaceInList1: List; PlaceInList2: LIst; Contents1: ItemType; Contents2: ItemType; --| 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 Equal (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; -------------------------------------------------------------------------- \f with Bounded_String,Lists; package Fields is type Object is private; type Field_Index is limited private; Error_Field_Store : exception; Error_Field_Empty : exception; Error_Field_Index : exception; --Creation procedure Create(D : in out Object); --Access function Has_Field (D : in Object; Name : in String) return Boolean; function Get_Field_Type_By_Name(D : Object; Name : String)return String; procedure Dump_Number_Of_Field(D : in Object); procedure Dump_Fields (D : in Object); procedure Surface_Copy(To_Fields : in out Object;The_Fields : Object); procedure Deep_Copy(To_Fields : in out Object;The_Fields : Object); -- function Object_Image (D : in Object) return String; --Modification procedure Store_Field(D : in out Object; aName : String;aType: String); --Liberation procedure Dispose_Object (D : in out Object); --Iteration procedure Open_Field_Indexation(D : Object; I : in out Field_Index); procedure Next_Field_Index (I : in out Field_Index); function Get_Indexed_Field_Name (I : Field_Index) return String; function Get_Indexed_Field_Type (I : Field_Index) return String; function No_More_Fields (I : Field_Index) return Boolean; private MAX_STRING_Field:Constant natural:=32; type Field is Record Field_Name:Bounded_string.Variable_String(MAX_STRING_Field); Field_Type:Bounded_string.Variable_String(MAX_STRING_Field); end record; function isEqual ( X,Y: in Field) return boolean; package Fields_List is new Lists(ItemType=>Field,Equal=>isEqual); Type Object is record Node:Fields_List.List; end record; Type Field_index is record Node:Fields_List.ListIter; end record; end Fields;with Text_Io, Bounded_String,Lists; package body Fields is use Fields_List; function Create_Field(N: String;T : String) return Field is A:Field; begin Bounded_string.free(A.Field_Name); Bounded_string.Copy(A.Field_Name,N); Bounded_string.free(A.Field_Type); Bounded_string.Copy(A.Field_Type,T); return A; end; function isEqual ( X,Y: in Field) return boolean is begin declare Use Bounded_String; begin if image(X.Field_name) = image(Y.Field_name) then return True; else return False; end if; end; end; procedure Dispose_Field (The_Field : in out Field) is begin Bounded_String.Free(The_Field.Field_Name); Bounded_String.Free(The_Field.Field_Type); end Dispose_Field; procedure Destroy_Object is New DestroyDeep(Dispose =>Dispose_Field); Function Copy_Field (The_Field : Field) return Field is begin return Create_Field(Bounded_String.Image(The_Field.Field_Name), Bounded_String.Image(The_Field.Field_Type)); end Copy_Field; Function Copy_object is New CopyDeep(Copy=>Copy_Field); --Creation procedure Create(D : in out Object) is begin D.Node:=Create; end; --Access function Has_Field (D : in Object; Name : in String) return Boolean is begin if not isEmpty(D.Node) then return isInlisT(D.Node,Create_Field(Name,Name)); else return False; end if; end; function Get_Field_Type_By_Name(D : Object; Name : String)return String is Index : Field_Index; Info : Field; Search: Field; Found : Boolean:=False; begin if not isEmpty(D.Node) then Search:=Create_Field(Name,Name); Index.Node:= MakeListIter(D.Node); while ( More(Index.Node) and not Found ) loop Next(Index.Node, Info); if isEqual(Info,Search) then found:=True; return (Bounded_String.Image(Info.Field_Type)); end if; end loop; else raise Error_Field_Empty; end if; end; procedure Dump_Fields (D : in Object) is Index : Field_Index; Info : Field; begin if not isEmpty(D.Node) then declare use Bounded_string; begin Index.Node:= MakeListIter(D.Node); while ( More(Index.Node) ) loop Next(Index.Node, Info); Text_io.put_Line("Nom: "&Image(Info.Field_Name)& " Type: "&Image(Info.Field_Type)); end loop; end; else raise Error_Field_Empty; end if; end; procedure Dump_Number_Of_Field(D : in Object) is begin Text_io.Put_Line("Number of field : "&Integer'Image(Fields_List.Length(D.node))); end; procedure Surface_Copy(To_Fields : in out Object;The_Fields : Object) is begin To_fields.Node:=The_fields.Node; end; procedure Deep_Copy(To_Fields : in out Object;The_Fields : Object) is begin To_Fields.Node:=Copy_Object(The_fields.Node); end; -- function Object_Image (D : in Object) return String; --Modification procedure Store_Field(D : in out Object; aName : String;aType: String) is begin if not isEmpty(D.Node) then Attach(D.Node,Create_Field(aName,aType)); else Attach(Create_Field(aName,aType),D.Node); end if; end; --Liberation procedure Dispose_Object (D : in out Object) is begin if not isEmpty(D.Node) then Destroy_Object(D.Node); end if; end; --Iteration procedure Open_Field_Indexation(D : Object; I : in out Field_Index) is begin I.Node:= MakeListIter(D.Node); end; procedure Next_Field_Index (I : in out Field_Index) is Info:Field; begin Next(I.Node, Info); end; function Get_Indexed_Field_Name (I : Field_Index) return String is Info:Field; begin Info:=CellValue(I.node); return Bounded_String.Image(Info.Field_Name); end; function Get_Indexed_Field_Type (I : Field_Index) return String is Info:Field; begin Info:=CellValue(I.node); return Bounded_String.Image(Info.Field_Type); end; function No_More_Fields (I : Field_Index) return Boolean is begin return Not More(I.Node); end; end fields;generic type Value_Type is private; --| Type of values stored in the tree. with function Difference(P, Q: Value_Type) return integer is <>; --| Must return a value > 0 if P > Q, 0 if P = Q, and less than --| zero otherwise. package binary_trees_pkg is --| Efficient implementation of binary trees. --| OVERVIEW --| This package is an efficient implementation of unbalanced binary trees. --| These trees have the following properties: --|- --| 1. Inserting a value is cheap (log n Differences per insertion). --| 2. Finding a value is cheap (log n Differences per querey). --| 3. Can iterate over the values in sorted order in linear time. --| 4. Space overhead is moderate (2 "pointers" per value stored). --|+ --| They are thus useful both for sorting sequences of indeterminate size --| and for lookup tables. --| --| OPERATIONS --| --|-The following operations are provided: --| --| Insert Insert a node into a tree --| Insert_if_not_Found Insert a node into a tree if not there already --| Replace_if_Found Replace a node if duplicate exists, else insert. --| Destroy Destroy a tree --| Destroy_Deep* Destroy a tree and its contents --| Balanced_Tree* Create a balanced tree from values supplied in order --| Copy* Copy a tree. The copy is balanced. --| --| Queries: --| Is_Empty Return TRUE iff a tree is empty. --| Find Search tree for a node --| Is_Found Return TRUE iff tree contains specified value. --| Size Return number of nodes in the tree. --| --| Iterators: --| Visit* Apply a procedure to every node in specified order --| Make_Iter Create an iterator for ordered scan --| More Test for exhausted iterator --| Next Bump an iterator to the next element --| --| * Indicates generic subprogram --| --| USAGE --| --| The following example shows how to use this package where nodes in --| the tree are labeled with a String_Type value (for which a natural --| Difference function is not available). --|- --| package SP renames String_Pkg; --| --| type my_Value is record --| label: SP.string_type; --| value: integer; --| end record; --| --| function differ_label(P, Q: SP.string_type) return integer is --| begin --| if SP."<"(P, Q) then return -1; --| elsif SP."<"(Q, P) then return 1; --| else return 0; --| end if; --| end differ_label; --| --| package my_Tree is new Binary_Trees_pkg(my_Value, differ_Label); --| --| Note that the required Difference function may be easily written in terms --| of "<" if that is available, but that frequently two comparisons must --| be done for each Difference. However, both comparisons would have --| to be done internally by this package for every instantiation if the --| generic parameter were "<" instead of Difference. --| --| PERFORMANCE --| --| Every node can be visited in the tree in linear time. The cost --| of creating an iterator is small and independent of the size --| of the tree. --| --| Recognizing that comparing values can be expensive, this package --| takes a Difference function as a generic parameter. If it took --| a comparison function such as "<", then two comparisons would be --| made per node visited during a search of the tree. Of course this --| is more costly when "<" is a trivial operation, but in those cases, --| Difference can be bound to "-" and the overhead in negligable. --| --| Two different kinds of iterators are provided. The first is the --| commonly used set of functions Make_Iter, More, and Next. The second --| is a generic procedure called Visit. The generic parameter to Visit is --| a procedure which is called once for each value in the tree. Visit --| is more difficult to use and results in code that is not quite as clear, --| but its overhead is about 20% of the More/Next style iterator. It --| is therefore recommended for use only in time critical inner loops. ---------------------------------------------------------------------------- -- Exceptions -- ---------------------------------------------------------------------------- Duplicate_Value: exception; --| Raised on attempt to insert a duplicate node into a tree. Not_Found: exception; --| Raised on attempt to find a node that is not in a tree. No_More: exception; --| Raised on attempt to bump an iterator that has already scanned the --| entire tree. Out_Of_Order: exception; --| Raised if a problem in the ordering of a tree is detected. Invalid_Tree: exception; --| Value is not a tree or was not properly initialized. ---------------------------------------------------------------------------- -- Types -- ---------------------------------------------------------------------------- type Scan_Kind is (inorder, preorder, postorder); --| Used to specify the order in which values should be scanned from a tree: --|- --| inorder: Left, Node, Right (nodes visited in increasing order) --| preorder: Node, Left, Right (top down) --| postorder: Left, Right, Node (bottom up) type Tree is private; type Iterator is private; ---------------------------------------------------------------------------- -- Operations -- ---------------------------------------------------------------------------- Function Create --| Return an empty tree. return Tree; --| Effects: Create and return an empty tree. Note that this allocates --| a small amount of storage which can only be reclaimed through --| a call to Destroy. ---------------------------------------------------------------------------- Procedure Insert( --| Insert a value into a tree. V: Value_Type; --| Value to be inserted T: Tree --| Tree to contain the new value ); --| Raises: Duplicate_Value, Invalid_Tree. --| Effects: Insert V into T in the proper place. If a value equal --| to V (according to the Difference function) is already contained --| in the tree, the exception Duplicate_Value is raised. --| Caution: Since this package does not attempt to balance trees as --| values are inserted, it is important to remember that inserting --| values in sorted order will create a degenerate tree, where search --| and insertion is proportional to the N instead of to Log N. If --| this pattern is common, use the Balanced_Tree function below. ---------------------------------------------------------------------------- procedure Insert_if_not_Found( --| Insert a value into a tree, provided a duplicate value is not already there V: Value_Type; --| Value to be inserted T: Tree; --| Tree to contain the new value Found: out boolean; --| Becomes True iff V already in tree Duplicate: out Value_Type --| the duplicate value, if there is one ); --| Raises: Invalid_Tree. --| Effects: Insert V into T in the proper place. If a value equal --| to V (according to the Difference function) is already contained --| in the tree, Found will be True and Duplicate will be the duplicate --| value. This might be a sequence of values with the same key, and --| V can then be added to the sequence. ---------------------------------------------------------------------------- procedure Replace_if_Found( --| Replace a value if label exists, otherwise insert it. V: Value_Type; --| Value to be inserted T: Tree; --| Tree to contain the new value Found: out boolean; --| Becomes True iff L already in tree Old_Value: out Value_Type --| the duplicate value, if there is one ); --| Raises: Invalid_Tree. --| Effects: Search for V in T. If found, replace the old value with V, --| and return Found => True, Old_Value => the old value. Otherwise, --| simply insert V into T and return Found => False. ---------------------------------------------------------------------------- procedure Destroy( --| Free space allocated to a tree. T: in out Tree --| The tree to be reclaimed. ); --| Effects: The space allocated to T is reclaimed. The space occupied by --| the values stored in T is not however, recovered. ---------------------------------------------------------------------------- generic with procedure free_Value(V: in out Value_Type) is <>; procedure Destroy_Deep( --| Free all space allocated to a tree. T: in out Tree --| The tree to be reclaimed. ); --| Effects: The space allocated to T is reclaimed. The values stored --| in T are reclaimed using Free_Value, and the tree nodes themselves --| are then reclaimed (in a single walk of the tree). ---------------------------------------------------------------------------- generic with function next_Value return Value_Type is <>; --| Each call to this procedure should return the next value to be --| inserted into the balanced tree being created. If necessary, --| this function should check that each value is greater than the --| previous one, and raise Out_of_Order if necessary. If values --| are not returned in strictly increasing order, the results are --| unpredictable. Function Balanced_Tree( Count: natural ) return Tree; --| Effects: Create a balanced tree by calling next_Value Count times. --| Each time Next_Value is called, it must return a value that compares --| greater than the preceeding value. This function is useful for balancing --| an existing tree (next_Value iterates over the unbalanced tree) or --| for creating a balanced tree when reading data from a file which is --| already sorted. ---------------------------------------------------------------------------- generic with function Copy_Value(V: Value_Type) return Value_Type is <>; --| This function is called to copy a value from the old tree to the --| new tree. Function Copy_Tree( T: Tree ) return Tree; --| Raises Invalid_Tree. --| Effects: Create a balanced tree that is a copy of the tree T. --| The exception Invalid_Tree is raised if T is not a valid tree. ---------------------------------------------------------------------------- Function Is_Empty( --| Check for an empty tree. T: Tree ) return boolean; --| Effects: Return TRUE iff T is an empty tree or if T was not initialized. ---------------------------------------------------------------------------- Function Find( --| Search a tree for a value. V: Value_Type; --| Value to be located T: Tree --| Tree to be searched ) return Value_Type; --| Raises: Not_Found, Invalid_Tree. --| Effects: Search T for a value that matches V. The matching value is --| returned. If no matching value is found, the exception Not_Found --| is raised. Procedure Find( --| Search a tree for a value. V: Value_Type; --| Value to be located T: Tree; --| Tree to be searched Found: out Boolean; --| TRUE iff a match was found Match: out Value_Type --| Matching value found in the tree ); --| Raises: Invalid_Tree; --| Effects: Search T for a value that matches V. On return, if Found is --| TRUE then the matching value is returned in Match. Otherwise, Found --| is FALSE and Match is undefined. ---------------------------------------------------------------------------- function is_Found( --| Check a tree for a value. V: Value_Type; --| Value to be located T: Tree --| Tree to be searched ) return Boolean; --| Raises: Invalid_Tree; --| Effects: Return TRUE iff V is found in T. ---------------------------------------------------------------------------- function Size( --| Return the count of values in T. T: Tree --| a tree ) return natural; --| Effects: Return the number of values stored in T. ---------------------------------------------------------------------------- generic with procedure Process(V: Value_Type) is <>; procedure Visit( T: Tree; Order: Scan_Kind ); --| Raises: Invalid_Tree; --| Effects: Invoke Process(V) for each value V in T. The nodes are visited --| in the order specified by Order. Although more limited than using --| an iterator, this function is also much faster. ---------------------------------------------------------------------------- function Make_Iter( --| Create an iterator over a tree T: Tree ) return Iterator; --| Raises: Invalid_Tree; ---------------------------------------------------------------------------- function More( --| Test for exhausted iterator I: Iterator --| The iterator to be tested ) return boolean; --| Effects: Return TRUE iff unscanned nodes remain in the tree being --| scanned by I. ---------------------------------------------------------------------------- procedure Next( --| Scan the next value in I I: in out Iterator; --| an active iterator V: out Value_Type --| Next value scanned ); --| Raises: No_More. --| Effects: Return the next value in the tree being scanned by I. --| The exception No_More is raised if there are no more values to scan. ---------------------------------------------------------------------------- private type Node; type Node_Ptr is access Node; type Node is record Value: Value_Type; Less: Node_Ptr; More: Node_Ptr; end record; type Tree_Header is record Count: natural := 0; Root: Node_Ptr := Null; end record; type Tree is access Tree_Header; type Iter_State is (Left, Middle, Right, Done); type Iterator_Record; type Iterator is access Iterator_Record; type Iterator_Record is record State: Iter_State; Parent: Iterator; subtree: Node_Ptr; end record; end binary_trees_pkg; with unchecked_deallocation; Package body Binary_Trees_Pkg is --| Efficient implementation of binary trees. ---------------------------------------------------------------------------- -- Local Operations -- ---------------------------------------------------------------------------- procedure Free_Node is new unchecked_deallocation(Node, Node_Ptr); procedure Free_Tree is new unchecked_deallocation(Tree_Header, Tree); procedure Free_Iterator is new unchecked_deallocation(Iterator_Record, Iterator); ---------------------------------------------------------------------------- -- Visible Operations -- ---------------------------------------------------------------------------- Function Create --| Return an empty tree. return Tree is begin return new Tree_Header'(0, Null); end Create; ---------------------------------------------------------------------------- Procedure Insert_Node( V: Value_Type; N: in out Node_Ptr; Found: out boolean; Duplicate: out Value_Type ) is D: integer; begin Found := False; if N = null then N := new Node'(V, Null, Null); else D := Difference(V, N.Value); if D < 0 then Insert_Node(V, N.Less, Found, Duplicate); elsif D > 0 then Insert_Node(V, N.More, Found, Duplicate); else Found := True; Duplicate := N.Value; end if; end if; end Insert_Node; Procedure Replace_Node( V: Value_Type; N: in out Node_Ptr; Found: out boolean; Duplicate: out Value_Type ) is D: integer; begin Found := False; if N = null then N := new Node'(V, Null, Null); else D := Difference(V, N.Value); if D < 0 then Replace_Node(V, N.Less, Found, Duplicate); elsif D > 0 then Replace_Node(V, N.More, Found, Duplicate); else Found := True; Duplicate := N.Value; N.Value := V; end if; end if; end Replace_Node; Procedure Insert( --| Insert a value into a tree. V: Value_Type; --| Value to be inserted T: Tree --| Tree to contain the new value ) --| Raises: Duplicate_Value, Invalid_Tree. is Found: boolean; Duplicate: Value_Type; begin if T = null then raise Invalid_Tree; end if; Insert_Node(V, T.Root, Found, Duplicate); if Found then raise Duplicate_Value; end if; T.Count := T.Count + 1; end Insert; Procedure Insert_if_not_Found( --| Insert a value into a tree, provided a duplicate value is not already there V: Value_Type; --| Value to be inserted T: Tree; --| Tree to contain the new value Found: out boolean; Duplicate: out Value_Type ) --| Raises: Invalid_Tree. is was_Found: boolean; begin if T = null then raise Invalid_Tree; end if; Insert_Node(V, T.Root, was_Found, Duplicate); Found := was_Found; if not was_Found then T.Count := T.Count + 1; end if; end Insert_if_Not_Found; procedure Replace_if_Found( --| Replace a value if label exists, otherwise insert it. V: Value_Type; --| Value to be inserted T: Tree; --| Tree to contain the new value Found: out boolean; --| Becomes True iff L already in tree Old_Value: out Value_Type --| the duplicate value, if there is one ) --| Raises: Invalid_Tree. is was_Found: boolean; Duplicate: Value_Type; begin if T = null then raise Invalid_Tree; end if; Replace_Node(V, T.Root, was_Found, Duplicate); Found := was_Found; if was_Found then Old_Value := Duplicate; else T.Count := T.Count + 1; end if; end Replace_if_Found; ---------------------------------------------------------------------------- procedure Destroy_Nodes( N: in out Node_Ptr ) is begin if N /= null then Destroy_Nodes(N.Less); Destroy_Nodes(N.More); Free_Node(N); end if; end Destroy_Nodes; procedure Destroy( --| Free space allocated to a tree. T: in out Tree --| The tree to be reclaimed. ) is begin if T /= Null then Destroy_Nodes(T.Root); Free_Tree(T); end if; end Destroy; ---------------------------------------------------------------------------- procedure Destroy_Deep( --| Free all space allocated to a tree. T: in out Tree --| The tree to be reclaimed. ) is procedure Destroy_Nodes( N: in out node_Ptr ) is begin if N /= null then Free_Value(N.Value); Destroy_Nodes(N.Less); Destroy_Nodes(N.More); Free_Node(N); end if; end Destroy_Nodes; begin if T /= Null then Destroy_Nodes(T.Root); Free_Tree(T); end if; end Destroy_Deep; ---------------------------------------------------------------------------- Function Balanced_Tree( Count: natural ) return Tree is new_Tree: Tree := Create; procedure subtree(Count: natural; N: in out Node_Ptr) is new_Node: Node_Ptr; begin if Count = 1 then new_Node := new Node'(next_Value, Null, Null); elsif Count > 1 then new_node := new Node; subtree(Count/2, new_Node.Less); -- Half are less new_Node.Value := next_Value; -- Median value subtree(Count - Count/2 - 1, new_Node.More); -- Other half are more end if; N := new_Node; end subtree; begin new_Tree.Count := Count; subtree(Count, new_Tree.Root); return new_Tree; end Balanced_Tree; ---------------------------------------------------------------------------- Function Copy_Tree( T: Tree ) return Tree is I: Iterator; function next_Val return Value_type is V: Value_Type; begin Next(I, V); return copy_Value(V); end next_Val; function copy_Balanced is new Balanced_Tree(next_Val); begin I := Make_Iter(T); -- Will raise Invalid_Tree if necessary return copy_Balanced(Size(T)); end Copy_Tree; ---------------------------------------------------------------------------- Function Is_Empty( --| Check for an empty tree. T: Tree ) return boolean is begin return T = Null or else T.Root = Null; end Is_Empty; ---------------------------------------------------------------------------- procedure Find_Node( V: Value_Type; --| Value to be located N: Node_Ptr; --| subtree to be searched Match: out Value_Type; --| Matching value found in the tree Found: out Boolean --| TRUE iff a match was found ) is D: integer; begin if N = null then Found := False; return; end if; D := Difference(V, N.Value); if D < 0 then Find_Node(V, N.Less, Match, Found); elsif D > 0 then Find_Node(V, N.More, Match, Found); else Match := N.Value; Found := TRUE; end if; end Find_Node; Function Find( --| Search a tree for a value. V: Value_Type; --| Value to be located T: Tree --| Tree to be searched ) return Value_Type --| Raises: Not_Found. is Found: Boolean; Match: Value_Type; begin if T = Null then raise Invalid_Tree; end if; Find_Node(V, T.Root, Match, Found); if Found then return Match; else raise Not_Found; end if; end Find; Procedure Find( --| Search a tree for a value. V: Value_Type; --| Value to be located T: Tree; --| Tree to be searched Found: out Boolean; --| TRUE iff a match was found Match: out Value_Type --| Matching value found in the tree ) is begin if T = Null then raise Invalid_Tree; end if; Find_Node(V, T.Root, Match, Found); end Find; ---------------------------------------------------------------------------- function is_Found( --| Check a tree for a value. V: Value_Type; --| Value to be located T: Tree --| Tree to be searched ) return Boolean is Found: Boolean; Match: Value_Type; begin if T = Null then raise Invalid_Tree; end if; Find_Node(V, T.Root, Match, Found); return Found; end is_Found; ---------------------------------------------------------------------------- function Size( --| Return the count of values in T. T: Tree --| a tree ) return natural is begin if T = Null then Return 0; else Return T.Count; end if; end Size; ---------------------------------------------------------------------------- procedure Visit( T: Tree; Order: Scan_Kind ) is procedure visit_Inorder(N: Node_Ptr) is begin if N.Less /= null then visit_Inorder(N.Less); end if; Process(N.Value); if N.More /= null then visit_Inorder(N.More); end if; end visit_Inorder; procedure visit_preorder(N: Node_Ptr) is begin Process(N.Value); if N.Less /= null then visit_preorder(N.Less); end if; if N.More /= null then visit_preorder(N.More); end if; end visit_preorder; procedure visit_postorder(N: Node_Ptr) is begin if N.Less /= null then visit_postorder(N.Less); end if; if N.More /= null then visit_postorder(N.More); end if; Process(N.Value); end visit_postorder; begin if T = Null then raise Invalid_Tree; else case Order is when inorder => Visit_Inorder(T.Root); when preorder => Visit_preorder(T.Root); when postorder => Visit_postorder(T.Root); end case; end if; end Visit; ---------------------------------------------------------------------------- function subtree_Iter( --| Create an iterator over a subtree N: Node_Ptr; P: Iterator ) return Iterator is begin if N = Null then return new Iterator_Record'(State => Done, Parent => P, subtree => N); elsif N.Less = Null then return new Iterator_Record'(State => Middle, Parent => P, subtree => N); else return new Iterator_Record'(State => Left, Parent => P, subtree => N); end if; end subtree_Iter; function Make_Iter( --| Create an iterator over a tree T: Tree ) return Iterator is begin if T = Null then raise Invalid_Tree; end if; return subtree_Iter(T.Root, Null); end Make_Iter; ---------------------------------------------------------------------------- function More( --| Test for exhausted iterator I: Iterator --| The iterator to be tested ) return boolean is begin if I = Null then return False; elsif I.Parent = Null then return I.State /= Done and I.subtree /= Null; elsif I.State = Done then return More(I.Parent); else return True; end if; end More; ---------------------------------------------------------------------------- procedure pop_Iterator( I: in out Iterator ) is NI: Iterator; begin loop NI := I; I := I.Parent; Free_Iterator(NI); exit when I = Null; exit when I.State /= Done; end loop; end pop_Iterator; procedure Next( --| Scan the next value in I I: in out Iterator; --| an active iterator V: out Value_Type --| Next value scanned ) --| Raises: No_More. is NI: Iterator; begin if I = Null or I.State = Done then raise No_More; end if; case I.State is when Left => -- Return the leftmost value while I.subtree.Less /= Null loop -- Find leftmost subtree I.State := Middle; -- Middle is next at this level I := subtree_Iter(I.subtree.Less, I); end loop; V := I.subtree.Value; if I.subtree.More /= Null then -- There will be more... I.State := Right; -- ... coming from the right else -- Nothing else here pop_Iterator(I); -- Pop up to parent iterator end if; when Middle => V := I.subtree.Value; if I.subtree.More /= Null then -- There will be more... I.State := Right; -- ... coming from the right else -- Nothing else here so... pop_Iterator(I); -- ... Pop up to parent iterator end if; when Right => -- Return the value on the right I.State := Done; -- No more at this level I := subtree_Iter(I.subtree.More, I); Next(I, V); when Done => pop_Iterator(I); Next(I, V); end case; end Next; ---------------------------------------------------------------------------- end binary_trees_pkg; with Fields, Text_Io, Bounded_String,binary_trees_pkg; package Models is Error_Model_Store : exception; Error_Model_Index : exception; Error_Model_Search: exception; type Object is limited private; type Model_Index is limited private; Max_Model_String : constant := 32; --Creation procedure Create (D : in out Object); --Access function Has_Model (D : in Object; Name : in String) return Boolean; function Get_Model_Type_By_Name(D : Object; Name : String)return String; Procedure Get_Model_Fields_By_Name(D : Object; Name : String;F:in out Fields.Object); procedure Dump_Models (D : in Object); procedure Dump_Number_Of_Model(D : in Object); --Modification procedure Store_Model (D : in out Object; aName : String;aType :String;F :Fields.Object); --Liberation procedure Dispose_Object (D : in out Object); --Iteration procedure Open_Model_Indexation (D : Object; I : in out Model_Index); procedure Next_Model_Index (I : in out Model_Index); function Get_Indexed_Model_Name (I : Model_Index) return String; function Get_Indexed_Model_Type (I : Model_Index) return String; procedure Get_Indexed_Model_Fields(I : Model_Index;F:in out Fields.Object); function No_More_Models (I : Model_Index) return Boolean; private type Model is record Model_Name : Bounded_String.Variable_String (Max_Model_String); Model_Type : Bounded_String.Variable_String (Max_Model_String); Model_Fields: Fields.Object; end record; function Compare (A, B : Model) return integer; package Models_Tree is new binary_Trees_pkg(Model,Compare); type Object is record Node : Models_Tree.Tree; end record; type Model_Index is record Node : Models_Tree.Iterator; end record; end Models; with Fields, Text_Io, Bounded_String,binary_trees_pkg; package body Models is Use Models_Tree; INF :constant Integer := -1; EQU :constant Integer := 0; SUP :constant Integer := 1; Current_Model :Model; LookAhead :Boolean; function Create_Model(N: String;T: String; F : Fields.Object) return Model is A:Model; begin Bounded_string.free(A.Model_Name); Bounded_string.Copy(A.Model_Name,N); Bounded_string.free(A.Model_Type); Bounded_string.Copy(A.Model_Type,T); Fields.Surface_copy(A.Model_Fields,F); return A; end; function Compare (A, B : Model) return integer is begin declare Use Bounded_String; begin if image(A.Model_name) < image(B.Model_name) then return INF; elsif image(A.Model_name) = image(B.Model_name) then return EQU; else return SUP; end if; end; end Compare; procedure Dispose_Model (The_Model : in out Model) is begin Fields.Dispose_Object(The_Model.Model_Fields); Bounded_String.Free(The_Model.Model_Name); Bounded_String.Free(The_Model.Model_Type); end Dispose_Model; procedure Destroy_Object is New Destroy_Deep(Free_Value =>Dispose_Model); procedure Dump_An_Model ( A : Model ) is begin Text_IO.Put_Line("........................................"); Text_Io.Put_Line ( Bounded_String.image(A.Model_Name) &" "& Bounded_String.image(A.Model_Type) &"With Fields:"); Fields.Dump_Fields(A.Model_Fields); end Dump_An_Model ; procedure Dump is new Visit ( Process => Dump_An_Model ) ; --Creation procedure Create (D : in out Object) is begin D.Node := Models_Tree.Create; end ; --Access procedure Dump_Number_Of_Model(D : in Object) is begin text_io.put_line("Number of Model:"&natural'image(Models_tree.size(D.Node))); end; function Has_Model (D : in Object; Name : in String) return Boolean is A : Model; F : Fields.Object; begin Fields.Create(F); A:=Create_Model(Name,Name,F); -- Only the first param. is important return Models_tree.Is_Found (A,D.node); end Has_Model; function Get_Model_Type_By_Name(D : Object; Name : String)return String is Found : Boolean := False; A : Model; B :Fields.Object; begin Fields.Create(B); A:=Create_Model(Name,Name,B); -- Only the first param. is important Models_tree.Find(A,D.node,Found,A); if found then return Bounded_String.Image(A.Model_Type); else return ""; end if; exception when others => raise Error_Model_Search; end; Procedure Get_Model_Fields_By_Name(D : Object; Name : String;F:in out Fields.Object) is Found : Boolean := False; A : Model; B :Fields.Object; begin Fields.Create(B); A:=Create_Model(Name,Name,B); -- Only the first param. is important Models_tree.Find(A,D.node,Found,A); if found then Fields.Deep_copy(F,A.Model_Fields); end if; exception when others => raise Error_Model_Search; end; procedure Dump_Models (D : in Object) is begin Dump ( D.Node,Models_tree.inorder); end Dump_Models; --Modification procedure Store_Model (D : in out Object; aName : String;aType :String;F :Fields.Object)is Found : Boolean := False; A : Model; B :Fields.Object; begin Fields.Create(B); Fields.Deep_copy(B,F); Models_tree.Replace_If_Found (Create_Model(aName,aType,B),D.Node,Found,A); if Found then Dispose_Model(A); end if; exception when others => raise Error_Model_Store; end Store_Model; --Liberation procedure Dispose_Object (D : in out Object) is begin Destroy_Object(D.Node); end Dispose_Object; --Iteration procedure Open_Model_Indexation (D : Object; I : in out Model_Index) is begin I.Node := Models_tree.Make_Iter(D.Node); LookAhead:=FALSE; Next_Model_Index(I); end Open_Model_Indexation; procedure Next_Model_Index (I : in out Model_Index) is begin if not Lookahead then if Models_tree.More (I.Node) then Models_tree.Next(I.Node,Current_Model); else raise Error_Model_Index; end if; end if; end Next_Model_Index; function Get_Indexed_Model_Name (I : Model_Index) return String is begin return Bounded_String.Image (Current_Model.Model_Name); exception when others=> raise Error_Model_Index; end Get_Indexed_Model_Name; function Get_Indexed_Model_Type (I : Model_Index) return String is begin return Bounded_String.Image (Current_Model.Model_Type); exception when others=> raise Error_Model_Index; end Get_Indexed_Model_Type; procedure Get_Indexed_Model_Fields(I : Model_Index;F:in out Fields.Object) is begin Fields.Deep_Copy (F, Current_Model.Model_Fields); exception when others=> raise Error_Model_Index; raise Error_Model_Index; end Get_Indexed_Model_Fields; function No_More_Models (I : Model_Index) return Boolean is More:Boolean:=TRUE; begin More:= Models_tree.More (I.Node); if More then return (False); end if; if (not More AND not LookAhead) then Lookahead:=TRUE; return(FALSE); elsif (not More AND LookAhead) then return(TRUE); end if; end No_More_Models; end Models; with fields,models,Text_io; procedure main is L1:Fields.Object; L2:Fields.Object; L3:Fields.Object; M:Models.Object; procedure Print_With_Index(D :Models.Object) is Index : Models.Model_Index; Liste:Fields.Object; begin Models.Open_Model_Indexation (D , Index); while not Models.No_More_Models(Index) loop Text_IO.Put_Line("****************************************"); Text_Io.Put_Line (Models.Get_Indexed_Model_Name (Index) & " : " & Models.Get_Indexed_Model_Type(Index)&"-> WITH:"); Fields.Create(Liste); Models.Get_Indexed_Model_Fields(Index,Liste); Fields.Dump_Fields(Liste); Fields.Dispose_Object(Liste); Models.Next_Model_Index (Index); end loop; end Print_With_Index; begin Fields.Create(L1); Fields.Create(L2); Fields.Create(L3); Models.Create(M); Fields.Store_field(L1,"Description","Chaine "); Fields.Store_field(L1,"NiveauEau ","Niveau "); Fields.Store_field(L1,"NiveauEnerg","Energie "); Text_IO.Put_Line("----------------------------------------"); Text_IO.Put_Line("--- Print Liste L1 ----------"); Fields.Dump_Fields(L1); Fields.Dump_Number_Of_Field(L1); Fields.Store_field(L2,"Lumiere ","Eclairage "); Fields.Store_field(L2,"Intensite ","Entier "); Fields.Store_field(L2,"Tension ","Entier "); Fields.Store_field(L2,"Puissance ","Entier "); Text_IO.Put_Line("----------------------------------------"); Text_IO.Put_Line("--- Print Liste L2 ----------"); Fields.Dump_Fields(L2); Fields.Dump_Number_Of_Field(L2); Fields.Store_field(L3,"Cuisine ","Piece "); Fields.Store_field(L3,"Salon ","Piece "); Text_IO.Put_Line("----------------------------------------"); Text_IO.Put_Line("--- Print Liste L3 ----------"); Fields.Dump_Fields(L3); Fields.Dump_Number_Of_Field(L3); Models.Store_Model(M,"Niveau ","Struct ",L1); Models.Store_Model(M,"Electriqu","Struct ",L2); Models.Store_Model(M,"Maison ","Struct ",L3); Text_IO.Put_Line("----------------------------------------"); Text_IO.Put_Line("--- Print Modele M ----------"); Models.Dump_Models(M); Models.Dump_Number_Of_Model(M); Text_IO.Put_Line("========================================"); Text_IO.Put_Line("--- Recherche du type Electriq ---------"); if Models.Has_Model(M,"Electriqu") Then declare List:Fields.Object; begin Text_Io.Put_Line ("Electriqu :"&Models.Get_Model_Type_By_Name (M,"Electriqu") &"WITH:"); Fields.Create(List); Models.Get_Model_Fields_by_Name(M,"Electriqu",List); Fields.Dump_Fields(List); Fields.Dispose_Object(List); end; end if; Text_IO.Put_Line("========================================"); Text_IO.Put_Line("--- Print Modele M with Index -------"); Print_With_Index(M); Fields.Dispose_Object(L1); Fields.Dispose_Object(L2); Fields.Dispose_Object(L3); Models.Dispose_Object(M); end