proposition: Lemma Find_MatchingIndexesOK_Subset' : forall (st : IndexSearchTermT) (MKey : KeyMapT) (MValues : ValuesMapT), (forall key indexes, MKeys.MapsTo key indexes MKey -> forall idx, List.In idx indexes -> exists item, MValues.MapsTo idx item MValues /\ InA E.eq key (projection item)) -> (forall idx item, MValues.MapsTo idx item MValues -> forall key, InA E.eq key (projection item) -> exists indexes, MKeys.MapsTo key indexes MKey /\ List.In idx indexes) -> forall item idx, MValues.MapsTo idx item MValues -> inclA E.eq st (projection item) -> MValues.MapsTo idx item (Find_MatchingIndexes MKey st MValues).
proof: Proof. induction st; simpl; intros; eauto. case_eq (MKeys.find a MKey); intros. - apply MKeys.find_2 in H3. assert (InA E.eq a (projection item)) by (eapply H2; econstructor; reflexivity). destruct (H0 _ _ H1 _ H4); intuition. rewrite <- (MoreMKeysFacts.BasicFacts.MapsTo_fun H6 H3); eauto. eapply IHst in H1; eauto. revert H7 H1; clear -projection; remember (fun (k : MValues.key) (_ : TItem) => bool_of_sumbool (in_dec eq_nat_dec k x)) as f; unfold not in Heqf; rewrite <- Heqf. intro. assert (forall v, f idx v = true) by (rewrite Heqf; destruct (in_dec eq_nat_dec idx x); simpl; eauto). generalize MValues f H; clear -projection. induction st. + simpl; intros. rewrite MValuesProperties.filter_iff; intuition. + simpl; intros. destruct (MKeys.find a MKey). * eapply (IHst _ f) in H1; eauto. setoid_rewrite Equal_filter_filter. setoid_rewrite Equal_filter_filter in H1. eapply Equal_mapsto_iff; eauto. repeat f_equiv. repeat (apply functional_extensionality; intros). apply andb_comm. * eauto. + unfold inclA; intros; apply H2; econstructor 2; eauto. - assert (InA E.eq a (projection item)) by (eapply H2; econstructor; reflexivity). destruct (H0 _ _ H1 _ H4); intuition. eapply MKeys.find_1 in H6; congruence. Qed.
imports: Fiat.Common.Coq__8_4__8_5__Compat Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsInterface Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsProperties Coq.Arith.Peano_dec Coq.Structures.OrdersEx Coq.FSets.FMapInterface Coq.FSets.FMapFacts Coq.FSets.FMapAVL Coq.ZArith.ZArith Fiat.Common Fiat.Common.String_as_OT Fiat.Common.List.ListFacts Fiat.Common.List.FlattenList Fiat.Common.SetEqProperties Fiat.Common.FMapExtensions Fiat.Common.List.PermutationFacts Fiat.QueryStructure.Specification.SearchTerms.ListInclusion