Class: StrokeDB::InvertedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/strokedb/data_structures/inverted_list.rb

Defined Under Namespace

Classes: HeadNode, Node, TailNode

Constant Summary collapse

SEPARATOR = 
"\x01"
TERMINATOR = 
"\x02"

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#each_consecutive_pair, #group_by, #map_with_index

Constructor Details

#initialize(cut_level = nil) ⇒ InvertedList

Returns a new instance of InvertedList.



10
11
12
13
14
15
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 10

def initialize(cut_level = nil)
	@cut_level = cut_level
	@head = HeadNode.new
	@tail = TailNode.new
	@head.forward[0] = @tail
end

Instance Attribute Details

#cut_level ⇒ Object

Returns the value of attribute cut_level.



8
9
10
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 8

def cut_level
  @cut_level
end

#default ⇒ Object

Returns the value of attribute default.



8
9
10
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 8

def default
  @default
end

#head ⇒ Object

Returns the value of attribute head.



8
9
10
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 8

def head
  @head
end

#tail ⇒ Object

Returns the value of attribute tail.



8
9
10
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 8

def tail
  @tail
end

Instance Method Details

#debug_dump ⇒ Object 



142
143
144
145
146
147
148
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 142

def debug_dump
  s = ""
  each do |n|
    s << "#{n.key.inspect}: #{n.values.inspect}\n"
   end
   s
end

#delete(slots, data) ⇒ Object 



61
62
63
64
65
66
67
68
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 61

def delete(slots, data)
  slots.each do |key, value|
    value = value.to_s
    key = key.to_s
    prefix = value + SEPARATOR + key + TERMINATOR
    delete_attribute(prefix, data)
  end
end

#delete_attribute(key, value) ⇒ Object 



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 70

def delete_attribute(key, value)
  @size_cache = nil
  update = Array.new(@head.level)
  x = @head
   @head.level.downto(1) do |i|
    x = x.forward[i-1] while x.forward[i-1] < key
    update[i-1] = x
  end
  x = x.forward[0]
  if x.key == key
    x.values.delete value
    value
  else
    nil
   end
end

#each ⇒ Object 



150
151
152
153
154
155
156
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 150

def each
  n = @head.forward[0]
  until TailNode === n
    yield n
    n = n.forward[0]
   end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


126
127
128
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 126

def empty?
  @head.forward[0] == @tail
end

#find(*args) ⇒ Object

Finders



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 90

def find(*args)
  q = PointQuery.new(*args)
  total = Set.new
  first_pass = true
  q.slots.each do |key, value|
    results = []
    key = key.to_s
    value = value.to_s
    prefix = value + SEPARATOR + key + TERMINATOR
    node = find_node(prefix)
    results = node.values if node
    total = (first_pass ? results.to_set : (total & results))
    first_pass = false
  end
  total
end

#find_node(key) ⇒ Object 



107
108
109
110
111
112
113
114
115
116
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 107

def find_node(key)
  x = @head
  @head.level.downto(1) do |i|
   x = x.forward[i-1] while x.forward[i-1] < key
 end
 x = x.forward[0]
 return (x.key && yield(x.key, key) ? x : nil) if block_given?
 return x if x.key == key
 nil
end

#first_node ⇒ Object 



118
119
120
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 118

def first_node
  @head.forward[0]
end

#insert(slots, data, __cheaters_level = nil) ⇒ Object 



17
18
19
20
21
22
23
24
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 17

def insert(slots, data, __cheaters_level = nil)
  slots.each do |key, value|
    value = value.to_s
    key = key.to_s
    prefix = value + SEPARATOR + key + TERMINATOR
    insert_attribute(prefix, data, __cheaters_level)
  end
end

#insert_attribute(key, value, __cheaters_level = nil) ⇒ Object 



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
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 26

def insert_attribute(key, value, __cheaters_level = nil)
  @size_cache = nil
  update = Array.new(@head.level)
  x = @head
   @head.level.downto(1) do |i|
    x = x.forward[i-1] while x.forward[i-1] < key
    update[i-1] = x
  end
  x = x.forward[0]
  if x.key == key
    x.values.push value
  else
    newlevel = __cheaters_level || random_level
    newlevel = 1 if empty?
    if newlevel > @head.level 
      (@head.level + 1).upto(newlevel) do |i|
        update[i-1] = @head
       end
     end

     x = Node.new(newlevel, key, value)

     if cut?(newlevel, update[0])
       return new_chunks!(x, update)
     else
       newlevel.times do |i|
         x.forward[i] = update[i].forward[i] || @tail
         update[i].forward[i] = x
       end
     end
   end
	return self
end

#size ⇒ Object 



122
123
124
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 122

def size
	@size_cache ||= inject(0){|c,k| c + 1}
end

#to_s ⇒ Object

Returns a string representation of the Skiplist.



131
132
133
134
135
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 131

def to_s
	"#<#{self.class.name} " + 
	[@head.to_s, map{|node| node.to_s }, @tail.to_s].flatten.join(', ') +
	">"
end

#to_s_levels ⇒ Object 



136
137
138
139
140
 
# File 'lib/strokedb/data_structures/inverted_list.rb', line 136

def to_s_levels
	"#<#{self.class.name}:levels " + 
	[@head.to_s, map{|node| node.level.to_s }, @tail.to_s].flatten.join(', ') +
	">"
end