破壊的デック

MutableDeque.sml

structure MutableDeque :
          sig
            type 'elem t
            val empty : unit -> 'elem t
            val cons : 'elem -> 'elem t -> 'elem t
            val head : 'elem t -> 'elem
            val tail : 'elem t -> 'elem t
            val snoc : 'elem -> 'elem t -> 'elem t
            val last : 'elem t -> 'elem
            val init : 'elem t -> 'elem t
          end
=
struct
  datatype 'elem cell = Null
                       | Cell of
                         {
                           prev: 'elem cell ref,
                           elem: 'elem,
                           next: 'elem cell ref
                         }
  type 'elem t = {front: 'elem cell ref, rear: 'elem cell ref}

  fun empty () = {front = ref Null, rear = ref Null}

  fun cons elem {front, rear} =
      case !front of
          Null =>
          let
            val cellPtr =
                ref (Cell {prev = ref Null, elem = elem, next = ref Null})
          in
            {front = cellPtr, rear = cellPtr}
          end
        | Cell _ =>
          let val newCell = (Cell {prev = ref Null, elem = elem, next = front})
          in {front = ref newCell, rear = rear} end

  fun head {front, rear} =
      case !front of
          Null => raise Empty
        | Cell {elem, ...} => elem

  fun tail {front, rear} =
      case !front of
          Null => raise Empty
        | Cell {next, ...} =>
          if front = rear then empty ()
          else {front = next, rear = rear}

  fun snoc elem {front, rear} =
      case !rear of
          Null =>
          let
            val cellPtr =
                ref (Cell {prev = ref Null, elem = elem, next = ref Null})
          in
            {front = cellPtr, rear = cellPtr}
          end
        | Cell _ =>
          let val newCell = (Cell {prev = rear, elem = elem, next = ref Null})
          in {front = front, rear = ref newCell} end

  fun last {front, rear} =
      case !rear of
          Null => raise Empty
        | Cell {elem, ...} => elem

  fun init {front, rear} =
      case !rear of
          Null => raise Empty
        | Cell {prev, ...} =>
          if front = rear then empty ()
          else {front = front, rear = prev}
end