axiom-source 20170501-3 / usr / share / axiom-20170501 / src / algebra / URAGG.spad

)abbrev category URAGG UnaryRecursiveAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
++ Date Created: August 87 through August 88
++ Date Last Updated: April 1991
++ Description:
++ A unary-recursive aggregate is a one where nodes may have either
++ 0 or 1 children.
++ This aggregate models, though not precisely, a linked
++ list possibly with a single cycle.
++ A node with one children models a non-empty list, with the
++ \spadfun{value} of the list designating the head, or \spadfun{first}, 
++ of the list, and the child designating the tail, or \spadfun{rest}, 
++ of the list. A node with no child then designates the empty list.
++ Since these aggregates are recursive aggregates, they may be cyclic.

UnaryRecursiveAggregate(S) : Category == SIG where
  S : Type

  SIG ==> RecursiveAggregate S with

    concat : (%,%) -> %
      ++ concat(u,v) returns an aggregate w consisting of the elements of u
      ++ followed by the elements of v.
      ++ Note that \axiom{v = rest(w,#a)}.
      ++
      ++X t1:=[1,2,3]
      ++X t2:=concat(t1,t1)
      ++X t1
      ++X t2
 
    concat : (S,%) -> %
      ++ concat(x,u) returns aggregate consisting of x followed by
      ++ the elements of u.
      ++ Note that if \axiom{v = concat(x,u)} then \axiom{x = first v}
      ++ and \axiom{u = rest v}.
      ++
      ++X t1:=[1,2,3]
      ++X t2:=concat(4,t1)
      ++X t1
      ++X t2
 
    first : % -> S
      ++ first(u) returns the first element of u
      ++ (equivalently, the value at the current node).
      ++
      ++X first [1,4,2,-6,0,3,5,4,2,3]
 
    elt : (%,"first") -> S
      ++ elt(u,"first") (also written: \axiom{u . first}) 
      ++ is equivalent to first u.
      ++
      ++X t1:=[1,2,3]
      ++X t1.first
 
    first : (%,NonNegativeInteger) -> %
      ++ first(u,n) returns a copy of the first n (\axiom{n >= 0}) 
      ++ elements of u.
      ++
      ++ first([1,4,2,-6,0,3,5,4,2,3],3)
 
    rest : % -> %
      ++ rest(u) returns an aggregate consisting of all but the first
      ++ element of u
      ++ (equivalently, the next node of u).
      ++
      ++X rest [1,4,2,-6,0,3,5,4,2,3]
 
    elt : (%,"rest") -> %
      ++ elt(%,"rest") (also written: \axiom{u.rest}) is
      ++ equivalent to \axiom{rest u}.
      ++
      ++X t1:=[1,2,3]
      ++X t1.rest
 
    rest : (%,NonNegativeInteger) -> %
      ++ rest(u,n) returns the \axiom{n}th (n >= 0) node of u.
      ++ Note that \axiom{rest(u,0) = u}.
      ++
      ++X rest([1,4,2,-6,0,3,5,4,2,3],3)
 
    last : % -> S
      ++ last(u) resturn the last element of u.
      ++ Note that for lists, \axiom{last(u)=u . (maxIndex u)=u . (# u - 1)}.
      ++
      ++X last [1,4,2,-6,0,3,5,4,2,3]
 
    elt : (%,"last") -> S
      ++ elt(u,"last") (also written: \axiom{u . last}) is equivalent 
      ++ to last u.
      ++
      ++X t1:=[1,2,3]
      ++X t1.last
 
    last : (%,NonNegativeInteger) -> %
      ++ last(u,n) returns a copy of the last n (\axiom{n >= 0}) nodes of u.
      ++ Note that \axiom{last(u,n)} is a list of n elements.
      ++
      ++X last([1,4,2,-6,0,3,5,4,2,3],3)
 
    tail : % -> %
      ++ tail(u) returns the last node of u.
      ++ Note that if u is \axiom{shallowlyMutable},
      ++ \axiom{setrest(tail(u),v) = concat(u,v)}.
      ++
      ++X tail [1,4,2,-6,0,3,5,4,2,3]
 
    second : % -> S
      ++ second(u) returns the second element of u.
      ++ Note that \axiom{second(u) = first(rest(u))}.
      ++
      ++X second [1,4,2,-6,0,3,5,4,2,3]
 
    third : % -> S
      ++ third(u) returns the third element of u.
      ++ Note that \axiom{third(u) = first(rest(rest(u)))}.
      ++
      ++X third [1,4,2,-6,0,3,5,4,2,3]
 
    cycleEntry : % -> %
      ++ cycleEntry(u) returns the head of a top-level cycle contained in
      ++ aggregate u, or \axiom{empty()} if none exists.
      ++
      ++X t1:=[1,2,3]
      ++X t2:=concat!(t1,t1)
      ++X cycleEntry t2
 
    cycleLength : % -> NonNegativeInteger
      ++ cycleLength(u) returns the length of a top-level cycle
      ++ contained  in aggregate u, or 0 is u has no such cycle.
      ++
      ++X t1:=[1,2,3]
      ++X t2:=concat!(t1,t1)
      ++X cycleLength t2
 
    cycleTail : % -> %
      ++ cycleTail(u) returns the last node in the cycle, or
      ++ empty if none exists.
      ++
      ++X t1:=[1,2,3]
      ++X t2:=concat!(t1,t1)
      ++X cycleTail t2
 
    if % has shallowlyMutable then
 
      concat_! : (%,%) -> %
        ++ concat!(u,v) destructively concatenates v to the end of u.
        ++ Note that \axiom{concat!(u,v) = setlast_!(u,v)}.
        ++
        ++X t1:=[1,2,3]
        ++X t2:=[4,5,6]
        ++X concat!(t1,t2)
        ++X t1
        ++X t2
 
      concat_! : (%,S) -> %
        ++ concat!(u,x) destructively adds element x to the end of u.
        ++ Note that \axiom{concat!(a,x) = setlast!(a,[x])}.
        ++
        ++X t1:=[1,2,3]
        ++X concat!(t1,7)
        ++X t1
 
      cycleSplit_! : % -> %
        ++ cycleSplit!(u) splits the aggregate by dropping off the cycle.
        ++ The value returned is the cycle entry, or nil if none exists.
        ++ For example, if \axiom{w = concat(u,v)} is the cyclic list where 
        ++ v is the head of the cycle, \axiom{cycleSplit!(w)} will drop v 
        ++ off w thus destructively changing w to u, and returning v.
        ++
        ++X t1:=[1,2,3]
        ++X t2:=concat!(t1,t1)
        ++X t3:=[1,2,3]
        ++X t4:=concat!(t3,t2)
        ++X t5:=cycleSplit!(t4)
        ++X t4
        ++X t5
 
      setfirst_! : (%,S) -> S
        ++ setfirst!(u,x) destructively changes the first element of a to x.
        ++
        ++X t1:=[1,2,3]
        ++X setfirst!(t1,7)
        ++X t1
 
      setelt : (%,"first",S) -> S
        ++ setelt(u,"first",x) (also written: \axiom{u.first := x}) is
        ++ equivalent to \axiom{setfirst!(u,x)}.
        ++
        ++X t1:=[1,2,3]
        ++X t1.first:=7
        ++X t1
 
      setrest_! : (%,%) -> %
        ++ setrest!(u,v) destructively changes the rest of u to v.
        ++
        ++X t1:=[1,2,3]
        ++X setrest!(t1,[4,5,6])
        ++X t1
 
      setelt : (%,"rest",%) -> %
        ++ setelt(u,"rest",v) (also written: \axiom{u.rest := v}) is 
        ++ equivalent to \axiom{setrest!(u,v)}.
        ++
        ++X t1:=[1,2,3]
        ++X t1.rest:=[4,5,6]
        ++X t1
 
      setlast_! : (%,S) -> S
        ++ setlast!(u,x) destructively changes the last element of u to x.
        ++
        ++X t1:=[1,4,2,-6,0,3,5,4,2,3]
        ++X setlast!(t1,7)
        ++X t1
 
      setelt : (%,"last",S) -> S
       ++ setelt(u,"last",x) (also written: \axiom{u.last := b})
       ++ is equivalent to \axiom{setlast!(u,v)}.
       ++
       ++X t1:=[1,4,2,-6,0,3,5,4,2,3]
       ++X t1.last := 7
       ++X t1
 
      split_! : (%,Integer) -> %
        ++ split!(u,n) splits u into two aggregates: \axiom{v = rest(u,n)}
        ++ and \axiom{w = first(u,n)}, returning \axiom{v}.
        ++ Note that afterwards \axiom{rest(u,n)} returns \axiom{empty()}.
        ++
        ++X t1:=[1,4,2,-6,0,3,5,4,2,3]
        ++X t2:=split!(t1,4)
        ++X t1
        ++X t2

   add

     cycleMax ==> 1000
   
     findCycle: % -> %
   
     elt(x, "first") == first x
 
     elt(x,  "last") == last x
 
     elt(x,  "rest") == rest x
 
     second x == first rest x
 
     third x == first rest rest x
 
     cyclic? x == not empty? x and not empty? findCycle x
 
     last x == first tail x
   
     nodes x ==
       l := empty()$List(%)
       while not empty? x repeat
         l := concat(x, l)
         x := rest x
       reverse_! l
   
     children x ==
       l := empty()$List(%)
       empty? x => l
       concat(rest x,l)
   
     leaf? x == empty? x
   
     value x ==
       empty? x => error "value of empty object"
       first x
   
     less?(l, n) ==
       i := n::Integer
       while i > 0 and not empty? l repeat (l := rest l; i := i - 1)
       i > 0
   
     more?(l, n) ==
       i := n::Integer
       while i > 0 and not empty? l repeat (l := rest l; i := i - 1)
       zero?(i) and not empty? l
   
     size?(l, n) ==
       i := n::Integer
       while not empty? l and i > 0 repeat (l := rest l; i := i - 1)
       empty? l and zero? i
   
     #x ==
       for k in 0.. while not empty? x repeat
         k = cycleMax and cyclic? x => error "cyclic list"
         x := rest x
       k
   
     tail x ==
       empty? x => error "empty list"
       y := rest x
       for k in 0.. while not empty? y repeat
         k = cycleMax and cyclic? x => error "cyclic list"
         y := rest(x := y)
       x
   
     findCycle x ==
       y := rest x
       while not empty? y repeat
         if eq?(x, y) then return x
         x := rest x
         y := rest y
         if empty? y then return y
         if eq?(x, y) then return y
         y := rest y
       y
   
     cycleTail x ==
       empty?(y := x := cycleEntry x) => x
       z := rest x
       while not eq?(x,z) repeat (y := z; z := rest z)
       y
   
     cycleEntry x ==
       empty? x => x
       empty?(y := findCycle x) => y
       z := rest y
       for l in 1.. while not eq?(y,z) repeat z := rest z
       y := x
       for k in 1..l repeat y := rest y
       while not eq?(x,y) repeat (x := rest x; y := rest y)
       x
   
     cycleLength x ==
       empty? x => 0
       empty?(x := findCycle x) => 0
       y := rest x
       for k in 1.. while not eq?(x,y) repeat y := rest y
       k
   
     rest(x, n) ==
       for i in 1..n repeat
         empty? x => error "Index out of range"
         x := rest x
       x
   
     if % has finiteAggregate then
 
       last(x, n) ==
         n > (m := #x) => error "index out of range"
         copy rest(x, (m - n)::NonNegativeInteger)
   
     if S has SetCategory then
 
       x = y ==
         eq?(x, y) => true
         for k in 0.. while not empty? x and not empty? y repeat
           k = cycleMax and cyclic? x => error "cyclic list"
           first x ^= first y => return false
           x := rest x
           y := rest y
         empty? x and empty? y
   
       node?(u, v) ==
         for k in 0.. while not empty? v repeat
           u = v => return true
           k = cycleMax and cyclic? v => error "cyclic list"
           v := rest v
         u=v
   
     if % has shallowlyMutable then
 
       setelt(x, "first", a) == setfirst_!(x, a)
 
       setelt(x,  "last", a) == setlast_!(x, a)
 
       setelt(x,  "rest", a) == setrest_!(x, a)
 
       concat(x:%, y:%) == concat_!(copy x, y)
   
       setlast_!(x, s) ==
         empty? x => error "setlast: empty list"
         setfirst_!(tail x, s)
         s
   
       setchildren_!(u,lv) ==
         #lv=1 => setrest_!(u, first lv)
         error "wrong number of children specified"
   
       setvalue_!(u,s) == setfirst_!(u,s)
   
       split_!(p, n) ==
         n < 1 => error "index out of range"
         p := rest(p, (n - 1)::NonNegativeInteger)
         q := rest p
         setrest_!(p, empty())
         q
   
       cycleSplit_! x ==
         empty?(y := cycleEntry x) or eq?(x, y) => y
         z := rest x
         while not eq?(z, y) repeat (x := z; z := rest z)
         setrest_!(x, empty())
         y