Data structures

Singly linked list

function empty_error(id)
   return table ValueError{
      value = "Value error in a.{}: a is empty."%[id]}
end

function link(a)
   y = table LinkedList{pfirst=null, plast=null}
   for x in a
      y.push(x)
   end
   return y
end

LinkedList = table(Type,"LinkedList",Iterable){
   function string()
      self.map(str).join(", ","link([","])")
   end,

   function empty()
      return self.pfirst is null
   end,

   function iter()
      t = self.pfirst
      return fn*||
         while not t is null
            yield t[0]
            t = t[1]
         end
      end
   end,

   function push(x)
      if self.pfirst is null
         self.plast = [x,null]
         self.pfirst = self.plast
      else
         self.plast[1] = [x,null]
         self.plast = self.plast[1]
      end
   end,
  
   function unshift(x)
      if self.pfirst is null
         self.plast = [x,null]
         self.pfirst = self.plast
      else
         self.pfirst = [x,self.pfirst]
      end
   end,

   function shift()
      if self.pfirst is null
         raise empty_error("shift()")
      else
         value = self.pfirst[0]
         self.pfirst = self.pfirst[1]
         return value
      end
   end,
  
   function first()
      if self.pfirst is null
         raise empty_error("first()")
      else
         return self.pfirst[0]
      end
   end,

   function rest()
      if self.pfirst is null
         raise empty_error("rest()")
      else
         return table LinkedList{
            pfirst = self.pfirst[1],
            plast = self.plast
         }
      end
   end
}