:-(: 午前, 午後, 夜, アルゴリズム辞典 - パトリシア(C実装), アルゴリズム辞典 - パトリシア(ruby実装)

2012-06-14 :-(

_ 午前

0520 起床

0830 出勤

0900 検討

_ 午後

1300 検討

1740 退勤

_ 夜

1900 アルゴリズムほげ

2100 飯

_ [アルゴリズム辞典][パトリシア]アルゴリズム辞典 - パトリシア(C実装)

/* -------------------------------------------------------------------------
 *  アルゴリズム辞典
 *  島内剛一 野下浩平 伏見正則 有沢誠 浜田穂積
 *
 *  パトリシア pp. 624-625
 * ---------------------------------------------------------------------- */


#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  char key;
  char chckbit;
  struct node* right;
  struct node* left;
} node;

static node head = { 0x0, 0x0, &head, &head };
static char mask[9] = { 0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

// 探索
node* search ( char key, node* x )
{
    node* p;
    do
    {
      p = x;
      x = ( key & mask[ x->chckbit ] ) ? x->right : x->left;
    } while ( p->chckbit < x->chckbit );

    return x;
}


// 挿入
void insert( char key, node* x )
{
  node* t, *p;
  int i;

  // キーの探索
  t = search( key, x );
  if( key == t->key )
  {
    printf( "%c exists\n", key );
    return;
  }

  // 挿入するキーと衝突するキーとの間で最初に
  // 異なるビットの位置を求める
  for( i = 1; ( key & mask[ i ] ) == ( t->key & mask[ i ] ); i++ )
    ;

  // キーを置く位置( x )を求める
  do
  {
    p = x;
    x = ( key & mask[ x->chckbit ] ) ? x->right : x->left;
  } while( ( x->chckbit < i ) && ( p->chckbit < x->chckbit ) );

  // 挿入する節点を生成し
  // キーと検査ビットの位置を設定する

  t = calloc( 1, sizeof( node ) );
  t->key = key;
  t->chckbit = i;

  // 子節と親節を設定する
  if( key & mask[ t->chckbit ] )
  {
    t->right = t;
    t->left =x;
  }
  else
  {
    t->left = t;
    t->right = x;
  }

  if( key & mask[ p->chckbit ] )
    p->right = t;
  else
    p->left = t;

  return;
}

int main( int ac, char** av )
{
  node *np;
  insert( 'a', &head );
  insert( 'b', &head );
  insert( 'c', &head );

  np = search( 'a', &head );
  if( np != NULL )
    printf( "key: %c\n", np->key );

  np = search( 'b', &head );
  if( np != NULL )
    printf( "key: %c\n", np->key );

  np = search( 'c', &head );
  if( np != NULL )
    printf( "key: %c\n", np->key );

  return;
}

% ./a.exe
key: a
key: b
key: c

4320027094

_ [アルゴリズム辞典][パトリシア]アルゴリズム辞典 - パトリシア(ruby実装)

#!/usr/bin/ruby

# -*- encoding: utf-8 -*-

#
# アルゴリズム辞典
# 島内剛一 野下浩平 伏見正則 有沢誠 浜田穂積
#
# パトリシア pp. 624-625


require 'pp'

class Node
  attr_accessor :key, :chckbit, :left, :right

  def initialize(key = 0, chckbit = 0, left = nil, right = nil)
    @key = key
    @chckbit = chckbit
    @left = left
    @right = right
  end
end


class Patricia
  def initialize()
    @head = Node.new()
    @head.key = 0
    @head.chckbit = 0
    @head.left = @head
    @head.right = @head
    @mask = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]
  end


  # 探索
  def search(key)
    x = @head
    p = nil

    begin
      p = x
      x = (key[0] & @mask[x.chckbit] != 0) ? x.right : x.left
    end while (p.chckbit < x.chckbit)

    return x
  end

  # 挿入
  def insert(key)
    x = @head
    t = nil
    p = nil
    i = 0

    # キーの探索
    t = self.search(key)
    if key == t.key
      puts "#{key} exists"
      return
    end

    # 挿入するキーと衝突するキーとの間で最初に
    # 異なるビットの位置を求める
    i = 1
    while (key[0] & @mask[i]) == (t.key[0] & @mask[i])
      i += 1
    end

    # キーを置く位置( x )を求める
    begin
      p = x
      x = (key[0] & @mask[x.chckbit] != 0) ? x.right : x.left
    end while ((x.chckbit < i) && (p.chckbit < x.chckbit))

    # 挿入する節点を生成し
    # キーと検査ビットの位置を設定する
    t = Node.new()
    t.key = key
    t.chckbit = i

    # 子節と親節を設定する
    if key[0] & @mask[t.chckbit] != 0
      t.right = t
      t.left =x
    else
      t.left = t
      t.right = x
    end

    if key[0] & @mask[p.chckbit] != 0
      p.right = t
    else
      p.left = t
    end

  end

end  # end of Patricia

def main(argv)
  pat = Patricia.new()
  pat.insert('a')
  pat.insert('b')
  pat.insert('c')

  np = pat.search('a')
  if np != nil
    puts "key: #{np.key}"
  end

  np = pat.search('b')
  if np != nil
    puts "key: #{np.key}"
  end

  np = pat.search('c')
  if np != nil
    puts "key: #{np.key}"
  end

end

main(ARGV)