QUESTION: Good data structure for list within list with duplicates?

Discussion in 'Ruby' started by basi, Jul 31, 2005.

  1. basi

    basi Guest

    Hello,
    I have a dictionary within a dictionary, where the inner dictionary may
    have duplicate keys:

    "x" =>
    "aa" => 2
    "aa" => 3
    "bb" => "boo"
    ..

    "y" =>
    "aa" => 5
    "cc" => "see"
    "cc" => "sea"
    ..
    ...

    The first level has about 750 entries.

    First, what is a good structure for this? I've looked at hash within
    hash, but I'm not up to adopting some of the ways to handle duplicate
    keys in hash -- unless there's one that even a rank newbie like myself
    can use.

    The key query I'd need from the list is finding if in the embedded
    dictionary a value exists for a key, where the key may have duplicates,
    for example, Is "see" a value of the key "cc" in "y"?

    Thanks.

    basi
     
    basi, Jul 31, 2005
    #1
    1. Advertisements

  2. basi

    Trans Guest

    The appropriate structure is probably Associative Arrays in Hash.

    {
    "x" => [
    [ "aa", 2 ],
    [ "aa", 3 ],
    [ "bb", "boo" ],
    ...
    ],

    "y" => [
    [ "aa", 5 ],
    [ "cc" , "see" ],
    [ "cc" , "sea" ],
    ...
    ],
    ...
    }

    You can create you own class for it too, start with something like
    this:

    class PairHash

    def initialize()
    @outer = Hash.new([])
    end

    def add_entry( x, y, z )
    a = [y,z]
    @outer[x] << a
    a
    end

    def del_entry( x, y=nil )
    if y
    @outer[x].reject! { |e| e[0] == y }
    else
    @outer.delete(x)
    end
    end

    def inner_value?( v, x, y )
    @outer[x].select { |e| e == [y,v] }
    end

    end

    # demo
    ph = PariHash.new
    ph.add_entry( "x", "aa", 2 )
    ph.add_entry( "x", "aa", 3 )
    ph.add_entry( "x", "bb", "boo" )
    ph.inner_value?( 3, "x", "aa" ) )

    T.
     
    Trans, Jul 31, 2005
    #2
    1. Advertisements

  3. On Sun, 31 Jul 2005 19:21:03 +0200, basi <> wrote:

    > Hello,
    > I have a dictionary within a dictionary, where the inner dictionary may
    > have duplicate keys:
    >
    > "x" =3D>
    > "aa" =3D> 2
    > "aa" =3D> 3
    > "bb" =3D> "boo"
    > ..
    >
    > "y" =3D>
    > "aa" =3D> 5
    > "cc" =3D> "see"
    > "cc" =3D> "sea"
    > ..
    > ...
    >
    > The first level has about 750 entries.
    >
    > First, what is a good structure for this? I've looked at hash within
    > hash, but I'm not up to adopting some of the ways to handle duplicate
    > keys in hash -- unless there's one that even a rank newbie like myself
    > can use.


    You can use hashes within a hash, where the values of your inner hashes =20
    are arrays. Your example would then look like:

    { "x" =3D> { "aa" =3D> [2, 3], "bb" =3D> ["boo"] },
    "y" =3D> { "aa" =3D> [5], "cc" =3D> ["see", "sea"] } }

    To ease the construction of this you should create your outer hash like =20
    that:

    h =3D Hash.new { |h,k|
    h[k] =3D Hash.new { |h2,k2|
    h2[k2] =3D []
    }
    }

    If you have never used Hash::new with a block, then please read "ri =20
    Hash::new":

    -------------------------------------------------------------- Hash::new
    Hash.new =3D> hash
    Hash.new(obj) =3D> aHash
    Hash.new {|hash, key| block } =3D> aHash
    ------------------------------------------------------------------------
    Returns a new, empty hash. If this hash is subsequently accessed by
    a key that doesn't correspond to a hash entry, the value returned
    depends on the style of +new+ used to create the hash. In the first
    form, the access returns +nil+. If _obj_ is specified, this single
    object will be used for all _default values_. If a block is
    specified, it will be called with the hash object and the key, and
    should return the default value. It is the block's responsibility
    to store the value in the hash if required.

    h =3D Hash.new("Go Fish")
    h["a"] =3D 100
    h["b"] =3D 200
    h["a"] #=3D> 100
    h["c"] #=3D> "Go Fish"
    # The following alters the single default object
    h["c"].upcase! #=3D> "GO FISH"
    h["d"] #=3D> "GO FISH"
    h.keys #=3D> ["a", "b"]

    # While this creates a new default object each time
    h =3D Hash.new { |hash, key| hash[key] =3D "Go Fish: #{key}" }
    h["c"] #=3D> "Go Fish: c"
    h["c"].upcase! #=3D> "GO FISH: C"
    h["d"] #=3D> "Go Fish: d"
    h.keys #=3D> ["c", "d"]


    Then you can build your example:

    irb(main):022:0> h =3D Hash.new { |h,k| h[k]=3DHash.new { |h2,k2| h2[k2]=3D=
    [] } }
    =3D> {}
    irb(main):023:0> h["x"]["aa"] << 2
    =3D> [2]
    irb(main):024:0> h["x"]["aa"] << 3
    =3D> [2, 3]
    irb(main):025:0> h["x"]["bb"] << "boo"
    =3D> ["boo"]
    irb(main):026:0> h["y"]["aa"] << 5
    =3D> [5]
    irb(main):027:0> h["y"]["cc"] << "see"
    =3D> ["see"]
    irb(main):028:0> h["y"]["cc"] << "sea"
    =3D> ["see", "sea"]
    irb(main):029:0> h
    =3D> {"x"=3D>{"bb"=3D>["boo"], "aa"=3D>[2, 3]}, "y"=3D>{"cc"=3D>["see", "=
    sea"], =20
    "aa"=3D>[5]}}

    > The key query I'd need from the list is finding if in the embedded
    > dictionary a value exists for a key, where the key may have duplicates,
    > for example, Is "see" a value of the key "cc" in "y"?


    irb(main):030:0> h["y"]["cc"].include?("see")
    =3D> true
    irb(main):031:0> h["y"]["cc"].include?("sea")
    =3D> true
    irb(main):032:0> h["y"]["cc"].include?("s")
    =3D> false

    Hope that helps,
    Dominik
     
    Dominik Bathon, Jul 31, 2005
    #3
  4. basi

    basi Guest

    Both Trans' and Dominik's suggestions look like I can get them to work.
    Thank you both!

    basi
     
    basi, Aug 1, 2005
    #4
  5. Or, as a variation on the above solutions, use an array of the two
    keys as the hash key:

    @h =3D {["x","aa"] =3D> [2,3], ["x", "bb"] =3D> ["boo"],
    ["y","aa"] =3D> [5], ["y", "cc"] =3D> ["see", "sea"]}

    def isValue?(main,embedded,value)
    return false if @h[[main, embedded]].nil?
    @h[[main, embedded]].include?(value)
    end
    =20
    p isValue?("y", "cc", "see") # true
    p isValue?("a", "b", "c") # false
    =20
    Wayne Vucenic
    No Bugs Software
    "Ruby and C++ Contract Programming in Silicon Valley"
     
    Wayne Vucenic, Aug 1, 2005
    #5
    1. Advertisements

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. Julia Jin
    Replies:
    0
    Views:
    381
    Julia Jin
    Aug 20, 2003
  2. Sebastian Bassi
    Replies:
    5
    Views:
    743
    Sebastian Bassi
    Jul 20, 2005
  3. Replies:
    3
    Views:
    599
    turbovince
    Jul 10, 2007
  4. Mike Copeland
    Replies:
    3
    Views:
    524
    Jerry Coffin
    May 14, 2008
  5. Ram
    Replies:
    3
    Views:
    548
    Barry Schwarz
    Mar 24, 2009
  6. A
    Replies:
    27
    Views:
    2,039
    Jorgen Grahn
    Apr 17, 2011
  7. Replies:
    1
    Views:
    351
  8. Replies:
    2
    Views:
    463
    Rui Maciel
    Dec 12, 2012
Loading...