You are previewing Ruby Cookbook.

Ruby Cookbook

Cover of Ruby Cookbook by Lucas Carlson... Published by O'Reilly Media, Inc.
  1. Ruby Cookbook
    1. SPECIAL OFFER: Upgrade this ebook with O’Reilly
    2. A Note Regarding Supplemental Files
    3. Preface
      1. 1. Life Is Short
      2. 2. Audience
      3. 3. The Structure of This Book
      4. 4. How the Code Listings Work
      5. 5. Installing the Software
      6. 6. Platform Differences, Version Differences, and Other Headaches
      7. 7. Other Resources
      8. 8. Conventions Used in This Book
      9. 9. Using Code Examples
      10. 10. Comments and Questions
      11. 11. Acknowledgments
    4. 1. Strings
      1. 1.1. Building a String from Parts
      2. 1.2. Substituting Variables into Strings
      3. 1.3. Substituting Variables into an Existing String
      4. 1.4. Reversing a String by Words or Characters
      5. 1.5. Representing Unprintable Characters
      6. 1.6. Converting Between Characters and Values
      7. 1.7. Converting Between Strings and Symbols
      8. 1.8. Processing a String One Character at a Time
      9. 1.9. Processing a String One Word at a Time
      10. 1.10. Changing the Case of a String
      11. 1.11. Managing Whitespace
      12. 1.12. Testing Whether an Object Is String-Like
      13. 1.13. Getting the Parts of a String You Want
      14. 1.14. Handling International Encodings
      15. 1.15. Word-Wrapping Lines of Text
      16. 1.16. Generating a Succession of Strings
      17. 1.17. Matching Strings with Regular Expressions
      18. 1.18. Replacing Multiple Patterns in a Single Pass
      19. 1.19. Validating an Email Address
      20. 1.20. Classifying Text with a Bayesian Analyzer
    5. 2. Numbers
      1. 2.1. Parsing a Number from a String
      2. 2.2. Comparing Floating-Point Numbers
      3. 2.3. Representing Numbers to Arbitrary Precision
      4. 2.4. Representing Rational Numbers
      5. 2.5. Generating Random Numbers
      6. 2.6. Converting Between Numeric Bases
      7. 2.7. Taking Logarithms
      8. 2.8. Finding Mean, Median, and Mode
      9. 2.9. Converting Between Degrees and Radians
      10. 2.10. Multiplying Matrices
      11. 2.11. Solving a System of Linear Equations
      12. 2.12. Using Complex Numbers
      13. 2.13. Simulating a Subclass of Fixnum
      14. 2.14. Doing Math with Roman Numbers
      15. 2.15. Generating a Sequence of Numbers
      16. 2.16. Generating Prime Numbers
      17. 2.17. Checking a Credit Card Checksum
    6. 3. Date and Time
      1. 3.1. Finding Today's Date
      2. 3.2. Parsing Dates, Precisely or Fuzzily
      3. 3.3. Printing a Date
      4. 3.4. Iterating Over Dates
      5. 3.5. Doing Date Arithmetic
      6. 3.6. Counting the Days Since an Arbitrary Date
      7. 3.7. Converting Between Time Zones
      8. 3.8. Checking Whether Daylight Saving Time Is in Effect
      9. 3.9. Converting Between Time and DateTime Objects
      10. 3.10. Finding the Day of the Week
      11. 3.11. Handling Commercial Dates
      12. 3.12. Running a Code Block Periodically
      13. 3.13. Waiting a Certain Amount of Time
      14. 3.14. Adding a Timeout to a Long-Running Operation
    7. 4. Arrays
      1. 4.1. Iterating Over an Array
      2. 4.2. Rearranging Values Without Using Temporary Variables
      3. 4.3. Stripping Duplicate Elements from an Array
      4. 4.4. Reversing an Array
      5. 4.5. Sorting an Array
      6. 4.6. Ignoring Case When Sorting Strings
      7. 4.7. Making Sure a Sorted Array Stays Sorted
      8. 4.8. Summing the Items of an Array
      9. 4.9. Sorting an Array by Frequency of Appearance
      10. 4.10. Shuffling an Array
      11. 4.11. Getting the N Smallest Items of an Array
      12. 4.12. Building Up a Hash Using Injection
      13. 4.13. Extracting Portions of Arrays
      14. 4.14. Computing Set Operations on Arrays
      15. 4.15. Partitioning or Classifying a Set
    8. 5. Hashes
      1. 5.1. Using Symbols as Hash Keys
      2. 5.2. Creating a Hash with a Default Value
      3. 5.3. Adding Elements to a Hash
      4. 5.4. Removing Elements from a Hash
      5. 5.5. Using an Array or Other Modifiable Object as a Hash Key
      6. 5.6. Keeping Multiple Values for the Same Hash Key
      7. 5.7. Iterating Over a Hash
      8. 5.8. Iterating Over a Hash in Insertion Order
      9. 5.9. Printing a Hash
      10. 5.10. Inverting a Hash
      11. 5.11. Choosing Randomly from a Weighted List
      12. 5.12. Building a Histogram
      13. 5.13. Remapping the Keys and Values of a Hash
      14. 5.14. Extracting Portions of Hashes
      15. 5.15. Searching a Hash with Regular Expressions
    9. 6. Files and Directories
      1. 6.1. Checking to See If a File Exists
      2. 6.2. Checking Your Access to a File
      3. 6.3. Changing the Permissions on a File
      4. 6.4. Seeing When a File Was Last Used Problem
      5. 6.5. Listing a Directory
      6. 6.6. Reading the Contents of a File
      7. 6.7. Writing to a File
      8. 6.8. Writing to a Temporary File
      9. 6.9. Picking a Random Line from a File
      10. 6.10. Comparing Two Files
      11. 6.11. Performing Random Access on "Read-Once" Input Streams
      12. 6.12. Walking a Directory Tree
      13. 6.13. Locking a File
      14. 6.14. Backing Up to Versioned Filenames
      15. 6.15. Pretending a String Is a File
      16. 6.16. Redirecting Standard Input or Output
      17. 6.17. Processing a Binary File
      18. 6.18. Deleting a File
      19. 6.19. Truncating a File
      20. 6.20. Finding the Files You Want
      21. 6.21. Finding and Changing the Current Working Directory
    10. 7. Code Blocks and Iteration
      1. 7.1. Creating and Invoking a Block
      2. 7.2. Writing a Method That Accepts a Block
      3. 7.3. Binding a Block Argument to a Variable
      4. 7.4. Blocks as Closures: Using Outside Variables Within a Code Block
      5. 7.5. Writing an Iterator Over a Data Structure
      6. 7.6. Changing the Way an Object Iterates
      7. 7.7. Writing Block Methods That Classify or Collect
      8. 7.8. Stopping an Iteration
      9. 7.9. Looping Through Multiple Iterables in Parallel
      10. 7.10. Hiding Setup and Cleanup in a Block Method
      11. 7.11. Coupling Systems Loosely with Callbacks
    11. 8. Objects and Classes
      1. 8.1. Managing Instance Data
      2. 8.2. Managing Class Data
      3. 8.3. Checking Class or Module Membership
      4. 8.4. Writing an Inherited Class
      5. 8.5. Overloading Methods
      6. 8.6. Validating and Modifying Attribute Values
      7. 8.7. Defining a Virtual Attribute
      8. 8.8. Delegating Method Calls to Another Object
      9. 8.9. Converting and Coercing Objects to Different Types
      10. 8.10. Getting a Human-Readable Printout of Any Object
      11. 8.11. Accepting or Passing a Variable Number of Arguments
      12. 8.12. Simulating Keyword Arguments
      13. 8.13. Calling a Superclass's Method
      14. 8.14. Creating an Abstract Method
      15. 8.15. Freezing an Object to Prevent Changes
      16. 8.16. Making a Copy of an Object
      17. 8.17. Declaring Constants
      18. 8.18. Implementing Class and Singleton Methods
      19. 8.19. Controlling Access by Making Methods Private
    12. 9. Modules and Namespaces
      1. 9.1. Simulating Multiple Inheritance with Mixins
      2. 9.2. Extending Specific Objects with Modules
      3. 9.3. Mixing in Class Methods
      4. 9.4. Implementing Enumerable: Write One Method, Get 22 Free
      5. 9.5. Avoiding Naming Collisions with Namespaces
      6. 9.6. Automatically Loading Libraries as Needed
      7. 9.7. Including Namespaces
      8. 9.8. Initializing Instance Variables Defined by a Module
      9. 9.9. Automatically Initializing Mixed-In Modules
    13. 10. Reflection and Metaprogramming
      1. 10.1. Finding an Object's Class and Superclass
      2. 10.2. Listing an Object's Methods
      3. 10.3. Listing Methods Unique to an Object
      4. 10.4. Getting a Reference to a Method
      5. 10.5. Fixing Bugs in Someone Else's Class
      6. 10.6. Listening for Changes to a Class
      7. 10.7. Checking Whether an Object Has Necessary Attributes
      8. 10.8. Responding to Calls to Undefined Methods
      9. 10.9. Automatically Initializing Instance Variables
      10. 10.10. Avoiding Boilerplate Code with Metaprogramming
      11. 10.11. Metaprogramming with String Evaluations
      12. 10.12. Evaluating Code in an Earlier Context
      13. 10.13. Undefining a Method
      14. 10.14. Aliasing Methods
      15. 10.15. Doing Aspect-Oriented Programming
      16. 10.16. Enforcing Software Contracts
    14. 11. XML and HTML
      1. 11.1. Checking XML Well-Formedness
      2. 11.2. Extracting Data from a Document's Tree Structure
      3. 11.3. Extracting Data While Parsing a Document
      4. 11.4. Navigating a Document with XPath
      5. 11.5. Parsing Invalid Markup
      6. 11.6. Converting an XML Document into a Hash
      7. 11.7. Validating an XML Document
      8. 11.8. Substituting XML Entities
      9. 11.9. Creating and Modifying XML Documents
      10. 11.10. Compressing Whitespace in an XML Document
      11. 11.11. Guessing a Document's Encoding
      12. 11.12. Converting from One Encoding to Another
      13. 11.13. Extracting All the URLs from an HTML Document
      14. 11.14. Transforming Plain Text to HTML
      15. 11.15. Converting HTML Documents from the Web into Text
      16. 11.16. A Simple Feed Aggregator
    15. 12. Graphics and Other File Formats
      1. 12.1. Thumbnailing Images
      2. 12.2. Adding Text to an Image
      3. 12.3. Converting One Image Format to Another
      4. 12.4. Graphing Data
      5. 12.5. Adding Graphical Context with Sparklines
      6. 12.6. Strongly Encrypting Data
      7. 12.7. Parsing Comma-Separated Data
      8. 12.8. Parsing Not-Quite-Comma-Separated Data
      9. 12.9. Generating and Parsing Excel Spreadsheets
      10. 12.10. Compressing and Archiving Files with Gzip and Tar
      11. 12.11. Reading and Writing ZIP Files
      12. 12.12. Reading and Writing Configuration Files
      13. 12.13. Generating PDF Files
      14. 12.14. Representing Data as MIDI Music
    16. 13. Databases and Persistence
      1. 13.1. Serializing Data with YAML
      2. 13.2. Serializing Data with Marshal
      3. 13.3. Persisting Objects with Madeleine
      4. 13.4. Indexing Unstructured Text with SimpleSearch
      5. 13.5. Indexing Structured Text with Ferret
      6. 13.6. Using Berkeley DB Databases
      7. 13.7. Controlling MySQL on Unix
      8. 13.8. Finding the Number of Rows Returned by a Query
      9. 13.9. Talking Directly to a MySQL Database
      10. 13.10. Talking Directly to a PostgreSQL Database
      11. 13.11. Using Object Relational Mapping with ActiveRecord
      12. 13.12. Using Object Relational Mapping with Og
      13. 13.13. Building Queries Programmatically
      14. 13.14. Validating Data with ActiveRecord
      15. 13.15. Preventing SQL Injection Attacks
      16. 13.16. Using Transactions in ActiveRecord
      17. 13.17. Adding Hooks to Table Events
      18. 13.18. Adding Taggability with a Database Mixin
    17. 14. Internet Services
      1. 14.1. Grabbing the Contents of a Web Page
      2. 14.2. Making an HTTPS Web Request
      3. 14.3. Customizing HTTP Request Headers
      4. 14.4. Performing DNS Queries
      5. 14.5. Sending Mail
      6. 14.6. Reading Mail with IMAP
      7. 14.7. Reading Mail with POP3
      8. 14.8. Being an FTP Client
      9. 14.9. Being a Telnet Client
      10. 14.10. Being an SSH Client
      11. 14.11. Copying a File to Another Machine
      12. 14.12. Being a BitTorrent Client
      13. 14.13. Pinging a Machine
      14. 14.14. Writing an Internet Server
      15. 14.15. Parsing URLs
      16. 14.16. Writing a CGI Script
      17. 14.17. Setting Cookies and Other HTTP Response Headers
      18. 14.18. Handling File Uploads via CGI
      19. 14.19. Running Servlets with WEBrick
      20. 14.20. A Real-World HTTP Client
    18. 15. Web Development: Ruby on Rails
      1. 15.1. Writing a Simple Rails Application to Show System Status
      2. 15.2. Passing Data from the Controller to the View
      3. 15.3. Creating a Layout for Your Header and Footer
      4. 15.4. Redirecting to a Different Location
      5. 15.5. Displaying Templates with Render
      6. 15.6. Integrating a Database with Your Rails Application
      7. 15.7. Understanding Pluralization Rules
      8. 15.8. Creating a Login System
      9. 15.9. Storing Hashed User Passwords in the Database
      10. 15.10. Escaping HTML and JavaScript for Display
      11. 15.11. Setting and Retrieving Session Information
      12. 15.12. Setting and Retrieving Cookies
      13. 15.13. Extracting Code into Helper Functions
      14. 15.14. Refactoring the View into Partial Snippets of Views
      15. 15.15. Adding DHTML Effects with script.aculo.us
      16. 15.16. Generating Forms for Manipulating Model Objects
      17. 15.17. Creating an Ajax Form
      18. 15.18. Exposing Web Services on Your Web Site
      19. 15.19. Sending Mail with Rails
      20. 15.20. Automatically Sending Error Messages to Your Email
      21. 15.21. Documenting Your Web Site
      22. 15.22. Unit Testing Your Web Site
      23. 15.23. Using breakpoint in Your Web Application
    19. 16. Web Services and Distributed Programming
      1. 16.1. Searching for Books on Amazon
      2. 16.2. Finding Photos on Flickr
      3. 16.3. Writing an XML-RPC Client
      4. 16.4. Writing a SOAP Client
      5. 16.5. Writing a SOAP Server
      6. 16.6. Searching the Web with Google's SOAP Service
      7. 16.7. Using a WSDL File to Make SOAP Calls Easier
      8. 16.8. Charging a Credit Card
      9. 16.9. Finding the Cost to Ship Packages via UPS or FedEx
      10. 16.10. Sharing a Hash Between Any Number of Computers
      11. 16.11. Implementing a Distributed Queue
      12. 16.12. Creating a Shared "Whiteboard"
      13. 16.13. Securing DRb Services with Access Control Lists
      14. 16.14. Automatically Discovering DRb Services with Rinda
      15. 16.15. Proxying Objects That Can't Be Distributed
      16. 16.16. Storing Data on Distributed RAM with MemCached
      17. 16.17. Caching Expensive Results with MemCached
      18. 16.18. A Remote-Controlled Jukebox
    20. 17. Testing, Debugging, Optimizing, and Documenting
      1. 17.1. Running Code Only in Debug Mode
      2. 17.2. Raising an Exception
      3. 17.3. Handling an Exception
      4. 17.4. Rerunning After an Exception
      5. 17.5. Adding Logging to Your Application
      6. 17.6. Creating and Understanding Tracebacks
      7. 17.7. Writing Unit Tests
      8. 17.8. Running Unit Tests
      9. 17.9. Testing Code That Uses External Resources
      10. 17.10. Using breakpoint to Inspect and Change the State of Your Application
      11. 17.11. Documenting Your Application
      12. 17.12. Profiling Your Application
      13. 17.13. Benchmarking Competing Solutions
      14. 17.14. Running Multiple Analysis Tools at Once
      15. 17.15. Who's Calling That Method? A Call Graph Analyzer
    21. 18. Packaging and Distributing Software
      1. 18.1. Finding Libraries by Querying Gem Respositories
      2. 18.2. Installing and Using a Gem
      3. 18.3. Requiring a Specific Version of a Gem
      4. 18.4. Uninstalling a Gem
      5. 18.5. Reading Documentation for Installed Gems
      6. 18.6. Packaging Your Code as a Gem
      7. 18.7. Distributing Your Gems
      8. 18.8. Installing and Creating Standalone Packages with setup.rb
    22. 19. Automating Tasks with Rake
      1. 19.1. Automatically Running Unit Tests
      2. 19.2. Automatically Generating Documentation
      3. 19.3. Cleaning Up Generated Files
      4. 19.4. Automatically Building a Gem
      5. 19.5. Gathering Statistics About Your Code
      6. 19.6. Publishing Your Documentation
      7. 19.7. Running Multiple Tasks in Parallel
      8. 19.8. A Generic Project Rakefile
    23. 20. Multitasking and Multithreading
      1. 20.1. Running a Daemon Process on Unix
      2. 20.2. Creating a Windows Service
      3. 20.3. Doing Two Things at Once with Threads
      4. 20.4. Synchronizing Access to an Object
      5. 20.5. Terminating a Thread
      6. 20.6. Running a Code Block on Many Objects Simultaneously
      7. 20.7. Limiting Multithreading with a Thread Pool
      8. 20.8. Driving an External Process with popen
      9. 20.9. Capturing the Output and Error Streams from a Unix Shell Command
      10. 20.10. Controlling a Process on Another Machine
      11. 20.11. Avoiding Deadlock
    24. 21. User Interface
      1. 21.1.
      2. 21.2. Getting Input One Line at a Time
      3. 21.3. Getting Input One Character at a Time
      4. 21.4. Parsing Command-Line Arguments
      5. 21.5. Testing Whether a Program Is Running Interactively
      6. 21.6. Setting Up and Tearing Down a Curses Program
      7. 21.7. Clearing the Screen
      8. 21.8. Determining Terminal Size
      9. 21.9. Changing Text Color
      10. 21.10. Reading a Password
      11. 21.11. Allowing Input Editing with Readline
      12. 21.12. Making Your Keyboard Lights Blink
      13. 21.13. Creating a GUI Application with Tk
      14. 21.14. Creating a GUI Application with wxRuby
      15. 21.15. Creating a GUI Application with Ruby/GTK
      16. 21.16. Creating a Mac OS X Application with RubyCocoa
      17. 21.17. Using AppleScript to Get User Input
    25. 22. Extending Ruby with Other Languages
      1. 22.1. Writing a C Extension for Ruby
      2. 22.2. Using a C Library from Ruby
      3. 22.3. Calling a C Library Through SWIG
      4. 22.4. Writing Inline C in Your Ruby Code
      5. 22.5. Using Java Libraries with JRuby
    26. 23. System Administration
      1. 23.1. Scripting an External Program
      2. 23.2. Managing Windows Services
      3. 23.3. Running Code as Another User
      4. 23.4. Running Periodic Tasks Without cron or at
      5. 23.5. Deleting Files That Match a Regular Expression
      6. 23.6. Renaming Files in Bulk
      7. 23.7. Finding Duplicate Files
      8. 23.8. Automating Backups
      9. 23.9. Normalizing Ownership and Permissions in User Directories
      10. 23.10. Killing All Processes for a Given User
    27. Index
    28. About the Authors
    29. Colophon
    30. SPECIAL OFFER: Upgrade this ebook with O’Reilly
O'Reilly logo

4.7. Making Sure a Sorted Array Stays Sorted

Problem

You want to make sure an array stays sorted, even as you replace its elements or add new elements to it.

Solution

Subclass Array and override the methods that add items to the array. The new implementations add every new item to a position that maintains the sortedness of the array.

As you can see below, there are a lot of these methods. If you can guarantee that a particular method will never be called, you can get away with not overriding it.

	class 
SortedArray < Array

	  def initialize(*args, &sort_by)
	    @sort_by = sort_by || Proc.new { |x,y| x <=> y }
	    super(*args)
	    sort! &sort_by
	  end

	  def insert(i, v)
	    # The next line could be further optimized to perform a
	    # binary search.
	    insert_before = index(find { |x| @sort_by.call(x, v) == 1 })
	    super(insert_before ? insert_before : -1, v)
	  end

	  def <<(v)
	    insert(0, v)
	  end

	  alias push <<
	  alias unshift <<

Some methods, like collect!, can modify the items in an array, taking them out of sort order. Some methods, like flatten!, can add new elements to strange places in an array. Rather than figuring out a way to implement these methods in a way that preserves the sortedness of the array, we'll just let them run and then re-sort the array.[1]

	  ["collect!", "flatten!", "[]="].each do |method_name|
	    module_eval %{
	      def #{method_name}(*args)
	        super
	        sort! &@sort_by
	      end
	    }
	  end

	  def reverse!
	    #Do nothing; reversing the array would disorder it.
	  end
	end

A SortedArray created from an unsorted array will end up sorted:

	a = SortedArray.new([3,2,1])         # => [1, 2, 3]

Discussion

Many methods of Array are much faster on sorted arrays, so it's often useful to expend some overhead on keeping an array sorted over time. Removing items from a sorted array won't unsort it, but adding or modifying items can. Keeping a sorted array sorted means intercepting and reimplementing every sneaky way of putting objects into the array.

The SortedArray constructor accepts any code block you can pass into Array#sort, and keeps the array sorted according to that code block. The default code block uses the comparison operator (<=>) used by sort.

	unsorted= ["b", "aa", "a", "cccc", "1", "zzzzz", "k", "z"]
	strings_by_alpha = SortedArray.new(unsorted)
	# => ["1", "a", "aa", "b", "cccc", "k", "z", "zzzzz"]
	strings_by_length = SortedArray.new(unsorted) do |x,y|
	  x.length <=> y.length
	end
	# => ["b", "z", "a", "k", "1", "aa", "cccc", "zzzzz"]

The methods that add elements to an array specify where in the array they operate: push operates on the end of the array, and insert operates on a specified spot. SortedArray responds to these methods but it ignores the caller's request to put elements in a certain place. Every new element is inserted into a position that keeps the array sorted.

	a << -1                            # => [-1, 1, 2, 3]
	a << 1.5                           # => [-1, 1, 1.5, 2, 3]
	a.push(2.5)                        # => [-1, 1, 1.5, 2, 2.5, 3]
	a.unshift(1.6)                     # => [-1, 1, 1.5, 1.6, 2, 2.5, 3]

For methods like collect! and array assignment ([]=)that allow complex changes to an array, the simplest solution is to allow the changes to go through and then re-sort:

	a = SortedArray.new([10, 6, 4, -4, 200, 100])  
	# => [-4, 4, 6, 10, 100, 200]
	a.collect! { |x| x * -1 }          # => [-200, -100, -10, -6, -4, 4]

	a[3] = 25
	a                                  # => [-200, -100, -10, -4, 4, 25]
	# That is, -6 has been replaced by 25 and the array has been re-sorted.

	a[1..2] = [6000, 10, 600, 6]
	a                                  # => [-200, -4, 4, 6, 10, 25, 600, 6000]
	# That is, -100 and -10 have been replaced by 6000, 10, 600, and 6,
	# and the array has been re-sorted.

But with a little more work, we can write a more efficient implementation of array assignment that gives the same behavior. What happens when you run a command like a[0]= 10 on a SortedArray? The first element in the SortedArray is replaced by 10, and the SortedArray is re-sorted. This is equivalent to removing the first element in the array, then adding the value 10 to a place in the array that keeps it sorted.

Array#[]= implements three different types of array assignment, but all three can be modeled as a series of removals followed by a series of insertions. We can use this fact to implement a more efficient version of SortedArray#[]=:.

	class 
SortedArray
	  def []=(*args)
	    if args.size == 3
	      #e.g. "a[6,3] = [1,2,3]"
	      start, length, value = args
	      slice! Range.new(start, start+length, true)
	      (value.respond_to? :each) ? value.each { |x| self << x } : self << value
	    elsif args.size == 2
	      index, value = args
	      if index.is_a? Numeric
	        #e.g. "a[0] = 10" (the most common form of array assignment)
	        delete_at(index)
	        self << value
	      elsif index.is_a? Range
	        #e.g. "a[0..3] = [1,2,3]"
	        slice! index
	        (value.respond_to? :each) ? value.each { |x| self << x } : self << value
	      else
	        #Not supported. Delegate to superclass; will probably give an error.
	        super
	        sort!(&sort_by)
	      end
	    else
	      #Not supported. Delegate to superclass; will probably give an error.
	      super
	      sort!(&sort_by)
	    end
	  end
	end

Just as before, the sort will be maintained even when you use array assignment to replace some of a SortedArray's elements with other objects. But this implementation doesn't have to re-sort the array every time.

	a = SortedArray.new([1,2,3,4,5,6])
	a[0] = 10
	a                                     # => [2, 3, 4, 5, 6, 10]

	a[0, 2] = [100, 200]
	a                                     # => [4, 5, 6, 10, 100, 200]

	a[1..2] = [-4, 6]
	a                                     # => [-4, 4, 6, 10, 100, 200]

It's possible to subvert the sortedness of a SortedArray by modifying an object in place in a way that changes its sort order. Since the SortedArray never hears about the change to this object, it has no way of updating itself to move that object to its new sort position:[2]

	stripes = 
SortedArray.new(["aardwolf", "zebrafish"])
	stripes[1].upcase!  
	stripes                                 # => ["aardwolf", "ZEBRAFISH"]
	stripes.sort!                           # => ["ZEBRAFISH", "aardwolf"]

If this bothers you, you can make a SortedArray keep frozen copies of objects instead of the objects themselves. This solution hurts performance and uses more memory, but it will also prevent objects from being modified after being put into the SortedArray. This code adds a convenience method to Object that makes a frozen copy of the object:

	class Object
	  def to_frozen
	    f = self
	    unless frozen?
	       begin  
	         f = dup.freeze
	       rescue TypeError  
	         #This object can't be duped (e.g. Fixnum); fortunately,
	         #it usually can't be modified either 
	       end
	    end
	    return f
	  end
	end

The FrozenCopySortedArray stores frozen copies of objects instead of the objects themselves:

	class FrozenCopySortedArray < SortedArray
	  def insert(i, v)  
	    insert_before = index(find { |x| x > v })
	    super(insert_before ? insert_before : -1, v.to_frozen)
	  end

	  ["initialize", "collect!", "flatten!"].each do |method_name|
	    define_method(method_name) do 
	      super
	      each_with_index { |x, i| self[i] = x.to_frozen }
	      # No need to sort; by doing an assignment to every element
	      # in the array, we've made #insert keep the array sorted.
	    end
	  end
	end

	stripes = SortedArray.new(["aardwolf", "zebrafish"])
	stripes[1].upcase!  
	# TypeError: can't modify frozen string

Unlike a regular array, which can have elements of arbitrarily different data classes, all the elements of a SortedArray must be mutually comparable. For instance, you can mix integers and floating-point numbers within a SortedArray, but you can't mix integers and strings. Any data set that would cause Array# sort to fail makes an invalid SortedArray:

	[1, "string"].sort
	# ArgumentError: comparison of Fixnum with String failed

	a = SortedArray.new([1]) 
	a << "string" 
	# ArgumentError: comparison of Fixnum with String failed

One other pitfall: operations that create a new object, such as |=, +=, and to_a will turn an SortedArray into a (possibly unsorted) array.

	a = SortedArray.new([3, 2, 1])       # => [1, 2, 3]
	a += [1, -10]                        # => [1, 2, 3, 1, -10]
	a.class                              # => Array

The simplest way to avoid this is to override these methods to transform the resulting array back into a SortedArray:

	class SortedArray  
	  def + (other_array) 
	    SortedArray.new(super)
	  end
	end

See Also



[1] We can't use define_method to define these methods because in Ruby 1.8 you can't use define_method to create a method that takes a block argument. See Chapter 10 for more on this.

[2] One alternative is to modify SortedArray[] so that when you look up an element of the array, you actually get a delegate object that intercepts all of the element's method calls, and re-sorts the array whenever the user calls a method that modifies the element in place. This is probably overkill.

The best content for your career. Discover unlimited learning on demand for around $1/day.