         get {
             return "\(String(key)): \(String(value))"
         }
+    }
+}
+
+public struct ListItemGenerator <Key: Hashable, Value>: GeneratorType {
+    public typealias Element = Value
+    var currentItem: ListItem<Key, Value>?
+    
+    mutating public func next() -> Value? {
+        guard let i = currentItem else { return nil }
+        currentItem = i.nextItem
+        return i.value
     }
 }
 

    /// for testing, don't rely on this
    var size: UInt {
        get {
            var acc: UInt = 0
            apply({ item in
                acc = acc + self.sizeOfItem(item.value)
            })
            return acc
        }
    }

        guard !(item === head) else { return }
        removeItemFromList(item)
        if let oldHead = head {
            item.nextItem = oldHead
            oldHead.prevItem = item
        } else {
            // list empty, item is also the tail
            tail = item
        }
        item.prevItem = nil
        head = item
    }
    
    func removeItemFromList(item: ListItem<Key, Value>) {
        if let prev = item.prevItem {
            prev.nextItem = item.nextItem
        }
        if let next = item.nextItem {
            next.prevItem = item.prevItem
        }
        if item === tail {
            tail = item.prevItem
        }
    }
}

extension LRUCache: SequenceType {
    public func generate() -> ListItemGenerator<Key, Value> {
        return ListItemGenerator(currentItem: head)
    }
}

extension LRUCache {
    public var descriptionString: String {
        get {
            var acc: [String] = map { return String($0) }
            acc.append("•")
            return acc.joinWithSeparator("\n")
        }
