Copying rows in a two dimensional array.
in [ADA]
|
From: Hibou57 (Yannick Duchêne) on 4 Feb 2010 04:23 On 4 fév, 10:10, "Dmitry A. Kazakov" <mail...(a)dmitry-kazakov.de> wrote: > This does not work either, I mean at the user interface level, because > slice does not have a type. In Ada types system you cannot express "the > subtype S is a vector of the type M". Therefore making it abstract types > you will loose most of the comfort built-in arrays offer. I've was to post him some seed of a package (not tested, I sincerely apologize for that) : package Matrix is -- Provides a matrix type with an efficient implementation -- of a row swapping method. A similar method as the one -- provided here, may be used to get a matrix type with an -- efficient implementation of column swapping method. -- This package most likely need to be extended in order -- to be fully useful to something in real life. subtype Float_Type is Float; subtype One_Dimensional_Size_Type is Natural range 1 .. 2 ** 15; -- Either a number of rows or a number of columns. -- The maximum size is so that One_Dimensional_Size_Type ** 2 is -- most unlikely to commit an overflow and will mostly be a valid -- value on most of target machines. First_Index : constant := 1; -- This may be changed to zero if needed, whenever the -- C indexing convention is preferred. This may not be -- changed to a value greater than one, otherwise -- Index_Type may potentially go out of Natural range. subtype Index_Type is Natural range (First_Index) .. (First_Index + (One_Dimensional_Size_Type'Last - 1)); type Instance_Type (<>) is private; -- The type must be initialized at declaration : -- use New_Instance in that purpose (see below). -- The methods First_Row, Last_Row, First_Column, -- Last_Column and Item, are at least required to -- define pre- and post- condition of the New_Instance -- and Swap_Rows method. function First_Row (Instance : Instance_Type) return Index_Type; --|Ensures: Result = First_Index function Last_Row (Instance : Instance_Type) return Index_Type; function First_Column (Instance : Instance_Type) return Index_Type; --|Ensures: Result = First_Index function Last_Column (Instance : Instance_Type) return Index_Type; function Item (Instance : Instance_Type; Row : Index_Type; Column : Index_Type) return Float_Type; --|Requires: Row in First_Row (Instance) .. Last_Row (Instance); --|Requires: --| Column in First_Column (Instance) .. --| Last_Column (Instance); function New_Instance (Number_Of_Rows : One_Dimensional_Size_Type; Number_Of_Columns : One_Dimensional_Size_Type) return Instance_Type; --|Ensures: --| Last_Row (Instance) = --| First_Index + Number_Of_Rows - 1; --|Ensures: --| Last_Column (Instance) = --| First_Index + Number_Of_Column - 1; --|Ensures: --| for each Row in First_Row (Instance) .. Last_Row (Instance) --| => for each Column in First_Column (Instance) .. --| Last_Column (Instance) => Item (Row, Column) = 0.0; -- Note : all items are zero initialized. procedure Swap_Rows (Instance : in out Instance_Type; Row_1 : in Index_Type; Row_2 : in Index_Type); --|Requires: Row_1 in First_Row (Instance) .. Last_Row (Instance); --|Requires: Row_2 in First_Row (Instance) .. Last_Row (Instance); --|Ensures: --| for each Column in First_Column (Instance) .. --| Last_Column (Instance) => (Item (Instance, Row_1, Column) = --| old Item (Instance, Row_2, Column)); --|Ensures: --| for each Column in First_Column (Instance) .. --| Last_Column (Instance) => (Item (Instance, Row_2, Column) = --| old Item (Instance, Row_1, Column)); -- Note: Row_1 and Row_2 may be equal. -- =================================================================== -- *** DO NOT CROSS *** DO NOT CROSS *** DO NOT CROSS *** DO NOT CROSS -- ------------------------------------------------------------------- private pragma Assert ((First_Index + (One_Dimensional_Size_Type'Last ** 2)) <= (Natural'Last)); -- Ensure computation on indexes will never go out of range. pragma Inline (First_Row); pragma Inline (Last_Row); pragma Inline (First_Column); pragma Inline (Last_Column); type Storage_Type is array (Natural range <>) of Float_Type; -- Flatenned array rows first columns next. -- Ex. (Row-1,Col-1),(Row-2,Col-1),(Row-1,Col-2),(Row-2,Col-2) -- -- This way of flatening the matrix is the one which gives -- better performance to swap rows, as all items of a row -- appears to be consecutive, allowing slice access. -- -- If good performance at swaping columns is targeting instead, -- then use the reverse representation (that is, like the -- Fortran convention), and update implementation of methods -- accordingly. -- -- Note: the index type musn't be Index_Type, -- which is an index in one dimension, not in the overall storage. type Instance_Type (Number_Of_Rows : One_Dimensional_Size_Type; Number_Of_Columns : One_Dimensional_Size_Type; Last_Data_Index : Natural) is record Data : Storage_Type (First_Index .. Last_Data_Index); end record; end Matrix; package body Matrix is function First_Row (Instance : Instance_Type) return Index_Type is begin return First_Index; end First_Row; function Last_Row (Instance : Instance_Type) return Index_Type is begin return First_Index + (Instance.Number_Of_Rows - 1); end Last_Row; function First_Column (Instance : Instance_Type) return Index_Type is begin return First_Index; end First_Column; function Last_Column (Instance : Instance_Type) return Index_Type is begin return First_Index + (Instance.Number_Of_Columns - 1); end Last_Column; function Start_Of_Row (Instance : Instance_Type; Row : Index_Type) return Natural -- Index in Data for the first item of the row -- whose index is Row. Used for accessing a matrix items -- and for row slice accesses. is Rows_Size : constant Natural := Instance.Number_Of_Columns; begin return First_Index + (Rows_Size * (Row - First_Index)); end Start_Of_Row; pragma Inline (Start_Of_Row); function End_Of_Row (Instance : Instance_Type; Row : Index_Type) return Natural -- Index in Data for the last item of the row -- whose index is Row. Used for row slice accesses. is Rows_Size : constant Natural := Instance.Number_Of_Columns; begin return Start_Of_Row (Instance, Row) + (Rows_Size - 1); -- This is an upper bound, not a limit, so -- Rows_Size - 1 is used. We add an offset starting -- the fist index of the row. end End_Of_Row; pragma Inline (End_Of_Row); function Item (Instance : Instance_Type; Row : Index_Type; Column : Index_Type) return Float_Type is begin Validity_Constraints : begin if Row not in First_Index .. Last_Row (Instance) then raise Program_Error; end if; if Column not in First_Index .. Last_Column (Instance) then raise Program_Error; end if; end Validity_Constraints; Method: declare Row_Start : constant Natural := Start_Of_Row (Instance, Row); Column_Offset : constant Natural := Column - First_Index; Data_Index : constant Natural := Row_Start + Column_Offset; begin return Instance.Data (Data_Index); end Method; end Item; -- Procedure function New_Instance (Number_Of_Rows : One_Dimensional_Size_Type; Number_Of_Columns : One_Dimensional_Size_Type) return Instance_Type is Data_Size : constant Natural := (Number_Of_Rows * Number_Of_Columns); Last_Data_Index : constant Natural := (First_Index + (Data_Size - 1)); begin return (Number_Of_Rows => Number_Of_Rows, Number_Of_Columns => Number_Of_Columns, Last_Data_Index => Last_Data_Index, Data => (others => 0.0)); end New_Instance; -- Function procedure Swap_Rows (Instance : in out Instance_Type; Row_1 : in Index_Type; Row_2 : in Index_Type) is begin Validity_Constraints : begin if Row_1 not in First_Index .. Last_Row (Instance) then raise Program_Error; end if; if Row_2 not in First_Index .. Last_Row (Instance) then raise Program_Error; end if; end Validity_Constraints; Special_Cases : begin if Row_1 = Row_2 then return; end if; end Special_Cases; Method : declare -- See comments in the package's private part. Rows_Size : constant Natural := (Instance.Number_Of_Columns); Slice_Start_Of_Row_1 : constant Natural := Start_Of_Row (Instance, Row_1); Slice_End_Of_Row_1 : constant Natural := End_Of_Row (Instance, Row_1); Slice_Start_Of_Row_2 : constant Natural := Start_Of_Row (Instance, Row_1); Slice_End_Of_Row_2 : constant Natural := End_Of_Row (Instance, Row_2); Row_1_Slice : constant Storage_Type -- Backup of Row-1 (Slice_Start_Of_Row_1 .. Slice_End_Of_Row_1) := Instance.Data (Slice_Start_Of_Row_1 .. Slice_End_Of_Row_1); begin -- Copy Row-2 at the place of Row-1 (Row-1 was -- backed up). Instance.Data (Slice_Start_Of_Row_1 .. Slice_End_Of_Row_1) := Instance.Data (Slice_Start_Of_Row_2 .. Slice_End_Of_Row_2); -- Copy backup of Row-1 at the place of -- Row-2. Instance.Data (Slice_Start_Of_Row_2 .. Slice_End_Of_Row_2) := Row_1_Slice; end Method; end Swap_Rows; -- Procedure end Matrix; -- Package
From: Robert A Duff on 7 Feb 2010 11:13 "Randy Brukardt" <randy(a)rrsoftware.com> writes: > "Dmitry A. Kazakov" <mailbox(a)dmitry-kazakov.de> wrote in message > news:178rg3rch8qdu$.13cgkywb09x3p.dlg(a)40tude.net... >> On Sun, 31 Jan 2010 21:11:12 -0500, Peter C. Chapin wrote: >> >>> So I thought, "Perhaps A needs to be an array of arrays." >>> >>> type Matrix is array(Positive range <>) of WHAT_EXACTLY? >>> >>> Apparently the component type of an array needs to be fully constrained >>> (which >>> again makes sense) >> >> Not really. Arrays should have been allowed to have discriminants. That >> was >> missed in the language design. > > Early Ada 9x had discriminants for arrays. The capability got dropped when > lots of "nice-to-have" features got dropped from Ada 95. Such "array" types > have to be implemented as discriminant dependent records anyway; there is no > real hope of performance improvement from them, but a lot of implementation > complication. (I recall I was one of the stronger opponents of this feature, > mostly for implementation cost/benefit reasons.) > > So it is completely wrong to say that "this was missed in the language > design". The correct statement is that "this was explicitly rejected in the > language design". It was missed in the design of Ada 83. By the time of Ada 9X, it was too late. Sad. If Ada 83 had had discriminated arrays, it would have been a (slightly) simpler language. And they're not hard to implement, if you know about them ahead of time. They may be hard to add to an existing Ada 83 compiler that was designed based on the rules of Ada 83. That's true in general -- it's a lot easier to build an Ada 95 compiler, than it is to build an Ada 83 compiler and then modify it to support Ada 95. Discriminated arrays would be more efficient than Ada's arrays. We would have: type String (Length : Natural) is array (Positive range 1..Length) of Character; This typically shrinks all unknown-length strings by 32 bits, which is significant. (Think about all the memory currently being wasted to store zillions of copies of the number 1.) And it makes bounds checking cheaper because the lower bound is known at compile time. And it would reduce the number of bugs -- all strings would start at 1 (as opposed to the current sitation, where 99.99% of all strings start at 1, and remaining 0.01% are bugs waiting to happen). And it would simplify the language (no need for the "range <>" syntax, no need for the 'First and 'Last attributes of arrays, no need for separate rules about array bounds and discriminants (which are almost, but not quite, the same), etc). Adding it to Ada 95 would NOT simplify, because we'd have to keep all those now-useless features for compatibility. - Bob
From: tmoran on 8 Feb 2010 01:30 > Discriminated arrays would be more efficient than Ada's arrays. > We would have: > > type String (Length : Natural) is > array (Positive range 1..Length) of Character; How would you handle slices, either in assignments or as parameters?
From: Robert A Duff on 8 Feb 2010 08:15 tmoran(a)acm.org writes: >> Discriminated arrays would be more efficient than Ada's arrays. >> We would have: >> >> type String (Length : Natural) is >> array (Positive range 1..Length) of Character; > > How would you handle slices, either in assignments or as parameters? Sliding. All strings should start at 1, including slices. In Ada, if you do "P(X(5..10));" procedure P can see that the lower bound is 5. That's a break in the abstraction -- P shouldn't know or care where the string came from. If both bounds are constrained, then slices should be illegal. That is, "is array(1..10) of ..." should mean that ALL objects of that type have bounds exactly 1..10. Actually, slices are one of the least useful features of Ada. I wouldn't mind (much) if they didn't exist in the first place. - Bob
From: Dmitry A. Kazakov on 8 Feb 2010 08:45
On Mon, 08 Feb 2010 08:15:50 -0500, Robert A Duff wrote: > Actually, slices are one of the least useful features of Ada. > I wouldn't mind (much) if they didn't exist in the first place. But only if the language provided means to have user-defined ones. Which is far from trivial. You need a lot of related types to describe slices themselves and indicator sets (ranges). Plus you have to provide means to determine if subarrays overlap in order to implement assignment in a safe way. And user-defined assignment itself need to be properly done (syntax, referential semantics of function results etc.) -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |