LinkedList implements a simple doubly linked list with efficient hash-like element access.
This is a simple linked list implementation with efficient random access of data elements. It was inspired by George Moscovitis’ LRUCache implementation found in Facets 1.7.30, but unlike the linked list in that cache, this one does not require the use of a mixin on any class to be stored. The linked list provides the push, pop, shift, unshift, first, last, delete and length methods which work just like their namesakes in the Array class, but it also supports setting and retrieving values by key, just like a hash.
LinkedList was ported from the original in Kirk Hanes IOWA web framework.
# File lib/more/facets/linkedlist.rb, line 67 67: def [](v) 68: @lookup[v].value 69: end
# File lib/more/facets/linkedlist.rb, line 71 71: def []=(k,v) 72: if @lookup.has_key?(k) 73: @lookup[k].value = v 74: else 75: n = Node.new(k,v,@head,@head.next_node) 76: node_join(n,@head.next_node) 77: node_join(@head,n) 78: @lookup[k] = n 79: end 80: v 81: end
# File lib/more/facets/linkedlist.rb, line 87 87: def delete(k) 88: n = @lookup.delete(k) 89: v = n ? node_purge(n) : nil 90: v 91: end
# File lib/more/facets/linkedlist.rb, line 165 165: def each 166: n = @head 167: while (n = n.next_node) and n != @tail 168: yield(n.key,n.value) 169: end 170: end
# File lib/more/facets/linkedlist.rb, line 83 83: def empty? 84: @lookup.empty? 85: end
# File lib/more/facets/linkedlist.rb, line 93 93: def first 94: @head.next_node.value 95: end
# File lib/more/facets/linkedlist.rb, line 97 97: def last 98: @tail.prev_node.value 99: end
# File lib/more/facets/linkedlist.rb, line 161 161: def length 162: @lookup.length 163: end
# File lib/more/facets/linkedlist.rb, line 122 122: def pop 123: k = @tail.prev_node.key 124: n = @lookup.delete(k) 125: node_delete(n) if n 126: end
# File lib/more/facets/linkedlist.rb, line 128 128: def push(v) 129: if @lookup.has_key?(v) 130: n = @lookup[v] 131: node_delete(n) 132: node_join(@tail.prev_node,n) 133: node_join(n,@tail) 134: else 135: n = Node.new(v,v,@tail.prev_node,@tail) 136: node_join(@tail.prev_node,n) 137: node_join(n,@tail) 138: @lookup[v] = n 139: end 140: v 141: end
# File lib/more/facets/linkedlist.rb, line 143 143: def queue 144: r = [] 145: n = @head 146: while (n = n.next_node) and n != @tail 147: r << n.key 148: end 149: r 150: end
# File lib/more/facets/linkedlist.rb, line 101 101: def shift 102: k = @head.next_node.key 103: n = @lookup.delete(k) 104: node_delete(n) if n 105: end
# File lib/more/facets/linkedlist.rb, line 152 152: def to_a 153: r = [] 154: n = @head 155: while (n = n.next_node) and n != @tail 156: r << n.value 157: end 158: r 159: end
# File lib/more/facets/linkedlist.rb, line 107 107: def unshift(v) 108: if @lookup.has_key?(v) 109: n = @lookup[v] 110: node_delete(n) 111: node_join(n,@head.next_node) 112: node_join(@head,n) 113: else 114: n = Node.new(v,v,@head,@head.next_node) 115: node_join(n,@head.next_node) 116: node_join(@head,n) 117: @lookup[v] = n 118: end 119: v 120: end
# File lib/more/facets/linkedlist.rb, line 174 174: def node_delete(n) 175: node_join(n.prev_node,n.next_node) 176: v = n.value 177: end
Disabled; run with --debug to generate this.
Generated with the Darkfish Rdoc Generator 1.1.6.