note description: "Multi-dimensional array" legal: "See notice at end of class." status: "See notice at end of class." representation: array access: multi_dimensional_index size: resizable contents: generic date: "$Date$" revision: "$Revision$" class ECOM_ARRAY [G] inherit ANY undefine is_equal, copy end ARRAY [detachable G] rename make as array_make, make_empty as array_make_empty, item as array_item, put as array_put, force as array_force, resize as array_resize, make_from_array as array_make_from_array export {NONE} all {ECOM_ARRAY} lower, upper, subarray {ANY} area, array_item, count, valid_index, compare_objects, compare_references, object_comparison, changeable_comparison_criterion redefine discard_items end create make, make_from_array, make_empty feature {NONE} -- Initialization make_empty -- Create empty array. do make (1, <<1>>, <<0>>) end make (a_dimension_count: INTEGER; some_lower_indices, some_element_counts: ARRAY [INTEGER]) -- Create `a_dimensional_count' dimensional array -- with lower indices in each dimension as described by `some_lower_indices' -- and element count in each dimension as described by `some_element_counts'. require valid_dimension_count: a_dimension_count >= 0 valid_lower_indices: some_lower_indices /= Void and then some_lower_indices.count = a_dimension_count and (a_dimension_count > 0 implies some_lower_indices.lower = 1) valid_element_count: some_element_counts /= Void and then some_element_counts.count = a_dimension_count and (a_dimension_count > 0 implies some_element_counts.lower = 1) and then are_element_counts_valid (some_element_counts) local a_count: INTEGER i: INTEGER v: detachable G do dimension_count := a_dimension_count element_counts := some_element_counts.twin lower_indices := some_lower_indices.twin if dimension_count > 0 then a_count := 1 else a_count := 0 end from i := 1 create upper_indices.make_filled (0, 1, dimension_count) until i > dimension_count loop upper_indices.put (element_counts.item (i) + lower_indices.item (i) - 1, i) a_count := a_count * element_counts.item (i) i := i + 1 variant dimension_count - i + 1 end make_filled (v, 0, a_count - 1) ensure valid_dimension_count: dimension_count >= 0 valid_element_counts: element_counts /= Void and then element_counts.count = dimension_count valid_lower_indices: lower_indices /= Void and then lower_indices.count = dimension_count valid_upper_indices: upper_indices /= Void and then upper_indices.count = dimension_count end make_from_array (a: ARRAY [G]; a_dimension_count: INTEGER; some_lower_indices, some_element_counts: ARRAY [INTEGER]) -- Create `a_dimensional_count' dimensional array -- with lower indices in each dimension as described by `some_lower_indices' -- and element count in each dimension as described by `some_element_counts'. require valid_dimension_count: a_dimension_count >= 0 valid_lower_indices: some_lower_indices /= Void and then some_lower_indices.count = a_dimension_count and (a_dimension_count > 0 implies some_lower_indices.lower = 1) valid_element_count: some_element_counts /= Void and then some_element_counts.count = a_dimension_count and (a_dimension_count > 0 implies some_element_counts.lower = 1) and then are_element_counts_valid (some_element_counts) valid_array_size: a.count >= total_count (some_element_counts) do make (a_dimension_count, some_lower_indices, some_element_counts) area := a.area ensure valid_dimension_count: dimension_count >= 0 valid_element_counts: element_counts /= Void and then element_counts.count = dimension_count valid_lower_indices: lower_indices /= Void and then lower_indices.count = dimension_count valid_upper_indices: upper_indices /= Void and then upper_indices.count = dimension_count end feature -- Initialization initialize (v: G) -- Make each entry have value `v' local an_index: ARRAY [INTEGER] i: INTEGER do from i := 1 create an_index.make_filled (0, 1, dimension_count) until i > dimension_count loop an_index.put (lower_indices.item (i), i) i := i + 1 variant dimension_count - i + 1 end from exhausted := False until exhausted loop put (v, an_index) next_index (an_index) end end feature -- Access item (some_indices: ARRAY [INTEGER]): G -- Entry at `some_indices' require valid_indices: are_indices_valid (some_indices) do Result := array_item (flat_index (some_indices)) end feature -- Measurement dimension_count: INTEGER -- Number of dimensions element_counts: ARRAY [INTEGER] -- Element count in each dimension lower_indices: ARRAY [INTEGER] -- Lower indedeces in each dimension upper_indices: ARRAY [INTEGER] -- Upper indices in each dimension feature -- Status report are_element_counts_valid (some_element_counts: ARRAY [INTEGER]): BOOLEAN -- Are `some_element_counts' valid element counts? require non_void_element_counts: some_element_counts /= Void valid_element_counts: some_element_counts.count > 0 implies some_element_counts.lower = 1 local i: INTEGER do Result := True from i := 1 until i > some_element_counts.count or not Result loop Result := some_element_counts.item (i) >= 0 i := i + 1 variant some_element_counts.count - i + 1 end end are_indices_valid (some_indices: ARRAY [INTEGER]): BOOLEAN -- Are `some_indices' valid indices? local i: INTEGER do Result := True if some_indices = Void or else some_indices.count /= dimension_count then Result := False else from i := 1 until i > dimension_count or not Result loop Result := (some_indices.item (i) >= lower_indices.item (i)) and (some_indices.item (i) <= upper_indices.item (i)) i := i + 1 variant dimension_count - i + 1 end end end are_indices_large_enough (some_indices: ARRAY [INTEGER]): BOOLEAN -- Are `some_indices' large enough? local i: INTEGER do Result := True if some_indices = Void or else some_indices.count /= dimension_count then Result := False else from i := 1 until i > dimension_count or not Result loop Result := some_indices.item (i) >= lower_indices.item (i) i := i + 1 variant dimension_count - i + 1 end end end total_count (some_element_counts: ARRAY [INTEGER]): INTEGER -- Total number of elements require valid_counts: are_element_counts_valid (some_element_counts) local i, a_count: INTEGER do Result := 1 from i := 1 a_count := some_element_counts.count until i > a_count loop Result := Result * some_element_counts.item (i) i := i + 1 variant a_count - i + 1 end ensure valid_count: Result >= 0 end are_element_counts_consistent: BOOLEAN -- Are `element_counts' consistent? local i: INTEGER do Result := element_counts.count = dimension_count and are_element_counts_valid (element_counts) from i := 1 until i > dimension_count or not Result loop Result := upper_indices.item (i) - lower_indices.item (i) + 1 = element_counts.item (i) i := i + 1 variant dimension_count - i + 1 end end feature -- Element change put (v: like item; some_indices: ARRAY [INTEGER]) -- Assign item `v' at indices `some_indices'. require valid_indices: are_indices_valid (some_indices) do array_put (v, flat_index (some_indices)) ensure element_inserted: item (some_indices) = v end force (v: like item; some_indices: ARRAY [INTEGER]) -- Assign item `v' at indices `some_indices'. -- Resize if necessary. require valid_indices: are_indices_large_enough (some_indices) do resize (some_indices) put (v, some_indices) ensure element_inserted: item (some_indices) = v end feature -- Removal discard_items -- Remove all elements do dimension_count := 0 upper := 0 element_counts := Void lower_indices := Void upper_indices := Void Precursor end feature -- Resizing resize (n_upper_indices: ARRAY [INTEGER]) -- Rearrange array so that it can accommodate `n_upper_indices' -- without losing any previously entered items -- or changing their indices; -- do nothing if possible. require are_indices_large_enough (n_upper_indices) local i, a_count: INTEGER new_upper_indices, new_element_counts, an_index: ARRAY [INTEGER] new: like Current need_resize: BOOLEAN do from i := 1 a_count := 1 create new_upper_indices.make_filled (0, 1, dimension_count) create new_element_counts.make_filled (0, 1, dimension_count) until i > dimension_count loop if n_upper_indices.item (i) > upper_indices.item (i) then new_upper_indices.put (n_upper_indices.item (i), i) new_element_counts.put (new_upper_indices.item (i) - lower_indices.item (i) + 1, i) need_resize := True else new_upper_indices.put (upper_indices.item (i), i) new_element_counts.put (element_counts.item (i), i) end a_count := a_count * new_element_counts.item (i) i := i + 1 variant dimension_count - i + 1 end if need_resize then create new.make (dimension_count, lower_indices, new_element_counts) from exhausted := False an_index := lower_indices.twin until exhausted loop new.put (item (an_index), an_index) next_index (an_index) end upper_indices := new_upper_indices element_counts := new_element_counts upper := lower + a_count - 1 area := new.area end end feature {NONE} -- Implementation flat_index (some_indices: ARRAY [INTEGER]): INTEGER -- Flattened index require valid_indices: are_indices_valid (some_indices) local i, j, inter_dim: INTEGER do from Result := 0 i := 1 until i = dimension_count + 1 loop from inter_dim := 1 j := i + 1 until j = dimension_count + 1 loop inter_dim := inter_dim * element_counts.item (j) j := j + 1 variant dimension_count - j + 1 end Result := Result + (some_indices.item (i) - lower_indices.item (i)) * inter_dim i := i + 1 variant dimension_count - i + 1 end end next_index (some_indices: ARRAY [INTEGER]) -- Generate next index require valid_indices: are_indices_valid (some_indices) local new_index: BOOLEAN i: INTEGER do from i := dimension_count exhausted := True until i = 0 or new_index loop if some_indices.item (i) < upper_indices.item (i) then some_indices.put (some_indices.item (i) + 1, i) new_index := True exhausted := False else some_indices.put (lower_indices.item (i), i) i := i - 1 end end end exhausted: BOOLEAN -- Is structure exhausted? invariant consistent_upper_indices: upper_indices.count = dimension_count consistent_lower_indices: lower_indices.count = dimension_count consistent_element_counts: are_element_counts_consistent consistent_size: capacity = total_count (element_counts) non_negative_count: count >= 0 note copyright: "Copyright (c) 1984-2017, Eiffel Software and others" license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)" source: "[ Eiffel Software 5949 Hollister Ave., Goleta, CA 93117 USA Telephone 805-685-1006, Fax 805-685-6869 Website http://www.eiffel.com Customer support http://support.eiffel.com ]" end