Class: Dll

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/gema/list.rb

Overview

Lista doblemente enlazada

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Dll

Returns a new instance of Dll.



8
9
10
11
12
 
# File 'lib/gema/list.rb', line 8

def initialize
	@head = nil
	@tail = nil
	@size = 0
end

Instance Attribute Details

#head ⇒ Object

Returns the value of attribute head.



4
5
6
 
# File 'lib/gema/list.rb', line 4

def head
  @head
end

#size ⇒ Object

Returns the value of attribute size.



4
5
6
 
# File 'lib/gema/list.rb', line 4

def size
  @size
end

#tail ⇒ Object

Returns the value of attribute tail.



4
5
6
 
# File 'lib/gema/list.rb', line 4

def tail
  @tail
end

Instance Method Details

#clasify_salt ⇒ Object

Clasifica usando la sal



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
 
# File 'lib/gema/list.rb', line 151

def clasify_salt

	i = 0
	sz = @size
			
	sorted_dll = Dll.new()
			
	while i < sz do
		aux = @head
		min = aux.value

		while aux != nil do
			if aux.value.sal < min.sal
				min = aux.value
			end
							
		aux = aux.next					
		end
	
	sorted_dll.insert_tail(min)
	remove(min.sal)
	i+=1	
	end

	return sorted_dll		
end

#each ⇒ Object

Metodo each utilizado para poder hacer uso del modulo Enumerable



199
200
201
202
203
204
205
206
207
 
# File 'lib/gema/list.rb', line 199

def each
	aux = @head
               while aux != nil do
		yield aux.value
                       aux = aux.next

               end

end

#empty ⇒ Object

Comprueba si la lista esta vacía



15
16
17
 
# File 'lib/gema/list.rb', line 15

def empty
	@size == 0
end

#extract_head ⇒ Object

Extrae por la cabeza



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/gema/list.rb', line 50

def extract_head

	aux = @head
	@head = @head.next
	
	if @head != nil
		@tail.next = nil
	else
		@tail = nil
	end
	
	aux.next = nil
	aux.prev = nil

	@size = @size - 1
	return aux
end

#extract_tail ⇒ Object

Extrae por la cola



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

def extract_tail

	aux = @tail
	@tail = @tail.prev
	
	if @tail != nil
		@tail.next = nil
	else
		@head = nil
	end
	
	aux.next = nil
	aux.prev = nil

	@size = @size - 1
	return aux
end

#get(n) ⇒ Object

Obtiene el elemento en la posicion n



109
110
111
112
113
114
115
116
117
118
119
 
# File 'lib/gema/list.rb', line 109

def get(n)
	i = 0
	aux = @head
	while i < n do
		aux = aux.next
	i += 1
	end

	return aux
		
end

#insert_head(value) ⇒ Object

Inserta por la cabeza



20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/gema/list.rb', line 20

def insert_head(value)

	if empty()
		@head = Node.new(value,nil,nil)
		@tail = @head
	else
		@head.prev = Node.new(value,@head,nil)
		@head = @head.prev;
	end

	@size = @size + 1
		
end

#insert_tail(value) ⇒ Object

Inserta por la cola



35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/gema/list.rb', line 35

def insert_tail(value)

	if empty()
		@head = Node.new(value,nil,nil)
		@tail = @head
	else
		@tail.next = Node.new(value,nil,@tail)
		@tail = @tail.next;
	end

	@size = @size + 1
		
end

#print ⇒ Object

Imprime la lista



89
90
91
92
93
94
95
96
 
# File 'lib/gema/list.rb', line 89

def print
	aux = @head
	
	while aux != nil do
		puts aux.value.to_s
		aux = aux.next
	end
end

#remove(value) ⇒ Object

Elimina el elemento al que corresponda value



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
 
# File 'lib/gema/list.rb', line 123

def remove(value)
	
	node = @head
	while node.value.sal != value do
		node = node.next
	end
	
	if node != nil
	
		if node != @head
			node.prev.next = node.next
		else
			@head = node.next
		end

		if node != @tail
			node.next.prev = node.prev
		else
			@tail = node.prev
		end

		@size-=1
	end			
			
end

#reverse_print ⇒ Object

Imprime la lista a la inversa



99
100
101
102
103
104
105
106
 
# File 'lib/gema/list.rb', line 99

def reverse_print
	aux = @tail
	
	while aux != nil do
		puts aux.value.to_s
		aux = aux.prev
	end
end

#salt_bubble ⇒ Object

Clasifica usando la sal con el metodo de la burbuja



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/gema/list.rb', line 180

def salt_bubble	
	i = 1
	
	while i < @size
		j = 0
		aux = @head
		while j < (@size - i)
			if aux.value.sal > aux.next.value.sal
				aux.value, aux.next.value = aux.next.value, aux.value
			end
			aux = aux.next
			j+=1	
		end	
		i+=1
	end		
	
end