Class: DS::List
- Inherits:
-
Object
- Object
- DS::List
- Includes:
- Comparable, Enumerable
- Defined in:
- lib/ds/lists/list.rb
Overview
Implements simple list data structure.
Instance Attribute Summary collapse
-
#head ⇒ Object
Returns the value of attribute head.
-
#tail ⇒ Object
Returns the value of attribute tail.
Instance Method Summary collapse
-
#<=>(other) ⇒ Object
Checks if two lists are equal.
-
#[](i, count = nil) ⇒ Object
Returns list element on given index.
-
#[]=(i, count = 1, val) ⇒ Object
Sets list element on given index.
-
#append(x) ⇒ Object
(also: #<<, #push)
Appends new element to list.
-
#at(index) ⇒ Object
Returns list element on given index.
-
#clear ⇒ Object
Clears list by reseting head and tail to nil.
-
#clone ⇒ Object
Clones list.
-
#concat(other) ⇒ Object
Appends one list to other.
-
#cycle_size ⇒ Object
Returns cycle size or nil if list has no cycles.
-
#each ⇒ Object
Default list iterator.
-
#empty? ⇒ Boolean
Checks if list is empty.
-
#first ⇒ Object
Returns first element of the list.
-
#get(x) ⇒ Object
Return ListElement if it is on list otherwise returns nil.
-
#get!(x) ⇒ Object
Return ListElement if it is on list or raises error.
-
#initialize(*arr) ⇒ List
constructor
Creates new list.
-
#insert_after(x, rel) ⇒ Object
Inserts element x after another element.
-
#insert_before(x, rel) ⇒ Object
Inserts element x before another element.
-
#joint ⇒ Object
Returns joint element if exists, otherwise returns nil.
-
#last ⇒ Object
Returns last element of the list.
-
#length ⇒ Object
(also: #size)
Returns length of the list.
-
#looped? ⇒ Boolean
Returns true if list has cycle.
-
#pop ⇒ Object
Removes last element from list.
-
#remove(x) ⇒ Object
Removes element x from list.
-
#replace(el, list, count = 1) ⇒ Object
Replaces list elements with other list.
-
#reverse! ⇒ Object
Reverses list.
-
#reverse_each ⇒ Object
Reverse list iterator.
-
#shift ⇒ Object
Removes list head.
-
#to_a ⇒ Object
Converts list to array.
- #to_s ⇒ Object
-
#unshift(x) ⇒ Object
Prepends new element to list.
-
#zip?(other) ⇒ Boolean
Checks if list is linked at the end with other list.
Constructor Details
#initialize(*arr) ⇒ List
Creates new list.
12 13 14 15 16 17 |
# File 'lib/ds/lists/list.rb', line 12 def initialize(*arr) @size = 0 @head = nil @tail = nil from_array(arr) if arr.any? end |
Instance Attribute Details
#head ⇒ Object
Returns the value of attribute head.
9 10 11 |
# File 'lib/ds/lists/list.rb', line 9 def head @head end |
#tail ⇒ Object
Returns the value of attribute tail.
9 10 11 |
# File 'lib/ds/lists/list.rb', line 9 def tail @tail end |
Instance Method Details
#<=>(other) ⇒ Object
Checks if two lists are equal
137 138 139 140 141 142 143 144 145 |
# File 'lib/ds/lists/list.rb', line 137 def <=>(other) a = head b = other.head while a && b && a.data == b.data a = a.next b = b.next end compare_list_elements(a, b) end |
#[](i, count = nil) ⇒ Object
Returns list element on given index.
94 95 96 97 98 99 100 101 102 103 |
# File 'lib/ds/lists/list.rb', line 94 def [](i, count = nil) return [] if count && count < 0 i = (i...i + count) if count && count > 0 case i when Integer at(i) when Range elements_in_range(i) end end |
#[]=(i, count = 1, val) ⇒ Object
Sets list element on given index.
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
# File 'lib/ds/lists/list.rb', line 106 def []=(i, count = 1, val) if i.is_a? Range index = i.first count = i.size else index = i end raise ListError, 'Ivalid count parameter' unless valid_count?(count, index) el = at(index) raise ListError, 'Element not found' unless el if val.is_a? Array replace(el, List.new(*val), count) else el.data = val end end |
#append(x) ⇒ Object Also known as: <<, push
Appends new element to list. Returns list tail
34 35 36 37 38 39 40 41 42 |
# File 'lib/ds/lists/list.rb', line 34 def append(x) if !empty? @tail = tail.append(x) increment_size else create_first(x) end @tail end |
#at(index) ⇒ Object
Returns list element on given index.
77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
# File 'lib/ds/lists/list.rb', line 77 def at(index) found = nil find_index = lambda do |element, i| if i == index found = element break end end if index >= 0 each_with_index(&find_index) else reverse_each(&find_index) end found end |
#clear ⇒ Object
Clears list by reseting head and tail to nil
27 28 29 30 31 |
# File 'lib/ds/lists/list.rb', line 27 def clear @size = 0 @head = nil @tail = nil end |
#clone ⇒ Object
Clones list
20 21 22 23 24 |
# File 'lib/ds/lists/list.rb', line 20 def clone list = self.class.new each { |e| list.append(e.data) } list end |
#concat(other) ⇒ Object
Appends one list to other
148 149 150 151 152 153 154 |
# File 'lib/ds/lists/list.rb', line 148 def concat(other) other.head.prev = tail tail.next = other.head self.tail = other.tail @size += other.size self end |
#cycle_size ⇒ Object
Returns cycle size or nil if list has no cycles
267 268 269 270 271 272 273 274 275 276 277 278 279 280 |
# File 'lib/ds/lists/list.rb', line 267 def cycle_size return unless looped? counter = 0 start = joint if start counter = 1 elem = start.next while elem != start elem = elem.next counter += 1 end end counter end |
#each ⇒ Object
Default list iterator.
306 307 308 309 310 311 312 |
# File 'lib/ds/lists/list.rb', line 306 def each elem = head while elem yield elem elem = elem.next end end |
#empty? ⇒ Boolean
Checks if list is empty.
216 217 218 |
# File 'lib/ds/lists/list.rb', line 216 def empty? @size.zero? end |
#first ⇒ Object
Returns first element of the list.
226 227 228 |
# File 'lib/ds/lists/list.rb', line 226 def first head.data end |
#get(x) ⇒ Object
Return ListElement if it is on list otherwise returns nil
64 65 66 67 68 |
# File 'lib/ds/lists/list.rb', line 64 def get(x) el = head el = el.next while el && el != x el end |
#get!(x) ⇒ Object
Return ListElement if it is on list or raises error
71 72 73 74 |
# File 'lib/ds/lists/list.rb', line 71 def get!(x) found = get(x) raise ListError, 'Element not found' unless found end |
#insert_after(x, rel) ⇒ Object
Inserts element x after another element.
157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
# File 'lib/ds/lists/list.rb', line 157 def insert_after(x, rel) x = ListElement.new(x) el = rel nxt = el.next x.next = nxt nxt.prev = x if nxt el.next = x x.prev = el self.tail = x if x.nil? increment_size self end |
#insert_before(x, rel) ⇒ Object
Inserts element x before another element.
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 |
# File 'lib/ds/lists/list.rb', line 174 def insert_before(x, rel) if rel == head unshift(x) else x = ListElement.new(x) prev = rel.prev prev.next = x x.prev = prev x.next = rel rel.prev = x end increment_size self end |
#joint ⇒ Object
Returns joint element if exists, otherwise returns nil.
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 |
# File 'lib/ds/lists/list.rb', line 243 def joint elem = head elem2 = elem.next while elem && elem2 # traversing by 1 elem = elem.next # traversing by 2 elem2 = elem2.next elem2 = elem2.next if elem2 return elem if elem2.equal? elem end nil end |
#last ⇒ Object
Returns last element of the list.
221 222 223 |
# File 'lib/ds/lists/list.rb', line 221 def last tail.data end |
#length ⇒ Object Also known as: size
Returns length of the list.
231 232 233 |
# File 'lib/ds/lists/list.rb', line 231 def length @size end |
#looped? ⇒ Boolean
Returns true if list has cycle.
262 263 264 |
# File 'lib/ds/lists/list.rb', line 262 def looped? !joint.nil? end |
#pop ⇒ Object
Removes last element from list.
211 212 213 |
# File 'lib/ds/lists/list.rb', line 211 def pop remove(tail).data end |
#remove(x) ⇒ Object
Removes element x from list.
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |
# File 'lib/ds/lists/list.rb', line 191 def remove(x) if x == head self.head = head.next x.next = nil head.prev = nil if head else nxt = x.next prev = x.prev prev.next = nxt nxt.prev = prev if nxt x.next = nil x.prev = nil self.tail = prev if nxt.nil? end decrement_size x end |
#replace(el, list, count = 1) ⇒ Object
Replaces list elements with other list
126 127 128 129 130 131 132 133 134 |
# File 'lib/ds/lists/list.rb', line 126 def replace(el, list, count = 1) if el.head? replace_head(el, list, count) elsif el.tail? replace_tail(el, list, count) else replace_inside(el, list, count) end end |
#reverse! ⇒ Object
Reverses list.
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 |
# File 'lib/ds/lists/list.rb', line 283 def reverse! @tail = head prev = head elem = prev.next prev.next = nil while elem nxt = elem.next elem.next = prev prev.prev = elem prev = elem elem = nxt end @head = prev self end |
#reverse_each ⇒ Object
Reverse list iterator.
315 316 317 318 319 320 321 322 323 |
# File 'lib/ds/lists/list.rb', line 315 def reverse_each elem = tail i = 0 while elem i -= 1 yield elem, i elem = elem.prev end end |
#shift ⇒ Object
Removes list head.
58 59 60 61 |
# File 'lib/ds/lists/list.rb', line 58 def shift raise ListError, 'List already empty' if empty? remove(head).data end |
#to_a ⇒ Object
Converts list to array.
301 302 303 |
# File 'lib/ds/lists/list.rb', line 301 def to_a map(&:data) end |
#to_s ⇒ Object
325 326 327 |
# File 'lib/ds/lists/list.rb', line 325 def to_s to_a.join('=') end |
#unshift(x) ⇒ Object
Prepends new element to list. Returns list head
48 49 50 51 52 53 54 55 |
# File 'lib/ds/lists/list.rb', line 48 def unshift(x) el = ListElement.new(x) el.next = @head @head.prev = el if @head increment_size @head = el end |
#zip?(other) ⇒ Boolean
Checks if list is linked at the end with other list.
238 239 240 |
# File 'lib/ds/lists/list.rb', line 238 def zip?(other) tail.equal? other.tail end |