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. Advertising

  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. Advertising

  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. 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. christof hoeke

    delete duplicates in list

    christof hoeke, Oct 29, 2003, in forum: Python
    Replies:
    22
    Views:
    835
    Michael Hudson
    Oct 31, 2003
  2. Mike Copeland
    Replies:
    3
    Views:
    426
    Jerry Coffin
    May 14, 2008
  3. xsl duplicates data

    , Sep 9, 2008, in forum: XML
    Replies:
    1
    Views:
    511
    Pavel Lepin
    Sep 10, 2008
  4. A
    Replies:
    27
    Views:
    1,675
    Jorgen Grahn
    Apr 17, 2011
  5. Replies:
    1
    Views:
    230
Loading...

Share This Page