Class: Hamster::SortedSet::AVLNode

Inherits:
Object
  • Object
show all
Defined in:
lib/hamster/sorted_set.rb

Direct Known Subclasses

PlainAVLNode

Defined Under Namespace

Classes: Empty

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(item, comparator, left, right) ⇒ AVLNode

Returns a new instance of AVLNode.



1004
1005
1006
1007
1008
 
# File 'lib/hamster/sorted_set.rb', line 1004

def initialize(item, comparator, left, right)
  @item, @comparator, @left, @right = item, comparator, left, right
  @height = ((right.height > left.height) ? right.height : left.height) + 1
  @size   = right.size + left.size + 1
end

Instance Attribute Details

#height ⇒ Object (readonly)

Returns the value of attribute height.



1009
1010
1011
 
# File 'lib/hamster/sorted_set.rb', line 1009

def height
  @height
end

#item ⇒ Object (readonly)

Returns the value of attribute item.



1009
1010
1011
 
# File 'lib/hamster/sorted_set.rb', line 1009

def item
  @item
end

#left ⇒ Object (readonly)

Returns the value of attribute left.



1009
1010
1011
 
# File 'lib/hamster/sorted_set.rb', line 1009

def left
  @left
end

#right ⇒ Object (readonly)

Returns the value of attribute right.



1009
1010
1011
 
# File 'lib/hamster/sorted_set.rb', line 1009

def right
  @right
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



1009
1010
1011
 
# File 'lib/hamster/sorted_set.rb', line 1009

def size
  @size
end

Class Method Details

.from_items(items, comparator, from = 0, to = items.size-1) ⇒ Object

items must be sorted



988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
 
# File 'lib/hamster/sorted_set.rb', line 988

def self.from_items(items, comparator, from = 0, to = items.size-1) # items must be sorted
  size = to - from + 1
  if size >= 3
    middle = (to + from) / 2
    AVLNode.new(items[middle], comparator, AVLNode.from_items(items, comparator, from, middle-1), AVLNode.from_items(items, comparator, middle+1, to))
  elsif size == 2
    empty = AVLNode::Empty.new(comparator)
    AVLNode.new(items[from], comparator, empty, AVLNode.new(items[from+1], comparator, empty, empty))
  elsif size == 1
    empty = AVLNode::Empty.new(comparator)
    AVLNode.new(items[from], comparator, empty, empty)
  elsif size == 0
    AVLNode::Empty.new(comparator)
  end
end

Instance Method Details

#at(index) ⇒ Object 



1261
1262
1263
1264
1265
1266
1267
1268
1269
 
# File 'lib/hamster/sorted_set.rb', line 1261

def at(index)
  if index < @left.size
    @left.at(index)
  elsif index > @left.size
    @right.at(index - @left.size - 1)
  else
    @item
  end
end

#balance ⇒ Object 



1279
1280
1281
 
# File 'lib/hamster/sorted_set.rb', line 1279

def balance
  @left.height - @right.height
end

#between(from, to) ⇒ Object 



1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
 
# File 'lib/hamster/sorted_set.rb', line 1166

def between(from, to)
  if direction(from) > 0 # all on the right
    @right.between(from, to)
  elsif direction(to) < 0 # all on the left
    @left.between(from, to)
  else
    left = @left.suffix(from, true)
    right = @right.prefix(to, true)
    rebalance(left, right)
  end
end

#bulk_delete(items) ⇒ Object 



1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
 
# File 'lib/hamster/sorted_set.rb', line 1084

def bulk_delete(items)
  return self if items.empty?
  if items.size == 1
    catch :not_present do
      return delete(items.first)
    end
    return self
  end

  left, right, keep_item = [], [], true
  items.each do |item|
    dir = direction(item)
    if dir > 0
      right << item
    elsif dir < 0
      left << item
    else
      keep_item = false
    end
  end

  left  = @left.bulk_delete(left)
  right = @right.bulk_delete(right)
  finish_removal(keep_item, left, right)
end

#bulk_insert(items) ⇒ Object 



1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
 
# File 'lib/hamster/sorted_set.rb', line 1042

def bulk_insert(items)
  return self if items.empty?
  if items.size == 1
    catch :present do
      return insert(items.first)
    end
    return self
  end
  left, right = partition(items)

  if right.size > left.size
    rebalance_right(@left.bulk_insert(left), @right.bulk_insert(right))
  else
    rebalance_left(@left.bulk_insert(left), @right.bulk_insert(right))
  end
end

#clear ⇒ Object 



1023
1024
1025
 
# File 'lib/hamster/sorted_set.rb', line 1023

def clear
  AVLNode::Empty.new(@comparator)
end

#delete(item) ⇒ Object 



1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
 
# File 'lib/hamster/sorted_set.rb', line 1059

def delete(item)
  dir = direction(item)
  if dir == 0
    if @right.empty?
      return @left # replace this node with its only child
    elsif @left.empty?
      return @right # likewise
    end

    if balance > 0
      # tree is leaning to the left. replace with highest node on that side
      replace_with = @left.max
      derive(replace_with, @left.delete(replace_with), @right)
    else
      # tree is leaning to the right. replace with lowest node on that side
      replace_with = @right.min
      derive(replace_with, @left, @right.delete(replace_with))
    end
  elsif dir > 0
    rebalance_left(@left, @right.delete(item))
  else
    rebalance_right(@left.delete(item), @right)
  end
end

#derive(item, left, right) ⇒ Object 



1027
1028
1029
 
# File 'lib/hamster/sorted_set.rb', line 1027

def derive(item, left, right)
  AVLNode.new(item, @comparator, left, right)
end

#direction(item) ⇒ Object 



1350
1351
1352
 
# File 'lib/hamster/sorted_set.rb', line 1350

def direction(item)
  @comparator.call(item, @item)
end

#drop(n) ⇒ Object 



1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
 
# File 'lib/hamster/sorted_set.rb', line 1224

def drop(n)
  if n >= @size
    clear
  elsif n <= 0
    self
  elsif @left.size >= n
    rebalance_right(@left.drop(n), @right)
  elsif @left.size + 1 == n
    @right
  else
    @right.drop(n - @left.size - 1)
  end
end

#each {|@item| ... } ⇒ Object

Yields:



1212
1213
1214
1215
1216
 
# File 'lib/hamster/sorted_set.rb', line 1212

def each(&block)
  @left.each(&block)
  yield @item
  @right.each(&block)
end

#each_between(from, to, &block) ⇒ Object 



1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
 
# File 'lib/hamster/sorted_set.rb', line 1200

def each_between(from, to, &block)
  if direction(from) > 0 # all on the right
    @right.each_between(from, to, &block)
  elsif direction(to) < 0 # all on the left
    @left.each_between(from, to, &block)
  else
    @left.each_greater(from, true, &block)
    yield @item
    @right.each_less(to, true, &block)
  end
end

#each_greater(item, inclusive, &block) ⇒ Object 



1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
 
# File 'lib/hamster/sorted_set.rb', line 1189

def each_greater(item, inclusive, &block)
  dir = direction(item)
  if dir < 0 || (inclusive && dir == 0)
    @left.each_greater(item, inclusive, &block)
    yield @item
    @right.each(&block)
  else
    @right.each_greater(item, inclusive, &block)
  end
end

#each_less(item, inclusive, &block) ⇒ Object 



1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
 
# File 'lib/hamster/sorted_set.rb', line 1178

def each_less(item, inclusive, &block)
  dir = direction(item)
  if dir > 0 || (inclusive && dir == 0)
    @left.each(&block)
    yield @item
    @right.each_less(item, inclusive, &block)
  else
    @left.each_less(item, inclusive, &block)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


1019
1020
1021
 
# File 'lib/hamster/sorted_set.rb', line 1019

def empty?
  false
end

#finish_removal(keep_item, left, right) ⇒ Object 



1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
 
# File 'lib/hamster/sorted_set.rb', line 1130

def finish_removal(keep_item, left, right)
  # deletion of items may have occurred on left and right sides
  # now we may also need to delete the current item
  if keep_item
    rebalance(left, right) # no need to delete the current item
  elsif left.empty?
    right
  elsif right.empty?
    left
  elsif left.height > right.height
    replace_with = left.max
    derive(replace_with, left.delete(replace_with), right)
  else
    replace_with = right.min
    derive(replace_with, left, right.delete(replace_with))
  end
end

#from_items(items) ⇒ Object 



1011
1012
1013
 
# File 'lib/hamster/sorted_set.rb', line 1011

def from_items(items)
  AVLNode.from_items(items.sort(&@comparator), @comparator)
end

#include?(item) ⇒ Boolean

Returns:

  • (Boolean) 


1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
 
# File 'lib/hamster/sorted_set.rb', line 1250

def include?(item)
  dir = direction(item)
  if dir == 0
    true
  elsif dir > 0
    @right.include?(item)
  else
    @left.include?(item)
  end
end

#insert(item) ⇒ Object 



1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
 
# File 'lib/hamster/sorted_set.rb', line 1031

def insert(item)
  dir = direction(item)
  if dir == 0
    throw :present
  elsif dir > 0
    rebalance_right(@left, @right.insert(item))
  else
    rebalance_left(@left.insert(item), @right)
  end
end

#keep_only(items) ⇒ Object 



1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
 
# File 'lib/hamster/sorted_set.rb', line 1110

def keep_only(items)
  return clear if items.empty?

  left, right, keep_item = [], [], false
  items.each do |item|
    dir = direction(item)
    if dir > 0
      right << item
    elsif dir < 0
      left << item
    else
      keep_item = true
    end
  end

  left  = @left.keep_only(left)
  right = @right.keep_only(right)
  finish_removal(keep_item, left, right)
end

#max ⇒ Object 



1271
1272
1273
 
# File 'lib/hamster/sorted_set.rb', line 1271

def max
  @right.empty? ? @item : @right.max
end

#min ⇒ Object 



1275
1276
1277
 
# File 'lib/hamster/sorted_set.rb', line 1275

def min
  @left.empty? ? @item : @left.min
end

#natural_order? ⇒ Boolean

Returns:

  • (Boolean) 


1015
1016
1017
 
# File 'lib/hamster/sorted_set.rb', line 1015

def natural_order?
  false
end

#partition(items) ⇒ Object 



1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
 
# File 'lib/hamster/sorted_set.rb', line 1297

def partition(items)
  left, right = [], []
  items.each do |item|
    dir = direction(item)
    if dir > 0
      right << item
    elsif dir < 0
      left << item
    end
  end
  [left, right]
end

#prefix(item, inclusive) ⇒ Object 



1148
1149
1150
1151
1152
1153
1154
1155
 
# File 'lib/hamster/sorted_set.rb', line 1148

def prefix(item, inclusive)
  dir = direction(item)
  if dir > 0 || (inclusive && dir == 0)
    rebalance_left(@left, @right.prefix(item, inclusive))
  else
    @left.prefix(item, inclusive)
  end
end

#rebalance(left, right) ⇒ Object 



1310
1311
1312
1313
1314
1315
1316
 
# File 'lib/hamster/sorted_set.rb', line 1310

def rebalance(left, right)
  if left.height > right.height
    rebalance_left(left, right)
  else
    rebalance_right(left, right)
  end
end

#rebalance_left(left, right) ⇒ Object 



1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
 
# File 'lib/hamster/sorted_set.rb', line 1318

def rebalance_left(left, right)
  # the tree might be unbalanced to the left (paths on the left too long)
  balance = left.height - right.height
  if balance >= 2
    if left.balance > 0
      # single right rotation
      derive(left.item, left.left, derive(@item, left.right, right))
    else
      # left rotation, then right
      derive(left.right.item, derive(left.item, left.left, left.right.left), derive(@item, left.right.right, right))
    end
  else
    derive(@item, left, right)
  end
end

#rebalance_right(left, right) ⇒ Object 



1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
 
# File 'lib/hamster/sorted_set.rb', line 1334

def rebalance_right(left, right)
  # the tree might be unbalanced to the right (paths on the right too long)
  balance = left.height - right.height
  if balance <= -2
    if right.balance > 0
      # right rotation, then left
      derive(right.left.item, derive(@item, left, right.left.left), derive(right.item, right.left.right, right.right))
    else
      # single left rotation
      derive(right.item, derive(@item, left, right.left), right.right)
    end
  else
    derive(@item, left, right)
  end
end

#reverse_each {|@item| ... } ⇒ Object

Yields:



1218
1219
1220
1221
1222
 
# File 'lib/hamster/sorted_set.rb', line 1218

def reverse_each(&block)
  @right.reverse_each(&block)
  yield @item
  @left.reverse_each(&block)
end

#slice(from, length) ⇒ Object 



1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
 
# File 'lib/hamster/sorted_set.rb', line 1283

def slice(from, length)
  if length <= 0
    clear
  elsif from + length <= @left.size
    @left.slice(from, length)
  elsif from > @left.size
    @right.slice(from - @left.size - 1, length)
  else
    left  = @left.slice(from, @left.size - from)
    right = @right.slice(0, from + length - @left.size - 1)
    rebalance(left, right)
  end
end

#suffix(item, inclusive) ⇒ Object 



1157
1158
1159
1160
1161
1162
1163
1164
 
# File 'lib/hamster/sorted_set.rb', line 1157

def suffix(item, inclusive)
  dir = direction(item)
  if dir < 0 || (inclusive && dir == 0)
    rebalance_right(@left.suffix(item, inclusive), @right)
  else
    @right.suffix(item, inclusive)
  end
end

#take(n) ⇒ Object 



1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
 
# File 'lib/hamster/sorted_set.rb', line 1238

def take(n)
  if n >= @size
    self
  elsif n <= 0
    clear
  elsif @left.size >= n
    @left.take(n)
  else
    rebalance_left(@left, @right.take(n - @left.size - 1))
  end
end