note description: "[ Lists implemented as sequences of arrays, the last of which may be non-full. No limit on size (a new array is allocated if list outgrows its initial allocation). ]" library: "Free implementation of ELKS library" legal: "See notice at end of class." status: "See notice at end of class." names: list, sequence representation: array, linked access: index, cursor, membership contents: generic date: "$Date$" revision: "$Revision$" class MULTI_ARRAY_LIST [G] inherit DYNAMIC_LIST [G] redefine start, finish, move, has, first, last, prune_all, search, duplicate, wipe_out, put_left end create make feature {NONE} -- Initialization make (b: INTEGER) -- Create an empty list, setting block_size to b do block_size := b first_element := new_cell (create {ARRAYED_LIST [G]}.make (b)) last_element := first_element active := first_element end feature -- Access item: G -- Item at cursor position do Result := active.item.item end first: like item -- Item at first position do Result := first_element.item.first end last: like item -- Item at last position do Result := last_element.item.last end has (v: like item): BOOLEAN -- Does list include `v'? -- (Reference or object equality, -- based on `object_comparison'.) local pos: CURSOR do if not is_empty then pos := cursor start search (v) Result := not after go_to (pos) end end index: INTEGER -- Current cursor index cursor: MULTAR_LIST_CURSOR [G] -- Current cursor position do create Result.make (active, active.item.index, index) end first_element: BI_LINKABLE [ARRAYED_LIST [G]] -- First array_sequence element of the list last_element: BI_LINKABLE [ARRAYED_LIST [G]] -- Last array_sequence element of the list block_size: INTEGER feature -- Measurement count: INTEGER -- Number of items feature -- Status report full: BOOLEAN do Result := False end valid_cursor (p: CURSOR): BOOLEAN -- Can the cursor be moved to position `p'? do if attached {MULTAR_LIST_CURSOR [G]} p as al_c then Result := (al_c /= Void) and then valid_cursor_index (al_c.index) and then al_c.active.item.valid_cursor_index (al_c.active_index) end end feature -- Cursor movement start -- Move cursor to first position. -- (No effect if empty) do active := first_element active.item.start index := 1 end finish -- Move cursor to last position. -- (No effect if empty) do active := last_element active.item.finish index := count end forth -- Move cursor to next position, if any. local current_array: ARRAYED_LIST [G] a: detachable like active do if not is_empty then current_array := active.item current_array.forth if current_array.after and then active /= last_element then a := active.right if a /= Void then active := a end active.item.start end end index := index + 1 end back -- Move cursor to previous position, if any. local current_array: ARRAYED_LIST [G] a: detachable like active do if not is_empty then current_array := active.item current_array.back if current_array.before and then active /= first_element then a := active.left if a /= Void then active := a end active.item.finish end end index := index - 1 end move (i: INTEGER) -- Move cursor `i' positions. The cursor -- may end up `off' if the offset is too big. local counter: INTEGER cell: detachable like active current_array: ARRAYED_LIST [G] do cell := active current_array := cell.item if i > 0 then from counter := i + active.item.index until counter <= current_array.count or cell = Void loop counter := counter - current_array.count cell := cell.right if cell /= Void then current_array := cell.item end end if cell = Void then current_array.finish current_array.forth else active := cell current_array.go_i_th (counter) end elseif i < 0 then from counter := current_array.count - current_array.index - i until counter <= current_array.count or cell = Void loop counter := counter - current_array.count cell := cell.left if cell /= Void then current_array := cell.item end end if counter = current_array.count then counter := 0 if cell /= Void then cell := cell.left if cell /= Void then current_array := cell.item end end end if cell = Void then current_array.go_i_th (0) else active := cell current_array.go_i_th (current_array.count - counter) end end if i /= 0 then if current_array.before then index := 0 elseif current_array.after then index := count + 1 else index := index + i end end end go_to (p: CURSOR) -- Move cursor to position `p' do if attached {MULTAR_LIST_CURSOR [G]} p as al_c then active := al_c.active active.item.go_i_th (al_c.active_index) index := al_c.index end end search (v: like item) -- Move cursor to first position (at or after current -- cursor position) where `item' and `v' are equal. -- (Reference or object equality, -- based on `object_comparison'.) local current_array: ARRAYED_LIST [G] old_index: INTEGER cell: detachable like active do cell := active current_array := cell.item old_index := current_array.index if object_comparison then current_array.compare_objects else current_array.compare_references end current_array.search (v) if current_array.after then cell := cell.right index := index + current_array.count - old_index + 1 else index := index + current_array.index - old_index end from invariant index <= count + 1 until not current_array.after or else cell = Void loop current_array := cell.item if object_comparison then current_array.compare_objects else current_array.compare_references end current_array.start current_array.search (v) if current_array.after then cell := cell.right index := index + current_array.count else index := index + current_array.index - 1 end end if cell /= Void then active := cell else active := last_element end end feature -- Element change replace (v: like item) -- Replace current item by `v'. do active.item.replace (v) end extend (v: like item) -- Add `v' to end. local current_array: ARRAYED_LIST [G] n: like new_cell do current_array := last_element.item if current_array.count = block_size then create current_array.make (block_size) n := new_cell (current_array) last_element.put_right (n) last_element := n end current_array.extend (v) count := count + 1 end put_front (v: like item) -- Add `v' at the beginning. -- Do not move cursor. local first_array: ARRAYED_LIST [G] pos: INTEGER do first_array := first_element.item if active = first_element then pos := first_array.index else pos := -1 end first_array.start -- `count' is updated in `put_left'. put_left (v) if pos > 0 then first_array.go_i_th (pos + 1) elseif pos = 0 then first_array.go_i_th (0) end if not before then index := index + 1 end end put_left (v: like item) -- Add `v' to the left of current position. -- Do not move cursor. local cell: like first_element current_array: ARRAYED_LIST [G] new_array: ARRAYED_LIST [G] pos, cut: INTEGER l: detachable like first_element i, n: like {ARRAYED_LIST [G]}.count do current_array := active_array check is_empty implies after end if after then extend (v) else if active /= first_element then l := active.left end if l /= Void and then not l.item.full then l.item.extend (v) elseif current_array.count <= block_size then current_array.put_left (v) else pos := current_array.index current_array.go_i_th (block_size // 2 + 1) cut := index from i := current_array.index n := if current_array.after then 0 else count.min (current_array.count - i + 1) end create new_array.make (n) until n <= 0 loop new_array.extend (current_array [i]) i := i + 1 n := n - 1 end cell := new_cell (new_array) cell.put_right (active.right) cell.put_left (active) if last_element = active then last_element := cell end if pos < cut then current_array.go_i_th (pos) current_array.put_left (v) elseif pos = cut then current_array.extend (v) active := cell active.item.start else active := cell current_array := cell.item current_array.go_i_th (pos - cut + 1) current_array.put_left (v) end end end index := index + 1 count := count + 1 end put_right (v: like item) -- Add `v' to the left of current position. -- Do not move cursor. do forth put_left (v) back back end feature -- Removal wipe_out -- Remove all items. do count := 0 index := 0 first_element.item.wipe_out first_element.forget_right active := first_element last_element := first_element end remove -- Remove current item local current_array: ARRAYED_LIST [G] new_active: detachable like active e: detachable like first_element do current_array := active.item current_array.remove if current_array.is_empty then if active = first_element then if active /= last_element then e := active.right if e /= Void then first_element := e e.forget_left end active := first_element active.item.start end elseif active = last_element then e := active.left if e /= Void then last_element := e e.forget_right end active := last_element active.item.finish else -- `put_left' modifies `active.right', so we need to remeber it -- as it will become the new value for `active'. new_active := active.right if new_active /= Void then e := active.left if e /= Void then new_active.put_left (e) end active := new_active end active.item.start end elseif current_array.after then if active /= last_element then e := active.right if e /= Void then active := e end active.item.start end end count := count - 1 end remove_left do back remove end remove_right do forth remove back end prune_all (v: like item) local cell: detachable like active new_active: like active array: ARRAYED_LIST [G] do from cell := first_element until cell = Void loop array := cell.item if object_comparison then array.compare_objects else array.compare_references end count := count - array.count array.prune_all (v) count := count + array.count if array.is_empty then if cell = first_element then if cell = last_element then cell := Void else if attached cell.right as e then first_element := e end cell := first_element cell.forget_left end elseif cell = last_element then if attached cell.left as e then last_element := e end last_element.forget_right cell := Void else -- `put_left' modifies `cell.right', so we need to remeber it -- as it will become the new value for `cell'. new_active := cell.right if attached new_active and then attached cell.left as e then new_active.put_left (e) end cell := new_active end else cell := cell.right end end active := last_element index := count + 1 end feature -- Duplication duplicate (n: INTEGER): like Current -- Copy of sub-list beginning at cursor position -- and having min (`n', `count' - `index' + 1) items obsolete "[ Create a new container explicitly using `make_from_iterable` if available. Otherwise, replace a call to the feature with code that creates and initializes container. [2018-11-30] ]" local pos: CURSOR counter: INTEGER do from pos := cursor Result := new_chain until (counter = n) or exhausted loop Result.extend (item) forth counter := counter + 1 end go_to (pos) end feature {MULTI_ARRAY_LIST} -- Implementation new_chain: like Current -- A newly created instance of the same type. -- This feature may be redefined in descendants so as to -- produce an adequately allocated and initialized object. obsolete "Use explicit creation instead. See also explanations for `duplicate`. [2018-11-30]" do create Result.make (block_size) end active_array: ARRAYED_LIST [G] -- Array_sequence at cursor position require active_exists: active /= Void not_off: not off do Result := active.item end active: like first_element -- Element at cursor position feature {NONE} -- Implementation new_cell (a: ARRAYED_LIST [G]): like first_element do create Result.put (a) end invariant writable_definition: writable = not off readable_definition: readable = not off extendible_definition: extendible note copyright: "Copyright (c) 1984-2018, 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