Class: DS::List
Overview
Implements simple list data structure.
Direct Known Subclasses
Instance Attribute Summary collapse
-
#head ⇒ Object
Returns the value of attribute head.
-
#tail ⇒ Object
Returns the value of attribute tail.
Class Method Summary collapse
-
.from_array(arr) ⇒ Object
Creates list from array.
Instance Method Summary collapse
-
#append(x) ⇒ Object
(also: #<<)
Appends new element to list.
-
#each ⇒ Object
Default list iterator.
- #each_with_index ⇒ Object
-
#empty? ⇒ Boolean
Checks if list is empty.
- #first ⇒ Object
-
#initialize(x = nil) ⇒ 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
Returns length of the list.
-
#looped? ⇒ Boolean
Returns true if list has cycle.
-
#merge(other) ⇒ Object
Merge list with other list.
-
#orderize ⇒ Object
Orderize list by evaluating block.
-
#prepend(x) ⇒ Object
Prepends new element to list.
-
#print ⇒ Object
Prints list.
-
#remove(x) ⇒ Object
Removes element x from list.
-
#remove!(other) ⇒ Object
Removes elements that exists on the other list.
-
#reverse! ⇒ Object
Reverses list.
-
#shift ⇒ Object
Removes list head.
-
#to_a ⇒ Object
Converts list to array.
-
#zip?(other) ⇒ Boolean
Checks if list is linked at the end with other list.
Constructor Details
#initialize(x = nil) ⇒ List
Creates new list.
11 12 13 14 |
# File 'lib/ds/lists/list.rb', line 11 def initialize(x=nil) @head = ListElement.new(x) @tail = @head end |
Instance Attribute Details
#head ⇒ Object
Returns the value of attribute head.
8 9 10 |
# File 'lib/ds/lists/list.rb', line 8 def head @head end |
#tail ⇒ Object
Returns the value of attribute tail.
8 9 10 |
# File 'lib/ds/lists/list.rb', line 8 def tail @tail end |
Class Method Details
.from_array(arr) ⇒ Object
Creates list from array.
17 18 19 20 21 22 23 |
# File 'lib/ds/lists/list.rb', line 17 def self.from_array(arr) list = new(arr.shift) tail = list.head arr.each{ |e| tail = tail.append(e) } list.tail = tail list end |
Instance Method Details
#append(x) ⇒ Object Also known as: <<
Appends new element to list.
26 27 28 29 30 31 32 33 34 |
# File 'lib/ds/lists/list.rb', line 26 def append(x) last_elem = self.tail if !empty? @tail = last_elem.append(x) else @head = ListElement.new(x) @tail = @head end end |
#each ⇒ Object
Default list iterator.
284 285 286 287 288 289 290 |
# File 'lib/ds/lists/list.rb', line 284 def each elem = @head while elem yield elem.data elem = elem.next end end |
#each_with_index ⇒ Object
292 293 294 295 296 297 298 299 300 |
# File 'lib/ds/lists/list.rb', line 292 def each_with_index elem = @head i = 0 while elem yield elem,i elem = elem.next i = i + 1 end end |
#empty? ⇒ Boolean
Checks if list is empty.
119 120 121 |
# File 'lib/ds/lists/list.rb', line 119 def empty? head.data.nil? end |
#first ⇒ Object
128 129 130 |
# File 'lib/ds/lists/list.rb', line 128 def first head.data end |
#insert_after(x, rel) ⇒ Object
Inserts element x after another element.
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
# File 'lib/ds/lists/list.rb', line 72 def insert_after(x,rel) x = ListElement.new(x) el = head while el and el != rel el = el.next end raise "Element not found" unless el x.next = el.next el.next = x if x.tail? self.tail = x end end |
#insert_before(x, rel) ⇒ Object
Inserts element x before another element.
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 |
# File 'lib/ds/lists/list.rb', line 91 def insert_before(x,rel) x = ListElement.new(x) #inserting at the beginnig of the list if rel == head x.next = head self.head = x #inserting in the tail of the list else el = head prev = head while el and el != rel prev = el el = el.next end if el.nil? raise "List element not found" else prev.next = x x.next = el end end end |
#joint ⇒ Object
Returns joint element if exists, otherwise returns nil.
143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
# File 'lib/ds/lists/list.rb', line 143 def joint elem = head elem2 = elem.next while elem and elem2 #traversing by 1 elem = elem.next #traversing by 2 elem2 = elem2.next elem2 = elem2.next if elem2 if elem2.equal? elem return elem end end nil end |
#last ⇒ Object
Returns last element of the list.
124 125 126 |
# File 'lib/ds/lists/list.rb', line 124 def last tail.data end |
#length ⇒ Object
Returns length of the list.
133 134 135 |
# File 'lib/ds/lists/list.rb', line 133 def length count end |
#looped? ⇒ Boolean
Returns true if list has cycle.
165 166 167 |
# File 'lib/ds/lists/list.rb', line 165 def looped? !!joint end |
#merge(other) ⇒ Object
Merge list with other list.
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 250 251 252 253 |
# File 'lib/ds/lists/list.rb', line 223 def merge(other) a = self.head b = other.head if a.data < b.data result = List.new(a.data) a = a.next else result = List.new(b.data) b = b.next end while a and b if a.data < b.data result.append(a.data) a = a.next else result.append(b.data) b = b.next end end if !b result.tail.next = a result.tail = self.tail elsif !a result.tail.next = b result.tail = other.tail end result end |
#orderize ⇒ Object
Orderize list by evaluating block. Block should evaluate to one of these values: 1,0,-1 (same as Comparable).
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 |
# File 'lib/ds/lists/list.rb', line 172 def orderize zero = List.new plus = List.new minus = List.new el = self.head while el case yield el.data when 0 zero_tail = zero.append(el.data) when 1 plus_tail = plus.append(el.data) when -1 minus_tail = minus.append(el.data) end el = el.next end minus_tail.next = zero.head zero_tail.next = plus.head return minus end |
#prepend(x) ⇒ Object
Prepends new element to list.
39 40 41 42 43 |
# File 'lib/ds/lists/list.rb', line 39 def prepend(x) el = ListElement.new(x) el.next = @head @head = el end |
#print ⇒ Object
Prints list.
274 275 276 |
# File 'lib/ds/lists/list.rb', line 274 def print each { |e| p } end |
#remove(x) ⇒ Object
Removes element x from list.
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
# File 'lib/ds/lists/list.rb', line 46 def remove(x) if x == head self.head = head.next x.next = nil else el = head while el and el != x prev = el el = el.next end raise "Element not found" unless el prev.next = el.next el.next = nil end x end |
#remove!(other) ⇒ Object
Removes elements that exists on the other list.
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 |
# File 'lib/ds/lists/list.rb', line 200 def remove!(other) a = head b = other.head while a and b while a.data < b.data prev = a a = a.next end while b.data < a.data b = b.next end a = a.next prev.next = a b = b.next end self end |
#reverse! ⇒ Object
Reverses list.
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 |
# File 'lib/ds/lists/list.rb', line 256 def reverse! @tail = self.head prev = self.head elem = prev.next prev.next = nil while elem nxt = elem.next elem.next = prev prev = elem elem = nxt end @head = prev self end |
#shift ⇒ Object
Removes list head.
67 68 69 |
# File 'lib/ds/lists/list.rb', line 67 def shift remove(head).data end |
#to_a ⇒ Object
Converts list to array.
279 280 281 |
# File 'lib/ds/lists/list.rb', line 279 def to_a map { |e| e} end |
#zip?(other) ⇒ Boolean
Checks if list is linked at the end with other list.
138 139 140 |
# File 'lib/ds/lists/list.rb', line 138 def zip?(other) tail.equal? other.tail end |