Class: Hashery::LinkedList

Inherits:
Object show all
Includes:
Enumerable
Defined in:
lib/hashery/linked_list.rb

Overview

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.

Acknowledgements

LinkedList is based on the LinkedList library by Kirk Haines.

Copyright © 2006 Kirk Haines <[email protected]>.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ LinkedList

Initialize new LinkedList instance.



46
47
48
49
50
51
52
 
# File 'lib/hashery/linked_list.rb', line 46

def initialize
  @head   = Node.new
  @tail   = Node.new
  @lookup = Hash.new

  node_join(@head,@tail)
end

Instance Method Details

#[](key) ⇒ Object

Lookup entry by key.



57
58
59
 
# File 'lib/hashery/linked_list.rb', line 57

def [](key)
  @lookup[key].value
end

#[]=(k, v) ⇒ Object

Add node to linked list.



64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/hashery/linked_list.rb', line 64

def []=(k,v)
  if @lookup.has_key?(k)
    @lookup[k].value = v
  else
    n = Node.new(k,v,@head,@head.next_node)
    node_join(n,@head.next_node)
    node_join(@head,n)
    @lookup[k] = n
  end
  v
end

#delete(key) ⇒ Object

Remove node idenified by key.



86
87
88
89
90
 
# File 'lib/hashery/linked_list.rb', line 86

def delete(key)
  n = @lookup.delete(key)
  v = n ? node_purge(n) : nil
  v
end

#each ⇒ Object

Iterate over nodes, starting with the head node and ending with the tail node.



203
204
205
206
207
208
 
# File 'lib/hashery/linked_list.rb', line 203

def each
  n = @head
  while (n = n.next_node) and n != @tail
    yield(n.key,n.value)
  end
end

#empty? ⇒ Boolean

Is linked list empty?

Returns:

  • (Boolean) 


79
80
81
 
# File 'lib/hashery/linked_list.rb', line 79

def empty?
  @lookup.empty?
end

#first ⇒ Object

Get value of first node.



95
96
97
 
# File 'lib/hashery/linked_list.rb', line 95

def first
  @head.next_node.value
end

#last ⇒ Object

Get value of last node.



102
103
104
 
# File 'lib/hashery/linked_list.rb', line 102

def last
  @tail.prev_node.value
end

#length ⇒ Object Also known as: size

Number of nodes.



193
194
195
 
# File 'lib/hashery/linked_list.rb', line 193

def length
  @lookup.length
end

#node_delete(n) ⇒ Object (private)

Delete a node.

Parameters:

  • n —

    A node.



217
218
219
220
 
# File 'lib/hashery/linked_list.rb', line 217

def node_delete(n)
  node_join(n.prev_node,n.next_node)
  v = n.value
end

#node_join(a, b) ⇒ Object (private)

Join two nodes.

Parameters:

  • a —

    A node.

  • b —

    A node.



242
243
244
245
 
# File 'lib/hashery/linked_list.rb', line 242

def node_join(a,b)
  a.next_node = b
  b.prev_node = a
end

#node_purge(n) ⇒ Object (private)

Purge a node.

Parameters:

  • n —

    A node.



227
228
229
230
231
232
233
234
235
 
# File 'lib/hashery/linked_list.rb', line 227

def node_purge(n)
  node_join(n.prev_node,n.next_node)
  v = n.value
  n.value = nil
  n.key = nil
  n.next_node = nil
  n.prev_node = nil
  v
end

#pop ⇒ Object 



136
137
138
139
140
 
# File 'lib/hashery/linked_list.rb', line 136

def pop
  k = @tail.prev_node.key
  n = @lookup.delete(k)
  node_delete(n) if n
end

#push(v) ⇒ Object Also known as: << 



145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/hashery/linked_list.rb', line 145

def push(v)
  if @lookup.has_key?(v)
    n = @lookup[v]
    node_delete(n)
    node_join(@tail.prev_node,n)
    node_join(n,@tail)
  else
    n = Node.new(v,v,@tail.prev_node,@tail)
    node_join(@tail.prev_node,n)
    node_join(n,@tail)
    @lookup[v] = n
  end
  v
end

#queue ⇒ Array

Produces an Array of key values.

Returns:

  • (Array) —

    Returns Array.



167
168
169
170
171
172
173
174
 
# File 'lib/hashery/linked_list.rb', line 167

def queue
  r = []
  n = @head
  while (n = n.next_node) and n != @tail
    r << n.key
  end
  r
end

#shift ⇒ Object 



109
110
111
112
113
 
# File 'lib/hashery/linked_list.rb', line 109

def shift
  k = @head.next_node.key
  n = @lookup.delete(k)
  node_delete(n) if n
end

#to_a ⇒ Array

Converts to an Array of node values.

Returns:

  • (Array) —

    Returns Array.



181
182
183
184
185
186
187
188
 
# File 'lib/hashery/linked_list.rb', line 181

def to_a
  r = []
  n = @head
  while (n = n.next_node) and n != @tail
    r << n.value
  end
  r
end

#unshift(v) ⇒ Object 



118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/hashery/linked_list.rb', line 118

def unshift(v)
  if @lookup.has_key?(v)
    n = @lookup[v]
    node_delete(n)
    node_join(n,@head.next_node)
    node_join(@head,n)
  else
    n = Node.new(v,v,@head,@head.next_node)
    node_join(n,@head.next_node)
    node_join(@head,n)
    @lookup[v] = n
  end
  v
end