| author | Jaroslav Tulach <jtulach@netbeans.org> |
| Sun, 02 Sep 2012 22:00:13 +0200 | |
| changeset 403 | ebe08056c60c |
| parent 402 | e25dbfce40e9 |
| permissions | -rw-r--r-- |
| jtulach@402 | 1 |
package org.apidesign.effectivelist |
| jtulach@402 | 2 |
|
| jtulach@402 | 3 |
/** |
| jtulach@402 | 4 |
* Implementation of add and remove efficient list. It has just one |
| jtulach@402 | 5 |
* restriction - its items need to carry additional information to help |
| jtulach@402 | 6 |
* the list to be effective. All items must extend trait {@link Listable}:
|
| jtulach@402 | 7 |
* <pre> |
| jtulach@402 | 8 |
* <b>case class</b> Person(name : String) <b>extends</b> Listable[Person] |
| jtulach@402 | 9 |
* </pre> |
| jtulach@402 | 10 |
*/ |
| jtulach@403 | 11 |
// BEGIN: effectivelist.list |
| jtulach@402 | 12 |
final class List[T <: Listable[T]] {
|
| jtulach@402 | 13 |
private var item : T = _ |
| jtulach@402 | 14 |
private final var EMPTY : T = _ |
| jtulach@402 | 15 |
|
| jtulach@402 | 16 |
final def get(index : Int) : T = {
|
| jtulach@402 | 17 |
var pos : T = item; |
| jtulach@402 | 18 |
for (i <- 1 to index) {
|
| jtulach@402 | 19 |
pos = pos.next; |
| jtulach@402 | 20 |
if (pos == item) {
|
| jtulach@402 | 21 |
throw new IndexOutOfBoundsException() |
| jtulach@402 | 22 |
} |
| jtulach@402 | 23 |
} |
| jtulach@402 | 24 |
return pos |
| jtulach@402 | 25 |
} |
| jtulach@402 | 26 |
|
| jtulach@402 | 27 |
final def size() : Int = {
|
| jtulach@402 | 28 |
if (item == EMPTY) {
|
| jtulach@402 | 29 |
return 0 |
| jtulach@402 | 30 |
} |
| jtulach@402 | 31 |
var size = 0 |
| jtulach@402 | 32 |
var pos : T = item |
| jtulach@402 | 33 |
do {
|
| jtulach@402 | 34 |
size = size + 1 |
| jtulach@402 | 35 |
pos = pos.next |
| jtulach@402 | 36 |
} while (pos != item) |
| jtulach@402 | 37 |
return size |
| jtulach@402 | 38 |
} |
| jtulach@402 | 39 |
|
| jtulach@402 | 40 |
final def add(toAdd : T) : Boolean = {
|
| jtulach@402 | 41 |
if (toAdd.prev != EMPTY) {
|
| jtulach@402 | 42 |
return false |
| jtulach@402 | 43 |
} |
| jtulach@402 | 44 |
|
| jtulach@402 | 45 |
if (item == null) {
|
| jtulach@402 | 46 |
item = toAdd |
| jtulach@402 | 47 |
toAdd.next = toAdd |
| jtulach@402 | 48 |
toAdd.prev = toAdd |
| jtulach@402 | 49 |
return true |
| jtulach@402 | 50 |
} else {
|
| jtulach@402 | 51 |
toAdd.prev = item.prev |
| jtulach@402 | 52 |
item.prev.next = toAdd |
| jtulach@402 | 53 |
item.prev = toAdd |
| jtulach@402 | 54 |
toAdd.next = item |
| jtulach@402 | 55 |
return true |
| jtulach@402 | 56 |
} |
| jtulach@402 | 57 |
} |
| jtulach@402 | 58 |
final def remove(toRemove : T) : Boolean = {
|
| jtulach@402 | 59 |
if (toRemove.prev == EMPTY) {
|
| jtulach@402 | 60 |
return false |
| jtulach@402 | 61 |
} else {
|
| jtulach@402 | 62 |
toRemove.prev.next = toRemove.next |
| jtulach@402 | 63 |
toRemove.next.prev = toRemove.prev; |
| jtulach@402 | 64 |
if (item.next == item) {
|
| jtulach@402 | 65 |
item = EMPTY |
| jtulach@402 | 66 |
} |
| jtulach@402 | 67 |
if (item == toRemove) {
|
| jtulach@402 | 68 |
item = toRemove.next |
| jtulach@402 | 69 |
} |
| jtulach@402 | 70 |
toRemove.next = EMPTY |
| jtulach@402 | 71 |
toRemove.prev = EMPTY |
| jtulach@402 | 72 |
return true |
| jtulach@402 | 73 |
} |
| jtulach@402 | 74 |
} |
| jtulach@402 | 75 |
} |
| jtulach@403 | 76 |
// END: effectivelist.list |