# From: http://www.matasano.com/log/basic-uncommented-crappy-binary-radix-trie/
# Author: Thomas Ptacek
# cf. also http://www.matasano.com/log/1009/aguri-coolest-data-structure-youve-never-heard-of/

#!/usr/local/bin/ruby -w

class Fixnum
    def to_b(l = 8)
        "0'" + self.to_s(2).rjust(l, "0")
    end
    def set?(i)
        if((self & (1 << i)) != 0)
            return true
        else
            return false
        end
    end

     def bdiff(x)
         ret = -1
         32.downto(0) do |i|
             if(self.set?(i) != x.set?(i))
                 ret = i
                 break
             end
         end
         ret
     end
end

class String
    def to_ip
        ip = 0
        split(".").each_with_index do |octet, index|
            ip |= (octet.to_i << ((3 - index)*8))
        end
        ip
    end
end

class SimpleTrie
    def initialize(width=32)
        @@node ||= Struct.new(:right, :left, :pos, :key, :value, :color)
        @root = @@node.new(nil, nil, width, 0, nil)
        @root.right = @root
        @root.left = @root
        @width = width
        @sz = 0
    end

    private

    def srch(key, limit=nil)
        cur = @root
        prev = nil

        while(((not prev) or (cur.pos < prev.pos)) and ((not limit) or cur.pos > limit))
            prev = cur
            if(key.set? cur.pos)
                cur = cur.right
            else
                cur = cur.left
            end
        end

        return cur, prev
    end

    public

    def []=(key, val)
        x, prev = srch(key)
        bit = key.bdiff(x.key)
        cur, prev = srch(key, bit)

        node = @@node.new(nil, nil, bit, key, val)

        if(key.set? bit)
            node.right = node
            node.left = cur
        else
            node.right = cur
            node.left = node
        end

        if(key.set? prev.pos)
            prev.right = node
        else
            prev.left = node
        end

        @sz += 1

        return val
    end

    def walk
        color = rand
        walker = lambda do |x, dir, tab|
            if(x.color != color)
                tab.times { print "  " }
                puts "#{ dir } #{ x.key } ( #{ x.key.to_b } ) @ #{ x.pos }"

                x.color = color

                walker.call(x.right, "-> ", tab+1)
                walker.call(x.left, "<- ", tab+1)
            end
        end

        walker.call(@root, ".   ", 0)
    end

    def [](key)
        res, p = srch(key)
        return res.value
    end
end


require 'pp'

t = SimpleTrie.new

t[3] = 3
t[4] = 4
t[2] = 2

t.walk
pp t

p t[3]

  # convert a dotted decimal IPv4 address to dotted binary format
  def ipv4_to_binary(ipv4addr)
    ia = ipv4addr.to_s.split('.')
    if ia.size != 4
      return "0.0.0.0"
    end
    output = ""
    i = 1
    for octett in ia
      output = output + octett.to_i.to_s(2).using("########","0",true)
      if i < 4
        output = output + "."
      end
      i += 1
    end
    return output
  end
  
  
  # convert a IPv4 adress in binary dotted format to a dotted IPv4 address
  def binary_to_ipv4(ipv4addr)
    ia = ipv4addr.to_s.split('.')
    if ia.size != 4
      return "0.0.0.0"
    end
    output = ""
    i = 1
    for octett in ia
      output = output + octett.to_s.to_i(2).to_s
      if i < 4
        output = output + "."
      end
      i += 1
    end
    return output
  end

num = 1024
num.toString(2)

parseInt('111', 2)

#include <stdio.h>

/* Print n as a binary number */
void printbitssimple(int n) {
	unsigned int i;
	i = 1<<(sizeof(n) * 8 - 1);

	while (i > 0) {
		if (n & i)
			printf("1");
		else
			printf("0");
		i >>= 1;
	}
}

/* Print n as a binary number */
void printbits(int n) {
	unsigned int i, step;

	if (0 == n) { /* For simplicity's sake, I treat 0 as a special case*/
		printf("0000");
		return;
	}

	i = 1<<(sizeof(n) * 8 - 1);

	step = -1; /* Only print the relevant digits */
	step >>= 4; /* In groups of 4 */
	while (step >= n) {
		i >>= 4;
		step >>= 4;
	}

	/* At this point, i is the smallest power of two larger or equal to n */
	while (i > 0) {
		if (n & i)
			printf("1");
		else
			printf("0");
		i >>= 1;
	}
}

int main(int argc, char *argv[]) {
	int i;
	for (i = 0; i < 16; ++i) {
		printf("%d = ", i);
		printbitssimple(i);
		printf("\n");
	}

	return 0;
}

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
	int i;
	printf("{ ");
	for (i = 0; i < n; ++i)
		if (mask[i])
			printf("%d ", i + 1); /*i+1 is part of the subset*/
	printf("\b }\n");
}

/* Generates the next mask*/
int next(int mask[], int n) {
	int i;
	for (i = 0; (i < n) && mask[i]; ++i)
		mask[i] = 0;

	if (i < n) {
		mask[i] = 1;
		return 1;
	}
	return 0;
}

int main(int argc, char *argv[]) {
	int n = 3;

	int mask[16]; /* Guess what this is */
	int i;
	for (i = 0; i < n; ++i)
		mask[i] = 0;

	/* Print the first set */
	printv(mask, n);

	/* Print all the others */
	while (next(mask, n))
		printv(mask, n);

	return 0;
}

#!/usr/bin/perl -wn
use strict;
s/\s//g;
print chr oct "0b$1" while /([01]{8})/g;
print "\n";

#        NAME: BitField
#      AUTHOR: Peter Cooper
#     LICENSE: MIT ( http://www.opensource.org/licenses/mit-license.php )
#   COPYRIGHT: (c) 2007 Peter Cooper (http://www.petercooper.co.uk/)
#     VERSION: v4
#     HISTORY: v4 (fixed bug where setting 0 bits to 0 caused a set to 1)
#              v3 (supports dynamic bitwidths for array elements.. now doing 32 bit widths default)
#              v2 (now uses 1 << y, rather than 2 ** y .. it's 21.8 times faster!)
#              v1 (first release)
#
# DESCRIPTION: Basic, pure Ruby bit field. Pretty fast (for what it is) and memory efficient.
#              I've written a pretty intensive test suite for it and it passes great. 
#              Works well for Bloom filters (the reason I wrote it).
#
#              Create a bit field 1000 bits wide
#                bf = BitField.new(1000)
#
#              Setting and reading bits
#                bf[100] = 1
#                bf[100]    .. => 1
#                bf[100] = 0
#
#              More
#                bf.to_s = "10101000101010101"  (example)
#                bf.total_set         .. => 10  (example - 10 bits are set to "1")

class BitField
  attr_reader :size
  include Enumerable
  
  ELEMENT_WIDTH = 32
  
  def initialize(size)
    @size = size
    @field = Array.new(((size - 1) / ELEMENT_WIDTH) + 1, 0)
  end
  
  # Set a bit (1/0)
  def []=(position, value)
    if value == 1
      @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH)
    elsif (@field[position / ELEMENT_WIDTH]) & (1 << (position % ELEMENT_WIDTH)) != 0
      @field[position / ELEMENT_WIDTH] ^= 1 << (position % ELEMENT_WIDTH)
    end
  end
  
  # Read a bit (1/0)
  def [](position)
    @field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) > 0 ? 1 : 0
  end
  
  # Iterate over each bit
  def each(&block)
    @size.times { |position| yield self[position] }
  end
  
  # Returns the field as a string like "0101010100111100," etc.
  def to_s
    inject("") { |a, b| a + b.to_s }
  end
  
  # Returns the total number of bits that are set
  # (The technique used here is about 6 times faster than using each or inject direct on the bitfield)
  def total_set
    @field.inject(0) { |a, byte| a += byte & 1 and byte >>= 1 until byte == 0; a }
  end
end

require "test/unit"
require "bitfield"

class TestLibraryFileName < Test::Unit::TestCase
  def setup
    @public_bf = BitField.new(1000)
  end
  
  def test_basic
    assert_equal 0, BitField.new(100)[0]
    assert_equal 0, BitField.new(100)[1]
  end
  
  def test_setting_and_unsetting
    @public_bf[100] = 1
    assert_equal 1, @public_bf[100]
    @public_bf[100] = 0
    assert_equal 0, @public_bf[100]
  end

  def test_random_setting_and_unsetting
    100.times do
      index = rand(1000)
      @public_bf[index] = 1
      assert_equal 1, @public_bf[index]
      @public_bf[index] = 0
      assert_equal 0, @public_bf[index]
    end
  end
  
  def test_multiple_setting
    1.upto(999) do |pos|
      2.times { @public_bf[pos] = 1 }
      assert_equal 1, @public_bf[pos]
    end
  end

  def test_multiple_unsetting
    1.upto(999) do |pos|
      2.times { @public_bf[pos] = 0 }
      assert_equal 0, @public_bf[pos]
    end
  end
  
  def test_size
    assert_equal 1000, @public_bf.size
  end
  
  def test_to_s
    bf = BitField.new(10)
    bf[1] = 1
    bf[5] = 1
    assert_equal "0100010000", bf.to_s
  end
  
  def test_total_set
    bf = BitField.new(10)
    bf[1] = 1
    bf[5] = 1
    assert_equal 2, bf.total_set
  end
end

count = 0
count += byte & 1 and byte >>= 1 until byte == 0

; Andrew Pennebaker
; 18 Feb 2007
; License: GPL
; URL: http://snippets.dzone.com/posts/show/3535

(define binary-search
	(lambda (ls value low high)
		(let ((mid (floor (/ (+ low high) 2))))
			(cond
				((> low high) -1)
				((= (list-ref ls mid) value) mid)
				((> (list-ref ls mid) value) (binary-search ls value low (- mid 1)))
				((< (list-ref ls mid) value) (binary-search ls value (+ mid 1) high))))))

; Andrew Pennebaker
; 5 Feb 2007
; License: GPL
; URL: http://snippets.dzone.com/posts/show/3479

(define bin->dec
	(lambda (b)
		(cond
			((integer? b) b)
			((= (length b) 0) 0)
			(else
				(+
					(* (expt 2 (- (length b) 1)) (car b))
					(bin->dec (cdr b)))))))