File: linked_list.rb

package info (click to toggle)
ruby-hashery 2.1.2-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid
  • size: 404 kB
  • sloc: ruby: 2,997; makefile: 7
file content (249 lines) | stat: -rw-r--r-- 4,576 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
require 'enumerator'

module Hashery

  # 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 (C) 2006 Kirk Haines <khaines@enigo.com>.
  #
  class LinkedList

    include Enumerable

    # Represents a single node of the linked list.
    #
    class Node
      attr_accessor :key, :value, :prev_node, :next_node

      def initialize(key=nil,value=nil,prev_node=nil,next_node=nil)
        @key = key
        @value = value
        @prev_node = prev_node
        @next_node = next_node
      end
    end

    #
    # Initialize new LinkedList instance.
    #
    def initialize
      @head   = Node.new
      @tail   = Node.new
      @lookup = Hash.new

      node_join(@head,@tail)
    end

    #
    # Lookup entry by key.
    #
    def [](key)
      @lookup[key].value
    end

    #
    # Add node to linked list.
    #
    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

    #
    # Is linked list empty?
    #
    def empty?
      @lookup.empty?
    end

    #
    # Remove node idenified by key.
    #
    def delete(key)
      n = @lookup.delete(key)
      v = n ? node_purge(n) : nil
      v
    end

    #
    # Get value of first node.
    #
    def first
      @head.next_node.value
    end

    #
    # Get value of last node.
    #
    def last
      @tail.prev_node.value
    end

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

    #
    #
    #
    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

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

    #
    #
    #
    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

    alias :<< :push

    #
    # Produces an Array of key values.
    #
    # Returns [Array].
    #
    def queue
      r = []
      n = @head
      while (n = n.next_node) and n != @tail
        r << n.key
      end
      r
    end

    #
    # Converts to an Array of node values.
    #
    # Returns [Array].
    #
    def to_a
      r = []
      n = @head
      while (n = n.next_node) and n != @tail
        r << n.value
      end
      r
    end

    #
    # Number of nodes.
    #
    def length
      @lookup.length
    end

    alias size length

    #
    # Iterate over nodes, starting with the head node
    # and ending with the tail node.
    #
    def each
      n = @head
      while (n = n.next_node) and n != @tail
        yield(n.key,n.value)
      end
    end

  private

    #
    # Delete a node.
    #
    # n - A node.
    #
    def node_delete(n)
      node_join(n.prev_node,n.next_node)
      v = n.value
    end

    #
    # Purge a node.
    #
    # n - A node.
    #
    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

    # Join two nodes.
    #
    # a - A node.
    # b - A node.
    #
    def node_join(a,b)
      a.next_node = b
      b.prev_node = a
    end

  end

end