A Extracts from the Base libraries Throughout the discussion,we have encountered references to a set of libraries collectively known as the "Base libraries",from which the most fundamental classes are grouped into the "Kemel library". Reading such classes is a good way to learn more about the method by benefiting from the example of widely reused software components,which have been around for a long time and continue to evolve. This page and the next are only the introduction to the appendix;the actual class texts,made available in electronic form so as to facilitate browsing,appear only on the CD- ROM version of this book (starting next page). See“Criteria for A detailed presentation of the libraries has been published separately [M 1994a],which view inheritance”, also describes the theoretical underpinnings-the general taxonomy principles used to page 856. classify the major data structures of computing science.A few of the basic ideas were summarized in the discussion of view inheritance. Among the most important classes whose concepts were discussed in the previous chapters and whose text you will find on the following pages on the CD-ROM are: ARRAY,describing one-dimensional arrays and relying on a flexible and general view of this notion (in particular,arrays can be freely resized to any dimension during the execution of a system). LINKABLE,describing cells of linked structures,chained one-way to similar cells. BI LINKABLE,the equivalent for two-way linked cells. LIST,a deferred class representing the general notion of list as"active data structure" with cursor,without commitment to a particular representation.(The next three classes provide specific implementations,using multiple inheritance through the “marriage of convenience”technique.) ARRAYED LIST,giving an implementation by an array (whose resizability of is particularly useful here). LINKED LIST,a one-way linked list implementation,relying internally on class LINKABLE
A Extracts from the Base libraries Throughout the discussion, we have encountered references to a set of libraries collectively known as the “Base libraries”, from which the most fundamental classes are grouped into the “Kernel library”. Reading such classes is a good way to learn more about the method by benefiting from the example of widely reused software components, which have been around for a long time and continue to evolve. This page and the next are only the introduction to the appendix; the actual class texts, made available in electronic form so as to facilitate browsing, appear only on the CDROM version of this book (starting next page). A detailed presentation of the libraries has been published separately [M 1994a], which also describes the theoretical underpinnings — the general taxonomy principles used to classify the major data structures of computing science. A few of the basic ideas were summarized in the discussion of view inheritance. Among the most important classes whose concepts were discussed in the previous chapters and whose text you will find on the following pages on the CD-ROM are: • ARRAY, describing one-dimensional arrays and relying on a flexible and general view of this notion (in particular, arrays can be freely resized to any dimension during the execution of a system). • LINKABLE, describing cells of linked structures, chained one-way to similar cells. • BI_LINKABLE, the equivalent for two-way linked cells. • LIST, a deferred class representing the general notion of list as “active data structure” with cursor, without commitment to a particular representation. (The next three classes provide specific implementations, using multiple inheritance through the “marriage of convenience” technique.) • ARRAYED_LIST, giving an implementation by an array (whose resizability of is particularly useful here). • LINKED_LIST, a one-way linked list implementation, relying internally on class LINKABLE. See “Criteria for view inheritance”, page 856
1166 EXTRACTS FROM THE BASE LIBRARY SA.I TWO WAY L/ST,a one-way linked list implementation,relying internally on class BI LINKABLE. TWO WAY TREE,a widely used implementation of general trees,based on TWO WAY LIST for its representation and relying on the observation made on the chapter on multiple inheritance:if we merge the notion of tree and node,we can consider that a tree is both a list (as in TWO WAY LIST)and a list element (as in BI LINKABLE). All these classes,representing containers,are generic,with a single generic parameter representing the type of elements. The classes are given"as is",without further formating.Note that the following page numbers are of the form 1266.1,1266.2 etc.to avoid any confusion with the numbering of the pages in the printed book A.1 ARRAYS indexing description: "Sequences of values,all of the same type or of a conforming one, %accessible through integer indices in a contiguous interval"; status:“See notice at end of class'”, date:“$Date:1996/06/0514:19:05$, revision:"SRevision:1.28 $ class ARRAY [G]inherit RESIZABLE [G] redefine full,copy,is_equal, consistent,setup end; INDEXABLE [G,INTEGER] redefine
1166 EXTRACTS FROM THE BASE LIBRARY §A.1 • TWO_WAY_LIST, a one-way linked list implementation, relying internally on class BI_LINKABLE. • TWO_WAY_TREE, a widely used implementation of general trees, based on TWO_WAY_LIST for its representation and relying on the observation made on the chapter on multiple inheritance: if we merge the notion of tree and node, we can consider that a tree is both a list (as in TWO_WAY_LIST) and a list element (as in BI_LINKABLE). All these classes, representing containers, are generic, with a single generic parameter representing the type of elements. The classes are given “as is”, without further formating. Note that the following page numbers are of the form 1266.1, 1266.2 etc. to avoid any confusion with the numbering of the pages in the printed book. A.1 ARRAYS indexing description: “Sequences of values, all of the same type or of a conforming one, % %accessible through integer indices in a contiguous interval”; status: “See notice at end of class”; date: “$Date: 1996/06/05 14:19:05 $”; revision: “$Revision: 1.28 $” class ARRAY [G] inherit RESIZABLE [G] redefine full, copy, is_equal, consistent, setup end; INDEXABLE [G, INTEGER] redefine
SA.1 ARRAYS 1166.1 copy,is_equal, consistent,setup end; TO SPECIAL [G] export (ARRAY)set area redefine copy,is_equal, consistent,setup end creation make feature--Initialization make (minindex,maxindex:INTEGER)is --Allocate array;set index interval to --'minindex'..'maxindex';set all values to default. --(Make array empty if'minindex'='maxindex'+1). require valid indices:minindex <maxindex or (minindex maxindex 1) do lower:=minindex; upper :maxindex; if minindex <maxindex then make area (maxindex-minindex +1) else make area(0)
§A.1 ARRAYS 1166.1 copy, is_equal, consistent, setup end; TO_SPECIAL [G] export {ARRAY} set_area redefine copy, is_equal, consistent, setup end creation make feature -- Initialization make (minindex, maxindex: INTEGER) is -- Allocate array; set index interval to -- `minindex’ .. `maxindex’; set all values to default. -- (Make array empty if `minindex’ = `maxindex’ + 1). require valid_indices: minindex <= maxindex or (minindex = maxindex + 1) do lower := minindex; upper := maxindex; if minindex <= maxindex then make_area (maxindex - minindex + 1) else make_area (0)
1166.2 EXTRACTS FROM THE BASE LIBRARY SA.I end; ensure lower minindex; upper maxindex end; make_from_array (a:ARRAY [G])is --Initialize from the items of'a'. -(Useful in proper descendants of class'ARRAY', -to initialize an array-like object from a manifest array.) require array_exists:a /Void do area :a.area; lower :a.lower; upper :a.upper end; setup (other:like Current)is --Perform actions on a freshly created object so that -the contents of'other'can be safely copied onto it. do make area (other.capacity) end; feature--Access frozen item,frozen infix"@",entry (i:INTEGER):G is --Entry at index'i',if in index interval do Result :area.item (i-lower); end;
1166.2 EXTRACTS FROM THE BASE LIBRARY §A.1 end; ensure lower = minindex; upper = maxindex end; make_from_array (a: ARRAY [G]) is -- Initialize from the items of `a’. -- (Useful in proper descendants of class `ARRAY’, -- to initialize an array-like object from a manifest array.) require array_exists: a /= Void do area := a.area; lower := a.lower; upper := a.upper end; setup (other: like Current) is -- Perform actions on a freshly created object so that -- the contents of `other’ can be safely copied onto it. do make_area (other.capacity) end; feature -- Access frozen item, frozen infix “@”, entry (i: INTEGER): G is -- Entry at index `i’, if in index interval do Result := area.item (i - lower); end;
SA.1 ARRAYS 1166.3 has(v:G):BOOLEAN is --Does'v'appear in array? --(Reference or object equality, --based on 'object comparison'.) local i:INTEGER do if object comparison then if v=void then i :upper 1 else from i:=lower until i>upper or else (item (i)/=Void and then item (i). is_equal(v)) loop i=i+1; end; end else from i:=lower until i>upper or else (item (i)=v) loop i=i+1; end; end Result :not(i>upper); end;
§A.1 ARRAYS 1166.3 has (v: G): BOOLEAN is -- Does `v’ appear in array? -- (Reference or object equality, -- based on `object_comparison’.) local i: INTEGER do if object_comparison then if v = void then i := upper + 1 else from i := lower until i > upper or else (item (i) /= Void and then item (i). is_equal(v)) loop i := i + 1; end; end else from i := lower until i > upper or else (item (i) = v) loop i := i + 1; end; end Result := not (i > upper); end;
1166.4 EXTRACTS FROM THE BASE LIBRARY SA.I feature--Measurement lower:INTEGER; --Minimum index upper:INTEGER: --Maximum index count,capacity:INTEGER is --Number of available indices do Result :upper-lower +1 end; occurrences(v:G):INTEGER is --Number of times'v'appears in structure local i:INTEGER do if object_comparison then if v/=Void then from i:=lower until i>upper loop if item (i)/=Void and then v.is_equal (item (i)) then Result:Result+1 end i=i+1
1166.4 EXTRACTS FROM THE BASE LIBRARY §A.1 feature -- Measurement lower: INTEGER; -- Minimum index upper: INTEGER; -- Maximum index count, capacity: INTEGER is -- Number of available indices do Result := upper - lower + 1 end; occurrences (v: G): INTEGER is -- Number of times `v’ appears in structure local i: INTEGER do if object_comparison then if v /= Void then from i := lower until i > upper loop if item (i) /= Void and then v.is_equal (item (i)) then Result := Result + 1 end i := i + 1
SA.1 ARRAYS 1166.5 end end else from i:=lower until i>upper loop if item (i)=v then Result:=Result+1 end; i=i+1 end end; end; feature--Comparison is_equal (other:like Current):BOOLEAN is --Is array made of the same items as'other'? do Result :area.is_equal (other.area) end; feature--Status report consistent (other:like Current):BOOLEAN is --Is object in a consistent state so that'other' --may be copied onto it?(Default answer:yes). do Result :=(capacity other.capacity) end;
§A.1 ARRAYS 1166.5 end end else from i := lower until i > upper loop if item (i) = v then Result := Result +1 end; i := i + 1 end end; end; feature -- Comparison is_equal (other: like Current): BOOLEAN is -- Is array made of the same items as `other’? do Result := area.is_equal (other.area) end; feature -- Status report consistent (other: like Current): BOOLEAN is -- Is object in a consistent state so that `other’ -- may be copied onto it? (Default answer: yes). do Result := (capacity = other.capacity) end;
1166.6 EXTRACTS FROM THE BASE LIBRARY SA.I full:BOOLEAN is --Is structure filled to capacity?(Answer:yes) do Result:=true end; all cleared:BOOLEAN is --Are all items set to default values? local i:INTEGER: dead element:G; do from i:=lower variant upper +1-i until (i>upper)or else not (dead_element item (i)) loop i=i+1 end; Result :=i>upper; end; valid index(i:INTEGER):BOOLEAN is -Is'i'within the bounds of the array? do Result:=(lower <=i)and then (i<=upper) end; extendible:BOOLEAN is
1166.6 EXTRACTS FROM THE BASE LIBRARY §A.1 full: BOOLEAN is -- Is structure filled to capacity? (Answer: yes) do Result := true end; all_cleared: BOOLEAN is -- Are all items set to default values? local i: INTEGER; dead_element: G; do from i := lower variant upper + 1 - i until (i > upper) or else not (dead_element = item (i)) loop i := i + 1 end; Result := i > upper; end; valid_index (i: INTEGER): BOOLEAN is -- Is `i’ within the bounds of the array? do Result := (lower <= i) and then (i <= upper) end; extendible: BOOLEAN is
SA.1 ARRAYS 1166.7 --May items be added? --(Answer:no,although array may be resized.) do Result:=false end; prunable:BOOLEAN is --May items be removed?(Answer:no.) do Result :false end; feature--Element change frozen put,enter(v:like item;i:INTEGER)is --Replace'i'-th entry,if in index interval,by'v'. do area.put(v,i-lower); end; force (v:like item;i:INTEGER)is --Assign item'v'to'i'-th entry. --Always applicable:resize the array if'i'falls out of --currently defined bounds;preserve existing items. do ifiupper then auto resize (lower,i); end; put (v,i) ensure
§A.1 ARRAYS 1166.7 -- May items be added? -- (Answer: no, although array may be resized.) do Result := false end; prunable: BOOLEAN is -- May items be removed? (Answer: no.) do Result := false end; feature -- Element change frozen put, enter (v: like item; i: INTEGER) is -- Replace `i’-th entry, if in index interval, by `v’. do area.put (v, i - lower); end; force (v: like item; i: INTEGER) is -- Assign item `v’ to `i’-th entry. -- Always applicable: resize the array if `i’ falls out of -- currently defined bounds; preserve existing items. do if i upper then auto_resize (lower, i); end; put (v, i) ensure
1166.8 EXTRACTS FROM THE BASE LIBRARY SA.I inserted:item (i)=v; higher_count:count>=old count end; subcopy (other:like Current;start_pos,end_pos,index_pos:INTEGER)is --Copy items of'other'within bounds'start_pos'and'end_pos' -to current array starting at index'index_pos'. require other_not_void:other/=Void; valid_start_pos:other.valid_index(start_pos) valid_end_pos:other.valid_index(end_pos) valid_bounds:(start_pos =(end_pos-start_pos) local other_area:like area; other_lower:INTEGER: start0,end0,index0:INTEGER do other_area:=other.area; other lower :other.lower; starto :start_pos-other_lower; endo:=end_pos-other_lower; index0:=index_pos-lower; spsubcopy (Sother_area,Sarea,starto,endo,index0) ensure --copied:forall'i'in0..('end_pos'-'start_pos'), -item (index pos +i)=other.item (start pos +i) end feature--Removal
1166.8 EXTRACTS FROM THE BASE LIBRARY §A.1 inserted: item (i) = v; higher_count: count >= old count end; subcopy (other: like Current; start_pos, end_pos, index_pos: INTEGER) is -- Copy items of `other’ within bounds `start_pos’ and `end_pos’ -- to current array starting at index `index_pos’. require other_not_void: other /= Void; valid_start_pos: other.valid_index (start_pos) valid_end_pos: other.valid_index (end_pos) valid_bounds: (start_pos = (end_pos - start_pos) local other_area: like area; other_lower: INTEGER; start0, end0, index0: INTEGER do other_area := other.area; other_lower := other.lower; start0 := start_pos - other_lower; end0 := end_pos - other_lower; index0 := index_pos - lower; spsubcopy ($other_area, $area, start0, end0, index0) ensure -- copied: forall `i’ in 0 .. (`end_pos’-`start_pos’), -- item (index_pos + i) = other.item (start_pos + i) end feature -- Removal
