msci Code

;the definitive IDL linked list object 

pro list_element__define
  struct={list_element, next:ptr_new(), data:ptr_new()}
end

pro linked_list__define
  struct={linked_list, $
  			head_ptr:ptr_new(), $
  			tail_ptr:ptr_new(), $
  			current_ptr:ptr_new(), $
  			current_el:0L, $
  			n:0L }
  			
end

function linked_list::init, data
  self.head_ptr=ptr_new({list_element})
  self.tail_ptr=self.head_ptr
  self.current_ptr=self.head_ptr
  for i=0L, n_elements(data)-1 do begin
    n=self->add(data[i])
;    print, n
  endfor
  return, 1
end

pro linked_list::cleanup
  self->reset
  for i=0L, self.n-2 do begin
    junk=self->delete_next()
  endfor
  ptr_free, (*self.head_ptr).data
  ptr_free, self.head_ptr
  ptr_free, self.tail_ptr
;  stop
end  

;adds an element to the end of the list:
function linked_list::add, data
;  for i=0, n_elements(data)-1 do begin
    (*self.tail_ptr).data=ptr_new(data)
    if not ptr_valid((*self.tail_ptr).data) then return, -1
    (*self.tail_ptr).next=ptr_new({list_element})
    if not ptr_valid((*self.tail_ptr).next) then return, -1
    self.current_ptr=self.tail_ptr
    self.current_el=self.n
    self.tail_ptr=(*self.tail_ptr).next
    self.n=self.n+1
;  endfor
  return, self.n-1
end

;gets the nth element, where n is a zero-based index
;starts from the current element, if the requested element is
;equal to or greater
function linked_list::get, n
  if n lt 0 or n ge self.n then return, ptr_new()
  if n ge self.current_el then begin
    offset=self.current_el
  endif else begin
    self.current_ptr=self.head_ptr
    offset=0
  endelse
  for i=offset, n-1 do begin
    self.current_ptr=(*self.current_ptr).next
  endfor
  self.current_el=n
  return, (*(*self.current_ptr).data)
end

;deletes the nth element, where n is a zero-based index
;returns the deleted element
;if there is an error, returns a null pointer
pro linked_list::delete, n, deleted
  nn=n_elements(n)

;  for i=0, nn-1 do begin
    if n lt 0 or n ge self.n then return
    if self.n eq 0 then return
    if n eq 0 then begin
      self.current_ptr=self.head_ptr
      deleted=(*(*self.current_ptr).data)
      self.head_ptr=(*self.head_ptr).next
      ptr_free, (*self.current_ptr).data
      ptr_free, self.current_ptr
      self.current_ptr=self.head_ptr
      self.n=self.n-1
    endif else begin
      if n gt self.current_el then begin
        offset=self.current_el
      endif else begin
        self.current_ptr=self.head_ptr
        offset=0
      endelse
      for i=offset, n-2 do begin
        self.current_ptr=(*self.current_ptr).next
      endfor
      previous_ptr=self.current_ptr
      self.current_ptr=(*self.current_ptr).next
      self.current_el=n
      deleted=(*(*self.current_ptr).data)
      (*previous_ptr).next=(*self.current_ptr).next
      ptr_free, (*self.current_ptr).data
      ptr_free, self.current_ptr
      self.current_ptr=(*previous_ptr).next
      self.n=self.n-1
    endelse
;  endfor
  
end

;steps the current pointer n forward in the list:
function linked_list::step, n
  if n_elements(n) eq 0 then n=1
  n=min([n, self.n-self.current_el-1])
  for i=1, n do begin
      self.current_ptr=(*self.current_ptr).next
      self.current_el=self.current_el+1
  endfor
  return, self.current_el
end

function linked_list::get_current

  return, (*self.current_ptr.data)
end

pro linked_list::reset
  self.current_ptr=self.head_ptr
  self.current_el=0
end

;deletes the element one forward from the current:
function linked_list::delete_next
  if self.current_el ge self.n-1 then return, ptr_new()
  hold=(*self.current_ptr).next
  deleted=(*(*hold).data)
  (*self.current_ptr).next=(*(*self.current_ptr).next).next
  ptr_free, (*hold).data
  ptr_free, hold
  self.n=self.n-1
  
  return, deleted
end

;inserts data after the nth element
pro linked_list::insert, data, n
  if n lt 0 then return
  if n ge self.n then begin
    (*self.tail_ptr).next=ptr_new({list_element})
    (*self.tail_ptr).data=ptr_new(ptr_new())
    for i=self.n, n-1 do begin
      ;use null pointer for missing data element:
      self.tail_ptr=(*self.tail_ptr).next
      (*self.tail_ptr).data=ptr_new(ptr_new())
      (*self.tail_ptr).next=ptr_new({list_element})
    endfor
    self.current_ptr=self.tail_ptr
    self.tail_ptr=(*self.tail_ptr).next
    self.n=n+1
    self.current_el=n
  endif else begin
    if n ge self.current_el then begin
      offset=self.current_el
    endif else begin
      self.current_ptr=self.head_ptr
      offset=0
    endelse
    for i=offset, n-1 do begin
      self.current_ptr=(*self.current_ptr).next
    endfor
    self.current_el=n
  endelse
  splice=(*self.current_ptr).next
  (*self.current_ptr).next=ptr_new({list_element})
  (*(*self.current_ptr).next).next=splice
  (*(*self.current_ptr).next).data=ptr_new(data)
  self.n=self.n+1
  
end

;returns the linked list converted to an array
;note: assumes all the elements are of the same type
pro linked_list::decompose, data
  if self.n le 0 then return
  data=replicate((*(*self.head_ptr).data), self.n)
  current_ptr=self.head_ptr
  for i=0, self.n-1 do begin
    data[i]=(*(*current_ptr).data)
    current_ptr=(*current_ptr).next
  endfor

end

function linked_list::sizeof
  return, self.n
end
  
pro linked_list::print
  self->reset
  for i=0, self.n-1 do begin
    print, (*(*self.current_ptr).data)
    n=self->step()
  endfor
end