A doubly-linked list in Scala

doubleLinkedList.scala

import scala.annotation.tailrec
import com.thoughtworks.enableIf

// Doubly-linked lists allow O(1) removals at the cost of having a
// reference to the doubly-linked node itself. Some game objects store
// their own next/prev links, which allows for a convenient reference to
// the doubly-linked node (i.e. it's just the value stored) however then
// each value can partake in at most one list at a time (per next/prev,
// can have multiple types of next/prev as is done with Affect).

// The book "Game Programming Patterns" discusses doubly linked lists.
// http://gameprogrammingpatterns.com/observer.html

// Naming conventions in this file:
//  type parameter A - the type of node in the doubly linked list
//  type parameter B - the type of value in the doubly linked list
//  type parameter C - the type of association for the doubly linked list
//  type parameter D - the type of value to which a B is converted using Convert
//  type parameter E - the type of value to/from which a B is mapped or folded
//  type parameter H - the type of GetHead container for the doubly linked list
//  type parameter I - the type of SetHead container for the doubly linked list
//  type parameter S - the type of a node or value that's also a SomeThis[S]
//  identifier ev - instance of typeclass DoubleLinkedList
//  identifier ev2 - instance of GetHead typeclass
//  identifier ev3 - instance of SetHead typeclass
//  identifier ev4 - instance of Convert typeclass
//  identifier h - list container from perspective of GetHead typeclass
//  identifier i - list container from perspective of SetHead typeclass
//  identifier a - list node

// GetHead and SetHead are two separate typeclasses because clients
// may need asymmetric instances
// Intuition behind this asymmetry:
//  1. most operations just need a GetHead
//  2. remove just needs a SetHead
//  3. prepend and foreachRemove* need GetHead and SetHead, but these can or may need to be asymmetrical

// GetHead is a typeclass to get the head of a doubly linked list
// for a container of type A that uses nodes of type B via an
// association of type C. For example GetHead[Room, Mob, NextInRoom].
trait GetHead[H, A, C] {
  def getHead(h: H): A // head node of list
}

final object GetHead {
  @inline final def getHead[H, A, C](h: H)(implicit ev: GetHead[H, A, C]): A = ev.getHead(h)
}

// SetHead is a typeclass to set the head of a doubly linked list
// for a container of type A that uses nodes of type B via an
// association of type C. For example SetHead[Room, Mob, NextInRoom].
trait SetHead[H, A, C] {
  def setHeadMaybeNull(doubleLinkedListContainer: H, newHeadMaybeNull: A): Unit // set head node of list; newHead may be null
  def setHeadNotNull(doubleLinkedListContainer: H, newHeadNotNull: A): Unit // set head node of list; newHeadNotNull not null; some clients need special behavior if newHead is known to be not null, eg. MobCommanders
}

// GetSetHead is a convenience amalgamation of GetHead and SetHead
// for (the majority of) clients whose needs aren't complex enough
// to need separate typeclass instances for GetHead/SetHead.
trait GetSetHead[H, A, C] extends GetHead[H, A, C] with SetHead[H, A, C]

// InferType is my solution to the problem of the DoubleLinkedList interface being
// rather "over" parameterized which prevents the compiler from interferring the
// correct type parameters to summon the correct implicit typeclass instances.
// Coincidentally for DLL the type params can usually be inferred with a single type
// hint (the type of the DLL node) and some DLL interface functions below take a `t:
// InferType[A]` so the caller can provide this type with `InferType[ConcreteA]`.
final object InferType {
  type InferType[A] = Option[A]
  def apply[A]: Option[A] = None // zero allocations when caller passes InferType[ConcreteA]
}

// DoubleLinkedList is a typeclass for a doubly linked list with nodes
// of type A that contains values of type B via an association of type
// C. For example DoubleLinkedList[Mob, Mob, NextInRoom]. null is used
// as the unlinked value instead of Option to minimize allocations.
// `A >: Null <: AnyRef` constrains A to types that are nullable.
// https://stackoverflow.com/questions/2336204/how-scala-generic-constraints-to-null
trait DoubleLinkedList[A >: Null <: AnyRef, B, C] {
  def value(a: A): B // value contained in A
  def next(a: A): A // next node in linked list
  def prev(a: A): A // previous node in linked list
  def setNext(a: A, next: A): Unit
  def setPrev(a: A, prev: A): Unit

  // NB all concrete method implementations should properly be on the
  // DoubleLinkedList object and take evidence of DoubleLinkedListHead and
  // DoubleLinkedList, but I left the impls here so that I could see the
  // entire DoubleLinkedList API on one screen in the DoubleLinkedList object
  // (because the methods on DoubleLinkedList forward here and are thus terse).

  // isEmpty returns true iff the list is empty. O(1)
  @inline final def isEmpty[H](h: H)(implicit ev2: GetHead[H, A, C]): Boolean = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    ev2.getHead(h) == null
  }

  // nonEmpty returns true iff the list is non empty. O(1)
  @inline final def nonEmpty[H](h: H)(implicit ev2: GetHead[H, A, C]): Boolean = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    ev2.getHead(h) != null
  }

  // atLeastTwo returns true iff the list has at least two elements. O(1)
  @inline final def atLeastTwo[H](h: H)(implicit ev2: GetHead[H, A, C]): Boolean = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    ev2.getHead(h) != null && next(ev2.getHead(h)) != null
  }

  // Forall returns true iff passed predicate is true for all values in list a. O(N)
  @inline final def forall[H](h: H, fn: B => Boolean)(implicit ev2: GetHead[H, A, C]): Boolean = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    forallInternal(ev2.getHead(h), fn)
  }
  @inline @tailrec private[this] final def forallInternal(a: A, fn: B => Boolean): Boolean = {
    if (a == null) true
    else if (fn(value(a))) forallInternal(next(a), fn)
    else false
  }

  // Exists returns true iff passed predicate is
  // true for at least one value in the list. O(N)
  @inline final def exists[H](h: H, fn: B => Boolean)(implicit ev2: GetHead[H, A, C]): Boolean = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    existsInternal(ev2.getHead(h), fn)
  }
  @inline @tailrec private[this] final def existsInternal(a: A, fn: B => Boolean): Boolean = {
    if (a == null) false
    else if (fn(value(a))) true
    else existsInternal(next(a), fn)
  }

  // Length returns the length of the list. WARNING O(N)
  @inline final def length[H](h: H)(implicit ev2: GetHead[H, A, C]): Int = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    lengthInternal(ev2.getHead(h), 0)
  }
  @inline @tailrec private[this] final def lengthInternal(a: A, c: Int): Int = {
    if (a == null) c
    else lengthInternal(next(a), c+1)
  }

  // Counts the number of list values which satisfy a predicate. O(N)
  @inline final def count[H](h: H, fn: B => Boolean)(implicit ev2: GetHead[H, A, C]): Int = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    countInternal(ev2.getHead(h), fn, 0)
  }
  @inline @tailrec private[this] final def countInternal(a: A, fn: B => Boolean, c: Int): Int = {
    if (a == null) c
    else if (fn(value(a))) countInternal(next(a), fn, c+1)
    else countInternal(next(a), fn, c)
  }

  // Finds the first node in the list satisfying a predicate
  // on its value, if any. O(N), allocates Some[A].
  @inline final def find[H](h: H, fn: B => Boolean)(implicit ev2: GetHead[H, A, C]): Option[A] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    findInternal(ev2.getHead(h), fn)
  }
  @inline @tailrec private[this] final def findInternal(a: A, fn: B => Boolean): Option[A] = {
    if (a == null) None
    else if (fn(value(a))) Some(a)
    else findInternal(next(a), fn)
  }

  // findSomeThis is identical to find except does zero allocations
  // because the found value is known to be a SomeThis.
  @inline final def findSomeThis[H, S >: A <: A with SomeThis[S]](h: H, fn: B => Boolean)(implicit ev2: GetHead[H, S, C]): Option[S] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    findSomeThisInternal(ev2.getHead(h), fn)(this)
  }
  @inline @tailrec private[this] final def findSomeThisInternal[S >: Null <: SomeThis[S]](s: S, fn: B => Boolean)(implicit ev: DoubleLinkedList[S, B, C]): Option[S] = {
    if (s == null) None
    else if (fn(ev.value(s))) s.someThis
    else findSomeThisInternal(ev.next(s), fn)
  }

  // Finds the first node in the list satisfying a predicate
  // on its converted value, if any. O(N), allocates Some[A]
  @inline final def findConvert[D, H](h: H, fn: D => Boolean)(implicit ev2: GetHead[H, A, C], ev4: Convert[B, D]): Option[A] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    findConvertInternal(ev2.getHead(h), fn)
  }
  @inline @tailrec private[this] final def findConvertInternal[D](a: A, fn: D => Boolean)(implicit ev4: Convert[B, D]): Option[A] = {
    if (a == null) return None
    val d = ev4.convert(value(a))
    if (d.isDefined && fn(d.get)) Some(a)
    else findConvertInternal(next(a), fn)
  }

  // Finds the the first node in the list whose value equals the passed b, if any.
  // This convenience function is equivalent to find(a, _==b). O(N), allocates Some[A]
  @inline final def findValue[H](h: H, b: B)(implicit ev2: GetHead[H, A, C]): Option[A] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(b != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    findValueInternal(ev2.getHead(h), b)
  }
  @inline @tailrec private[this] final def findValueInternal(a: A, b: B): Option[A] = {
    if (a == null) None
    else if (b == value(a)) Some(a)
    else findValueInternal(next(a), b)
  }

  // Finds the the first node in the list whose converted value
  // equals the passed d, if any. This convenience function is
  // equivalent to findConvert(a, _==d). O(N), allocates Some[A]
  @inline final def findValueConvert[D, H](h: H, d: D)(implicit ev2: GetHead[H, A, C], ev4: Convert[B, D]): Option[A] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    findValueConvertInternal(ev2.getHead(h), d)
  }
  @inline @tailrec private[this] final def findValueConvertInternal[D](a: A, d: D)(implicit ev4: Convert[B, D]): Option[A] = {
    if (a == null) return None
    val e = ev4.convert(value(a))
    if (e.isDefined && e.get == d) Some(a)
    else findValueConvertInternal(next(a), d)
  }

  // Remove passed `a` from its list. Removing during iteration
  // is supported. Precondition: `a` in the list. Postcondition:
  // `a` not in the list and `a`.next/prev set to null. O(1)
  @inline final def remove[I](i: I, a: A)(implicit ev3: SetHead[I, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(i != null)
      assert(a != null)
      DoubleLinkedList.assertDoublyLinked(getHead(a))(this)
    }
    if (next(a) != null) setPrev(next(a), prev(a))
    if (prev(a) == null) {
      // This A is head of list
      ev3.setHeadMaybeNull(i, next(a))
      @enableIf(noricmud.If.Sanity) val __ = {
        DoubleLinkedList.assertDoublyLinked(next(a))(this)
      }
    } else {
      setNext(prev(a), next(a))
      @enableIf(noricmud.If.Sanity) val __ = {
        DoubleLinkedList.assertDoublyLinked(getHead(a))(this)
      }
      setPrev(a, null)
    }
    setNext(a, null)
  }

  // clearList clears the passed list, setting its head to null and all of its
  // nodes' next/prev to null. Required eg. if a list's container is being destroyed,
  // so that the nodes involved in the list properly have next/prev set to null
  // prior to potential reuse. The passed postRemove is called for each removed
  // node, after the node is fully removed and so nodes passed to postRemove may be
  // arbitrarily modified (eg. to return the node to a DoubleLinkedList.Pool). O(N)
  @inline final def clearList[H, I](h: H, i: I, postRemove: Option[A => Unit])(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(i != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    val head = ev2.getHead(h)
    if (head != null) {
      ev3.setHeadMaybeNull(i, null)
      clearListInternal(next(head), postRemove)
      setNext(head, null)
      if (postRemove.isDefined) postRemove.get(head)
    }
  }
  @inline @tailrec private[this] final def clearListInternal(a: A, postRemove: Option[A => Unit]): Unit = {
    if (a == null) return
    val nextA = next(a)
    setNext(a, null)
    setPrev(a, null)
    if (postRemove.isDefined) postRemove.get(a)
    clearListInternal(nextA, postRemove)
  }

  // clearList clears the passed list, setting its head to null and all
  // of its nodes' next/prev to null. Each cleared node is returned to
  // the passed Pool via pool.free. Required eg. if a list's container
  // is being destroyed, so that the nodes involved in the list
  // properly have next/prev set to null prior to potential reuse. O(N)
  @inline final def clearListWithPool[H, I](h: H, i: I, pool: DoubleLinkedList.Pool[A, B, C])(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(i != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    val head = ev2.getHead(h)
    if (head != null) {
      ev3.setHeadMaybeNull(i, null)
      clearListWithPoolInternal(next(head), pool)
      setNext(head, null)
      pool.free(head)
    }
  }
  @inline @tailrec private[this] final def clearListWithPoolInternal(a: A, pool: DoubleLinkedList.Pool[A, B, C]): Unit = {
    if (a == null) return
    val nextA = next(a)
    setNext(a, null)
    setPrev(a, null)
    pool.free(a)
    clearListWithPoolInternal(nextA, pool)
  }

  // Prepend passed `a` to the list. Precondition: `a` not in any list. O(1)
  @inline final def prepend[H, I](h: H, i: I, a: A)(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(i != null)
      assert(a != null)
      assert(next(a) == null)
      assert(prev(a) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    setNext(a, ev2.getHead(h))
    if (ev2.getHead(h) != null) setPrev(ev2.getHead(h), a)
    ev3.setHeadNotNull(i, a)
  }

  // Foreach visits all values in the list with the passed fn. Removing during
  // iteration is supported (WARNING) for any node except nextA, ie. you may not
  // remove `next(a)` while processing `a` because nextA is cached on the stack
  // and always processed next. You may also use a foreachRemove* function. O(N)
  @inline final def foreach[H](h: H, fn: B => Unit)(implicit ev2: GetHead[H, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    foreachInternal(ev2.getHead(h), fn)
  }
  @inline @tailrec private[this] final def foreachInternal(a: A, fn: B => Unit): Unit = {
    if (a == null) return
    val nextA = next(a)
    fn(value(a))
    foreachInternal(nextA, fn)
  }

  // foreachRemoveFilter is similar to foreach except nodes are removed
  // from the list if the passed filter fn returns false. This allows the
  // client's passed fn to remove nodes during iteration (by way of the
  // filter function returning false). The passed postRemove is called for
  // each removed node, after the node is fully removed and so nodes passed
  // to postRemove may be arbitrarily modified (eg. to return the node to a
  // DoubleLinkedList.Pool). Behavior is undefined if the visit function calls
  // remove(node) _and_ asks foreachRemove* to also remove the node. O(N)
  @inline final def foreachRemoveFilter[H, I](h: H, i: I, fn: B => Boolean, postRemove: Option[A => Unit])(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(i != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    while (ev2.getHead(h) != null) {
      if (!fn(value(ev2.getHead(h)))) {
        // visit function returned false, remove head
        val nodeToBeRemoved = ev2.getHead(h)
        removeHead(h, i)
        if (postRemove.isDefined) postRemove.get(nodeToBeRemoved)
      } else {
        // head is now permanent head. Process tail
        var a = next(ev2.getHead(h))
        while (a != null) {
          val nextA = next(a)
          if (!fn(value(a))) {
            // visit function returned false, remove node
            removeNotHead(a)
            if (postRemove.isDefined) postRemove.get(a)
          }
          a = nextA
        }
        return // entire list processed
      }
    }
  }

  // foreachRemoveConvert is similar to foreach except nodes are removed from the
  // list if their values fail conversion. This allows the client function to remove
  // nodes during iteration (by way of node values failing conversion). The passed
  // postRemove is called for each removed node, after the node is fully removed and
  // so nodes passed to postRemove may be arbitrarily modified (eg. to return the
  // node to a DoubleLinkedList.Pool). Behavior is undefined if the visit function
  // calls remove(node) _and_ asks foreachRemove* to also remove the node. O(N)
  @inline final def foreachRemoveConvert[D, H, I](h: H, i: I, fn: D => Unit, postRemove: Option[A => Unit])(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C], ev4: Convert[B, D]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(i != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    while (ev2.getHead(h) != null) {
      ev4.convert(value(ev2.getHead(h))) match {
        case Some(d) => {
          fn(d)
          // head is now permanent head. Process tail
          var a = next(ev2.getHead(h))
          while (a != null) {
            val nextA = next(a)
            ev4.convert(value(a)) match {
              case Some(d) => fn(d)
              case None => {
                // conversion failed, remove node
                removeNotHead(a)
                if (postRemove.isDefined) postRemove.get(a)
              }
            }
            a = nextA
          }
          return // entire list processed
        }
        case None => {
          // conversion failed, remove head
          val nodeToBeRemoved = ev2.getHead(h)
          removeHead(h, i)
          if (postRemove.isDefined) postRemove.get(nodeToBeRemoved)
        }
      }
    }
  }

  // foreachRemoveConvertFilter is similar to foreach except nodes are removed
  // from the list if their values fail conversion or the passed filter fn returns
  // false. This allows the client function to remove nodes during iteration (by way
  // of node values failing conversion or if filter fn returns false). The passed
  // postRemove is called for each removed node, after the node is fully removed and
  // so nodes passed to postRemove may be arbitrarily modified (eg. to return the
  // node to a DoubleLinkedList.Pool). Behavior is undefined if the visit function
  // calls remove(node) _and_ asks foreachRemove* to also remove the node. O(N)
  @inline final def foreachRemoveConvertFilter[D, H, I](h: H, i: I, fn: D => Boolean, postRemove: Option[A => Unit])(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C], ev4: Convert[B, D]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      assert(i != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    while (ev2.getHead(h) != null) {
      ev4.convert(value(ev2.getHead(h))) match {
        case Some(d) => {
          if (!fn(d)) {
            // visit function returned false, head will be removed
          } else {
            // visit function returned true, head is now permanent head. Process tail
            var a = next(ev2.getHead(h))
            while (a != null) {
              val nextA = next(a)
              ev4.convert(value(a)) match {
                case Some(d) => if (!fn(d)) {
                  // visit function returned false, remove node
                  removeNotHead(a)
                  if (postRemove.isDefined) postRemove.get(a)
                }
                case None => {
                  // conversion failed, remove node
                  removeNotHead(a)
                  if (postRemove.isDefined) postRemove.get(a)
                }
              }
              a = nextA
            }
            return // entire list processed
          }
        }
        case None => // conversion failed, head will be removed
      }
      val nodeToBeRemoved = ev2.getHead(h)
      removeHead(h, i)
      if (postRemove.isDefined) postRemove.get(nodeToBeRemoved)
    }
  }

  // foldLeft applies a binary operator to a start value and all values
  // of the list, returning the result of these applications. Removing
  // during foldLeft is supported (WARNING) for any node except nextA,
  // ie. you may not remove `next(a)` while processing `a` because
  // nextA is cached on the stack and always processed next. O(N)
  @inline final def foldLeft[E, H](h: H, e: E)(fn: (E, B) => E)(implicit ev2: GetHead[H, A, C]): E = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    foldLeftInternal(ev2.getHead(h), e, fn)
  }
  @inline @tailrec private[this] final def foldLeftInternal[E](a: A, e: E, fn: (E, B) => E): E = {
    if (a == null) e
    else {
      val nextA = next(a)
      foldLeftInternal(nextA, fn(e, value(a)), fn)
    }
  }

  // flatMapToList creates a new List by mapping all values in the doubly linked list
  // using the passed fn, discarding values that map to None. O(N), allocates new List
  @inline final def flatMapToList[H, E](h: H, fn: B => Option[E])(implicit ev2: GetHead[H, A, C]): List[E] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    if (ev2.getHead(h) == null) return Nil
    var tmp = getLast(ev2.getHead(h)) // getLast() is @tailrec so flatMapToList() uses constant stack frames. We iterate backwards because List supports only O(1) prepend and must be built backwards
    var list: List[E] = Nil
    do {
      fn(value(tmp)) match {
        case Some(e) => list ::= e
        case None =>
      }
      tmp = prev(tmp)
    } while (tmp != null)
    list
  }

  // mapToList creates a new List by mapping all values in the
  // doubly linked list using the passed fn. O(N), allocates new List
  @inline final def mapToList[H, E](h: H, fn: B => E)(implicit ev2: GetHead[H, A, C]): List[E] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    if (ev2.getHead(h) == null) return Nil
    var tmp = getLast(ev2.getHead(h)) // getLast() is @tailrec so mapToList() uses constant stack frames. We iterate backwards because List supports only O(1) prepend and must be built backwards
    var list: List[E] = Nil
    do {
      list ::= fn(value(tmp))
      tmp = prev(tmp)
    } while (tmp != null)
    list
  }

  // toList creates a new List from the list with
  // the passed head `a`. O(N), allocates new List
  @inline final def toList[H](h: H)(implicit ev2: GetHead[H, A, C]): List[B] = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) == null || prev(ev2.getHead(h)) == null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    if (ev2.getHead(h) == null) return Nil
    var tmp = getLast(ev2.getHead(h)) // getLast() is @tailrec so toList() uses constant stack frames. We iterate backwards because List supports only O(1) prepend and must be built backwards
    var list: List[B] = Nil
    do {
      list ::= value(tmp)
      tmp = prev(tmp)
    } while (tmp != null)
    list
  }

  // Append `a` to the list with passed last. Returns `a`, the new last. `a` must
  // not be null, but last may be null. Clients usually don't keep track of a list's
  // last and instead use prepend; append is used to build lists efficently. O(1)
  @inline private final def append(a: A, last: A): A = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(a != null)
      if (last != null) assert(next(last) == null)
      DoubleLinkedList.assertDoublyLinked(last)(this)
    }
    setPrev(a, last)
    setNext(a, null)
    if (last != null) setNext(last, a)
    a
  }

  // removeHead removes the head of the list when that head is known to be not null.
  @inline private final def removeHead[H, I](h: H, i: I)(implicit ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(h != null)
      assert(ev2.getHead(h) != null)
      assert(prev(ev2.getHead(h)) == null)
      assert(i != null)
      DoubleLinkedList.assertDoublyLinked(ev2.getHead(h))(this)
    }
    val headToBeRemoved = ev2.getHead(h)
    if (next(headToBeRemoved) != null) setPrev(next(headToBeRemoved), null)
    ev3.setHeadMaybeNull(i, next(headToBeRemoved))
    setNext(headToBeRemoved, null)
    setPrev(headToBeRemoved, null)
  }

  // Flavor of remove called when `a` is known to not be list head.
  @inline private final def removeNotHead(a: A): Unit = {
    @enableIf(noricmud.If.Sanity) val __ = {
      assert(a != null)
      assert(prev(a) != null)
      DoubleLinkedList.assertDoublyLinked(getHead(a))(this)
    }
    if (next(a) != null) setPrev(next(a), prev(a))
    setNext(prev(a), next(a))
    setNext(a, null)
    setPrev(a, null)
  }

  // getHead returns head of `a`'s list, used for debug
  // purposes when a DoubleLinkedListHead is not in scope.
  @inline @tailrec private final def getHead(a: A): A = {
    if (a == null || prev(a) == null) a
    else getHead(prev(a))
  }

  // getLast returns the last node of `a`'s list.
  @inline @tailrec private final def getLast(a: A): A = {
    if (a == null || next(a) == null) a
    else getLast(next(a))
  }
}

final object DoubleLinkedList {
  import InferType.InferType // see doc on InferType

  // NB for public APIs that take postRemove: postRemove takes the place
  // of InferType[A] because if postRemove is defined then InferType is
  // not required and if postRemove is None then the client can still
  // use InferType in place of postRemove like: InferType[A => Unit]

  // NB DoubleLinkedList APIs which require an instance of both GetHead and
  // SetHead are overloaded in two flavors: one flavor where GetHead and
  // SetHead operate on the same list container type, ie. type parameters H
  // = I and only an instance `h` must be passed; and another flavor where
  // GetHead and SetHead operate on different list container types, ie.
  // type parameters H != I and both instances `h` and `i` must be passed.

  // Most clients shouldn't use DoubleLinkedList.value/next/prev
  // and instead should use the safe, convenient API below.
  @inline def value[A >: Null <: AnyRef, B, C](a: A)(implicit ev: DoubleLinkedList[A, B, C]) = ev.value(a)
  @inline def next[A >: Null <: AnyRef, B, C](a: A)(implicit ev: DoubleLinkedList[A, B, C]) = ev.next(a)
  @inline def prev[A >: Null <: AnyRef, B, C](a: A)(implicit ev: DoubleLinkedList[A, B, C]) = ev.prev(a)

  // TODO APIs that take functions should allow those functions to take a supertype of B, eg. instead of `B => Boolean` --> `F >: B, F => Boolean`
  // TODO unit tests with assertions at bottom in a val _ = {}
  //   partial list of test cases for foreachRemove*()
  //     in null
  //     in is only node in list and removed and now head is null
  //     [in, a] are both removed and now head is null
  //     in is removed and only other node in list is now head
  @inline def isEmpty[A >: Null <: AnyRef, B, C, H](h: H, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.isEmpty(h)
  @inline def nonEmpty[A >: Null <: AnyRef, B, C, H](h: H, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.nonEmpty(h)
  @inline def atLeastTwo[A >: Null <: AnyRef, B, C, H](h: H, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.atLeastTwo(h)
  @inline def forall[A >: Null <: AnyRef, B, C, H](h: H, fn: B => Boolean, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.forall(h, fn)
  @inline def exists[A >: Null <: AnyRef, B, C, H](h: H, fn: B => Boolean, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.exists(h, fn)
  @inline def length[A >: Null <: AnyRef, B, C, H](h: H, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.length(h) // WARNING length is O(N)
  @inline def count[A >: Null <: AnyRef, B, C, H](h: H, fn: B => Boolean, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.count(h, fn)
  // WARNING clients should use findSomeThis and other SomeThis variants where possible because they incur zero allocations, whereas non-SomeThis variants allocate a Some.
  @inline def find[A >: Null <: AnyRef, B, C, H](h: H, fn: B => Boolean, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.find(h, fn)
  @inline def findSomeThis[A >: Null <: AnyRef with SomeThis[A], B, C, H](h: H, fn: B => Boolean, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.findSomeThis(h, fn)
  @inline def findConvert[A >: Null <: AnyRef, B, C, D, H](h: H, fn: D => Boolean, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev4: Convert[B, D]) = ev.findConvert(h, fn)
  @inline def findValue[A >: Null <: AnyRef, B, C, H](h: H, b: B, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.findValue(h, b)
  @inline def findValueConvert[A >: Null <: AnyRef, B, C, D, H](h: H, d: D, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev4: Convert[B, D]) = ev.findValueConvert(h, d)
  @inline def remove[A >: Null <: AnyRef, B, C, I](i: I, a: A)(implicit ev: DoubleLinkedList[A, B, C], ev3: SetHead[I, A, C]) = ev.remove(i, a)
  @inline def clearList[A >: Null <: AnyRef, B, C, H](h: H, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[H /* not a typo, I = H in this overload */, A, C]) = ev.clearList(h, h, postRemove)
  @inline def clearList[A >: Null <: AnyRef, B, C, H, I](h: H, i: I, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]) = ev.clearList(h, i, postRemove)
  @inline def clearListWithPool[A >: Null <: AnyRef, B, C, H](h: H, pool: Pool[A, B, C])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[H /* not a typo, I = H in this overload */, A, C]) = ev.clearListWithPool(h, h, pool)
  @inline def clearListWithPool[A >: Null <: AnyRef, B, C, H, I](h: H, i: I, pool: Pool[A, B, C])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]) = ev.clearListWithPool(h, i, pool)
  @inline def prepend[A >: Null <: AnyRef, B, C, H](h: H, a: A)(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[H /* not a typo, I = H in this overload */, A, C]) = ev.prepend(h, h, a)
  @inline def prepend[A >: Null <: AnyRef, B, C, H, I](h: H, i: I, a: A)(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]) = ev.prepend(h, i, a)
  def foreach[A >: Null <: AnyRef, B, C, H](h: H, fn: B => Unit, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.foreach(h, fn)
  @inline def foreachRemoveFilter[A >: Null <: AnyRef, B, C, H](h: H, fn: B => Boolean, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[H /* not a typo, I = H in this overload */, A, C]) = ev.foreachRemoveFilter(h, h, fn, postRemove)
  @inline def foreachRemoveFilter[A >: Null <: AnyRef, B, C, H, I](h: H, i: I, fn: B => Boolean, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[I, A, C]) = ev.foreachRemoveFilter(h, i, fn, postRemove)
  @inline def foreachRemoveConvert[A >: Null <: AnyRef, B, C, D, H](h: H, fn: D => Unit, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[H /* not a typo, I = H in this overload */, A, C], ev4: Convert[B, D]) = ev.foreachRemoveConvert(h, h, fn, postRemove)
  @inline def foreachRemoveConvert[A >: Null <: AnyRef, B, C, D, H, I](h: H, i: I, fn: D => Unit, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[I, A, C], ev4: Convert[B, D]) = ev.foreachRemoveConvert(h, i, fn, postRemove)
  @inline def foreachRemoveConvertFilter[A >: Null <: AnyRef, B, C, D, H](h: H, fn: D => Boolean, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[H /* not a typo, I = H in this overload */, A, C], ev4: Convert[B, D]) = ev.foreachRemoveConvertFilter(h, h, fn, postRemove)
  @inline def foreachRemoveConvertFilter[A >: Null <: AnyRef, B, C, D, H, I](h: H, i: I, fn: D => Boolean, postRemove: Option[A => Unit])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C], ev3: SetHead[I, A, C], ev4: Convert[B, D]) = ev.foreachRemoveConvertFilter(h, i, fn, postRemove)
  def foldLeft[A >: Null <: AnyRef, B, C, E, H](h: H, e: E, t: InferType[A])(fn: (E, B) => E)(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.foldLeft(h, e)(fn)
  @inline def flatMapToList[A >: Null <: AnyRef, B, C, E, H](h: H, fn: B => Option[E], t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]): List[E] = ev.flatMapToList(h, fn)
  @inline def mapToList[A >: Null <: AnyRef, B, C, E, H](h: H, fn: B => E, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]): List[E] = ev.mapToList(h, fn)
  @inline def toList[A >: Null <: AnyRef, B, C, H](h: H, t: InferType[A])(implicit ev: DoubleLinkedList[A, B, C], ev2: GetHead[H, A, C]) = ev.toList(h)

  // fromList builds a new doubly linked list from the passed List.
  // Returns the head node of the built list. The passed `fn: B => A`
  // is expected to wrap the passed B in an A. Eg. the Bs are ActorRef
  // and `fn: B => A` gets a DoubleLinkedListDefault from a Pool.
  @inline def fromList[A >: Null <: AnyRef, B, C](bs: List[B], fn: B => A)(implicit ev: DoubleLinkedList[A, B, C]): A = {
    if (bs.isEmpty) return null
    val dllHead: A = fn(bs.head)
    var dllLast: A = dllHead
    var bsTail = bs.tail
    while (bsTail.nonEmpty) {
      dllLast = ev.append(fn(bsTail.head), dllLast)
      bsTail = bsTail.tail
    }
    dllHead
  }

  // fromList builds a new doubly linked list from the passed List where the DLL
  // node type is the same as the value type. Returns the head node of the built
  // list. Ie. typically we have DLL[A,B,C] and instead here we have DLL[A,A,C].
  // Eg. the `as` are Item which, in most cases, store their own DLL links.
  @inline def fromList[A >: Null <: AnyRef, C](as: List[A])(implicit ev: DoubleLinkedList[A, A, C]): A = {
    if (as.isEmpty) return null
    val dllHead: A = as.head
    var dllLast: A = dllHead
    var asTail = as.tail
    while (asTail.nonEmpty) {
      dllLast = ev.append(asTail.head, dllLast)
      asTail = asTail.tail
    }
    dllHead
  }

  // mapFromList converts the passed List[E] into a doubly linked list containing
  // those Es converted to Bs in nodes of type A. Returns the head node of the
  // built list. The passed `fn: B => A` is expected to wrap the passed B in
  // an A. Eg. the Es are FooImmutable, Bs are Foo, but Foo doesn't store its
  // own DLL links and `fn: B => A` gets a DoubleLinkedListDefault from a Pool.
  @inline def mapFromList[A >: Null <: AnyRef, B, C, E](es: List[E], fn: B => A, fn2: E => B)(implicit ev: DoubleLinkedList[A, B, C]): A = {
    if (es.isEmpty) return null
    val dllHead: A = fn(fn2(es.head))
    var dllLast: A = dllHead
    var esTail = es.tail
    while (esTail.nonEmpty) {
      dllLast = ev.append(fn(fn2(esTail.head)), dllLast)
      esTail = esTail.tail
    }
    dllHead
  }

  // mapFromList converts the passed List[E] into a doubly linked list containing
  // those Es converted into As and the DLL node type is the same as the value type.
  // Returns the head node of the built list. Ie. typically we have DLL[A,B,C] and
  // instead here we have DLL[A,A,C] with each E converted into an A. Eg. the Es are
  // ItemImmutable and As are Item which, in most cases, store their own DLL links.
  @inline def mapFromList[A >: Null <: AnyRef, C, E](es: List[E], fn: E => A)(implicit ev: DoubleLinkedList[A, A, C]): A = {
    if (es.isEmpty) return null
    val dllHead: A = fn(es.head)
    var dllLast: A = dllHead
    var esTail = es.tail
    while (esTail.nonEmpty) {
      dllLast = ev.append(fn(esTail.head), dllLast)
      esTail = esTail.tail
    }
    dllHead
  }

  // Pool is an object pool of nodes implementing DoubleLinkedList which
  // can help minimize allocations. Pool has zero allocations and O(1)
  // runtime, unless the pool has no nodes available on next(). Pool is not
  // tool against memory fragmentation which is highly magical in the JVM.
  // A separate tool against memory fragmentation (and allocations) is to
  // use contiguous arrays of primitives to represent a pool of objects, see
  // https://stackoverflow.com/questions/9632288/can-i-allocate-objects-contiguously-i
  // Also see // http://gameprogrammingpatterns.com/object-pool.html
  // . The passed makeA is expected to instantiate a new A.
  final class Pool[A >: Null <: AnyRef, B, C](initialSize: Int, makeA: => A)(implicit ev: DoubleLinkedList[A, B, C]) {
    private var nodeCount: Int = 1 // ie. because head is initialized to makeA
    private var head: A = makeA // singly-linked list (stack) of nodes in pool
    for (_ <- 0 to initialSize-2) free(makeA) // grow pool to initialSize

    // Free the passed A, returning it to the pool. Assumes A is currently
    // not participating in another list. WARNING ev.value(a) must be
    // cleared by the client if possible. Some instances of DoubleLinkedList
    // can't "clear" the value because A is itself the value (eg. Mob
    // nextInRoom). DoubleLinkedList doesn't offer clearValue() because
    // Pool would be the only client and it's unsafe in general. O(1)
    @inline def free(a: A): Unit = {
      nodeCount += 1
      @enableIf(noricmud.If.Sanity) val __ = {
        assert(ev.next(a) == null)
        assert(ev.prev(a) == null)
      }
      ev.setNext(a, head)
      head = a
    }

    // Next gets the next A for client use, removing it
    // from the pool. O(1) unless no nodes available.
    @inline def next(): A = {
      if (nodeCount < 1) {
        // pool is empty, instantiate new A for client
        makeA
      } else {
        nodeCount -= 1
        val a = head
        head = ev.next(head)
        ev.setNext(a, null)
        a
      }
    }
  }

  @enableIf(noricmud.If.Sanity)
  @inline private def assertDoublyLinked[A >: Null <: AnyRef, B, C](as: A)(implicit ev: DoubleLinkedList[A, B, C]): Unit = {
    if (as == null) return
    import scala.collection._
    val seen = mutable.Set[A]()
    var err = ""
    var s = ""
    var i = 0
    var prev: A = ev.prev(as)
    var a = as
    while (a != null) {
      if (seen.contains(a)) throw new RuntimeException(s"cycle in list $as $a $seen")
      seen.add(a)
      if (i > 0 && prev != ev.prev(a)) {
        err += s"\nlinked list isn't double, prev=$prev, a.prev=${ev.prev(a)}, a=$a"
      } else if (i < 1 && ev.prev(a) != null) {
        err += s"\n head of linked list has prev != null, head.prev=${ev.prev(a)}, head=$a"
      }
      s += a.toString + "-"
      prev = a
      a = ev.next(a)
      i += 1
    }
    s += s"null $err"
    if (err != "") throw new RuntimeException(s)
  }
}

// DoubleLinkedListDefault is a convenience class to serve as the
// node type for DoubleLinkedList when it's unsuitable for the
// value type to contain its own next/prev, eg. for 3rd-party types.
final class DoubleLinkedListDefault[A](var v: A) {
  var next: DoubleLinkedListDefault[A] = null
  var prev: DoubleLinkedListDefault[A] = null
}

final object DoubleLinkedListDefault {
  // Make a typeclass instance of DoubleLinkedList
  // for use with DoubleLinkedListDefault
  def doubleLinkedListNodeDefaultDLL[A, C]: DoubleLinkedList[DoubleLinkedListDefault[A], A, C] = new DoubleLinkedList[DoubleLinkedListDefault[A], A, C] {
    type T = DoubleLinkedListDefault[A]
    @inline def value(a: T) = a.v
    @inline def next(a: T) = a.next
    @inline def prev(a: T) = a.prev
    @inline def setNext(a: T, b: T) = a.next = b
    @inline def setPrev(a: T, b: T) = a.prev = b
  }
}