jtulach@402: package org.apidesign.effectivelist
jtulach@402: 
jtulach@402: /** 
jtulach@402:  * Implementation of add and remove efficient list. It has just one
jtulach@402:  * restriction - its items need to carry additional information to help
jtulach@402:  * the list to be effective. All items must extend trait {@link Listable}:
jtulach@402:  * <pre>
jtulach@402:  * <b>case class</b> Person(name : String) <b>extends</b> Listable[Person]
jtulach@402:  * </pre>
jtulach@402:  */
jtulach@403: // BEGIN: effectivelist.list
jtulach@402: final class List[T <: Listable[T]] {
jtulach@402:   private var item : T = _
jtulach@402:   private final var EMPTY : T = _
jtulach@402:   
jtulach@402:   final def get(index : Int) : T = {
jtulach@402:     var pos : T = item;
jtulach@402:     for (i <- 1 to index) {
jtulach@402:       pos = pos.next;
jtulach@402:       if (pos == item) {
jtulach@402:         throw new IndexOutOfBoundsException()
jtulach@402:       }
jtulach@402:     }
jtulach@402:     return pos
jtulach@402:   }
jtulach@402:   
jtulach@402:   final def size() : Int = {
jtulach@402:     if (item == EMPTY) {
jtulach@402:       return 0
jtulach@402:     }
jtulach@402:     var size = 0
jtulach@402:     var pos : T = item
jtulach@402:     do {
jtulach@402:       size = size + 1
jtulach@402:       pos = pos.next
jtulach@402:     } while (pos != item)
jtulach@402:     return size
jtulach@402:   }
jtulach@402:   
jtulach@402:   final def add(toAdd : T) : Boolean = {
jtulach@402:     if (toAdd.prev != EMPTY) {
jtulach@402:       return false
jtulach@402:     }
jtulach@402:     
jtulach@402:     if (item == null) {
jtulach@402:       item = toAdd
jtulach@402:       toAdd.next = toAdd
jtulach@402:       toAdd.prev = toAdd
jtulach@402:       return true
jtulach@402:     } else {
jtulach@402:       toAdd.prev = item.prev
jtulach@402:       item.prev.next = toAdd
jtulach@402:       item.prev = toAdd
jtulach@402:       toAdd.next = item
jtulach@402:       return true
jtulach@402:     }
jtulach@402:   }
jtulach@402:   final def remove(toRemove : T) : Boolean = {
jtulach@402:     if (toRemove.prev == EMPTY) {
jtulach@402:       return false
jtulach@402:     } else {
jtulach@402:       toRemove.prev.next = toRemove.next
jtulach@402:       toRemove.next.prev = toRemove.prev;
jtulach@402:       if (item.next == item) {
jtulach@402:         item = EMPTY
jtulach@402:       }
jtulach@402:       if (item == toRemove) {
jtulach@402:         item = toRemove.next
jtulach@402:       }
jtulach@402:       toRemove.next = EMPTY
jtulach@402:       toRemove.prev = EMPTY
jtulach@402:       return true
jtulach@402:     }
jtulach@402:   }
jtulach@402: }
jtulach@403: // END: effectivelist.list