[PHP] Search a multidimensional array

Discussion in 'Scripts, 3rd Party Apps, and Programming' started by diabolo, Dec 29, 2009.

  1. diabolo

    diabolo Community Advocate Community Support

    Messages:
    1,682
    Likes Received:
    32
    Trophy Points:
    48
    PHP:
    $textbook = array(
       
    'cantonese' => array(
          
    'class1' => array(
             array(
    '1''One - Two''Chapter 1 to Chapter 2',
                       
    'text'),
             array(
    '3''Three - Five''Chapter 3 to Chapter5',
                       
    'text'),
             array(
    '6''Six - Eight''Chapter 6 to Chapter 8',
                       
    'text'),
          ),
          
    'class2' => array(
          ),
       ),
       
    'mandarin' => array(
          
    'class1'  => array(
          ),
          
    'class2'  => array(
          )
       )
    );
    that is the array where I have all the class textbooks. Now I need to be able to search through it and pick up the text from a specified chapter.
    i.e. I pass on $_GET variables, ['cls'] and ['ch']

    but I can't just do: $textbook[$language][$cls][$ch], because the keys are not the ['ch'] numbers

    also, array_search() does not exactly work, because it doesn't search down multiple arrays.
     
    Last edited: Dec 29, 2009
  2. misson

    misson Community Paragon Community Support

    Messages:
    2,572
    Likes Received:
    72
    Trophy Points:
    48
    What do the contents of $_GET['cls'] and $_GET['ch'] look like? "classN" and an integer? Given that each chapter list in each class array is a range of chapters, you'll need to implement your own search. As long as the chapter ranges are in ascending order (as in the sample), you can use binsearch:

    PHP:
    function getChapter($textbook$lang$cls$ch) {
        
    // TODO: add error checking
        
    $cls $textbook[$lang][$cls];
        
    $lo 0;
        
    $hi count($cls);
        
    $mid = ($lo+$hi)>>1;
        do {
            if (
    $ch $cls[$mid][0]) {
                
    $hi $mid;
            } else {
                
    $lo $mid;
            }
            
    $mid = ($lo+$hi) >> 1;
        } while (
    $mid != $lo);
        return 
    $cls[$mid];
    }
    Alternatively, store the chapter list in a DB. For example,
    Code:
    CREATE TABLE classes (
        id INT PRIMARY KEY  AUTO_INCREMENT,
        name VARCHAR(64) DEFAULT NULL,
        level INT,
        lang ENUM('cantonese', 'mandarin') NOT NULL
    ) ENGINE=InnoDB;
    
    /* `sections` is denormalized; in normal form, column `class` 
    belongs in a separate `textbook` table, and column `content` 
    belongs in a `chapters` table.
    */
    CREATE TABLE sections (
        id INT PRIMARY KEY AUTO_INCREMENT,
        start INT NOT NULL, -- starting chapter
        end INT NOT NULL, -- ending chapter
        `range` VARCHAR(32), -- e.g. 'Three - Five'
        label VARCHAR(128), -- short description of chapters
        content TEXT NOT NULL,
        class INT NOT NULL,
        FOREIGN KEY (class) REFERENCES classes (id),
        INDEX (start, end)
    ) ENGINE=InnoDB;
    To get a section:
    Code:
    SELECT sect.start, sect.end, sect.label, sect.content 
        FROM sections AS sect 
        JOIN classes AS cl 
          ON sect.class=cl.id AND sect.class=:class
        WHERE cl.lang=:lang AND sect.start <= :ch AND :ch <= sect.end;
    Of course, if one textbook can be used for multiple classes, you'll have to redesign the schema.

    You might want to create a trigger to prevent sections from overlapping:
    Code:
    DROP TRIGGER IF EXISTS section_nooverlap;
    DELIMITER //
    CREATE TRIGGER section_nooverlap BEFORE INSERT ON sections
    FOR EACH ROW 
    BEGIN
        DECLARE dummy INT;
        IF EXISTS(SELECT id FROM sections AS s 
                      WHERE New.class = s.class
                        AND ((New.start <= s.start AND s.start <= New.end) 
                          OR (New.start <= s.end   AND s.end   <= New.end)))
        THEN 
            SELECT `New section overlaps existing section(s).` INTO dummy 
                FROM sections WHERE sections.id=NEW.id;
        END IF ;
    END //
    DELIMITER ;
    
    Since the `section` table won't likely be updated often, the trigger will have at most a small impact on the speed of your site.
     
    Last edited: Dec 29, 2009
  3. diabolo

    diabolo Community Advocate Community Support

    Messages:
    1,682
    Likes Received:
    32
    Trophy Points:
    48
    I was thinking about using a db, but I because Im working on an offline copy(localhost)
    I hate having to change settings and do everything twice once I put it to a production server

    but it would make everything easier,
    so I guess Ill will try one of those, and see how things go
     
    Last edited: Dec 29, 2009
  4. t2t2t

    t2t2t New Member

    Messages:
    690
    Likes Received:
    0
    Trophy Points:
    0
    Restructure it then:
    PHP:
    <?php
    $textbook 
    = array(
        
    'cantonese' => array(
            
    'class1' => array(
                
    => array('One - Two''Chapter 1 to Chapter 2''text'),
                
    => array('Three - Five''Chapter 3 to Chapter 5''text'),
                
    => array('Six - Eight''Chapter 6 to Chapter 8''text'),
            ),
            
    'class2' => array(
                
    // Follow above
            
    )
        ),
        
    'mandarin' => array(
            
    // Follow above
        
    )
        
    // And so on
    );
    // Example:
    echo $textbook['cantonese']['class1'][3][0].'<br />'.$textbook['cantonese']['class1'][3][1]; // Three - Five<br />Chapter 3 to Chapter 5
    ?>
     
  5. misson

    misson Community Paragon Community Support

    Messages:
    2,572
    Likes Received:
    72
    Trophy Points:
    48
    You shouldn't need to do everything twice. Just set up the design server as a mirror of the production server. Alternatively, have a configuration script that sets DB configuration options, such as user, password, database and table names.

    If all you need to do with the data is fetch a single chapter, the binsearch approach should be fine. Any more than that and using a DB is the best choice.

    What if $_GET['cls']==1 && $_GET['ch'] == 2? Since Diabolo hasn't clarified the legal values of $_GET['ch'], we can't rule out that case.

    Of course, if it comes down to altering the input format, he could use section numbers rather than chapter numbers, which would simplify both indexing and error checking.
     
    Last edited: Dec 29, 2009
  6. t2t2t

    t2t2t New Member

    Messages:
    690
    Likes Received:
    0
    Trophy Points:
    0
    That value wasn't mentioned in original post ;). And a simple check for that would be:
    PHP:
    if(is_array($textbook['cantonese']['class'.$_GET['cls']][$_GET['ch']])) {
        echo 
    $textbook['cantonese']['class'.$_GET['cls']][$_GET['ch']][0].'<br />'.$textbook['cantonese']['class'.$_GET['cls']][$_GET['ch']][1];
    } else {
        echo 
    'Oopsies!';
    }
    // Example outputs:

    // ?cls=1&ch=3
    // Three - Five<br />Chapter 3 to Chapter 5

    // ?cls=1&ch=4
    // Oopsies!
     
  7. diabolo

    diabolo Community Advocate Community Support

    Messages:
    1,682
    Likes Received:
    32
    Trophy Points:
    48
    I did also try a restructure version of it, but that went haywire after I couldn't figure out how the foreach loops would function
     
  8. t2t2t

    t2t2t New Member

    Messages:
    690
    Likes Received:
    0
    Trophy Points:
    0
    Here's a small example to show how to loop everything:
    PHP:
    <?php
    // Just repeating text for example.
    $textbook = array(
        
    'cantonese' => array(
            
    'class1' => array(
                
    => array('One - Two''Chapter 1 to Chapter 2''text'),
                
    => array('Three - Five''Chapter 3 to Chapter 5''text'),
                
    => array('Six - Eight''Chapter 6 to Chapter 8''text'),
            ),
            
    'class2' => array(
                
    => array('One - Two''Chapter 1 to Chapter 2''text'),
                
    => array('Three - Five''Chapter 3 to Chapter 5''text'),
                
    => array('Six - Eight''Chapter 6 to Chapter 8''text'),
            )
        ),
        
    'mandarin' => array(
            
    'class1' => array(
                
    => array('One - Two''Chapter 1 to Chapter 2''text'),
                
    => array('Three - Five''Chapter 3 to Chapter 5''text'),
                
    => array('Six - Eight''Chapter 6 to Chapter 8''text'),
            ),
            
    'class2' => array(
                
    => array('One - Two''Chapter 1 to Chapter 2''text'),
                
    => array('Three - Five''Chapter 3 to Chapter 5''text'),
                
    => array('Six - Eight''Chapter 6 to Chapter 8''text'),
            )
        )
    );
    ?>
    <!-- Some styling for better understanding -->
    <style type="text/css">
        div {
            margin-left: 2em;
        }
    </style>
    <?php
    foreach($textbook as $lang => $langdata) { // Loop languages
        
    echo '<h2>'.ucfirst($lang).'</h2><div>';
        foreach(
    $langdata as $class => $classdata) { // Loop classes
            
    echo '<h3>'.ucfirst($class).'</h3><div>';
            foreach(
    $classdata as $chapter => $chapterdata) { // Loop chapters
                
    echo '<h4>Chapter '.$chapter.' - '.$chapterdata[0].'</h4><div><span style="font-style: italic;">'.$chapterdata[1].'</span><p>'.$chapterdata[2].'</p></div>';
            }
            echo 
    '</div>';
        }
        echo 
    '</div>';
    }
    ?>
    Example output
     
  9. xav0989

    xav0989 Community Public Relation Community Support

    Messages:
    4,467
    Likes Received:
    95
    Trophy Points:
    0
    Can't you have a recursive array search?
     
  10. diabolo

    diabolo Community Advocate Community Support

    Messages:
    1,682
    Likes Received:
    32
    Trophy Points:
    48
    well here's what I originally had.

    PHP:
    function loadClass($dialect$error=NULL) {
       include 
    ROOT.'sources/bits/textbook.php';
       
    $i 0;
       
       foreach (
    $textbookList[$dialect] as $class => $chapters) {
          
    $numClasses count($textbookList[$dialect]);
          
    $rowClass 'row';
             if(
    $i == ($numClasses-1)) { $rowClass 'row lastRow'; }
          
    $html .= '<div class="'.$rowClass.'" id="'.$class.'">';
          
    $html .= '<div class="class">'.$class.'</div>';
          
    $html .= '<div class="chapterContainer">';
             
    $numChapters count($chapters);
             
    $ii 0;
             while(
    $ii $numChapters) {
                
    $html .= '<a href="'.ROOT.'curriculum/'.$dialect.'/textbook.php?cls='.$class.'&ch='.$chapters[$ii]['0'].'"><span class="chapter">'.$chapters[$ii]['1'].'</span></a>';
                
    $ii++;
             }
          
    $html .= '</div>';
          
    $html .= '</div>';
       
    $i++;
       }
    echo 
    $html;   
    }
    I needed to separate it by classes too. but i've started working on the db version so unless someone can come with an awesome breakthrough that requires no brain work for me other than copy+paste, I think im going to work with the db version
     
    Last edited: Dec 29, 2009
  11. misson

    misson Community Paragon Community Support

    Messages:
    2,572
    Likes Received:
    72
    Trophy Points:
    48
    Agreed, the original post was underspecified. I also agree your solution works if only first chapters in section are valid input. However, my point was that Diabolo may want (someday, if not today) to allow other chapter numbers to be used as input, since it's more robust. As long as sections are indexed by starting chapter, some form of search is required, though the code could perform the search only when an index doesn't exist. Something like:
    PHP:
    $textbook = array(
        
    'cantonese' => array(
            
    'class1' => array(
                
    => array('start' => 1'range' => 'One - Two''label' => 'Chapter 1 to Chapter 2''content' => 'text'),
                
    => array('start' => 3'range' => 'Three - Five''label' => 'Chapter 3 to Chapter 5''content' => 'text'),
                
    => array('start' => 6'range' => 'Six - Eight''label' => 'Chapter 6 to Chapter 8''content' => 'text'),
            ),
            
    'class2' => array(
                
    // Follow above
            
    )
        ),
        
    'mandarin' => array(
            
    // Follow above
        
    )
        
    // And so on
    );

    function 
    getSection($textbook$lang$cls$ch) {
        if (isset(
    $textbook[$lang][$cls][$ch])) {
            return 
    $textbook[$lang][$cls][$ch];
        }
        
    // binsearch as before.
        
    ...
    }
    getSection is O(1) for starting chapters and O(lg(n)) for other chapters.

    In this case, recursion is unnecessary, since the only array that needs to be searched is one array of chapters. Getting to that point can be done by indexing alone.
     
    Last edited: Dec 29, 2009
  12. Bryon

    Bryon I Fix Things

    Messages:
    8,149
    Likes Received:
    100
    Trophy Points:
    48
    Thumbs up for Misson! :p
     
  13. xav0989

    xav0989 Community Public Relation Community Support

    Messages:
    4,467
    Likes Received:
    95
    Trophy Points:
    0
    You're right, I haven't seen it that way... Anyway, nice post!
     
  14. matthew88

    matthew88 New Member

    Messages:
    9
    Likes Received:
    1
    Trophy Points:
    0
    These type of things give me a headache, but if you work with it long enough im sure you'll figure out what ur looking for. Good luck.
     
  15. raphman

    raphman New Member

    Messages:
    7
    Likes Received:
    0
    Trophy Points:
    0
    that was helpful
     

Share This Page