need: hierarchic data structure

Discussion in 'Ruby' started by henon, Feb 21, 2006.

  1. henon

    henon Guest

    hi,
    i am searching for an implementation of a hierarchic datastructure that
    behaves similar to a file system except that get of an inexistent path
    returns nil and set of an unexistent path creates the required nodes
    silently.

    example:
    d=HierarchicData.new

    d[:foo, :bar] # => nil
    d[:foo, :bar]=42
    d[:foo, :bar] # => 42

    d[:foo, :foo, 0, 1, :bar]=Object.new # creates a hash in an array in an
    array in a hash in a hash

    i want to check if this kind of data structure (or similar) has been
    implemented already as library. if not i am going to do it.

    thx for any comments!
    -- henon
     
    henon, Feb 21, 2006
    #1
    1. Advertising

  2. On Feb 21, 2006, at 12:33 PM, henon wrote:

    > hi,
    > i am searching for an implementation of a hierarchic datastructure
    > that
    > behaves similar to a file system except that get of an inexistent path
    > returns nil and set of an unexistent path creates the required nodes
    > silently.
    >
    > example:
    > d=HierarchicData.new
    >
    > d[:foo, :bar] # => nil
    > d[:foo, :bar]=42
    > d[:foo, :bar] # => 42
    >
    > d[:foo, :foo, 0, 1, :bar]=Object.new # creates a hash in an array
    > in an
    > array in a hash in a hash
    >
    > i want to check if this kind of data structure (or similar) has been
    > implemented already as library. if not i am going to do it.
    >
    > thx for any comments!
    > -- henon
    >
    >



    Have you considered this?

    class HierarchicData < Hash
    def [](*args)
    super(args)
    end

    def []=(*args)
    keys = args[0..(args.length - 2)]
    value = args.last
    super(keys, value)
    end
    end


    irb(main):012:0> d = HierarchicData.new
    => {}
    irb(main):013:0> d[:foo, :bar]
    => nil
    irb(main):014:0> d[:foo, :bar] = 42
    => 42
    irb(main):015:0> d[:foo, :bar]
    => 42
    irb(main):016:0> d[:foo, :foo, 0, 1, :bar] = Object.new
    => #<Object:0x315d24>
     
    Logan Capaldo, Feb 21, 2006
    #2
    1. Advertising

  3. Re: hierarchic data structure

    "henon" <> schrieb im Newsbeitrag
    news:...
    > hi,
    > i am searching for an implementation of a hierarchic datastructure that
    > behaves similar to a file system except that get of an inexistent path
    > returns nil and set of an unexistent path creates the required nodes
    > silently.
    >
    > example:
    > d=HierarchicData.new
    >
    > d[:foo, :bar] # => nil
    > d[:foo, :bar]=42
    > d[:foo, :bar] # => 42
    >
    > d[:foo, :foo, 0, 1, :bar]=Object.new # creates a hash in an array in an
    > array in a hash in a hash
    >
    > i want to check if this kind of data structure (or similar) has been
    > implemented already as library. if not i am going to do it.
    >
    > thx for any comments!


    There is the usual idiom of nested hashes:

    insert = lambda {|h,k| h[k] = Hash.new(&insert)}
    tree = Hash.new(&insert)

    Then you can do

    >> tree[:foo][:bar]

    => {}
    >> tree[:foo][:bar]=42

    => 42
    >> tree

    => {:foo=>{:bar=>42}}

    Of course you can wrap that in a single class:

    class HT
    def initialize
    insert = lambda {|h,k| h[k] = Hash.new(&insert)}
    @tree = Hash.new(&insert)
    end

    def [](*a)
    a.inject(@tree) {|h,k| h[k]}
    end

    def []=(*a)
    val = a.pop
    key = a.pop
    a.inject(@tree) {|h,k| h[k]}[key]=val
    val
    end
    end

    >> h[:foo, :bar]

    => {}
    >> h

    => #<HT:0x101dc690 @tree={:foo=>{:bar=>{}}}>
    >> h[:foo, :bar]=24

    => 24
    >> h

    => #<HT:0x101dc690 @tree={:foo=>{:bar=>24}}>
    >> h[:bar]=2345

    => 2345
    >> h

    => #<HT:0x101dc690 @tree={:bar=>2345, :foo=>{:bar=>24}}>

    HTH

    robert
     
    Robert Klemme, Feb 21, 2006
    #3
  4. henon

    henon Guest

    actually this yields a flat hash with array keys not a hierarchic one,
    which is not what i want because it cannot be iterated in different
    hierarchy levels
     
    henon, Feb 21, 2006
    #4
  5. henon

    henon Guest

    Re: hierarchic data structure

    > There is the usual idiom of nested hashes:

    sure there's no problem implementing it ... I guess it has been
    implemented a thousand times by a thousand different people. i am
    asking if anyone knows a library because it might feature iterators,
    clever error handling code, etc. and it might be tested better than yet
    annother quicky-hacky-implementation.

    are there any libraries or prominent applications known?
    thanks for response,
    -- henon
     
    henon, Feb 21, 2006
    #5
  6. Re: hierarchic data structure

    henon <> wrote:
    >> There is the usual idiom of nested hashes:

    >
    > sure there's no problem implementing it ... I guess it has been
    > implemented a thousand times by a thousand different people. i am
    > asking if anyone knows a library because it might feature iterators,
    > clever error handling code, etc. and it might be tested better than
    > yet annother quicky-hacky-implementation.
    >
    > are there any libraries or prominent applications known?
    > thanks for response,


    The basic idiom is so simple (two lines, see my last posting) that it
    doesn't make any sense to package that into a lib. I don't know whether
    your requirements are met by anthing done already. Did you check the RAA?
    That's usually a good starting point.

    http://raa.ruby-lang.org/

    Kind regards

    robert
     
    Robert Klemme, Feb 22, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Knews
    Replies:
    5
    Views:
    373
    E.C. Bäck
    Sep 4, 2003
  2. Heiner Kücker
    Replies:
    0
    Views:
    407
    Heiner Kücker
    Feb 23, 2005
  3. John
    Replies:
    5
    Views:
    708
    Karl Heinz Buchegger
    Jan 23, 2004
  4. Raghavendra Mahuli

    need an efficient data structure

    Raghavendra Mahuli, May 27, 2004, in forum: C++
    Replies:
    10
    Views:
    598
    Jeff Schwab
    May 28, 2004
  5. A
    Replies:
    27
    Views:
    1,665
    Jorgen Grahn
    Apr 17, 2011
Loading...

Share This Page