package org.apidesign.effectivelist

/** 

 * Implementation of add and remove efficient list. It has just one

 * restriction - its items need to carry additional information to help

 * the list to be effective. All items must extend trait {@link Listable}:

 * <pre>

 * <b>case class</b> Person(name : String) <b>extends</b> Listable[Person]

 * </pre>

 */

final class List[T <: Listable[T]] {

  private var item : T = _

  private final var EMPTY : T = _

  final def get(index : Int) : T = {

    var pos : T = item;

    for (i <- 1 to index) {

      pos = pos.next;

      if (pos == item) {

        throw new IndexOutOfBoundsException()

      }

    }

    return pos

  }

  final def size() : Int = {

    if (item == EMPTY) {

      return 0

    }

    var size = 0

    var pos : T = item

    do {

      size = size + 1

      pos = pos.next

    } while (pos != item)

    return size

  }

  final def add(toAdd : T) : Boolean = {

    if (toAdd.prev != EMPTY) {

      return false

    }

    if (item == null) {

      item = toAdd

      toAdd.next = toAdd

      toAdd.prev = toAdd

      return true

    } else {

      toAdd.prev = item.prev

      item.prev.next = toAdd

      item.prev = toAdd

      toAdd.next = item

      return true

    }

  }

  final def remove(toRemove : T) : Boolean = {

    if (toRemove.prev == EMPTY) {

      return false

    } else {

      toRemove.prev.next = toRemove.next

      toRemove.next.prev = toRemove.prev;

      if (item.next == item) {

        item = EMPTY

      }

      if (item == toRemove) {

        item = toRemove.next

      }

      toRemove.next = EMPTY

      toRemove.prev = EMPTY

      return true

    }

  }

}