MODULE Key_Types
      USE Precision
      IMPLICIT NONE
      PRIVATE
      
      
      INTEGER(KIND=i_wp),PARAMETER,PUBLIC::huge_Key_i_wp=HUGE(huge_Key_i_wp)
      
      PUBLIC::Key_i_wp
      TYPE Key_i_wp
      INTEGER(KIND=i_wp)::my_value
      ENDTYPE
      
      PUBLIC::Data_Key_i_wp
      TYPE Data_Key_i_wp
      TYPE(Key_i_wp)::my_key
      
      ENDTYPE
      
      INTEGER(KIND=i_wp),PARAMETER,PUBLIC::huge_Key_i_wp_r_wp=HUGE(huge_Key_i_wp_r_wp)
      
      PUBLIC::Key_i_wp_r_wp
      TYPE Key_i_wp_r_wp
      INTEGER(KIND=i_wp)::my_value
      ENDTYPE
      
      PUBLIC::Data_Key_i_wp_r_wp
      TYPE Data_Key_i_wp_r_wp
      TYPE(Key_i_wp_r_wp)::my_key
      
      REAL(KIND=r_wp)::my_cost
      ENDTYPE
      
      END MODULE Key_Types
      
      
      
      MODULE Skip_Lists
      USE Precision
      USE Error_Handling
      USE System_Monitors
      USE Random_Numbers
      USE Key_Types
      IMPLICIT NONE
      PUBLIC::InitializeSkipList,DestroySkipList,&
      SearchInSkipList,InsertInSkipList,DeleteFromSkipList,&
      PrintSkipList
      PRIVATE
      
      
      
      PUBLIC::Node_Key_i_wp
      TYPE Node_Key_i_wp
      PRIVATE
      TYPE(Data_Key_i_wp)::my_data
      INTEGER(KIND=i_byte)::my_max_level=1,my_page=1
      INTEGER(KIND=i_wp)::my_next=0
      ENDTYPE
      
      PUBLIC::NodePointer_Key_i_wp
      TYPE NodePointer_Key_i_wp
      PRIVATE
      TYPE(Node_Key_i_wp),POINTER::my_node=>NULL()
      ENDTYPE
      
      TYPE BlockOfNodes_Key_i_wp
      TYPE(Node_Key_i_wp),DIMENSION(:),POINTER::my_nodes=>NULL()
      TYPE(NodePointer_Key_i_wp),DIMENSION(:),POINTER::my_pointers=>NULL()
      INTEGER(KIND=i_wp)::my_n_nodes=0
      ENDTYPE
      
      PUBLIC::PageOfNodes_Key_i_wp
      TYPE PageOfNodes_Key_i_wp
      PRIVATE
      TYPE(BlockOfNodes_Key_i_wp)::my_block
      TYPE(NodePointer_Key_i_wp)::my_free_node
      INTEGER(KIND=i_byte)::my_next=0
      ENDTYPE
      
      PUBLIC::MemoryMapOfNodes_Key_i_wp
      TYPE MemoryMapOfNodes_Key_i_wp
      TYPE(PageOfNodes_Key_i_wp),DIMENSION(:),POINTER::my_pages=>NULL()
      REAL(KIND=r_sp)::my_p=0.25_r_sp,my_log_p=-1.386294_r_sp
      INTEGER(KIND=i_wp)::my_page_size=100
      INTEGER(KIND=i_byte)::my_n_lists=0,my_max_lists=10
      INTEGER(KIND=i_byte)::my_max_pages=10,my_n_pages=0
      INTEGER(KIND=i_byte)::my_free_page=0
      ENDTYPE
      
      PUBLIC::SkipList_Key_i_wp
      TYPE SkipList_Key_i_wp
      TYPE(Node_Key_i_wp),POINTER::my_head=>NULL(),my_tail=>NULL()
      TYPE(NodePointer_Key_i_wp),DIMENSION(:),POINTER::my_search_finger=>NULL()
      TYPE(MemoryMapOfNodes_Key_i_wp),POINTER::my_memory=>NULL()
      INTEGER(KIND=i_byte)::my_n_levels=0,my_max_levels=0
      INTEGER(KIND=i_wp)::my_n_elements=0,my_max_elements=1000
      LOGICAL(KIND=l_short)::my_use_search_finger=.TRUE.,my_keep_duplicates=.FALSE.,&
      my_trace_allocation=.TRUE.
      ENDTYPE
      
      
      PUBLIC::Node_Key_i_wp_r_wp
      TYPE Node_Key_i_wp_r_wp
      PRIVATE
      TYPE(Data_Key_i_wp_r_wp)::my_data
      INTEGER(KIND=i_byte)::my_max_level=1,my_page=1
      INTEGER(KIND=i_wp)::my_next=0
      ENDTYPE
      
      PUBLIC::NodePointer_Key_i_wp_r_wp
      TYPE NodePointer_Key_i_wp_r_wp
      PRIVATE
      TYPE(Node_Key_i_wp_r_wp),POINTER::my_node=>NULL()
      ENDTYPE
      
      TYPE BlockOfNodes_Key_i_wp_r_wp
      TYPE(Node_Key_i_wp_r_wp),DIMENSION(:),POINTER::my_nodes=>NULL()
      TYPE(NodePointer_Key_i_wp_r_wp),DIMENSION(:),POINTER::my_pointers=>NULL()
      INTEGER(KIND=i_wp)::my_n_nodes=0
      ENDTYPE
      
      PUBLIC::PageOfNodes_Key_i_wp_r_wp
      TYPE PageOfNodes_Key_i_wp_r_wp
      PRIVATE
      TYPE(BlockOfNodes_Key_i_wp_r_wp)::my_block
      TYPE(NodePointer_Key_i_wp_r_wp)::my_free_node
      INTEGER(KIND=i_byte)::my_next=0
      ENDTYPE
      
      PUBLIC::MemoryMapOfNodes_Key_i_wp_r_wp
      TYPE MemoryMapOfNodes_Key_i_wp_r_wp
      TYPE(PageOfNodes_Key_i_wp_r_wp),DIMENSION(:),POINTER::my_pages=>NULL()
      REAL(KIND=r_sp)::my_p=0.25_r_sp,my_log_p=-1.386294_r_sp
      INTEGER(KIND=i_wp)::my_page_size=100
      INTEGER(KIND=i_byte)::my_n_lists=0,my_max_lists=10
      INTEGER(KIND=i_byte)::my_max_pages=10,my_n_pages=0
      INTEGER(KIND=i_byte)::my_free_page=0
      ENDTYPE
      
      PUBLIC::SkipList_Key_i_wp_r_wp
      TYPE SkipList_Key_i_wp_r_wp
      TYPE(Node_Key_i_wp_r_wp),POINTER::my_head=>NULL(),my_tail=>NULL()
      TYPE(NodePointer_Key_i_wp_r_wp),DIMENSION(:),POINTER::my_search_finger=>NULL()
      TYPE(MemoryMapOfNodes_Key_i_wp_r_wp),POINTER::my_memory=>NULL()
      INTEGER(KIND=i_byte)::my_n_levels=0,my_max_levels=0
      INTEGER(KIND=i_wp)::my_n_elements=0,my_max_elements=1000
      LOGICAL(KIND=l_short)::my_use_search_finger=.TRUE.,my_keep_duplicates=.FALSE.,&
      my_trace_allocation=.TRUE.
      ENDTYPE
      
      
      
      INTERFACE AllocateNode
      MODULE PROCEDURE AllocateNode_Key_i_wp
      MODULE PROCEDURE AllocateNode_Key_i_wp_r_wp
      END INTERFACE
      
      INTERFACE DeallocateNode
      MODULE PROCEDURE DeallocateNode_Key_i_wp
      MODULE PROCEDURE DeallocateNode_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      INTERFACE InitializeSkipList
      MODULE PROCEDURE InitializeSkipList_Key_i_wp
      MODULE PROCEDURE InitializeSkipList_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      INTERFACE DestroySkipList
      MODULE PROCEDURE DestroySkipList_Key_i_wp
      MODULE PROCEDURE DestroySkipList_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      
      INTERFACE SearchInSkipList
      MODULE PROCEDURE SearchInSkipList_Key_i_wp
      MODULE PROCEDURE SearchInSkipList_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      INTERFACE InsertInSkipList
      MODULE PROCEDURE InsertInSkipList_Key_i_wp
      MODULE PROCEDURE InsertInSkipList_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      INTERFACE DeleteFromSkipList
      MODULE PROCEDURE DeleteFromSkipList_Key_i_wp
      MODULE PROCEDURE DeleteFromSkipList_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      INTERFACE PrintSkipList
      MODULE PROCEDURE PrintSkipList_Key_i_wp
      MODULE PROCEDURE PrintSkipList_Key_i_wp_r_wp
      END INTERFACE
      
      
      
      
      CONTAINS
      
      
      
      
      SUBROUTINE AllocateNode_Key_i_wp(skip_list,new_node)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      TYPE(Node_Key_i_wp),POINTER::new_node
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      
      TYPE(PageOfNodes_Key_i_wp),DIMENSION(:),ALLOCATABLE::temp_pages
      TYPE(Node_Key_i_wp),DIMENSION(:),ALLOCATABLE::temp_nodes
      TYPE(NodePointer_Key_i_wp),DIMENSION(:),ALLOCATABLE::temp_pointers
      
      REAL::dice
      INTEGER(KIND=i_byte)::page,temp_page
      INTEGER(KIND=i_wp)::n_nodes,n_pointers
      INTEGER::alloc_status
      LOGICAL::find_free_node,get_next_node,get_next_page,new_page,reallocate_pages
      
      
      HeadAndTail:IF(skip_list%my_n_elements<=1)THEN
      IF(skip_list%my_n_elements==0)THEN
      skip_list%my_memory%my_n_lists=skip_list%my_memory%my_n_lists+1
      IF(skip_list%my_trace_allocation)WRITE(*,*)"Allocating head for list #",skip_list%my_memory%my_n_lists
      END IF
      
      IF(.NOT.ASSOCIATED(skip_list%my_memory%my_pages(0)%my_block%my_nodes))THEN
      n_nodes=2*skip_list%my_memory%my_max_lists
      n_pointers=n_nodes*MAX(INT(-LOG(REAL(skip_list%my_memory%my_max_pages*skip_list%my_memory%my_page_size,KIND=r_wp))/skip_list&
     &%my_memory%my_log_p),1)
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Allocating page 0 of heads and tails ",&
      " for ",n_nodes," sentinel nodes and ",n_pointers," next pointers"
      END IF
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_nodes(0:n_nodes))
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_pointers(0:n_pointers))
      node=>skip_list%my_memory%my_pages(0)%my_block%my_nodes(0)
      node%my_page=0
      node%my_max_level=0
      node%my_next=0
      END IF
      
      n_nodes=skip_list%my_memory%my_pages(0)%my_block%my_n_nodes
      node=>skip_list%my_memory%my_pages(0)%my_block%my_nodes(n_nodes)
      n_pointers=node%my_next+node%my_max_level
      
      IF((n_nodes+1)>SIZE(skip_list%my_memory%my_pages(0)%my_block%my_nodes))THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Reallocating nodes block of page 0 of heads and tails!"
      END IF
      
      ALLOCATE(temp_nodes(1:n_nodes+1))
      temp_nodes(1:1+SIZE(skip_list%my_memory%my_pages(0)%my_block%my_nodes)-1)=skip_list%my_memory%my_pages(0)%my_block%my_nodes
      DEALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_nodes)
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_nodes(1:n_nodes+1))
      skip_list%my_memory%my_pages(0)%my_block%my_nodes=temp_nodes
      DEALLOCATE(temp_nodes)
      END IF
      IF((n_pointers+skip_list%my_max_levels)>SIZE(skip_list%my_memory%my_pages(0)%my_block%my_pointers))THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Reallocating nexts block of page 0 of heads and tails!"
      END IF
      
      ALLOCATE(temp_pointers(1:n_pointers+skip_list%my_max_levels))
      temp_pointers(1:1+SIZE(skip_list%my_memory%my_pages(0)%my_block%my_pointers)-1)=skip_list%my_memory%my_pages(0)%my_block%my_&
     &pointers
      DEALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_pointers)
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_pointers(1:n_pointers+skip_list%my_max_levels))
      skip_list%my_memory%my_pages(0)%my_block%my_pointers=temp_pointers
      DEALLOCATE(temp_pointers)
      END IF
      
      skip_list%my_memory%my_pages(page)%my_block%my_n_nodes=skip_list%my_memory%my_pages(0)%my_block%my_n_nodes+1
      new_node=>skip_list%my_memory%my_pages(0)%my_block%my_nodes(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes)
      new_node%my_page=0
      new_node%my_max_level=skip_list%my_max_levels
      new_node%my_next=n_pointers
      RETURN
      END IF HeadAndTail
      
      find_free_node=.FALSE.
      page=skip_list%my_memory%my_free_page
      IF(page/=0)THEN
      IF(.NOT.ASSOCIATED(skip_list%my_memory%my_pages(page)%my_free_node%my_node))find_free_node=.TRUE.
      ELSE
      find_free_node=.TRUE.
      END IF
      
      FindFreeNode:IF(find_free_node)
      reallocate_pages=.FALSE.
      get_next_node=.FALSE.
      get_next_page=.FALSE.
      new_page=.FALSE.
      
      FindFreePage:DO
      
      IF(page==0)THEN
      n_nodes=HUGE(1_i_wp)
      CheckAllPages:DO temp_page=1,skip_list%my_memory%my_n_pages
      CheckForOpenings:IF(ASSOCIATED(skip_list%my_memory%my_pages(temp_page)%my_block%my_nodes))THEN
      
      IF(skip_list%my_memory%my_pages(temp_page)%my_block%my_n_nodes<INT(SIZE(skip_list%my_memory%my_pages(temp_page)%my_block%my_&
     &nodes),KIND=i_wp))THEN
      IF(skip_list%my_memory%my_pages(temp_page)%my_block%my_n_nodes<n_nodes)page=temp_page
      END IF
      ELSE
      IF(page==0)THEN
      page=temp_page
      END IF
      END IF CheckForOpenings
      END DO CheckAllPages
      IF(page/=0)THEN
      
      skip_list%my_memory%my_pages(page)%my_next=skip_list%my_memory%my_free_page
      skip_list%my_memory%my_free_page=page
      EXIT FindFreePage
      END IF
      new_page=.TRUE.
      get_next_node=.TRUE.
      get_next_page=.TRUE.
      IF(skip_list%my_memory%my_n_pages>=SIZE(skip_list%my_memory%my_pages))reallocate_pages=.TRUE.
      EXIT FindFreePage
      END IF
      
      FullPage:IF(ASSOCIATED(skip_list%my_memory%my_pages(page)%my_block%my_nodes))THEN
      IF(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes==INT(SIZE(skip_list%my_memory%my_pages(page)%my_block%my_nodes),KI&
     &ND=i_wp))THEN
      
      temp_page=skip_list%my_memory%my_pages(skip_list%my_memory%my_free_page)%my_next
      page=skip_list%my_memory%my_free_page
      skip_list%my_memory%my_free_page=temp_page
      page=skip_list%my_memory%my_free_page
      CYCLE FindFreePage
      ELSE
      get_next_node=.TRUE.
      EXIT FindFreePage
      END IF
      ELSE
      new_page=.TRUE.
      get_next_node=.TRUE.
      EXIT FindFreePage
      END IF FullPage
      
      END DO FindFreePage
      
      IF(reallocate_pages)THEN
      IF(skip_list%my_trace_allocation)THEN
      CALL Warning(message="Reallocation of pages in virtual memory in skip list",&
      caller="AllocateNode")
      END IF
      
      ALLOCATE(temp_pages(0:skip_list%my_memory%my_n_pages+1))
      temp_pages(0:0+SIZE(skip_list%my_memory%my_pages)-1)=skip_list%my_memory%my_pages
      DEALLOCATE(skip_list%my_memory%my_pages)
      ALLOCATE(skip_list%my_memory%my_pages(0:skip_list%my_memory%my_n_pages+1))
      skip_list%my_memory%my_pages=temp_pages
      DEALLOCATE(temp_pages)
      END IF
      
      IF(get_next_page)THEN
      skip_list%my_memory%my_n_pages=skip_list%my_memory%my_n_pages+1
      page=skip_list%my_memory%my_n_pages
      
      skip_list%my_memory%my_pages(page)%my_next=skip_list%my_memory%my_free_page
      skip_list%my_memory%my_free_page=page
      END IF
      
      NewPage:IF(new_page)THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Allocating page of nodes and links #",page,&
      " of size ",skip_list%my_memory%my_page_size,", n_pages=",skip_list%my_memory%my_n_pages,", n_elements=",skip_list%my_n_elem&
     &ents
      END IF
      ALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_nodes(skip_list%my_memory%my_page_size))
      n_pointers=0
      CreateNodes:DO n_nodes=1,skip_list%my_memory%my_page_size
      node=>skip_list%my_memory%my_pages(page)%my_block%my_nodes(n_nodes)
      
      
      CALL RandomUniform(dice)
      node_level=MAX(1_i_byte,CEILING(LOG(dice)/skip_list%my_memory%my_log_p,KIND=i_byte))
      node%my_max_level=node_level
      node%my_page=page
      node%my_next=n_pointers
      n_pointers=n_pointers+node_level
      END DO CreateNodes
      ALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_pointers(n_pointers))
      END IF NewPage
      
      IF(get_next_node)THEN
      node=>skip_list%my_memory%my_pages(page)%my_block%my_nodes(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes+1)
      
      
      skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+1)%my_node=>skip_list%my_memory%my_pages(page)%&
     &my_free_node%my_node
      skip_list%my_memory%my_pages(page)%my_free_node%my_node=>node
      END IF
      
      END IF FindFreeNode
      
      
      
      next_node=>skip_list%my_memory%my_pages(skip_list%my_memory%my_pages(page)%my_free_node%my_node%my_page)%my_block%my_pointer&
     &s(skip_list%my_memory%my_pages(page)%my_free_node%my_node%my_next+1)%my_node
      new_node=>skip_list%my_memory%my_pages(page)%my_free_node%my_node
      skip_list%my_memory%my_pages(page)%my_free_node%my_node=>next_node
      skip_list%my_memory%my_pages(page)%my_block%my_n_nodes=skip_list%my_memory%my_pages(page)%my_block%my_n_nodes+1
      
      END SUBROUTINE
      
      SUBROUTINE AllocateNode_Key_i_wp_r_wp(skip_list,new_node)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      TYPE(Node_Key_i_wp_r_wp),POINTER::new_node
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      
      TYPE(PageOfNodes_Key_i_wp_r_wp),DIMENSION(:),ALLOCATABLE::temp_pages
      TYPE(Node_Key_i_wp_r_wp),DIMENSION(:),ALLOCATABLE::temp_nodes
      TYPE(NodePointer_Key_i_wp_r_wp),DIMENSION(:),ALLOCATABLE::temp_pointers
      
      REAL::dice
      INTEGER(KIND=i_byte)::page,temp_page
      INTEGER(KIND=i_wp)::n_nodes,n_pointers
      INTEGER::alloc_status
      LOGICAL::find_free_node,get_next_node,get_next_page,new_page,reallocate_pages
      
      
      HeadAndTail:IF(skip_list%my_n_elements<=1)THEN
      IF(skip_list%my_n_elements==0)THEN
      skip_list%my_memory%my_n_lists=skip_list%my_memory%my_n_lists+1
      IF(skip_list%my_trace_allocation)WRITE(*,*)"Allocating head for list #",skip_list%my_memory%my_n_lists
      END IF
      
      IF(.NOT.ASSOCIATED(skip_list%my_memory%my_pages(0)%my_block%my_nodes))THEN
      n_nodes=2*skip_list%my_memory%my_max_lists
      n_pointers=n_nodes*MAX(INT(-LOG(REAL(skip_list%my_memory%my_max_pages*skip_list%my_memory%my_page_size,KIND=r_wp))/skip_list&
     &%my_memory%my_log_p),1)
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Allocating page 0 of heads and tails ",&
      " for ",n_nodes," sentinel nodes and ",n_pointers," next pointers"
      END IF
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_nodes(0:n_nodes))
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_pointers(0:n_pointers))
      node=>skip_list%my_memory%my_pages(0)%my_block%my_nodes(0)
      node%my_page=0
      node%my_max_level=0
      node%my_next=0
      END IF
      
      n_nodes=skip_list%my_memory%my_pages(0)%my_block%my_n_nodes
      node=>skip_list%my_memory%my_pages(0)%my_block%my_nodes(n_nodes)
      n_pointers=node%my_next+node%my_max_level
      
      IF((n_nodes+1)>SIZE(skip_list%my_memory%my_pages(0)%my_block%my_nodes))THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Reallocating nodes block of page 0 of heads and tails!"
      END IF
      
      ALLOCATE(temp_nodes(1:n_nodes+1))
      temp_nodes(1:1+SIZE(skip_list%my_memory%my_pages(0)%my_block%my_nodes)-1)=skip_list%my_memory%my_pages(0)%my_block%my_nodes
      DEALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_nodes)
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_nodes(1:n_nodes+1))
      skip_list%my_memory%my_pages(0)%my_block%my_nodes=temp_nodes
      DEALLOCATE(temp_nodes)
      END IF
      IF((n_pointers+skip_list%my_max_levels)>SIZE(skip_list%my_memory%my_pages(0)%my_block%my_pointers))THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Reallocating nexts block of page 0 of heads and tails!"
      END IF
      
      ALLOCATE(temp_pointers(1:n_pointers+skip_list%my_max_levels))
      temp_pointers(1:1+SIZE(skip_list%my_memory%my_pages(0)%my_block%my_pointers)-1)=skip_list%my_memory%my_pages(0)%my_block%my_&
     &pointers
      DEALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_pointers)
      ALLOCATE(skip_list%my_memory%my_pages(0)%my_block%my_pointers(1:n_pointers+skip_list%my_max_levels))
      skip_list%my_memory%my_pages(0)%my_block%my_pointers=temp_pointers
      DEALLOCATE(temp_pointers)
      END IF
      
      skip_list%my_memory%my_pages(page)%my_block%my_n_nodes=skip_list%my_memory%my_pages(0)%my_block%my_n_nodes+1
      new_node=>skip_list%my_memory%my_pages(0)%my_block%my_nodes(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes)
      new_node%my_page=0
      new_node%my_max_level=skip_list%my_max_levels
      new_node%my_next=n_pointers
      RETURN
      END IF HeadAndTail
      
      find_free_node=.FALSE.
      page=skip_list%my_memory%my_free_page
      IF(page/=0)THEN
      IF(.NOT.ASSOCIATED(skip_list%my_memory%my_pages(page)%my_free_node%my_node))find_free_node=.TRUE.
      ELSE
      find_free_node=.TRUE.
      END IF
      
      FindFreeNode:IF(find_free_node)
      reallocate_pages=.FALSE.
      get_next_node=.FALSE.
      get_next_page=.FALSE.
      new_page=.FALSE.
      
      FindFreePage:DO
      
      IF(page==0)THEN
      n_nodes=HUGE(1_i_wp)
      CheckAllPages:DO temp_page=1,skip_list%my_memory%my_n_pages
      CheckForOpenings:IF(ASSOCIATED(skip_list%my_memory%my_pages(temp_page)%my_block%my_nodes))THEN
      
      IF(skip_list%my_memory%my_pages(temp_page)%my_block%my_n_nodes<INT(SIZE(skip_list%my_memory%my_pages(temp_page)%my_block%my_&
     &nodes),KIND=i_wp))THEN
      IF(skip_list%my_memory%my_pages(temp_page)%my_block%my_n_nodes<n_nodes)page=temp_page
      END IF
      ELSE
      IF(page==0)THEN
      page=temp_page
      END IF
      END IF CheckForOpenings
      END DO CheckAllPages
      IF(page/=0)THEN
      
      skip_list%my_memory%my_pages(page)%my_next=skip_list%my_memory%my_free_page
      skip_list%my_memory%my_free_page=page
      EXIT FindFreePage
      END IF
      new_page=.TRUE.
      get_next_node=.TRUE.
      get_next_page=.TRUE.
      IF(skip_list%my_memory%my_n_pages>=SIZE(skip_list%my_memory%my_pages))reallocate_pages=.TRUE.
      EXIT FindFreePage
      END IF
      
      FullPage:IF(ASSOCIATED(skip_list%my_memory%my_pages(page)%my_block%my_nodes))THEN
      IF(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes==INT(SIZE(skip_list%my_memory%my_pages(page)%my_block%my_nodes),KI&
     &ND=i_wp))THEN
      
      temp_page=skip_list%my_memory%my_pages(skip_list%my_memory%my_free_page)%my_next
      page=skip_list%my_memory%my_free_page
      skip_list%my_memory%my_free_page=temp_page
      page=skip_list%my_memory%my_free_page
      CYCLE FindFreePage
      ELSE
      get_next_node=.TRUE.
      EXIT FindFreePage
      END IF
      ELSE
      new_page=.TRUE.
      get_next_node=.TRUE.
      EXIT FindFreePage
      END IF FullPage
      
      END DO FindFreePage
      
      IF(reallocate_pages)THEN
      IF(skip_list%my_trace_allocation)THEN
      CALL Warning(message="Reallocation of pages in virtual memory in skip list",&
      caller="AllocateNode")
      END IF
      
      ALLOCATE(temp_pages(0:skip_list%my_memory%my_n_pages+1))
      temp_pages(0:0+SIZE(skip_list%my_memory%my_pages)-1)=skip_list%my_memory%my_pages
      DEALLOCATE(skip_list%my_memory%my_pages)
      ALLOCATE(skip_list%my_memory%my_pages(0:skip_list%my_memory%my_n_pages+1))
      skip_list%my_memory%my_pages=temp_pages
      DEALLOCATE(temp_pages)
      END IF
      
      IF(get_next_page)THEN
      skip_list%my_memory%my_n_pages=skip_list%my_memory%my_n_pages+1
      page=skip_list%my_memory%my_n_pages
      
      skip_list%my_memory%my_pages(page)%my_next=skip_list%my_memory%my_free_page
      skip_list%my_memory%my_free_page=page
      END IF
      
      NewPage:IF(new_page)THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Allocating page of nodes and links #",page,&
      " of size ",skip_list%my_memory%my_page_size,", n_pages=",skip_list%my_memory%my_n_pages,", n_elements=",skip_list%my_n_elem&
     &ents
      END IF
      ALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_nodes(skip_list%my_memory%my_page_size))
      n_pointers=0
      CreateNodes:DO n_nodes=1,skip_list%my_memory%my_page_size
      node=>skip_list%my_memory%my_pages(page)%my_block%my_nodes(n_nodes)
      
      
      CALL RandomUniform(dice)
      node_level=MAX(1_i_byte,CEILING(LOG(dice)/skip_list%my_memory%my_log_p,KIND=i_byte))
      node%my_max_level=node_level
      node%my_page=page
      node%my_next=n_pointers
      n_pointers=n_pointers+node_level
      END DO CreateNodes
      ALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_pointers(n_pointers))
      END IF NewPage
      
      IF(get_next_node)THEN
      node=>skip_list%my_memory%my_pages(page)%my_block%my_nodes(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes+1)
      
      
      skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+1)%my_node=>skip_list%my_memory%my_pages(page)%&
     &my_free_node%my_node
      skip_list%my_memory%my_pages(page)%my_free_node%my_node=>node
      END IF
      
      END IF FindFreeNode
      
      
      
      next_node=>skip_list%my_memory%my_pages(skip_list%my_memory%my_pages(page)%my_free_node%my_node%my_page)%my_block%my_pointer&
     &s(skip_list%my_memory%my_pages(page)%my_free_node%my_node%my_next+1)%my_node
      new_node=>skip_list%my_memory%my_pages(page)%my_free_node%my_node
      skip_list%my_memory%my_pages(page)%my_free_node%my_node=>next_node
      skip_list%my_memory%my_pages(page)%my_block%my_n_nodes=skip_list%my_memory%my_pages(page)%my_block%my_n_nodes+1
      
      END SUBROUTINE
      
      
      SUBROUTINE DeallocateNode_Key_i_wp(skip_list,free_node)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      TYPE(Node_Key_i_wp),POINTER::free_node
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER(KIND=i_byte)::page,temp_page
      
      page=free_node%my_page
      
      
      skip_list%my_memory%my_pages(free_node%my_page)%my_block%my_pointers(free_node%my_next+1)%my_node=>skip_list%my_memory%my_pa&
     &ges(page)%my_free_node%my_node
      skip_list%my_memory%my_pages(page)%my_free_node%my_node=>free_node
      skip_list%my_memory%my_pages(page)%my_block%my_n_nodes=skip_list%my_memory%my_pages(page)%my_block%my_n_nodes-1
      
      IF(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes==0)THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Deallocating page of nodes and links #",page,&
      ", n_pages=",skip_list%my_memory%my_n_pages,", n_elements=",skip_list%my_n_elements
      END IF
      NULLIFY(skip_list%my_memory%my_pages(page)%my_free_node%my_node)
      DEALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_nodes)
      DEALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_pointers)
      END IF
      
      END SUBROUTINE
      
      SUBROUTINE DeallocateNode_Key_i_wp_r_wp(skip_list,free_node)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      TYPE(Node_Key_i_wp_r_wp),POINTER::free_node
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER(KIND=i_byte)::page,temp_page
      
      page=free_node%my_page
      
      
      skip_list%my_memory%my_pages(free_node%my_page)%my_block%my_pointers(free_node%my_next+1)%my_node=>skip_list%my_memory%my_pa&
     &ges(page)%my_free_node%my_node
      skip_list%my_memory%my_pages(page)%my_free_node%my_node=>free_node
      skip_list%my_memory%my_pages(page)%my_block%my_n_nodes=skip_list%my_memory%my_pages(page)%my_block%my_n_nodes-1
      
      IF(skip_list%my_memory%my_pages(page)%my_block%my_n_nodes==0)THEN
      IF(skip_list%my_trace_allocation)THEN
      WRITE(message_print_unit,*)"Deallocating page of nodes and links #",page,&
      ", n_pages=",skip_list%my_memory%my_n_pages,", n_elements=",skip_list%my_n_elements
      END IF
      NULLIFY(skip_list%my_memory%my_pages(page)%my_free_node%my_node)
      DEALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_nodes)
      DEALLOCATE(skip_list%my_memory%my_pages(page)%my_block%my_pointers)
      END IF
      
      END SUBROUTINE
      
      
      
      
      
      SUBROUTINE InitializeSkipList_Key_i_wp(skip_list)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER(KIND=i_byte)::page
      
      IF(.NOT.ASSOCIATED(skip_list))ALLOCATE(skip_list)
      
      IF(.NOT.ASSOCIATED(skip_list%my_memory))THEN
      ALLOCATE(skip_list%my_memory)
      skip_list%my_memory%my_page_size=CEILING(REAL(skip_list%my_max_elements)/REAL(skip_list%my_memory%my_max_pages))
      
      END IF
      
      IF(.NOT.ASSOCIATED(skip_list%my_memory%my_pages))ALLOCATE(skip_list%my_memory%my_pages(0:skip_list%my_memory%my_max_pages))
      skip_list%my_memory%my_log_p=LOG(skip_list%my_memory%my_p)
      
      IF(skip_list%my_max_levels<=0)skip_list%my_max_levels=MAX(INT(-LOG(REAL(skip_list%my_max_elements,KIND=r_wp))/skip_list%my_m&
     &emory%my_log_p),1)
      
      skip_list%my_n_elements=0
      CALL AllocateNode(skip_list,skip_list%my_head)
      skip_list%my_n_elements=1
      CALL AllocateNode(skip_list,skip_list%my_tail)
      skip_list%my_n_elements=2
      skip_list%my_head%my_data%my_key%my_value=-huge_Key_i_wp
      skip_list%my_tail%my_data%my_key%my_value=huge_Key_i_wp
      ALLOCATE(skip_list%my_search_finger(skip_list%my_max_levels))
      
      DO level=1,skip_list%my_max_levels
      
      skip_list%my_memory%my_pages(skip_list%my_head%my_page)%my_block%my_pointers(skip_list%my_head%my_next+level)%my_node=>skip_&
     &list%my_tail
      
      skip_list%my_memory%my_pages(skip_list%my_tail%my_page)%my_block%my_pointers(skip_list%my_tail%my_next+level)%my_node=>NULL(&
     &)
      
      skip_list%my_search_finger(level)%my_node=>skip_list%my_head
      END DO
      
      END SUBROUTINE
      
      SUBROUTINE InitializeSkipList_Key_i_wp_r_wp(skip_list)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER(KIND=i_byte)::page
      
      IF(.NOT.ASSOCIATED(skip_list))ALLOCATE(skip_list)
      
      IF(.NOT.ASSOCIATED(skip_list%my_memory))THEN
      ALLOCATE(skip_list%my_memory)
      skip_list%my_memory%my_page_size=CEILING(REAL(skip_list%my_max_elements)/REAL(skip_list%my_memory%my_max_pages))
      
      END IF
      
      IF(.NOT.ASSOCIATED(skip_list%my_memory%my_pages))ALLOCATE(skip_list%my_memory%my_pages(0:skip_list%my_memory%my_max_pages))
      skip_list%my_memory%my_log_p=LOG(skip_list%my_memory%my_p)
      
      IF(skip_list%my_max_levels<=0)skip_list%my_max_levels=MAX(INT(-LOG(REAL(skip_list%my_max_elements,KIND=r_wp))/skip_list%my_m&
     &emory%my_log_p),1)
      
      skip_list%my_n_elements=0
      CALL AllocateNode(skip_list,skip_list%my_head)
      skip_list%my_n_elements=1
      CALL AllocateNode(skip_list,skip_list%my_tail)
      skip_list%my_n_elements=2
      skip_list%my_head%my_data%my_key%my_value=-huge_Key_i_wp_r_wp
      skip_list%my_tail%my_data%my_key%my_value=huge_Key_i_wp_r_wp
      ALLOCATE(skip_list%my_search_finger(skip_list%my_max_levels))
      
      DO level=1,skip_list%my_max_levels
      
      skip_list%my_memory%my_pages(skip_list%my_head%my_page)%my_block%my_pointers(skip_list%my_head%my_next+level)%my_node=>skip_&
     &list%my_tail
      
      skip_list%my_memory%my_pages(skip_list%my_tail%my_page)%my_block%my_pointers(skip_list%my_tail%my_next+level)%my_node=>NULL(&
     &)
      
      skip_list%my_search_finger(level)%my_node=>skip_list%my_head
      END DO
      
      END SUBROUTINE
      
      
      
      
      
      SUBROUTINE DestroySkipList_Key_i_wp(skip_list,deallocate_memory)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      LOGICAL,INTENT(IN),OPTIONAL::deallocate_memory
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER::alloc_status
      LOGICAL::free_memory
      
      free_memory=.FALSE.
      IF(PRESENT(deallocate_memory))free_memory=deallocate_memory
      
      DEALLOCATE(skip_list%my_search_finger)
      
      node=>skip_list%my_head
      DeleteNodes:DO
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+1)%my_node
      CALL DeallocateNode(skip_list,node)
      IF(.NOT.ASSOCIATED(next_node))EXIT DeleteNodes
      node=>next_node
      END DO DeleteNodes
      
      IF(free_memory)THEN
      DEALLOCATE(skip_list%my_memory%my_pages)
      DEALLOCATE(skip_list%my_memory,STAT=alloc_status)
      IF(alloc_status/=0)NULLIFY(skip_list%my_memory)
      END IF
      
      DEALLOCATE(skip_list,STAT=alloc_status)
      IF(alloc_status/=0)NULLIFY(skip_list)
      
      END SUBROUTINE
      
      SUBROUTINE DestroySkipList_Key_i_wp_r_wp(skip_list,deallocate_memory)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      LOGICAL,INTENT(IN),OPTIONAL::deallocate_memory
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER::alloc_status
      LOGICAL::free_memory
      
      free_memory=.FALSE.
      IF(PRESENT(deallocate_memory))free_memory=deallocate_memory
      
      DEALLOCATE(skip_list%my_search_finger)
      
      node=>skip_list%my_head
      DeleteNodes:DO
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+1)%my_node
      CALL DeallocateNode(skip_list,node)
      IF(.NOT.ASSOCIATED(next_node))EXIT DeleteNodes
      node=>next_node
      END DO DeleteNodes
      
      IF(free_memory)THEN
      DEALLOCATE(skip_list%my_memory%my_pages)
      DEALLOCATE(skip_list%my_memory,STAT=alloc_status)
      IF(alloc_status/=0)NULLIFY(skip_list%my_memory)
      END IF
      
      DEALLOCATE(skip_list,STAT=alloc_status)
      IF(alloc_status/=0)NULLIFY(skip_list)
      
      END SUBROUTINE
      
      
      
      
      
      SUBROUTINE SearchInSkipList_Key_i_wp(skip_list,key,data,found)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      TYPE(Key_i_wp),INTENT(IN)::key
      TYPE(Data_Key_i_wp),INTENT(OUT),OPTIONAL::data
      LOGICAL,INTENT(OUT),OPTIONAL::found
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      
      
      IF(skip_list%my_use_search_finger)THEN
      level=1
      
      search_node=>skip_list%my_search_finger(level)%my_node
      
      comparison=(key%my_value<=search_node%my_data%my_key%my_value)
      IF(.NOT.comparison)THEN
      PointAhead_Search:DO
      level=level+1
      IF(level>skip_list%my_n_levels)EXIT PointAhead_Search
      
      node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+level)%my_node
      
      comparison=(key%my_value<=next_node%my_data%my_key%my_value)
      IF(comparison)THEN
      EXIT PointAhead_Search
      ELSE
      search_node=>next_node
      END IF
      END DO PointAhead_Search
      ELSE
      level=1
      PointBack_Search:DO
      level=level+1
      IF(level>skip_list%my_n_levels)THEN
      search_node=>skip_list%my_head
      EXIT PointBack_Search
      END IF
      
      node=>skip_list%my_search_finger(level)%my_node
      
      comparison=(key%my_value<=node%my_data%my_key%my_value)
      IF(.NOT.comparison)THEN
      search_node=>node
      EXIT PointBack_Search
      END IF
      END DO PointBack_Search
      END IF
      ELSE
      level=skip_list%my_n_levels+1
      search_node=>skip_list%my_head
      END IF
      
      SearchAhead_Search:DO
      level=level-1
      IF(level<1)EXIT SearchAhead_Search
      
      skip_list%my_search_finger(level)%my_node=>search_node
      SkipAhead_Search:DO
      
      node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+level)%my_node
      
      comparison=(key%my_value<=next_node%my_data%my_key%my_value)
      IF(.NOT.comparison)THEN
      
      skip_list%my_search_finger(level)%my_node=>next_node
      ELSE
      EXIT SkipAhead_Search
      END IF
      END DO SkipAhead_Search
      END DO SearchAhead_Search
      
      
      search_node=>skip_list%my_search_finger(1)%my_node
      
      node=>skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+1)%my_node
      
      comparison=(node%my_data%my_key%my_value==key%my_value)
      IF(PRESENT(found))found=comparison
      IF(PRESENT(data).AND.comparison)data=node%my_data
      
      END SUBROUTINE
      
      SUBROUTINE SearchInSkipList_Key_i_wp_r_wp(skip_list,key,data,found)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      TYPE(Key_i_wp_r_wp),INTENT(IN)::key
      TYPE(Data_Key_i_wp_r_wp),INTENT(OUT),OPTIONAL::data
      LOGICAL,INTENT(OUT),OPTIONAL::found
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      
      
      IF(skip_list%my_use_search_finger)THEN
      level=1
      
      search_node=>skip_list%my_search_finger(level)%my_node
      
      comparison=(key%my_value<=search_node%my_data%my_key%my_value)
      IF(.NOT.comparison)THEN
      PointAhead_Search:DO
      level=level+1
      IF(level>skip_list%my_n_levels)EXIT PointAhead_Search
      
      node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+level)%my_node
      
      comparison=(key%my_value<=next_node%my_data%my_key%my_value)
      IF(comparison)THEN
      EXIT PointAhead_Search
      ELSE
      search_node=>next_node
      END IF
      END DO PointAhead_Search
      ELSE
      level=1
      PointBack_Search:DO
      level=level+1
      IF(level>skip_list%my_n_levels)THEN
      search_node=>skip_list%my_head
      EXIT PointBack_Search
      END IF
      
      node=>skip_list%my_search_finger(level)%my_node
      
      comparison=(key%my_value<=node%my_data%my_key%my_value)
      IF(.NOT.comparison)THEN
      search_node=>node
      EXIT PointBack_Search
      END IF
      END DO PointBack_Search
      END IF
      ELSE
      level=skip_list%my_n_levels+1
      search_node=>skip_list%my_head
      END IF
      
      SearchAhead_Search:DO
      level=level-1
      IF(level<1)EXIT SearchAhead_Search
      
      skip_list%my_search_finger(level)%my_node=>search_node
      SkipAhead_Search:DO
      
      node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+level)%my_node
      
      comparison=(key%my_value<=next_node%my_data%my_key%my_value)
      IF(.NOT.comparison)THEN
      
      skip_list%my_search_finger(level)%my_node=>next_node
      ELSE
      EXIT SkipAhead_Search
      END IF
      END DO SkipAhead_Search
      END DO SearchAhead_Search
      
      
      search_node=>skip_list%my_search_finger(1)%my_node
      
      node=>skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+1)%my_node
      
      comparison=(node%my_data%my_key%my_value==key%my_value)
      IF(PRESENT(found))found=comparison
      IF(PRESENT(data).AND.comparison)data=node%my_data
      
      END SUBROUTINE
      
      
      
      
      
      SUBROUTINE InsertInSkipList_Key_i_wp(skip_list,data)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      TYPE(Data_Key_i_wp),INTENT(IN)::data
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      TYPE(Node_Key_i_wp),POINTER::new_node
      LOGICAL::duplicate
      
      CALL SearchInSkipList(skip_list=skip_list,key=data%my_key,found=duplicate)
      IF((.NOT.skip_list%my_keep_duplicates).AND.duplicate)RETURN
      
      CALL AllocateNode(skip_list,new_node)
      skip_list%my_n_elements=skip_list%my_n_elements+1
      new_node%my_data=data
      
      node_level=MIN(skip_list%my_max_levels,new_node%my_max_level)
      skip_list%my_n_levels=MAX(skip_list%my_n_levels,node_level)
      DO level=1,node_level
      
      search_node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node
      
      
      skip_list%my_memory%my_pages(new_node%my_page)%my_block%my_pointers(new_node%my_next+level)%my_node=>next_node
      
      skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node=>new_node
      
      END DO
      
      END SUBROUTINE
      
      SUBROUTINE InsertInSkipList_Key_i_wp_r_wp(skip_list,data)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      TYPE(Data_Key_i_wp_r_wp),INTENT(IN)::data
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      TYPE(Node_Key_i_wp_r_wp),POINTER::new_node
      LOGICAL::duplicate
      
      CALL SearchInSkipList(skip_list=skip_list,key=data%my_key,found=duplicate)
      IF((.NOT.skip_list%my_keep_duplicates).AND.duplicate)RETURN
      
      CALL AllocateNode(skip_list,new_node)
      skip_list%my_n_elements=skip_list%my_n_elements+1
      new_node%my_data=data
      
      node_level=MIN(skip_list%my_max_levels,new_node%my_max_level)
      skip_list%my_n_levels=MAX(skip_list%my_n_levels,node_level)
      DO level=1,node_level
      
      search_node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node
      
      
      skip_list%my_memory%my_pages(new_node%my_page)%my_block%my_pointers(new_node%my_next+level)%my_node=>next_node
      
      skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node=>new_node
      
      END DO
      
      END SUBROUTINE
      
      
      
      
      
      SUBROUTINE DeleteFromSkipList_Key_i_wp(skip_list,key,data,deleted)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      TYPE(Key_i_wp),INTENT(IN)::key
      TYPE(Data_Key_i_wp),INTENT(OUT),OPTIONAL::data
      LOGICAL,INTENT(OUT),OPTIONAL::deleted
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      TYPE(Node_Key_i_wp),POINTER::old_node
      LOGICAL::found
      
      
      IF(.NOT.PRESENT(data))THEN
      CALL SearchInSkipList(skip_list=skip_list,key=key,found=found)
      ELSE
      CALL SearchInSkipList(skip_list=skip_list,key=key,data=data,found=found)
      END IF
      IF(PRESENT(deleted))deleted=found
      IF(.NOT.found)RETURN
      
      BypassNode:DO level=1,skip_list%my_n_levels
      
      search_node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node
      IF(level==1)old_node=>next_node
      IF(.NOT.ASSOCIATED(old_node,next_node))EXIT BypassNode
      
      
      next_node=>skip_list%my_memory%my_pages(old_node%my_page)%my_block%my_pointers(old_node%my_next+level)%my_node
      
      skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node=>next_node
      END DO BypassNode
      
      ReduceLevel:DO
      
      next_node=>skip_list%my_memory%my_pages(skip_list%my_head%my_page)%my_block%my_pointers(skip_list%my_head%my_next+skip_list%&
     &my_n_levels)%my_node
      IF((.NOT.ASSOCIATED(next_node,skip_list%my_tail)).OR.(skip_list%my_n_levels<=1))EXIT ReduceLevel
      skip_list%my_n_levels=skip_list%my_n_levels-1
      END DO ReduceLevel
      
      CALL DeallocateNode(skip_list,old_node)
      skip_list%my_n_elements=skip_list%my_n_elements-1
      
      END SUBROUTINE
      
      SUBROUTINE DeleteFromSkipList_Key_i_wp_r_wp(skip_list,key,data,deleted)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      TYPE(Key_i_wp_r_wp),INTENT(IN)::key
      TYPE(Data_Key_i_wp_r_wp),INTENT(OUT),OPTIONAL::data
      LOGICAL,INTENT(OUT),OPTIONAL::deleted
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      TYPE(Node_Key_i_wp_r_wp),POINTER::old_node
      LOGICAL::found
      
      
      IF(.NOT.PRESENT(data))THEN
      CALL SearchInSkipList(skip_list=skip_list,key=key,found=found)
      ELSE
      CALL SearchInSkipList(skip_list=skip_list,key=key,data=data,found=found)
      END IF
      IF(PRESENT(deleted))deleted=found
      IF(.NOT.found)RETURN
      
      BypassNode:DO level=1,skip_list%my_n_levels
      
      search_node=>skip_list%my_search_finger(level)%my_node
      
      next_node=>skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node
      IF(level==1)old_node=>next_node
      IF(.NOT.ASSOCIATED(old_node,next_node))EXIT BypassNode
      
      
      next_node=>skip_list%my_memory%my_pages(old_node%my_page)%my_block%my_pointers(old_node%my_next+level)%my_node
      
      skip_list%my_memory%my_pages(search_node%my_page)%my_block%my_pointers(search_node%my_next+level)%my_node=>next_node
      END DO BypassNode
      
      ReduceLevel:DO
      
      next_node=>skip_list%my_memory%my_pages(skip_list%my_head%my_page)%my_block%my_pointers(skip_list%my_head%my_next+skip_list%&
     &my_n_levels)%my_node
      IF((.NOT.ASSOCIATED(next_node,skip_list%my_tail)).OR.(skip_list%my_n_levels<=1))EXIT ReduceLevel
      skip_list%my_n_levels=skip_list%my_n_levels-1
      END DO ReduceLevel
      
      CALL DeallocateNode(skip_list,old_node)
      skip_list%my_n_elements=skip_list%my_n_elements-1
      
      END SUBROUTINE
      
      
      
      
      
      SUBROUTINE PrintSkipList_Key_i_wp(skip_list)
      TYPE(SkipList_Key_i_wp),POINTER::skip_list
      
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      
      WRITE(*,*)
      
      node=>skip_list%my_memory%my_pages(skip_list%my_head%my_page)%my_block%my_pointers(skip_list%my_head%my_next+1)%my_node
      PrintList:DO
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+1)%my_node
      IF(ASSOCIATED(next_node))THEN
      WRITE(UNIT=*,FMT="(G10.3)",ADVANCE="NO")node%my_data%my_key%my_value
      WRITE(UNIT=*,FMT="(A)",ADVANCE="NO")" ---> "
      
      node_level=1
      DO level=1,node_level
      
      search_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+level)%my_node
      WRITE(UNIT=*,FMT="(G10.3)",ADVANCE="NO")search_node%my_data%my_key%my_value
      END DO
      WRITE(*,*)
      node=>next_node
      ELSE
      EXIT PrintList
      END IF
      END DO PrintList
      WRITE(*,*)
      
      END SUBROUTINE
      
      SUBROUTINE PrintSkipList_Key_i_wp_r_wp(skip_list)
      TYPE(SkipList_Key_i_wp_r_wp),POINTER::skip_list
      
      
      TYPE(Node_Key_i_wp_r_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      
      WRITE(*,*)
      
      node=>skip_list%my_memory%my_pages(skip_list%my_head%my_page)%my_block%my_pointers(skip_list%my_head%my_next+1)%my_node
      PrintList:DO
      
      next_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+1)%my_node
      IF(ASSOCIATED(next_node))THEN
      WRITE(UNIT=*,FMT="(G10.3)",ADVANCE="NO")node%my_data%my_key%my_value
      WRITE(UNIT=*,FMT="(A)",ADVANCE="NO")" ---> "
      
      node_level=1
      DO level=1,node_level
      
      search_node=>skip_list%my_memory%my_pages(node%my_page)%my_block%my_pointers(node%my_next+level)%my_node
      WRITE(UNIT=*,FMT="(G10.3)",ADVANCE="NO")search_node%my_data%my_key%my_value
      END DO
      WRITE(*,*)
      node=>next_node
      ELSE
      EXIT PrintList
      END IF
      END DO PrintList
      WRITE(*,*)
      
      END SUBROUTINE
      
      
      
      END MODULE Skip_Lists
      
      
      
      PROGRAM Test_Skip_Lists
      USE Precision
      USE Error_Handling
      USE System_Monitors
      USE Initialization_Termination
      USE Random_Numbers
      USE Sorting_Ranking
      USE Key_Types
      USE Skip_Lists
      IMPLICIT NONE
      
      INTEGER(KIND=i_wp)::key
      INTEGER,DIMENSION(:),ALLOCATABLE::permutation
      TYPE(Data_Key_i_wp)::data
      TYPE(SkipList_Key_i_wp),POINTER::skip_list=>NULL()
      
      TYPE(Node_Key_i_wp),POINTER::node,next_node,search_node
      INTEGER(KIND=i_byte)::level,node_level
      LOGICAL::comparison
      INTEGER::element,n_elements,min_elements=HUGE(0),max_elements=0,n_reps,reps
      REAL::variance,disorder,random,elapsed_time
      LOGICAL::test,found
      
      CALL StartProgram()
      
      ALLOCATE(skip_list)
      ALLOCATE(skip_list%my_memory)
      WRITE(*,*)"Enter max_elements, page_size, max_pages, and p"
      READ(*,*)skip_list%my_max_elements,skip_list%my_memory%my_page_size,skip_list%my_memory%my_max_pages,skip_list%my_memory%my_&
     &p
      WRITE(*,*)"Enter size variance, key disorder and use_search_finger"
      READ(*,*)variance,disorder,skip_list%my_use_search_finger
      skip_list%my_memory%my_max_lists=1
      skip_list%my_keep_duplicates=.FALSE.
      skip_list%my_trace_allocation=.FALSE.
      CALL InitializeSkipList(skip_list)
      
      CALL RandomUniform(random,range=(/1.0-variance,1.0+variance/))
      n_elements=INT(random*REAL(skip_list%my_max_elements))
      WRITE(*,*)"The maximum size of the list will be:",n_elements
      ALLOCATE(permutation(n_elements))
      CALL DisorderPermutation(disorder=disorder,permutation=permutation,disorder_distribution='U')
      
      WRITE(*,*)"Starting insertion of nodes!"
      
      n_reps=0
      CALL ResetTimer(1)
      DO
      n_reps=n_reps+1
      CALL StartTimer(1)
      DO reps=1,1
      CALL Insertion()
      END DO
      CALL StopTimer(1)
      IF(ReadTimer(1)>2.5)EXIT
      END DO
      elapsed_time=ReadTimer(1)/REAL(n_reps)
      WRITE(*,*)"Insertion took:",elapsed_time," seconds."
      
      WRITE(*,*)"Starting search for disordered keys!"
      
      n_reps=0
      CALL ResetTimer(2)
      DO
      n_reps=n_reps+1
      CALL StartTimer(2)
      DO reps=1,1
      CALL Search()
      END DO
      CALL StopTimer(2)
      IF(ReadTimer(2)>2.5)EXIT
      END DO
      elapsed_time=ReadTimer(2)/REAL(n_reps)
      WRITE(*,*)"Search took:",elapsed_time," seconds."
      
      WRITE(*,*)"Starting allocation stress test of mixed insertion/deletion!"
      
      n_reps=0
      CALL ResetTimer(3)
      DO
      n_reps=n_reps+1
      CALL StartTimer(3)
      DO reps=1,1
      CALL InsertionDeletion()
      END DO
      CALL StopTimer(3)
      IF(ReadTimer(3)>2.5)EXIT
      END DO
      elapsed_time=ReadTimer(3)/REAL(n_reps)
      WRITE(*,*)"Mixed insertion/deletion took:",elapsed_time," seconds."
      WRITE(*,*)"Minimum and maximum number of nodes was ",min_elements,max_elements
      
      WRITE(*,*)"Inserting all nodes back and then deleting them!"
      CALL Insertion()
      
      n_reps=0
      CALL ResetTimer(4)
      DO
      n_reps=n_reps+1
      CALL StartTimer(4)
      DO reps=1,1
      CALL Deletion()
      END DO
      CALL StopTimer(4)
      IF(ReadTimer(4)>2.5)EXIT
      END DO
      elapsed_time=ReadTimer(4)/REAL(n_reps)
      WRITE(*,*)"Deletion took:",elapsed_time," seconds."
      
      DEALLOCATE(permutation)
      CALL DestroySkipList(skip_list,deallocate_memory=.TRUE.)
      CALL EndProgram()
      
      CONTAINS
      
      SUBROUTINE Insertion()
      DO element=1,n_elements
      data%my_key%my_value=permutation(element)
      CALL InsertInSkipList(skip_list,data)
      END DO
      END SUBROUTINE Insertion
      
      SUBROUTINE Deletion()
      DO element=1,n_elements
      CALL DeleteFromSkipList(skip_list=skip_list,key=Key_i_wp(permutation(element)),&
      data=data,deleted=found)
      END DO
      END SUBROUTINE Deletion
      
      SUBROUTINE InsertionDeletion()
      DO element=1,n_elements
      CALL RandomUniform(key,range=(/1,n_elements/))
      key=permutation(key)
      CALL DeleteFromSkipList(skip_list=skip_list,key=Key_i_wp(key),deleted=found)
      IF(.NOT.found)THEN
      data%my_key=Key_i_wp(key)
      CALL InsertInSkipList(skip_list=skip_list,data=data)
      END IF
      min_elements=MIN(min_elements,skip_list%my_n_elements)
      max_elements=MAX(max_elements,skip_list%my_n_elements)
      END DO
      END SUBROUTINE InsertionDeletion
      
      SUBROUTINE Search()
      DO element=1,n_elements
      CALL SearchInSkipList(skip_list=skip_list,key=Key_i_wp(permutation(element)),&
      data=data,found=found)
      END DO
      END SUBROUTINE Search
      
      END PROGRAM Test_Skip_Lists