1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/samples/effectivelist/src/org/apidesign/effectivelist/List.scala	Fri Aug 31 20:16:57 2012 +0200
     1.3 @@ -0,0 +1,74 @@
     1.4 +package org.apidesign.effectivelist
     1.5 +
     1.6 +/** 
     1.7 + * Implementation of add and remove efficient list. It has just one
     1.8 + * restriction - its items need to carry additional information to help
     1.9 + * the list to be effective. All items must extend trait {@link Listable}:
    1.10 + * <pre>
    1.11 + * <b>case class</b> Person(name : String) <b>extends</b> Listable[Person]
    1.12 + * </pre>
    1.13 + */
    1.14 +final class List[T <: Listable[T]] {
    1.15 +  private var item : T = _
    1.16 +  private final var EMPTY : T = _
    1.17 +  
    1.18 +  final def get(index : Int) : T = {
    1.19 +    var pos : T = item;
    1.20 +    for (i <- 1 to index) {
    1.21 +      pos = pos.next;
    1.22 +      if (pos == item) {
    1.23 +        throw new IndexOutOfBoundsException()
    1.24 +      }
    1.25 +    }
    1.26 +    return pos
    1.27 +  }
    1.28 +  
    1.29 +  final def size() : Int = {
    1.30 +    if (item == EMPTY) {
    1.31 +      return 0
    1.32 +    }
    1.33 +    var size = 0
    1.34 +    var pos : T = item
    1.35 +    do {
    1.36 +      size = size + 1
    1.37 +      pos = pos.next
    1.38 +    } while (pos != item)
    1.39 +    return size
    1.40 +  }
    1.41 +  
    1.42 +  final def add(toAdd : T) : Boolean = {
    1.43 +    if (toAdd.prev != EMPTY) {
    1.44 +      return false
    1.45 +    }
    1.46 +    
    1.47 +    if (item == null) {
    1.48 +      item = toAdd
    1.49 +      toAdd.next = toAdd
    1.50 +      toAdd.prev = toAdd
    1.51 +      return true
    1.52 +    } else {
    1.53 +      toAdd.prev = item.prev
    1.54 +      item.prev.next = toAdd
    1.55 +      item.prev = toAdd
    1.56 +      toAdd.next = item
    1.57 +      return true
    1.58 +    }
    1.59 +  }
    1.60 +  final def remove(toRemove : T) : Boolean = {
    1.61 +    if (toRemove.prev == EMPTY) {
    1.62 +      return false
    1.63 +    } else {
    1.64 +      toRemove.prev.next = toRemove.next
    1.65 +      toRemove.next.prev = toRemove.prev;
    1.66 +      if (item.next == item) {
    1.67 +        item = EMPTY
    1.68 +      }
    1.69 +      if (item == toRemove) {
    1.70 +        item = toRemove.next
    1.71 +      }
    1.72 +      toRemove.next = EMPTY
    1.73 +      toRemove.prev = EMPTY
    1.74 +      return true
    1.75 +    }
    1.76 +  }
    1.77 +}