Class: BitSet

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*data) ⇒ BitSet

Returns a new instance of BitSet.



180
181
182
183
184
185
 
# File 'lib/setfu.rb', line 180

def initialize(*data)
  @bits = 0
  @entropy = 0
  add!(data)
  self
end

Instance Attribute Details

#entropy ⇒ Object

Returns the value of attribute entropy.



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

def entropy
  @entropy
end

Class Method Details

.digit_chars ⇒ Object 



31
32
33
34
35
36
 
# File 'lib/setfu.rb', line 31

def self.digit_chars
  set = BitSet.new
  set.set_bits!(287948901175001088)
  set.entropy=58
  return set
end

.letter_chars ⇒ Object 



24
25
26
27
28
29
 
# File 'lib/setfu.rb', line 24

def self.letter_chars
  set = BitSet.new
  set.set_bits!(10633823810298881996379053697534001152)
  set.entropy=123
  return set
end

.lowercase_chars ⇒ Object 



17
18
19
20
21
22
 
# File 'lib/setfu.rb', line 17

def self.lowercase_chars
  set = BitSet.new
  set.set_bits!(10633823807823001954701781295154855936)
  set.entropy=123
  return set
end

.parse_chars ⇒ Object 



38
39
40
41
42
43
 
# File 'lib/setfu.rb', line 38

def self.parse_chars
  set = BitSet.new
  set.set_bits!(159507359650170349735020301117175103487)
  set.entropy=127
  return set
end

.uppercase_chars ⇒ Object 



10
11
12
13
14
15
 
# File 'lib/setfu.rb', line 10

def self.uppercase_chars
  set = BitSet.new
  set.set_bits!(2475880041677272402379145216)
  set.entropy=91
  return set
end

Instance Method Details

#!=(item) ⇒ Object 



318
319
320
321
322
323
324
325
 
# File 'lib/setfu.rb', line 318

def !=(item)
  if(item.class==BitSet)
    rtn = item.to_i != self.to_i
  else
    rtn = BitSet.new(item).to_i != self.to_i
  end
  rtn
end

#&(item) ⇒ Object 



273
274
275
276
277
278
279
280
281
282
 
# File 'lib/setfu.rb', line 273

def &(item)
  rtn = self.dup
  if(item.class==BitSet)
    rtn.set_bits!(rtn.to_i & item.to_i)
  else
    rtn = BitSet.new(item)
    rtn.set_bits!(@bits & rtn.to_i)
  end
  rtn
end

#**(item) ⇒ Object

intersection test



302
303
304
305
306
 
# File 'lib/setfu.rb', line 302

def **(item)  # intersection test
  set_item = BitSet.new(item)
  return false if (self & set_item).empty?
  return true
end

#-(item) ⇒ Object 



284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
 
# File 'lib/setfu.rb', line 284

def -(item)
  rtn = BitSet.new
  rtn.entropy = self.entropy
  a = self.to_i
  if(item.class==BitSet)
    b = item.to_i
    rtn.entropy = item.entropy
  else
    b = BitSet.new(item)
    rtn.entropy = b.entropy
    b = b.to_i
  end
  c = a & b
  d = c ^ a
  rtn.set_bits!(d)
  rtn
end

#<(item) ⇒ Object 



360
361
362
363
364
 
# File 'lib/setfu.rb', line 360

def <(item)
  si = BitSet.new item
  return false if (si == self)  # not a 'proper' subset
  return si.include?(self)
end

#<=(item) ⇒ Object 



355
356
357
358
 
# File 'lib/setfu.rb', line 355

def <=(item)
  si = BitSet.new item
  return si.include?(self)
end

#==(item) ⇒ Object

comparison operators:



309
310
311
312
313
314
315
316
 
# File 'lib/setfu.rb', line 309

def ==(item)
  if(item.class==BitSet)
    rtn = item.to_i == self.to_i
  else
    rtn = BitSet.new(item).to_i == self.to_i
  end
  rtn
end

#===(item) ⇒ Object 



332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/setfu.rb', line 332

def ===(item)
  # self ... when clause  ... 
  # item ... case clause  ... case(item)
  # Note: coerce does not work in this context ...
  
  md = item.to_bset.mode || @mode
  
  case md
    when :mode_intersection
      return item ** self
    when :mode_sub
      return item <= self
    when :mode_proper
      return item < self
    when :mode_super
      return self <= item
    when :mode_superproper
      return self < item
    else
      return self == item  
  end
end

#[](*pset) ⇒ Object

new behavior … single element returns true/false multi element … returns subset



527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
 
# File 'lib/setfu.rb', line 527

def [](*pset)
  idx = nil
  if pset.count==1  # check for single instance  inst[5], inst['t']
    if pset.first.kind_of? Integer
      idx = pset.first
    elsif pset.first.kind_of? String
      if pset.first.length == 1
        idx = pset.first.ord
      end
    end
  end
  unless idx.nil?
    raise "Negative indexes are illegal for BitSet" if idx < 0
    self.entropy = idx+1
    y = @bits & (1<<idx)
    return true if y > 0
    return false    
  end
  return pset.to_bset & self
end

#[]=(*pset, value) ⇒ Object

pset goes in the box, value after ‘=’



548
549
550
551
552
553
554
555
556
557
 
# File 'lib/setfu.rb', line 548

def []=(*pset,value)  # pset goes in the box, value after '='
  pset = pset.to_bset
  state = value ? true : false
  if state
    replace pset | self  # add elements to set
  else
    replace self - pset  # remove elements from set
  end
  return state # this gets ignored, but to be safe, do what the previous version did   
end

#^(item) ⇒ Object 



250
251
252
253
254
255
256
257
258
259
 
# File 'lib/setfu.rb', line 250

def ^(item)
  rtn = self.dup
  if(item.class==BitSet)
    rtn.set_bits!(rtn.to_i ^ item.to_i)
  else
    rtn = BitSet.new(item)
    rtn.set_bits!(@bits ^ rtn.to_i)
  end
  rtn
end

#add(items) ⇒ Object 



396
397
398
 
# File 'lib/setfu.rb', line 396

def add(items)
  dup.add!(items)
end

#add!(items) ⇒ Object 



366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
 
# File 'lib/setfu.rb', line 366

def add!(items)
  if(items.class==BitSet)
    @bits |= items.to_i
    entropy = items.entropy
  elsif(items.class==Range)
    f=items.first.ord
    l=items.last.ord
    f,l = l,f if f>l
    t = (l-f)+1
    t = (1 << t)-1
    @bits |= t << f
    self.entropy = l+1
  elsif(items.respond_to? :each_char)
    items.each_char do |item|
      @bits |= 1 << item.ord
      self.entropy = item.ord+1
    end
  elsif(items.respond_to? :each)
    items.each do |item|
      add! item
    end
  else #assume number
    raise "negative numbers are not allowed" if items < 0
    pos = 1 << items
    @bits |= pos
    self.entropy = items+1
  end
  self
end

#add_digit_chars ⇒ Object 



68
69
70
 
# File 'lib/setfu.rb', line 68

def add_digit_chars
  return BitSet.digit_chars | self
end

#add_digit_chars! ⇒ Object 



63
64
65
66
 
# File 'lib/setfu.rb', line 63

def add_digit_chars!
  add! BitSet.digit_chars
  self
end

#add_letter_chars ⇒ Object 



90
91
92
 
# File 'lib/setfu.rb', line 90

def add_letter_chars
  return BitSet.letter_chars | self
end

#add_letter_chars! ⇒ Object 



94
95
96
97
 
# File 'lib/setfu.rb', line 94

def add_letter_chars!
  add! BitSet.letter_chars
  self
end

#add_lowercase_chars ⇒ Object 



86
87
88
 
# File 'lib/setfu.rb', line 86

def add_lowercase_chars
  return BitSet.lowercase_chars | self
end

#add_lowercase_chars! ⇒ Object 



81
82
83
84
 
# File 'lib/setfu.rb', line 81

def add_lowercase_chars!
  add! BitSet.lowercase_chars
  self
end

#add_opposing_case ⇒ Object 



168
169
170
 
# File 'lib/setfu.rb', line 168

def add_opposing_case
  dup.add_opposing_case!
end

#add_opposing_case! ⇒ Object 



157
158
159
160
161
162
163
164
165
166
 
# File 'lib/setfu.rb', line 157

def add_opposing_case!
  aa = BitSet.lowercase_chars
  bb = BitSet.uppercase_chars
  ka = aa & self  # subset lower case
  kb = bb & self  # subset upper case
  @bits |= ka.to_i >> 32
  @bits |= kb.to_i << 32
  self.entropy = 32 + kb.recalculate_entropy! if self.entropy <= 123
  self
end

#add_parse_chars ⇒ Object 



59
60
61
 
# File 'lib/setfu.rb', line 59

def add_parse_chars
  return BitSet.parse_chars | self
end

#add_parse_chars! ⇒ Object 



53
54
55
56
57
 
# File 'lib/setfu.rb', line 53

def add_parse_chars!
  # add! [0..47, 58..64, 91..96, 123..126]
  add! BitSet.parse_chars
  self
end

#add_uppercase_chars ⇒ Object 



77
78
79
 
# File 'lib/setfu.rb', line 77

def add_uppercase_chars
  return BitSet.uppercase_chars | self
end

#add_uppercase_chars! ⇒ Object 



72
73
74
75
 
# File 'lib/setfu.rb', line 72

def add_uppercase_chars!
  add! BitSet.uppercase_chars
  self
end

#coerce(other) ⇒ Object

this only works on integer … String, Array, Range does not implement: &, |, ^



239
240
241
242
 
# File 'lib/setfu.rb', line 239

def coerce(other)
  #puts "TESTING ... coerce called!"
  return [self, other]   # does not seem to get called ...
end

#count ⇒ Object 



452
453
454
455
456
457
458
 
# File 'lib/setfu.rb', line 452

def count
  cnt = 0
  each_member do |toss|
    cnt += 1
  end 
  cnt    
end

#dec ⇒ Object 



208
209
210
 
# File 'lib/setfu.rb', line 208

def dec
  return dup.dec!
end

#dec! ⇒ Object 



199
200
201
202
 
# File 'lib/setfu.rb', line 199

def dec!
  @bits >>= 1
  self
end

#dup ⇒ Object 



244
245
246
247
248
 
# File 'lib/setfu.rb', line 244

def dup
  rtn = BitSet.new
  rtn.replace(self)
  return rtn
end

#each_member ⇒ Object 



437
438
439
440
441
442
443
444
445
446
 
# File 'lib/setfu.rb', line 437

def each_member
  bits = @bits
  pos = 0
  while bits > 0
    yield pos if ((bits & 1) == 1)
    pos += 1
    bits >>= 1
  end  
  self
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


400
401
402
 
# File 'lib/setfu.rb', line 400

def empty?
  @bits == 0
end

#inc ⇒ Object 



204
205
206
 
# File 'lib/setfu.rb', line 204

def inc
  return dup.inc!
end

#inc! ⇒ Object 



193
194
195
196
197
 
# File 'lib/setfu.rb', line 193

def inc!
  @entropy += 1
  @bits <<= 1
  self
end

#include?(items) ⇒ Boolean

Returns:

  • (Boolean) 


404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
 
# File 'lib/setfu.rb', line 404

def include?(items)
  return false if items.nil?   # sets never include nil
  return false if @bits == 0   # empty sets include nothing including other empty sets
  if(items.class==BitSet)
    tmp = @bits & items.to_i
    return false if tmp==0
    return (tmp) == items.to_i
  elsif(items.class==Range)
    f=items.first.ord
    l=items.last.ord
    f,l = l,f if f>l
    t = (l-f)+1
    t = (1 << t)-1
    t = t << f
    return (@bits & t) == t
  elsif(items.respond_to? :each_char)
    return false if items.empty?
    items.each_char do |item|
      t = 1 << item.ord
      return false if 0 == (t & @bits)
    end
  elsif(items.respond_to? :each)
    return false if items.empty?
    items.each do |item|
      return false if false==include?(item)
    end
  else #assume number
    t = 1 << items.abs
    return false if 0 == (t & @bits)
  end
  return true
end

#max ⇒ Object

look from left



573
574
575
576
577
578
579
580
581
582
583
584
585
586
 
# File 'lib/setfu.rb', line 573

def max  #look from left
  #byebug
  return nil if empty?
  range = (self.entropy)..(0)
  while((range.first - range.last) >= 2) do
    mid = ((range.first - range.last) >> 1) + range.last
    top = (range.first)..(mid)
    bot = (mid)..(range.last)
    range = self ** top ? top : bot
  end
  #byebug
  return range.first if (self[range.first])
  range.last
end

#max_run ⇒ Object

max_run << returns maximum number of consecutive numbers



134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/setfu.rb', line 134

def max_run # max_run << returns maximum number of consecutive numbers
  return 0 if @bits==0
  mx = 1
  bits = @bits
  loop do
    bits <<= 1
    bits &= @bits
    break if 0 == bits
    mx += 1
  end
  return mx
end

#min ⇒ Object 



559
560
561
562
563
564
565
566
567
568
569
570
571
 
# File 'lib/setfu.rb', line 559

def min
  return nil if empty?
  range = (self.entropy)..(0)
  while((range.first - range.last) >= 2) do
    mid = ((range.first - range.last) >> 1) + range.last
    top = (range.first)..(mid)
    bot = (mid)..(range.last)
    range = self ** bot ? bot : top
  end
  #byebug
  return range.last if (self[range.last])
  range.first
end

#mode ⇒ Object 



176
177
178
 
# File 'lib/setfu.rb', line 176

def mode
  return @mode
end

#rand(elm_count, format = :set) ⇒ Object

:array :array_chars :string :set



589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
 
# File 'lib/setfu.rb', line 589

def rand(elm_count, format = :set)
  raise "rand minimum count too low" if elm_count < 1
  ary = self.to_a
  ary.shuffle!
  ary = ary[0..(elm_count-1)]
  case format
    when :array
      return ary
    when :array_chars
      rtn = []
      ary.each do |elm|
        rtn.push elm.chr(Encoding::UTF_8)
      end
      return rtn
    when :string
      rtn = []
      ary.each do |elm|
        rtn.push elm.chr(Encoding::UTF_8)
      end
      return rtn.join ""
    else # :set
      return ary.to_bset
  end
end

#recalculate_entropy! ⇒ Object 



212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/setfu.rb', line 212

def recalculate_entropy!
  @entropy = 0
  bits = @bits
  num = 1 << 8192
  while(bits > num)
    @entropy += 8192
    bits >>= 8192
  end
  num = 1 << 256
  while(bits > num)
    @entropy += 256
    bits >>= 256
  end
  num = 1 << 16
  while(bits > num)
    @entropy += 16
    bits >>= 16
  end
  while(bits > 0)
    @entropy += 1
    bits >>= 1
  end
  #@entropy += 1
  @entropy
end

#replace(ent) ⇒ Object 



45
46
47
48
49
50
51
 
# File 'lib/setfu.rb', line 45

def replace(ent)
  ent = ent.to_bset
  @mode = ent.mode
  @entropy = ent.entropy
  @bits = ent.to_i
  self  
end

#runs ⇒ Object

01100010011111111100010101001101 … test

01100010011111111100010101001101    ... left shift
001000000011111111000000000001000   ... and with left shift

 01100010011111111100010101001101   ... test
 00110001001111111110001010100110    ... right shift
 00100000001111111100000000000100    ... and with right shift

001000000011111111000000000001000   ... AND with left shift
 00100000001111111100000000000100    ... AND with right shift
001100000011111111100000000001100    ... OR the two ands
 01100010011111111100010101001101   ... test original
 01100000011111111100000000001100   ... BINGO ... original with the OR  gives us the runs only
 00000010000000000000010101000001   ... BINGO ... original XOR with OR gives us the singles!



114
115
116
117
118
119
120
121
122
 
# File 'lib/setfu.rb', line 114

def runs # runs    << creates a set of touching elements
  an_l = (@bits << 1) & @bits
  an_r = (@bits >> 1) & @bits
  or_lr = an_l | an_r
  rtn = BitSet.new
  rtn.set_bits!(or_lr & @bits)
  rtn.entropy=self.entropy
  return rtn
end

#runs?(cnt = 2) ⇒ Boolean

Returns:

  • (Boolean) 


147
148
149
150
151
152
153
154
155
 
# File 'lib/setfu.rb', line 147

def runs?(cnt=2)
  bits = @bits
  (cnt-1).times do
    bits <<= 1
    bits &= @bits
    return false if 0 == bits
  end
  return true
end

#set_bits!(bits) ⇒ Object 



513
514
515
516
 
# File 'lib/setfu.rb', line 513

def set_bits!(bits)
  raise "negative numbers are not allowed" if bits.to_i < 0
  @bits = bits.to_i
end

#set_case(mode = :mode_equal) ⇒ Object 



327
328
329
330
 
# File 'lib/setfu.rb', line 327

def set_case(mode=:mode_equal)
  @mode = mode
  self
end

#singles ⇒ Object

singles << creates a set of non-touching elements



124
125
126
127
128
129
130
131
132
 
# File 'lib/setfu.rb', line 124

def singles # singles << creates a set of non-touching elements 
  an_l = (@bits << 1) & @bits
  an_r = (@bits >> 1) & @bits
  or_lr = an_l | an_r
  rtn = BitSet.new
  rtn.set_bits!(or_lr ^ @bits)
  rtn.entropy=self.entropy
  return rtn
end

#to_a(int = true) ⇒ Object 



468
469
470
471
472
473
474
 
# File 'lib/setfu.rb', line 468

def to_a(int = true)
  rtn = []
  each_member do |num|
    rtn.push int ? num : num.chr(Encoding::UTF_8)
  end
  rtn
end

#to_bset ⇒ Object 



172
173
174
 
# File 'lib/setfu.rb', line 172

def to_bset
  return self
end

#to_i ⇒ Object 



448
449
450
 
# File 'lib/setfu.rb', line 448

def to_i
  return @bits
end

#to_ra(int = true, th = 3) ⇒ Object 



476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
 
# File 'lib/setfu.rb', line 476

def to_ra(int=true, th=3)
  raise "Threshold too low" unless th >= 2
  rtn = []
  cnt = 0
  last  = -100
  flag  = false
  th -= 1
  each_member do |num|
    # byebug unless int
    rtn.push int ? num : num.chr(Encoding::UTF_8)
    if ((last+1)==num)
      # byebug if cnt.nil?
      cnt += 1
      flag = cnt >= th
    elsif flag
      save = rtn.pop
      tmp = rtn.pop(cnt+1)
      range = (tmp.first)..(tmp.last)
      rtn.push range
      rtn.push save
      cnt = 0
      last = -100
      flag = false
    else
      cnt = 0  
    end
    last = num
  end
  #byebug
  if flag # convert final range
    tmp = rtn.pop(cnt+1)
    range = (tmp.first)..(tmp.last)
    rtn.push range
  end
  rtn
end

#to_s ⇒ Object 



460
461
462
463
464
465
466
 
# File 'lib/setfu.rb', line 460

def to_s
  rtn = ""
  each_member do |ch|
    rtn += ch.chr(Encoding::UTF_8)
  end
  rtn
end

#zap! ⇒ Object 



187
188
189
190
191
 
# File 'lib/setfu.rb', line 187

def zap!
  @bits = 0
  @entropy = 0
  self
end

#|(item) ⇒ Object 



261
262
263
264
265
266
267
268
269
270
271
 
# File 'lib/setfu.rb', line 261

def |(item)
  rtn = self.dup
  if(item.class==BitSet)
    rtn.set_bits!(rtn.to_i | item.to_i)
    self.entropy=item.entropy
  else
    rtn = BitSet.new(item)
    rtn.set_bits!(@bits | rtn.to_i)
  end
  rtn
end

#~@ ⇒ Object 



518
519
520
521
522
523
 
# File 'lib/setfu.rb', line 518

def ~@()
  rtn = dup
  mask = (1 << @entropy) - 1
  rtn.set_bits!(mask ^ @bits)
  rtn
end