#	COLLATE
#
#	Collate and decollate strings
#
#	Ralph E. Griswold
#
#	Last modified 4/27/83
#

#  collate s1 and s2
#
procedure collate(s1,s2)
   local length, ltemp, rtemp
   static llabels, rlabels, clabels, blabels, half
   initial {
      llabels := "ab"
      rlabels := "cd"
      blabels := llabels || rlabels
      clabels := "acbd"
      half := 2
      ltemp := left(&cset,*&cset / 2)
      rtemp := right(&cset,*&cset / 2)
      clabels := collate(ltemp,rtemp)
      llabels := ltemp
      rlabels := rtemp
      blabels := string(&cset)
      half := *llabels
      }
   length := *s1
   if length <= half then
      return map(left(clabels,2 * length),left(llabels,length) ||
         left(rlabels,length),s1 || s2)
   else return map(clabels,blabels,left(s1,half) || left(s2,half)) ||
      collate(right(s1,length - half),right(s2,length - half))
end

#  decollate s according to even or odd i
#
procedure decollate(s,i)
   static dsize, image, object
   local ssize
   initial {
      image := collate(left(&cset,*&cset / 2),left(&cset,*&cset / 2))
      object := left(&cset,*&cset / 2)
      dsize := *image
      }
   i %:= 2
   ssize := *s
   if ssize + i <= dsize then
      return map(object[1+:(ssize + i) / 2],image[(i + 1)+:ssize],s)
   else return map(object[1+:(dsize - 2) / 2],image[(i + 1)+:dsize - 2],
      s[1+:(dsize - 2)]) || decollate(s[dsize - 1:0],i)
end