### Home Classes Methods

### In Files

- lib/data-structures.rb

### Parent

Object

### Methods

- ::new
- #==
- #clone
- #delete_node
- #empty?
- #get_next
- #get_node
- #get_node_i
- #hash
- #insert_node
- #reset_iterator
- #to_array

### Files

- LessThan5BlueLabels.txt
- AtLeast2LargeSegments.txt

### Class Index

Quicksearch

- AddLabelTool
- AllRulesAppliedGoal
- Area
- AreaConstraint
- Array
- BalancedBinaryTree
- BalancedBinaryTreeNode
- CloseObserver
- Constants
- Constraint
- CurrentLabelledShape
- DistinctShapeConstraint
- Execution
- Goal
- Grammar
- Label
- LabelledShape
- LineDescriptor
- LinearLinkedList
- LinearLinkedListNode
- NoLabelsGoal
- NoMoreRulesGoal
- NoScalesConstraint
- Numeric
- Object
- OrderedPoint
- PiList
- Point
- Project
- Robot
- Rule
- RuleGroupsObserver
- RuleLabelledShape
- RuleShapeObserver
- Segment
- ShaDeLayersObserver
- Shade
- ShadeUtils
- UndoObserver

No matching classes.

# LinearLinkedList

Author | Manuela Ruiz (mruiz@lcc.uma.es)

This class represents a linked list

### Attributes

first[RW]

First node of the list (LinearLinkedListNode)

size[RW]

Number of nodes in the list

current_node[RW]

Current node for getting the nodes in order

last[RW]

Last node of the list (LinearLinkedListNode)

### Public Class Methods

new() click to toggle source

Initializes the List

        # File lib/data-structures.rb, line 91
    91:         def initialize()

    92:                 @first = nil

    93:                 @size = 0

    94:                 @current_node = Constants::START

    95:                 @last = nil

    96:         end

### Public Instance Methods

==(other_list) click to toggle source

other_list | another LinearLinkedList object
returns | true if this list is identical to the specified list

         # File lib/data-structures.rb, line 262
    262:         def ==(other_list)

    263:                 result = false

    264:                 if !other_list

    265:                         other_list = LinearLinkedList.new

    266:                 end

    267:                 if other_list.kind_of? LinearLinkedList

    268:                         result = (@size == other_list.size)

    269:                         current = @first

    270:                         other_current = other_list.first

    271:                         while (result && current && other_current)

    272:                                 result = ((current.key == other_current.key) && (current.list == other_current.list))

    273:                                 current = current._next

    274:                                 other_current = other_current._next

    275:                         end

    276:                 end

    277:                 return result

    278:         end

clone() click to toggle source

returns | a new LinearLinkedList, identical to this one

         # File lib/data-structures.rb, line 248
    248:         def clone()

    249:                 new_lllist = LinearLinkedList.new

    250:                 current = @first

    251:                 while current

    252:                         new_node = current.clone

    253:                         new_lllist.insert_node(new_node)

    254:                         current = current._next

    255:                 end

    256:                 return new_lllist

    257:         end

delete_node(key) click to toggle source

key | key of the node to remove
returns | true iff the node has been deleted, false otherwise.

Deletes the specified node

         # File lib/data-structures.rb, line 176
    176:         def delete_node(key)

    177:                 previous = nil

    178:                 current = @first

    179:                 exists = false

    180:                 while (current && !exists)

    181:                         if (key == current.key)

    182:                                 exists = true

    183:                         else

    184:                                 previous = current

    185:                                 current = current._next

    186:                         end

    187:                 end

    188:

    189:                 if exists

    190:                         if !previous #Is the first node

    191:                                 @first = @first._next

    192:                                 if (@size == 1)

    193:                                         @last = nil

    194:                                 end

    195:                         else #General case

    196:                                 if !current._next

    197:                                         @last = previous

    198:                                 end

    199:                                 previous._next = current._next

    200:                         end

    201:                         @size -= 1

    202:                         result = true

    203:                 else

    204:                         result = false

    205:                 end

    206:                 return result

    207:         end

empty?() click to toggle source

returns | true iff the list is empty

         # File lib/data-structures.rb, line 243
    243:         def empty?()

    244:                 return !@first

    245:         end

get_next() click to toggle source

returns | returns, in each invocation, the next node, in order, in the list

         # File lib/data-structures.rb, line 225
    225:         def get_next()

    226:                 if @current_node == Constants::START

    227:                         @current_node = @first

    228:                 elsif @current_node

    229:                         @current_node = @current_node._next

    230:                 else

    231:                         self.reset_iterator

    232:                 end

    233:                 result = @current_node

    234:                 return result

    235:         end

get_node(key) click to toggle source

key::key of the node we want to recover

returns | the node with the specified key. In case it does not exists, returns nil.

         # File lib/data-structures.rb, line 157
    157:         def get_node(key)

    158:                 result = nil

    159:                 current = @first

    160:                 found = false

    161:                 while (current && !found)

    162:                         if (current.key == key)

    163:                                 found = true

    164:                                 result = current

    165:                         else

    166:                                 current = current._next

    167:                         end

    168:                 end

    169:                 return result

    170:         end

get_node_i(i) click to toggle source

i::index ofthe node to be retrieved

returns | the node in the position i, or nil if i >= size of the list

         # File lib/data-structures.rb, line 212
    212:         def get_node_i(i)

    213:                 if (i < @size)

    214:                         j = 0

    215:                         result = @first

    216:                         while (j < i)

    217:                                 result = result._next

    218:                                 j += 1

    219:                         end

    220:                 end

    221:                 return result

    222:         end

hash() click to toggle source

returns | the hash code for this list

         # File lib/data-structures.rb, line 281
    281:         def hash

    282:                 array = self.to_array

    283:                 hash_array = Array.new

    284:                 array.each { |node|

    285:                         hash_array.push node.hash

    286:                 }

    287:                 return hash_array.hash

    288:         end

insert_node(n) click to toggle source

n | LinearLinkedListNode to add
returns | the inserted node or the previously existing node in case the key already exist in the list

Inserts the node, maintaining the order of the list

         # File lib/data-structures.rb, line 102
    102:         def insert_node(n)

    103:                 previous = nil

    104:                 current = @first

    105:                 position_found = false

    106:                 exists = false

    107:                 while (current && !position_found && !exists)

    108:                         if (n.key < current.key)

    109:                                 position_found = true

    110:                         elsif (n.key == current.key)

    111:                                 exists = true

    112:                         else

    113:                                 previous = current

    114:                                 current = current._next

    115:                         end

    116:                 end

    117:

    118:                 if !exists #If the node does'n exist

    119:                         if !previous #Is the first node

    120:                                 n._next = @first

    121:                                 @first = n

    122:                                 @current_node = Constants::START

    123:                                 if (@size == 0)

    124:                                         @last = n

    125:                                 end

    126:                         else # General case (or last to be added if !position_found)

    127:                                 if !position_found

    128:                                         @last = n

    129:                                 end

    130:                                 previous._next = n

    131:                                 n._next = current

    132:                         end

    133:

    134:                         @size += 1

    135:                         result =  n

    136:                 else

    137:                         result = current

    138:                 end

    139:                 return result

    140:         end

reset_iterator() click to toggle source

resets the iterator used by get_next()

         # File lib/data-structures.rb, line 238
    238:         def reset_iterator()

    239:                 @current_node = Constants::START

    240:         end

to_array() click to toggle source

returns | the nodes of the list in the form of an array

         # File lib/data-structures.rb, line 143
    143:         def to_array

    144:                 result = Array.new

    145:                 current = @first

    146:                 while current

    147:                         result.push current

    148:                         current = current._next

    149:                 end

    150:

    151:                 return result

    152:         end

Disabled; run with --debug to generate this.

[Validate]

Generated with the Darkfish Rdoc Generator 1.1.6.