use context essentials2021

# CMPU 101, Section 53
# 15 February 2023

# Solution


data RumorMill:
  | no-one
  | gossip(name :: String, next1 :: RumorMill, next2 :: RumorMill)
end


#|
fun rumor-mill-template(rm :: RumorMill) -> ...:
  doc: "Template for a function with a RumorMill as input"
  cases (RumorMill) rm:
    | no-one => ...
    | gossip(name, next1, next2) =>
      ... name
      ... rumor-mill-template(next1)
      ... rumor-mill-template(next2)
  end
where:
  rumor-mill-template(...) is ...
end
|#


#| An example rumor mill for everyone to hear that Emma 
   Woodhouse and Mr Knightley are engaged. This could be 
   given as a single definition, but, as in the slides, 
   I've given names to the parts to make it easier to type 
   and to use sub-trees for testing.
|#
   
MRS-COLE-MILL = 
  gossip("Mrs Cole", no-one, no-one)

MRS-ELTON-MILL = 
  gossip("Mrs Elton", no-one, no-one)

MISS-BATES-MILL = 
  gossip("Miss Bates", MRS-COLE-MILL, MRS-ELTON-MILL)

JANE-MILL = 
  gossip("Jane", no-one, no-one)

MR-WESTON-MILL = 
  gossip("Mr Weston", JANE-MILL, MISS-BATES-MILL)

MRS-WESTON-MILL = 
  gossip("Mrs Weston", MR-WESTON-MILL, no-one)

MR-WOODHOUSE-MILL = 
  gossip("Mr Woodhouse", no-one, no-one)

EMMA-MILL = 
  gossip("Emma", MR-WOODHOUSE-MILL, MRS-WESTON-MILL)


fun is-informed(rm :: RumorMill, possible-gossip :: String)
  -> Boolean:
  doc: "Return true if `possible-gossip` is informed about a rumor that starts in `rm`"

  cases (RumorMill) rm:
    | no-one => false
    | gossip(name, next1, next2) =>
      (possible-gossip == name) or
      is-informed(next1, possible-gossip) or
      is-informed(next2, possible-gossip)
  end

where:
  is-informed(no-one, "Emma") is false
  is-informed(MRS-ELTON-MILL, "Emma") is false
  is-informed(EMMA-MILL, "Emma") is true
  is-informed(EMMA-MILL, "Mrs Elton") is true
  is-informed(EMMA-MILL, "Mr Knightley") is false
end


fun gossip-length(rm :: RumorMill) -> Number:
  doc: "Return the length of the longest path the gossip travels"

  cases (RumorMill) rm:
    | no-one => 0
    | gossip(name, next1, next2) =>
      1 +
      num-max(
        gossip-length(next1),
        gossip-length(next2))
  end

where:
  gossip-length(no-one) is 0
  gossip-length(MRS-ELTON-MILL) is 1
  gossip-length(EMMA-MILL) is 5
end


fun add-gossip(rm :: RumorMill, teller :: String, told :: String) -> RumorMill:
  doc: "Return a rumor mill that's like `rm` but with `teller` telling the gossip to `told`. (Assume the teller has an empty slot.)"
  
  cases (RumorMill) rm:
    | no-one => no-one
    | gossip(name, next1, next2) =>
      if name == teller:
        if next1 == no-one:
          gossip(name, 
            gossip(told, no-one, no-one),
            next2)
        else:
          gossip(name,
            next1,
            gossip(told, no-one, no-one))
        end
      else:
        gossip(name, 
          add-gossip(next1, teller, told),
          add-gossip(next2, teller, told))
      end
  end
  
where:
  add-gossip(no-one, "Mrs Elton", "Philip Elton") is no-one
  
  add-gossip(MRS-ELTON-MILL, "Mrs Elton", "Philip Elton") is 
  gossip("Mrs Elton", 
    gossip("Philip Elton", no-one, no-one), 
    no-one)
  
  add-gossip(MISS-BATES-MILL, "Mrs Elton", "Philip Elton") is
  gossip("Miss Bates", 
    MRS-COLE-MILL, 
    gossip("Mrs Elton", 
      gossip("Philip Elton", no-one, no-one), 
      no-one))
end