lib/linked/item.rb in linked-0.2.0 vs lib/linked/item.rb in linked-0.2.1

@@ -4,21 +4,34 @@
   # Item
   #
   # This class implements doubly linked list items, designed to work both on
   # their own and as children of list.
   #
-  #  +- - - +    +------+------+            +- - - +
-  #  | Head | <--| prev | next |--> ... --> | Tail |
-  #  + - - -+    +------+------+            + - - -+
-  # (optional)     First Item     N Items  (optional)
+  #             +- - - +    +------+------+            +- - - +
+  #             | Head | <--| prev | next |--> ... --> | Tail |
+  #             + - - -+    +------+------+            + - - -+
+  #            (optional)     First Item     N Items  (optional)
   #
   # An object is considered a list if it responds to #head, #tail, #grow and
   # #shrink. The latter facilitate counting of the items and will be called
   # everytime an item is appended, prepended or deleted. #head and #tail are
   # expected to return two objects that, respectivly
   # a) responds to #next= and #append, or #prev= and #prepend and
   # b) returns true for #nil?.
+  #
+  # Notation
+  # --------
+  #
+  # Some methods operate on chains of items, and to describe the effects of an
+  # operation the following syntax is used.
+  #
+  #                    A   ( A <> B )   [ A <> B ]
+  #                   (i)     (ii)        (iii)
+  #
+  # Single items are denoted with capital letters (i), while chains are written
+  # as multiple connected items (ii). The parenthesis are optional. To show that
+  # one or more nodes are wraped in a list, angle brackets are used (iii).
 
   class Item
     # Access the list (if any) that the item belongs to. Writing to this
     # attribute is protected and should be avoided.
     #
@@ -189,20 +202,21 @@
     #
     # By default all items followng this one will be kept together, but if given
     # the argument after: true, the split will instead happen after this item
     # and it will instead be kept with those before it.
     #
-    # Example
+    # Example for the chain (A <> B <> C)
     #
-    #   item_b.split(after: false) => ~item_a~ |> item_b     item_c
-    #   item_b.split(after: true)  =>  item_a     item_b <| ~item_c~
+    #   B.split(after: false) => (A), (B <> C)
+    #   B.split(after: true)  => (A <> B), (C)
     #
     # after - determine wheter to split the chain before or after this item.
     #
     # Returns self.
 
     def split after: false
+      warn '[DEPRECATION] this method will be removed in the next major update. Please use #delete_before and #delete_after instead'
       if after
         unless last?
           if @list
             item = self
             count = 1 + loop.count do
@@ -244,10 +258,14 @@
 
     # Inserts the given item between this one and the one after it (if any). If
     # the given item is part of a chain, all items following it will be moved to
     # this one, and added to the list if one is set.
     #
+    # Example for the chain (A <> C)
+    #
+    #   A.append B # => (A <> B <> C)
+    #
     # Alternativly the argument can be an arbitrary object, in which case a new
     # item will be created around it.
     #
     # If this item is part of a list #grow will be called on it with the
     # number of added items as an argument. Should it also be the last item
@@ -256,37 +274,35 @@
     # sibling - the item to append, or an arbitrary object to be wraped in a new
     #           item.
     #
     # Returns the last item that was appended.
 
-    def append(sibling)
-      if sibling.is_a? Item
-        sibling.split
+    def append(object)
+      if object.respond_to? :item
+        first_item = object.item
+        last_item = first_item.send :extract_beginning_with, @list
       else
-        sibling = self.class.new sibling
+        first_item = last_item = self.class.new object
+        first_item.list = @list
+        @list.send :grow if @list
       end
-
-      sibling.prev = self
-      after_sibling = @next
-      @next = sibling
-
-      count = 1 + loop.count do
-        sibling.list = @list
-        sibling = sibling.next
-      end
-
-      @list.send :grow, count if @list
-
-      sibling.next = after_sibling
-      after_sibling.prev = sibling if after_sibling
-      sibling
+      
+      first_item.prev = self
+      @next.prev = last_item if @next
+      @next, last_item.next = first_item, @next
+      
+      last_item
     end
 
     # Inserts the given item between this one and the one before it (if any). If
     # the given item is part of a chain, all items preceeding it will be moved
     # to this one, and added to the list if one is set.
     #
+    # Example for the chain (A <> C)
+    #
+    #   C.prepend B # => (A <> B <> C)
+    #
     # Alternativly the argument can be an arbitrary object, in which case a new
     # item will be created around it.
     #
     # If this item is part of a list #grow will be called on it with the
     # number of added items as an argument. Should it also be the first item
@@ -295,33 +311,27 @@
     # sibling - the item to prepend. or an arbitrary object to be wraped in a
     #           new item.
     #
     # Returns the last item that was prepended.
 
-    def prepend(sibling)
-      if sibling.is_a? Item
-        sibling.split after: true
+    def prepend(object)
+      if object.respond_to? :item
+        last_item = object.item
+        first_item = last_item.send :extract_ending_with, @list
       else
-        sibling = self.class.new sibling
+        first_item = last_item = self.class.new object
+        first_item.list = @list
+        @list.send :grow, 1 if @list
       end
-
-      sibling.next = self
-      before_sibling = @prev
-      @prev = sibling
-
-      count = 1 + loop.count do
-        sibling.list = @list
-        sibling = sibling.prev
-      end
-
-      @list.send :grow, count if @list
-
-      sibling.prev = before_sibling
-      before_sibling.next = sibling if before_sibling
-      sibling
+      
+      last_item.next = self
+      @prev.next = first_item if @prev
+      @prev, first_item.prev = last_item, @prev
+      
+      first_item
     end
-
+    
     # Remove an item from the chain. If this item is part of a list and is
     # either first, last or both in that list, #next= and #prev= will be called
     # on the list head and tail respectivly.
     #
     # If this item is part of a list #shrink will be called on it.
@@ -334,13 +344,36 @@
       @list.send :shrink if @list
 
       @next = @prev = @list = nil
       self
     end
+    
+    # Remove all items before this one in the chain. If the items are part of a
+    # list they will be removed from it.
+    #
+    # Returns the last item in the chain that was just deleted, or nil if this
+    # is the first item.
+    
+    def delete_before
+      @prev.send :extract_ending_with unless first?
+    end
+    
+    # Remove all items after this one in the chain. If the items are part of a
+    # list they will be removed from it.
+    #
+    # Returns the last item in the chain that was just deleted, or nil if this
+    # is the first item.
+    
+    def delete_after
+      @next.send :extract_beginning_with unless last?
+    end
 
     # Iterates over each item before this, in reverse order. If a block is not
     # given an enumerator is returned.
+    #
+    # Note that raising a StopIteraion inside the block will cause the loop to
+    # silently stop the iteration early.
 
     def before
       return to_enum(__callee__) unless block_given?
       return if first?
 
@@ -352,10 +385,13 @@
       end
     end
 
     # Iterates over each item after this. If a block is not given an enumerator
     # is returned.
+    #
+    # Note that raising a StopIteraion inside the block will cause the loop to
+    # silently stop the iteration early.
 
     def after
       return to_enum(__callee__) unless block_given?
       return if last?
 
@@ -381,8 +417,103 @@
     def inspect
       return yield self if block_given?
 
       output = format '%s:0x%0x', self.class.name, object_id
       value ? output + " value=#{value.inspect}" : output
+    end
+    
+    # PRIVATE DANGEROUS METHOD. This method should never be called directly
+    # since it may leave the extracted item chain in an invalid state.
+    #
+    # This method extracts the item, together with the chain following it, from
+    # the list they are in (if any) and optionally facilitates moving them to a
+    # new list.
+    #
+    # Given the two lists
+    #                         [ A <> B <> C ]   [ D ]
+    #                               (I)          (II)
+    #
+    # calling B.extract_beginning_with(II) will result in (B <> C) being removed
+    # from (I), and (II) to be grown by two. (B <> C) will now reference (II)
+    # but they will not yet be linked to any of the items in it. It is therefore
+    # necessary to insert them directly after calling this method, or (II) will
+    # be left in an invalid state.
+    #
+    # Returns the last item of the chain.
+    
+    private def extract_beginning_with(new_list = nil)
+      old_list = @list
+      # Count items and move them to the new list
+      last_item = self
+      count = 1 + loop.count do
+        last_item.list = new_list
+        last_item = last_item.next
+      end
+      
+      # Make sure the old list is in a valid state
+      if old_list
+        if first?
+          old_list.send :clear
+        else
+          old_list.send :shrink, count
+          # Fix the links within in the list
+          @prev.next = last_item.next!
+          last_item.next!.prev = @prev
+        end
+      else
+        # Disconnect the item directly after the chain
+        @prev.next = nil unless first?
+      end
+      
+      # Disconnect the chain from the list
+      @prev = last_item.next = nil
+      
+      # Preemptivly tell the new list to grow
+      new_list.send :grow, count if new_list
+      
+      last_item
+    end
+    
+    # PRIVATE DANGEROUS METHOD. This method should never be called directly
+    # since it may leave the extracted item chain in an invalid state.
+    #
+    # This method extracts the item, together with the chain preceding it, from
+    # the list they are in (if any) and optionally facilitates moving them to a
+    # new list. See #extract_beginning_with for a description of the side
+    # effects from calling this method.
+    #
+    # Returns the first item in the chain.
+    
+    private def extract_ending_with(new_list = nil)
+      old_list = @list
+      # Count items and move them to the new list
+      first_item = self
+      count = 1 + loop.count do
+        first_item.list = new_list
+        first_item = first_item.prev
+      end
+      
+      # Make sure the old list is in a valid state
+      if old_list
+        if last?
+          old_list.send :clear
+        else
+          old_list.send :shrink, count
+          # Fix the links within in the list
+          @next.prev = first_item.prev!
+          first_item.prev!.next = @next
+        end
+      else
+        # Disconnect the item directly after the chain
+        @next.prev = nil unless last?
+      end
+      
+      # Disconnect the chain from the list
+      first_item.prev = @next = nil
+      
+      # Preemptivly tell the new list to grow
+      new_list.send :grow, count if new_list
+      
+      first_item
     end
   end
 end