Parent

Namespace

Included Modules

LinkedList

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.

Public Class Methods

new() click to toggle source
    # File lib/more/facets/linkedlist.rb, line 60
60:         def initialize
61:                 @head = Node.new
62:                 @tail = Node.new
63:                 @lookup = Hash.new
64:                 node_join(@head,@tail)
65:         end

Public Instance Methods

[](v) click to toggle source
    # File lib/more/facets/linkedlist.rb, line 67
67:         def [](v)
68:                 @lookup[v].value
69:         end
[]=(k,v) click to toggle source
    # 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
delete(k) click to toggle source
    # 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
each() click to toggle source
     # 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
empty?() click to toggle source
    # File lib/more/facets/linkedlist.rb, line 83
83:         def empty?
84:                 @lookup.empty?
85:         end
first() click to toggle source
    # File lib/more/facets/linkedlist.rb, line 93
93:         def first
94:                 @head.next_node.value
95:         end
last() click to toggle source
    # File lib/more/facets/linkedlist.rb, line 97
97:         def last
98:                 @tail.prev_node.value
99:         end
length() click to toggle source
     # File lib/more/facets/linkedlist.rb, line 161
161:         def length
162:                 @lookup.length
163:         end
pop() click to toggle source
     # 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
push(v) click to toggle source
     # 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
queue() click to toggle source
     # 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
shift() click to toggle source
     # 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
to_a() click to toggle source
     # 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
unshift(v) click to toggle source
     # 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

Private Instance Methods

node_delete(n) click to toggle source
     # 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
node_join(a,b) click to toggle source
     # File lib/more/facets/linkedlist.rb, line 189
189:         def node_join(a,b)
190:                 a.next_node = b
191:                 b.prev_node = a
192:         end
node_purge(n) click to toggle source
     # File lib/more/facets/linkedlist.rb, line 179
179:         def node_purge(n)
180:                 node_join(n.prev_node,n.next_node)
181:                 v = n.value
182:                 n.value = nil
183:                 n.key = nil
184:                 n.next_node = nil
185:                 n.prev_node = nil
186:                 v
187:         end

Disabled; run with --debug to generate this.

[Validate]

Generated with the Darkfish Rdoc Generator 1.1.6.