Advertisement
DanielDv99

SET_INT

Sep 25th, 2017
1,082
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. note
  2.     description: "{SET_INT} implements a set of integers"
  3.  
  4. class
  5.     SET_INT
  6. inherit
  7.     ANY
  8.     redefine
  9.         out
  10.     end
  11. create
  12.     empty_set, singleton
  13.  
  14. feature {NONE} -- Initialization
  15.     empty_set
  16.         do
  17.             create elements.make
  18.             elements.start
  19.         end
  20.     singleton (element : INTEGER)
  21.         do
  22.             empty_set
  23.             elements.force (element)
  24.         end
  25.  
  26. feature -- Queries
  27.  
  28.     is_empty: BOOLEAN
  29.             -- Is the current set empty?
  30.         do
  31.             Result := elements.is_empty
  32.         ensure
  33.             result_correct : Result implies elements.count = 0
  34.         end
  35.  
  36.     has (v: INTEGER): BOOLEAN
  37.             -- Does the Current set have 'v'?
  38.         local
  39.             i : INTEGER
  40.         do
  41.             from
  42.                 i := 1
  43.             until
  44.                 i > elements.count
  45.             loop
  46.                 if v ~ elements @ i then
  47.                     Result := True
  48.                 end
  49.                 i := i + 1
  50.             variant
  51.                 elements.count - i + 1
  52.             end
  53.         ensure
  54.             Result = (across 1 |..| card as ith some elements [ith.item] = v end)
  55.         end
  56.  
  57.     card: INTEGER
  58.             -- What is the cardinality of the Current set?
  59.         do
  60.             Result := elements.count
  61.         ensure
  62.             result_correct: Result = elements.count
  63.         end
  64.  
  65.     is_subset (other: SET_INT): BOOLEAN
  66.             -- Is the Current set a subset of 'other'?
  67.         do
  68.             Result := True
  69.             from
  70.                 elements.start
  71.             until
  72.                 elements.exhausted
  73.             loop
  74.                 if not other.has (elements.item) then
  75.                     Result := False
  76.                 end
  77.                 elements.forth
  78.             end
  79.         ensure
  80.             result_correct : elements.count = 0 or across other.elements as element all other.has (element.item) end
  81.         end
  82.  
  83.     is_not_subset (other: SET_INT): BOOLEAN
  84.             -- Is the Current set not a subset of 'other'?
  85.         local
  86.             i : INTEGER
  87.         do
  88.             Result := False
  89.             from
  90.                 elements.start
  91.             until
  92.                 elements.exhausted
  93.             loop
  94.                 if not other.has (elements.item) then
  95.                     Result := True
  96.                 end
  97.                 elements.forth
  98.             variant
  99.                 elements.count - elements.index
  100.             end
  101.  
  102.         ensure
  103.             result_correct: across elements as element some not other.has (element.item) end
  104.         end
  105.  
  106.     is_strict_subset (other: SET_INT): BOOLEAN
  107.             -- Is the Current set a strict subset of 'other'?
  108.         do
  109.             Result := Current.is_subset (other) and not other.is_subset (Current)
  110.         ensure
  111.             result_correct: across other.elements as element some not Current.has (element.item) end
  112.         end
  113.  
  114.     is_not_strict_subset (other: SET_INT): BOOLEAN
  115.             -- Is the Current set not a strict subset of 'other'?
  116.         do
  117.             Result := Current.is_subset (other)
  118.         ensure
  119.             result_correct: across elements as element all other.has (element.item) end
  120.         end
  121.  
  122.     min: INTEGER
  123.             -- gives the smallest number in the current set
  124.         require
  125.             at_least_one_element: not is_empty
  126.         do
  127.             from
  128.                 elements.start
  129.                 Result := elements.item
  130.                 elements.forth
  131.             until
  132.                 elements.exhausted
  133.             loop
  134.                 if elements.item <  Result then
  135.                     Result := elements.item
  136.                 end
  137.             end
  138.  
  139.         ensure
  140.             result_correct: across elements as element all element.item >= Result end
  141.         end
  142.  
  143.     max: INTEGER
  144.             -- gives the largest number in the current set
  145.         require
  146.             at_least_one_element: not is_empty
  147.         do
  148.             from
  149.                 elements.start
  150.                 Result := elements.item
  151.                 elements.forth
  152.             until
  153.                 elements.exhausted
  154.             loop
  155.                 if elements.item > Result then
  156.                         Result := elements.item
  157.                 end
  158.         end
  159.         ensure
  160.             result_correct: across elements as element all element.item <= Result end
  161.         end
  162.  
  163.     equal_set (other: SET_INT): BOOLEAN
  164.             -- Is Current set equal to other?
  165.         do
  166.             Result := Current.is_subset (other) and other.is_subset (current)
  167.         ensure
  168.             equal_sets: Result = is_subset (other) and then other.is_subset (Current)
  169.         end
  170.  
  171.  
  172. feature -- Modification
  173.  
  174.     add (v: INTEGER)
  175.             -- adds an element to the set
  176.         do
  177.             if not Current.has (v) then
  178.                 elements.force (v)
  179.             end
  180.         ensure
  181.             element_in_set: has (v)
  182.         end
  183.  
  184. feature -- Operations (no side effect)
  185.     union (other: SET_INT): SET_INT
  186.             -- gives the union of the elements of other and Current
  187.         do
  188.             create Result.empty_set
  189.             Result.elements.copy (elements)
  190.             from
  191.                 other.elements.start
  192.             until
  193.                 other.elements.exhausted
  194.             loop
  195.                 if not Result.has (other.elements.item) then
  196.                     Result.add (other.elements.item)
  197.                 end
  198.                 other.elements.forth
  199.             end
  200.         ensure
  201.             union_correct: Current.is_subset (Result) and other.is_subset (Result)
  202.         end
  203.  
  204.     intersection (other: SET_INT): SET_INT
  205.             -- gives the intersection of the elements of other and Current
  206.         do
  207.             create Result.empty_set
  208.             from
  209.                 elements.start
  210.             until
  211.                 elements.exhausted
  212.             loop
  213.                 if other.has (elements.item) then
  214.                     Result.add (elements.item)
  215.                 end
  216.                 elements.forth
  217.             end
  218.         ensure
  219.             result_correct: across Result.elements as element all Current.has (element.item) and other.has (element.item) end
  220.         end
  221.  
  222.     difference alias "-"(other: SET_INT): SET_INT
  223.             -- gives the difference of the elements of Current and other
  224.         do
  225.             create Result.empty_set
  226.             from
  227.                 elements.start
  228.             until
  229.                 elements.exhausted
  230.             loop
  231.                 if not other.has (elements.item) then
  232.                     Result.add (elements.item)
  233.                 end
  234.                 elements.forth
  235.             end
  236.         ensure
  237.             result_correct: across elements as element all not other.has (element.item) implies Result.has (element.item) end
  238.         end
  239.  
  240.     out: STRING
  241.             -- Returns a printable set
  242.         local
  243.             index: INTEGER
  244.         do
  245.             Result := ""
  246.             Result := Result +  ("{")
  247.             from
  248.                 index := 1
  249.             until
  250.                 index > card
  251.             loop
  252.                 Result := Result + elements [index].out
  253.                 if index < card then
  254.                     Result := Result + ", "
  255.                 end
  256.                 index := index + 1
  257.             end
  258.             Result := Result + "}"
  259.         end
  260.  
  261. feature -- Access
  262.  
  263.     elements: LINKED_LIST [INTEGER]
  264.             -- `elements' contains the elements of the set
  265.  
  266.  
  267. invariant
  268.     no_repeated_elements: across 1 |..| card as ith all elements.occurrences (elements [ith.item]) = 1 end
  269. end
Advertisement
RAW Paste Data Copied
Advertisement