Automatic generation produced by ISE Eiffel

Classes
Clusters
Cluster hierarchy
Chart
Relations
Text
Flat
Contracts
Flat contracts
Go to: 
indexing
	description: "Sets represented as arrayed lists"
	status: "See notice at end of class"
	names: arrayed_set, set, arrayed_list
	representation: array
	size: fixed
	access: membership
	contents: generic
	date: "$Date: 2001/11/16 20:34:21 $"
	revision: "$Revision: 1.1.1.1 $"

class 
	ARRAYED_SET [G]

create 
	make

feature {NONE} -- Initialization

	make (n: INTEGER) is
			-- Allocate list with n items.
			-- (n may be zero for empty list.)
			-- (from ARRAYED_LIST)
		require -- from ARRAYED_LIST
			valid_number_of_items: n >= 0
		do
			index := 0
			count := 0
			array_make (1, n)
		ensure -- from ARRAYED_LIST
			correct_position: before
		end

	array_make (min_index, max_index: INTEGER) is
			-- Allocate array; set index interval to
			-- min_index .. max_index; set all values to default.
			-- (Make array empty if min_index = max_index + 1).
			-- (from ARRAY)
		require -- from ARRAY
			valid_bounds: min_index <= max_index + 1
		do
			lower := min_index
			upper := max_index
			if min_index <= max_index then
				make_area (max_index - min_index + 1)
			else
				make_area (0)
			end
		ensure -- from ARRAY
			lower_set: lower = min_index
			upper_set: upper = max_index
			items_set: all_default
		end

	make_area (n: INTEGER) is
			-- Creates a special object for n entries.
			-- (from TO_SPECIAL)
		require -- from TO_SPECIAL
			non_negative_argument: n >= 0
		do
			create area.make (n)
		ensure -- from TO_SPECIAL
			area_allocated: area /= void and then area.count = n
		end

	make_filled (n: INTEGER) is
			-- Allocate list with n items.
			-- (n may be zero for empty list.)
			-- This list will be full.
			-- (from ARRAYED_LIST)
		require -- from ARRAYED_LIST
			valid_number_of_items: n >= 0
		do
			index := 0
			count := n
			array_make (1, n)
		ensure -- from ARRAYED_LIST
			correct_position: before
			filled: full
		end

	make_from_array (a: ARRAY [G]) is
			-- Create list from array a.
			-- (from ARRAYED_LIST)
		require -- from ARRAY
			array_exists: a /= void
		do
			Precursor  (a)
			lower := 1
			count := a.count
			upper := count
			index := 0
		end
	
feature -- Access

	has (v: G): BOOLEAN is
			-- Does v appear in array?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from ARRAY)
		local
			i: INTEGER
			upper_bound: INTEGER
		do
			upper_bound := upper
			if object_comparison then
				if v = void then
					i := upper_bound + 1
				else
					from
						i := lower
					until
						i > upper_bound or else (i_th (i) /= void and then i_th (i).is_equal (v))
					loop
						i := i + 1
					end
				end
			else
				from
					i := lower
				until
					i > upper_bound or else (i_th (i) = v)
				loop
					i := i + 1
				end
			end
			Result := not (i > upper_bound)
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	index: INTEGER
			-- Index of item, if valid.
			-- (from ARRAYED_LIST)

	item: like first is
			-- Current item
			-- (from ARRAYED_LIST)
		require -- from TRAVERSABLE
			not_off: not off
		require -- from ACTIVE
			readable: readable
		require -- from TRAVERSABLE_SUBSET
			not_off: not off
		require else -- from ARRAYED_LIST
			index_is_valid: valid_index (index)
		do
			Result := area.item (index - 1)
		end
	
feature {NONE} -- Access

	area: SPECIAL [G]
			-- Special data zone
			-- (from TO_SPECIAL)

	cursor: CURSOR is
			-- Current cursor position
			-- (from ARRAYED_LIST)
		do
			create {ARRAYED_LIST_CURSOR} Result.make (index)
		end

	entry (i: INTEGER): G is
			-- Entry at index i, if in index interval
			-- (from ARRAY)
		require -- from ARRAY
			valid_key: array_valid_index (i)
		do
			Result := i_th (i)
		end

	first: G is
			-- Item at first position
			-- (from ARRAYED_LIST)
		require -- from CHAIN
			not_empty: not is_empty
		do
			Result := area.item (0)
		end

	sequential_has (v: like item): BOOLEAN is
			-- Does structure include an occurrence of v?
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		do
			start
			if not off then
				search (v)
			end
			Result := not exhausted
		ensure -- from CONTAINER
			not_found_in_empty: Result implies not is_empty
		end

	sequential_index_of (v: like item; i: INTEGER): INTEGER is
			-- Index of i-th occurrence of v.
			-- 0 if none.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		require -- from LINEAR
			positive_occurrences: i > 0
		local
			occur, pos: INTEGER
		do
			if object_comparison and v /= void then
				from
					start
					pos := 1
				until
					off or (occur = i)
				loop
					if item /= void and then v.is_equal (item) then
						occur := occur + 1
					end
					forth
					pos := pos + 1
				end
			else
				from
					start
					pos := 1
				until
					off or (occur = i)
				loop
					if item = v then
						occur := occur + 1
					end
					forth
					pos := pos + 1
				end
			end
			if occur = i then
				Result := pos - 1
			end
		ensure -- from LINEAR
			non_negative_result: Result >= 0
		end

	index_of (v: like item; i: INTEGER): INTEGER is
			-- Index of i-th occurrence of item identical to v.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- 0 if none.
			-- (from CHAIN)
		require -- from LINEAR
			positive_occurrences: i > 0
		local
			pos: CURSOR
		do
			pos := cursor
			Result := sequential_index_of (v, i)
			go_to (pos)
		ensure -- from LINEAR
			non_negative_result: Result >= 0
		end

	i_th (i: INTEGER): G is
			-- Entry at index i, if in index interval
			-- Was declared in ARRAY as synonym of @.
			-- (from ARRAY)
		require -- from TABLE
			valid_key: array_valid_index (k)
		do
			Result := area.item (i - lower)
		end

	last: like first is
			-- Item at last position
			-- (from ARRAYED_LIST)
		require -- from CHAIN
			not_empty: not is_empty
		do
			Result := area.item (count - 1)
		end

	sequential_occurrences (v: G): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from LINEAR)
		do
			from
				start
				search (v)
			until
				exhausted
			loop
				Result := Result + 1
				forth
				search (v)
			end
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	sequential_search (v: like item) is
			-- Move to first position (at or after current
			-- position) where item and v are equal.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- If no such position ensure that exhausted will be true.
			-- (from LINEAR)
		do
			if object_comparison and v /= void then
				from
				until
					exhausted or else (item /= void and then v.is_equal (item))
				loop
					forth
				end
			else
				from
				until
					exhausted or else v = item
				loop
					forth
				end
			end
		ensure -- from LINEAR
			object_found: (not exhausted and object_comparison) implies equal (v, item)
			item_found: (not exhausted and not object_comparison) implies v = item
		end

	infix "@" (i: INTEGER): G is
			-- Entry at index i, if in index interval
			-- Was declared in ARRAY as synonym of item.
			-- (from ARRAY)
		require -- from TABLE
			valid_key: array_valid_index (k)
		do
			Result := area.item (i - lower)
		end
	
feature -- Measurement

	count: INTEGER
			-- Number of items.
			-- (from ARRAYED_LIST)
	
feature {NONE} -- Measurement

	additional_space: INTEGER is
			-- Proposed number of additional items
			-- (from RESIZABLE)
		do
			Result := (capacity * growth_percentage // 100).max (minimal_increase)
		ensure -- from RESIZABLE
			at_least_one: Result >= 1
		end

	capacity: INTEGER is
			-- Number of available indices
			-- Was declared in ARRAY as synonym of count.
			-- (from ARRAY)
		do
			Result := upper - lower + 1
		ensure then -- from ARRAY
			consistent_with_bounds: Result = upper - lower + 1
		end

	array_count: INTEGER is
			-- Number of available indices
			-- (from ARRAY)
		do
			Result := upper - lower + 1
		ensure then -- from ARRAY
			consistent_with_bounds: Result = upper - lower + 1
		end

	Growth_percentage: INTEGER is 50
			-- Percentage by which structure will grow automatically
			-- (from RESIZABLE)

	array_index_set: INTEGER_INTERVAL is
			-- Range of acceptable indexes
			-- (from ARRAY)
		do
			create Result.make (lower, upper)
		ensure -- from INDEXABLE
			not_void: Result /= void
		ensure then -- from ARRAY
			same_count: Result.count = count
			same_bounds: ((Result.lower = lower) and (Result.upper = upper))
		end

	index_set: INTEGER_INTERVAL is
			-- Range of acceptable indexes
			-- (from CHAIN)
		do
			create Result.make (1, count)
		ensure -- from INDEXABLE
			not_void: Result /= void
		ensure then -- from CHAIN
			count_definition: Result.count = count
		end

	lower: INTEGER
			-- Minimum index
			-- (from ARRAY)

	Minimal_increase: INTEGER is 5
			-- Minimal number of additional items
			-- (from RESIZABLE)

	occurrences (v: like item): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CHAIN)
		local
			pos: CURSOR
		do
			pos := cursor
			Result := sequential_occurrences (v)
			go_to (pos)
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	occurrences (v: like item): INTEGER is
			-- Number of times v appears.
			-- (Reference or object equality,
			-- based on object_comparison.)
			-- (from CHAIN)
		local
			pos: CURSOR
		do
			pos := cursor
			Result := sequential_occurrences (v)
			go_to (pos)
		ensure -- from BAG
			non_negative_occurrences: Result >= 0
		end

	upper: INTEGER
			-- Maximum index
			-- (from ARRAY)
	
feature -- Comparison

	disjoint (other: TRAVERSABLE_SUBSET [G]): BOOLEAN is
			-- Do current set and other have no
			-- items in common?
			-- (from TRAVERSABLE_SUBSET)
		require -- from SUBSET
			set_exists: other /= void
			same_rule: object_comparison = other.object_comparison
		local
			s: SUBSET_STRATEGY [G]
		do
			if not is_empty and not other.is_empty then
				s := subset_strategy (other)
				Result := s.disjoint (Current, other)
			else
				Result := True
			end
		end

	is_equal (other: like Current): BOOLEAN is
			-- Does other contain the same elements?
			-- (from LIST)
		require -- from ANY
			other_not_void: other /= void
		local
			c1, c2: CURSOR
		do
			if Current = other then
				Result := True
			else
				Result := (is_empty = other.is_empty) and (object_comparison = other.object_comparison)
				if Result and not is_empty then
					c1 ?= cursor
					c2 ?= other.cursor
					check
						cursors_exist: c1 /= void and c2 /= void
					end
					from
						start
						other.start
					until
						after or not Result
					loop
						if object_comparison then
							Result := equal (item, other.item)
						else
							Result := (item = other.item)
						end
						forth
						other.forth
					end
					go_to (c1)
					other.go_to (c2)
				elseif is_empty and other.is_empty and object_comparison = other.object_comparison then
					Result := True
				end
			end
		ensure -- from ANY
			symmetric: Result implies other.is_equal (Current)
			consistent: standard_is_equal (other) implies Result
		ensure then -- from LIST
			indices_unchanged: index = old index and other.index = old other.index
			true_implies_same_size: Result implies count = other.count
		end

	is_subset (other: TRAVERSABLE_SUBSET [G]): BOOLEAN is
			-- Is current set a subset of other?
			-- (from TRAVERSABLE_SUBSET)
		require -- from SUBSET
			set_exists: other /= void
			same_rule: object_comparison = other.object_comparison
		do
			if not other.is_empty and then count <= other.count then
				from
					start
				until
					off or else not other.has (item)
				loop
					forth
				end
				if off then
					Result := True
				end
			elseif is_empty then
				Result := True
			end
		end

	is_superset (other: SUBSET [G]): BOOLEAN is
			-- Is current set a superset of other?
			-- (from SUBSET)
		require -- from SUBSET
			set_exists: other /= void
			same_rule: object_comparison = other.object_comparison
		do
			Result := other.is_subset (Current)
		end
	
feature -- Status report

	after: BOOLEAN is
			-- Is there no valid cursor position to the right of cursor?
			-- (from LIST)
		do
			Result := (index = count + 1)
		end

	before: BOOLEAN is
			-- Is there no valid cursor position to the left of cursor?
			-- (from LIST)
		do
			Result := (index = 0)
		end

	empty: BOOLEAN is
		obsolete "ELKS 2000: Use `is_empty' instead"
			-- Is there no element?
			-- (from CONTAINER)
		do
			Result := is_empty
		end

	Extendible: BOOLEAN is True
			-- May new items be added? (Answer: yes.)
			-- (from DYNAMIC_CHAIN)

	is_empty: BOOLEAN is
			-- Is structure empty?
			-- (from FINITE)
		do
			Result := (count = 0)
		end

	is_inserted (v: G): BOOLEAN is
			-- Has v been inserted by the most recent insertion?
			-- (By default, the value returned is equivalent to calling
			-- `has (v)'. However, descendants might be able to provide more
			-- efficient implementations.)
			-- (from COLLECTION)
		do
			Result := has (v)
		end

	islast: BOOLEAN is
			-- Is cursor at last position?
			-- (from CHAIN)
		do
			Result := not is_empty and (index = count)
		ensure -- from CHAIN
			valid_position: Result implies not is_empty
		end

	object_comparison: BOOLEAN
			-- Must search operations use equal rather than =
			-- for comparing references? (Default: no, use =.)
			-- (from CONTAINER)

	off: BOOLEAN is
			-- Is there no current item?
			-- (from CHAIN)
		do
			Result := (index = 0) or (index = count + 1)
		end

	prunable: BOOLEAN is
			-- May items be removed? (Answer: yes.)
			-- (from ARRAYED_LIST)
		do
			Result := True
		end

	valid_index (i: INTEGER): BOOLEAN is
			-- Is i a valid index?
			-- (from ARRAYED_LIST)
		do
			Result := (1 <= i) and (i <= count)
		ensure then -- from INDEXABLE
			only_if_in_index_set: Result implies ((i >= index_set.lower) and (i <= index_set.upper))
		ensure then -- from CHAIN
			valid_index_definition: Result = ((i >= 1) and (i <= count))
		ensure -- from LINEAR_SUBSET
			index_valid: 0 <= n and n <= count + 1
		end

	valid_index (i: INTEGER): BOOLEAN is
			-- Is i a valid index?
			-- (from ARRAYED_LIST)
		do
			Result := (1 <= i) and (i <= count)
		ensure then -- from INDEXABLE
			only_if_in_index_set: Result implies ((i >= index_set.lower) and (i <= index_set.upper))
		ensure then -- from CHAIN
			valid_index_definition: Result = ((i >= 1) and (i <= count))
		ensure -- from LINEAR_SUBSET
			index_valid: 0 <= n and n <= count + 1
		end
	
feature {NONE} -- Status report

	all_cleared: BOOLEAN is
		obsolete "Use `all_default' instead"
			-- Are all items set to default values?
			-- (from ARRAY)
		do
			Result := all_default
		end

	all_default: BOOLEAN is
			-- Are all items set to default values?
			-- (from ARRAY)
		do
			Result := area.all_default (upper - lower)
		ensure -- from ARRAY
			definition: Result = (count = 0 or else ((i_th (upper) = void or else i_th (upper) = i_th (upper).default) and subarray (lower, upper - 1).all_default))
		end

	exhausted: BOOLEAN is
			-- Has structure been completely explored?
			-- (from LINEAR)
		do
			Result := off
		ensure -- from LINEAR
			exhausted_when_off: off implies Result
		end

	full: BOOLEAN is
			-- Is structure filled to capacity?
			-- (from ARRAYED_LIST)
		do
			Result := (count = capacity)
		end

	isfirst: BOOLEAN is
			-- Is cursor at first position?
			-- (from CHAIN)
		do
			Result := not is_empty and (index = 1)
		ensure -- from CHAIN
			valid_position: Result implies not is_empty
		end

	readable: BOOLEAN is
			-- Is there a current item that may be read?
			-- (from SEQUENCE)
		do
			Result := not off
		end

	resizable: BOOLEAN is
			-- May capacity be changed? (Answer: yes.)
			-- (from RESIZABLE)
		do
			Result := True
		end

	same_items (other: like Current): BOOLEAN is
			-- Do other and Current have same items?
			-- (from ARRAY)
		require -- from ARRAY