Class: Immutable::SortedSet::AVLNode

Inherits:
Object
  • Object
show all
Defined in:
lib/immutable/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.



1038
1039
1040
1041
1042
 
# File 'lib/immutable/sorted_set.rb', line 1038

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.



1043
1044
1045
 
# File 'lib/immutable/sorted_set.rb', line 1043

def height
  @height
end

#item ⇒ Object (readonly)

Returns the value of attribute item.



1043
1044
1045
 
# File 'lib/immutable/sorted_set.rb', line 1043

def item
  @item
end

#left ⇒ Object (readonly)

Returns the value of attribute left.



1043
1044
1045
 
# File 'lib/immutable/sorted_set.rb', line 1043

def left
  @left
end

#right ⇒ Object (readonly)

Returns the value of attribute right.



1043
1044
1045
 
# File 'lib/immutable/sorted_set.rb', line 1043

def right
  @right
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



1043
1044
1045
 
# File 'lib/immutable/sorted_set.rb', line 1043

def size
  @size
end

Class Method Details

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



1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
 
# File 'lib/immutable/sorted_set.rb', line 1021

def self.from_items(items, comparator, from = 0, to = items.size-1)
  # items must be sorted, without duplicates (as determined by comparator)
  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 



1299
1300
1301
1302
1303
1304
1305
1306
1307
 
# File 'lib/immutable/sorted_set.rb', line 1299

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 



1317
1318
1319
 
# File 'lib/immutable/sorted_set.rb', line 1317

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

#between(from, to) ⇒ Object 



1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
 
# File 'lib/immutable/sorted_set.rb', line 1204

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 



1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
 
# File 'lib/immutable/sorted_set.rb', line 1122

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 



1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
 
# File 'lib/immutable/sorted_set.rb', line 1080

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 



1061
1062
1063
 
# File 'lib/immutable/sorted_set.rb', line 1061

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

#delete(item) ⇒ Object 



1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
 
# File 'lib/immutable/sorted_set.rb', line 1097

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 



1065
1066
1067
 
# File 'lib/immutable/sorted_set.rb', line 1065

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

#direction(item) ⇒ Object 



1388
1389
1390
 
# File 'lib/immutable/sorted_set.rb', line 1388

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

#drop(n) ⇒ Object 



1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
 
# File 'lib/immutable/sorted_set.rb', line 1262

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:



1250
1251
1252
1253
1254
 
# File 'lib/immutable/sorted_set.rb', line 1250

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

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



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

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 



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

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 



1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
 
# File 'lib/immutable/sorted_set.rb', line 1216

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) 


1057
1058
1059
 
# File 'lib/immutable/sorted_set.rb', line 1057

def empty?
  false
end

#finish_removal(keep_item, left, right) ⇒ Object 



1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
 
# File 'lib/immutable/sorted_set.rb', line 1168

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

Used to implement #map Takes advantage of the fact that Enumerable#map allocates a new Array



1047
1048
1049
1050
1051
 
# File 'lib/immutable/sorted_set.rb', line 1047

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

#include?(item) ⇒ Boolean

Returns:

  • (Boolean) 


1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
 
# File 'lib/immutable/sorted_set.rb', line 1288

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 



1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
 
# File 'lib/immutable/sorted_set.rb', line 1069

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 



1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
 
# File 'lib/immutable/sorted_set.rb', line 1148

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 



1309
1310
1311
 
# File 'lib/immutable/sorted_set.rb', line 1309

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

#min ⇒ Object 



1313
1314
1315
 
# File 'lib/immutable/sorted_set.rb', line 1313

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

#natural_order? ⇒ Boolean

Returns:

  • (Boolean) 


1053
1054
1055
 
# File 'lib/immutable/sorted_set.rb', line 1053

def natural_order?
  false
end

#partition(items) ⇒ Object 



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

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 



1186
1187
1188
1189
1190
1191
1192
1193
 
# File 'lib/immutable/sorted_set.rb', line 1186

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 



1348
1349
1350
1351
1352
1353
1354
 
# File 'lib/immutable/sorted_set.rb', line 1348

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 



1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
 
# File 'lib/immutable/sorted_set.rb', line 1356

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 



1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
 
# File 'lib/immutable/sorted_set.rb', line 1372

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:



1256
1257
1258
1259
1260
 
# File 'lib/immutable/sorted_set.rb', line 1256

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

#slice(from, length) ⇒ Object 



1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
 
# File 'lib/immutable/sorted_set.rb', line 1321

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 



1195
1196
1197
1198
1199
1200
1201
1202
 
# File 'lib/immutable/sorted_set.rb', line 1195

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 



1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
 
# File 'lib/immutable/sorted_set.rb', line 1276

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